Logical Connectives (Negation, Conjunction, Disjunction)
Learning Objectives
-
Distinguish atomic propositions from compound propositions
-
Define negation, conjunction, and disjunction rigorously
-
Construct the truth table for each connective
-
Evaluate the truth value of compound propositions
-
Identify connectives in natural-language mathematical statements
From Atomic to Compound Propositions
In Unit 1 we studied atomic propositions: individual declarative sentences, each carrying a single truth value. Statements such as “2 +3 =5” or “7 is even” stand alone — they assert one fact and are either true or false.
Mathematics, however, rarely works with isolated assertions. Theorems, definitions, and proofs are built by combining propositions: “𝑛 is even and 𝑛 is greater than 2,” or “the function is continuous or it is differentiable.” The words and, or, and not are not mere rhetorical flourishes — they are operations on truth values, as precise as addition or multiplication.
These operations are called logical connectives. In this lesson we define the three most fundamental ones.
Logical Connective
A logical connective is an operation that takes one or more propositions as input and produces a new proposition whose truth value is entirely determined by the truth values of its inputs.
This deterministic relationship is specified by a truth table: an exhaustive listing of all possible input truth-value combinations and the corresponding output
Atomic Proposition and Compound Proposition
An atomic proposition (or simple proposition) is a proposition that contains no logical connectives. It cannot be decomposed into simpler propositions.
A compound proposition is a proposition formed by applying one or more logical connectives to atomic propositions.
We denote atomic propositions by capital letters: 𝑃,𝑄,𝑅,…. These are called propositional variables.
Negation (\(\neg\))
The negation of a proposition \(P\), written \(\neg P\) (read “not \(P\)”), is the proposition that is true when \(P\) is false, and false when \(P\) is true.
Formally:
\[\neg P \;=\; \begin{cases} F & \text{if } P = T \\ T & \text{if } P = F \end{cases}\]
Negation is a unary connective: it operates on a single proposition.
Truth Table
\[\begin{array}{|c|c|} \hline P & \neg P \\ \hline T & F \\ F & T \\ \hline \end{array}\]
Negation — Examples
Let \(P\): “\(6\) is even.” Then \(\neg P\): “\(6\) is not even.” — Since \(P\) is true, \(\neg P\) is false.
Let \(Q\): “\(\sqrt{2}\) is rational.” Then \(\neg Q\): “\(\sqrt{2}\) is not rational.” — Since \(Q\) is false, \(\neg Q\) is true.
Let \(R\): “\(0 > 1\).” Then \(\neg R\): “\(0 \leq 1\).” — Since \(R\) is false, \(\neg R\) is true.
Remark: Double Negation
Negating a proposition twice returns the original truth value:
\[\neg(\neg P) \;=\; P\]
This is the Law of Double Negation. It follows immediately from the truth table: if \(P = T\), then \(\neg P = F\), and \(\neg(\neg P) = T\). Similarly for \(P = F\). We will revisit this law formally when we study logical equivalences.
Conjunction (\(\land\))
The conjunction of propositions \(P\) and \(Q\), written \(P \land Q\) (read “\(P\) and \(Q\)”), is the proposition that is true if and only if both \(P\) and \(Q\) are true.
Formally:
\[P \land Q \;=\; \begin{cases} T & \text{if } P = T \text{ and } Q = T \\ F & \text{otherwise} \end{cases}\]
Conjunction is a binary connective: it operates on two propositions.
Truth Table
\[\begin{array}{|c|c|c|} \hline P & Q & P \lor Q \\ \hline T & T & T \\ T & F & T \\ F & T & T \\ F & F & F \\ \hline \end{array}\]
Conjunction — Examples
Let \(P\): “\(4\) is even” (\(T\)) and \(Q\): “\(4 < 10\)” (\(T\)). Then \(P \land Q\): “\(4\) is even and \(4 < 10\)” → \(T\).
Let \(P\): “\(3\) is odd” (\(T\)) and \(Q\): “\(3\) is negative” (\(F\)). Then \(P \land Q\): “\(3\) is odd and \(3\) is negative” → \(F\).
Let \(P\): “\(1 > 5\)” (\(F\)) and \(Q\): “\(2 > 7\)” (\(F\)). Then \(P \land Q\) → \(
Natural Language and Conjunction
In everyday language, “and” sometimes implies temporal sequence (“I woke up and ate breakfast”) or causation (“He studied hard and passed the exam”). In logic, \(P \land Q\) carries no such connotation. The conjunction \(P \land Q\) is commutative:
\[P \land Q \;\equiv\; Q \land P\]
It asserts nothing beyond the simultaneous truth of both components.
Disjunction (\(\lor\))
The disjunction of propositions \(P\) and \(Q\), written \(P \lor Q\) (read “\(P\) or \(Q\)”), is the proposition that is true if at least one of \(P\) or \(Q\) is true.
Formally:
\[P \lor Q \;=\; \begin{cases} F & \text{if } P = F \text{ and } Q = F \\ T & \text{otherwise} \end{cases}\]
Disjunction is a binary connective.
Truth Table
\[\begin{array}{|c|c|c|} \hline P & Q & P \lor Q \\ \hline T & T & T \\ T & F & T \\ F & T & T \\ F & F & F \\ \hline \end{array}\]
Disjunction — Examples
Let \(P\): “\(5\) is prime” (\(T\)) and \(Q\): “\(5\) is even” (\(F\)). Then \(P \lor Q\): “\(5\) is prime or \(5\) is even” → \(T\).
Let \(P\): “\(2 > 3\)” (\(F\)) and \(Q\): “\(1 > 3\)” (\(F\)). Then \(P \lor Q\) → \(F\).
Let \(P\): “\(9\) is odd” (\(T\)) and \(Q\): “\(9\) is a perfect square” (\(T\)). Then \(P \lor Q\) → \(T\). — Note: both are true, and the disjunction is still true.
Inclusive vs. Exclusive Disjunction
In everyday language, “or” is often exclusive: “You may have tea or coffee” typically means one but not both. In mathematics and logic, the disjunction \(P \lor Q\) is always inclusive: it is true when at least one operand is true, including the case where both are true.
An exclusive disjunction (\(P \oplus Q\) or \(P \veebar Q\)) does exist as a separate connective, but \(\lor\) in standard mathematical logic is always inclusive.
This convention is not arbitrary. The inclusive reading is more natural for mathematical reasoning: when we say “\(x\) is divisible by 2 or \(x\) is divisible by 3,” we certainly do not wish to exclude \(x = 6\).
Formalising the Principles of Unit 1
In Unit 1, Lesson 2, we introduced three fundamental principles of classical logic. At that stage, we stated them informally. We are now in a position to write these principles precisely.
Law of Non-Contradiction
A proposition and its negation cannot both be true:
\[\neg\,(P \land \neg P)\]
This is a compound proposition built using all three connectives introduced in this lesson: negation (applied to \(P\) and again to the whole conjunction) and conjunction.
Law of Excluded Middle (Tertium Non Datur)
For any proposition \(P\), either \(P\) or its negation holds:
\[P \lor \neg P\]
This is a disjunction of a proposition with its own negation. Its truth can now be verified by exhausting the truth table: when \(P = T\), we have \(T \lor F = T\); when \(P = F\), we have \(F \lor T = T\). The disjunction is true in every case.
Principle of Bivalence
Every proposition has exactly one of the two truth values \(T\) or \(F\). Unlike the first two principles, bivalence is a metalogical principle — a statement about the logical system rather than a formula within it. It cannot be expressed as a propositional formula; it is an axiom governing how truth values are assigned.
Exercise 1
Determine the truth value of each compound proposition.
Exercise 2
Identify the main logical connective in each statement.
Exercise 3
Determine the truth value. These involve multiple connectives — evaluate step by step.
Critical Examination
In the negation examples, we wrote \(\neg(0 > 1)\) as “\(0 \leq 1\).” A student objects:
“The opposite of ‘greater than’ is ‘less than.’ So the negation of \(0 > 1\) should be \(0 < 1\), not \(0 \leq 1\).”
Is this correct?
Analysis
It is not. The negation must reverse the truth value in every case, not merely in the case at hand.
Consider the proposition \(P\): “\(5 > 5\).” This is false. Therefore \(\neg P\) must be true. Now test the two candidates:
“\(5 < 5\)” — this is also false. It fails to reverse the truth value.
“\(5 \leq 5\)” — this is true (since \(5 = 5\)). It correctly reverses the truth value.
The error stems from confusing contraries with contradictories. Two propositions are contraries if they cannot both be true but can both be false (“\(a > b\)” and “\(a < b\)” are contraries: when \(a = b\), both are false). Two propositions are contradictories if exactly one of them is true in every case (“\(a > b\)” and “\(a \leq b\)” are contradictories). Negation produces the contradictory, never merely a contrary.
The general pattern for order relations:
\[\neg(a > b) \;\equiv\; a \leq b \qquad\qquad \neg(a < b) \;\equiv\; a \geq b\]
\[\neg(a \geq b) \;\equiv\; a < b \qquad\qquad \neg(a \leq b) \;\equiv\; a > b\]
Summary
An atomic proposition contains no connectives; a compound proposition is formed by applying connectives to one or more propositions.
Negation (\(\neg P\)) reverses the truth value of \(P\). It is the only unary connective introduced in this lesson.
Conjunction (\(P \land Q\)) is true only when both \(P\) and \(Q\) are true.
Disjunction (\(P \lor Q\)) is true when at least one of \(P\) or \(Q\) is true. In logic, disjunction is always inclusive.
The truth value of any compound proposition is entirely determined by the truth values of its components and the truth tables of the connectives involved.