Difficulty: Intermediate | Prerequisites: Propositional calculus identities (Part 1 of these notes), truth table construction, familiarity with ¬, ∧, ∨, →.
Once you have the basic identities down, the next step is applying them to prove more complex equivalences and properties of the logical connectives. This material covers three things: expressing exclusive-or using only the basic connectives, proving a biconditional equivalence both by truth table and by algebraic manipulation, and showing that implication is transitive. These are standard textbook exercises, but the techniques involved (truth table verification, step-by-step identity application) are the same ones you will use in more advanced topics like resolution, SAT solving, and knowledge representation.
XOR (P ⊕ Q) can be rewritten as (P ∧ ¬Q) ∨ (¬P ∧ Q) using only ¬, ∧, and ∨. The biconditional (P → Q) ∧ (Q → P) is equivalent to (P ∨ Q) → (P ∧ Q), provable by truth table or algebraic rewriting. Implication is transitive: if P → Q and Q → R, then P → R. This is a tautology, confirmed by truth table.
Exclusive-or (⊕, XOR)
True when exactly one of the two operands is true, false when both agree. Think of it as "one or the other, but not both." In everyday language, "you can have cake or ice cream" usually means XOR.
Biconditional (↔)
True when both sides have the same truth value. P ↔ Q means "P if and only if Q." Equivalent to (P → Q) ∧ (Q → P).
Transitivity (of implication)
The property that if P → Q and Q → R, then P → R. In simple terms, a chain of implications can be collapsed: if A leads to B and B leads to C, then A leads to C.
Tautology
A formula that is true under every possible assignment of its variables. The transitivity of implication is itself a tautology.
Algebraic proof (identity-based proof)
Proving an equivalence by rewriting one side into the other using known identities, rather than by exhaustive truth table. This is often faster and gives more insight into why the equivalence holds.
The exclusive-or connective is not always included as a primitive in logical systems, so it is useful to know how to express it using only negation, conjunction, and disjunction.
Result: P ⊕ Q ≡ (P ∧ ¬Q) ∨ (¬P ∧ Q)
The intuition: XOR is true when P is true and Q is false, or when P is false and Q is true. Each of those two cases is a conjunction, and the overall expression is the disjunction of the two cases.
Truth table verification:
P = T, Q = T: (T ∧ F) ∨ (F ∧ T) = F ∨ F = F. XOR gives F. ✓
P = T, Q = F: (T ∧ T) ∨ (F ∧ F) = T ∨ F = T. XOR gives T. ✓
P = F, Q = T: (F ∧ F) ∨ (T ∧ T) = F ∨ T = T. XOR gives T. ✓
P = F, Q = F: (F ∧ T) ∨ (T ∧ F) = F ∨ F = F. XOR gives F. ✓
All four rows match, confirming the equivalence.
This is a less obvious equivalence that says: "P and Q imply each other" is the same as "if at least one of them is true, then both are true." Both expressions capture the idea that P and Q must have the same truth value.
Evaluate both sides across all four rows:
P = T, Q = T: LHS = T ∧ T = T. RHS = T → T = T. ✓
P = T, Q = F: LHS = F ∧ T = F. RHS = T → F = F. ✓
P = F, Q = T: LHS = T ∧ F = F. RHS = T → F = F. ✓
P = F, Q = F: LHS = T ∧ T = T. RHS = F → F = T. ✓
Both sides agree on every row.
Starting from the left-hand side:
(P → Q) ∧ (Q → P)
(¬P ∨ Q) ∧ (¬Q ∨ P) — applying implication elimination to both
Distribute: ((¬Q ∨ P) ∧ ¬P) ∨ ((¬Q ∨ P) ∧ Q) — distributive law
Distribute each sub-expression again:
(¬P ∧ ¬Q) ∨ (¬P ∧ P) for the first part
(Q ∧ ¬Q) ∨ (P ∧ Q) for the second part
Apply P ∧ ¬P ≡ FALSE to both middle terms:
(¬P ∧ ¬Q) ∨ FALSE ∨ FALSE ∨ (P ∧ Q)
Apply P ∨ FALSE ≡ P:
(¬P ∧ ¬Q) ∨ (P ∧ Q)
Apply De Morgan's law to the first term: ¬(P ∨ Q) ∨ (P ∧ Q)
Apply implication elimination in reverse (¬A ∨ B ≡ A → B):
(P ∨ Q) → (P ∧ Q)
This confirms the equivalence algebraically, which is the more instructive proof because it shows exactly which identities are doing the work.
Claim: ((P → Q) ∧ (Q → R)) → (P → R) is a tautology.
This means: whenever the premises P → Q and Q → R are both true, the conclusion P → R is guaranteed to be true.
Truth table verification (three variables, eight rows):
The key observation is that the overall formula evaluates to T in every single row. You can verify this by noting:
Whenever the antecedent (P → Q) ∧ (Q → R) is false, the whole implication is vacuously true.
Whenever the antecedent is true, both P → Q and Q → R hold, and you can trace through to confirm P → R also holds.
The critical rows are the ones where the antecedent is true:
P = T, Q = T, R = T: both premises true, P → R = T. ✓
P = F, Q = T, R = T: both premises true, P → R = T. ✓
P = F, Q = F, R = T: both premises true, P → R = T. ✓
P = F, Q = F, R = F: both premises true, P → R = T. ✓
P = F, Q = T, R = F: Q → R = F, so antecedent is false, whole thing is vacuously T.
In no row is the antecedent true and the conclusion false, confirming the tautology.
XOR is fundamental in cryptography (one-time pads, stream ciphers) and error detection (parity bits). The biconditional appears whenever you need to express "if and only if" conditions in specifications or contracts. Transitivity of implication is the formal basis for chaining rules in expert systems and forward-chaining inference engines: if rule 1 gives you Q from P, and rule 2 gives you R from Q, the engine can conclude R from P.
Students sometimes write the XOR expansion as (P ∨ Q) instead of (P ∧ ¬Q) ∨ (¬P ∧ Q). Plain OR includes the case where both are true, which XOR excludes. You need the negations to rule out the "both true" case.
When doing algebraic proofs, students forget to apply the contradiction identity (P ∧ ¬P ≡ FALSE) to simplify intermediate terms. Leaving these unsimplified makes the expression unmanageable.
Transitivity is sometimes confused with "if P → Q then Q → P." That is the converse, not transitivity. Transitivity requires a chain through a middle variable.
In the biconditional proof, students sometimes skip steps in the distribution and get lost. Writing out every intermediate expression, even when it feels tedious, prevents errors.
⚠️ Expressing XOR with basic connectives is a common exam question. Memorise the expansion: (P ∧ ¬Q) ∨ (¬P ∧ Q).
⚠️ Algebraic proofs using identities are typically worth more marks than truth table proofs, because they demonstrate deeper understanding. Know how to apply implication elimination, distribution, contradiction, and De Morgan's in sequence.
⚠️ Transitivity of implication is foundational for chaining inferences. Expect to see it in questions about proof systems and rule-based reasoning.
⚠️ The biconditional equivalence may appear in a "prove this using two methods" format: truth table and algebraic.
Fill in the blank: P ⊕ Q ≡ (P ∧ ) ∨ ( ∧ Q).
True or false: (P → Q) ∧ (Q → P) is true whenever P and Q have different truth values.
True or false: ((P → Q) ∧ (Q → R)) → (P → R) is a tautology.
Fill in the blank: The first step in an algebraic proof involving implications is usually to apply ____.
True or false: XOR is the same as OR.
Answers: 1. ¬Q, ¬P. 2. False (it is true only when P and Q have the same truth value). 3. True. 4. Implication elimination (P → Q ≡ ¬P ∨ Q). 5. False (OR is true when both are true; XOR is false when both are true).
Q: Express P ⊕ Q using only ¬, ∧, and ∨, and verify with a truth table.
A: P ⊕ Q ≡ (P ∧ ¬Q) ∨ (¬P ∧ Q). Build a four-row truth table evaluating both sides. They agree on all rows: F, T, T, F.
Q: Prove algebraically that (P → Q) ∧ (Q → P) ≡ (P ∨ Q) → (P ∧ Q).
A: Start with (¬P ∨ Q) ∧ (¬Q ∨ P). Distribute, apply P ∧ ¬P ≡ FALSE twice, simplify with P ∨ FALSE ≡ P to get (¬P ∧ ¬Q) ∨ (P ∧ Q). Apply De Morgan's to get ¬(P ∨ Q) ∨ (P ∧ Q), then reverse implication elimination to obtain (P ∨ Q) → (P ∧ Q).
Q: What does it mean for implication to be transitive? Give a plain-English example.
A: If P implies Q and Q implies R, then P implies R. Example: if studying leads to understanding, and understanding leads to good grades, then studying leads to good grades.
Q: How many rows are needed in the truth table to verify transitivity of implication?
A: Eight rows (2³), because there are three propositional variables: P, Q, and R.
The XOR equivalence connects to digital circuit design (XOR gates) and to the concept of parity in coding theory. The biconditional is the basis for logical equivalence itself, linking back to how we define ≡. Transitivity of implication is the formal underpinning of hypothetical syllogism, one of the classical rules of inference you will meet in the next section on inference rules. It also appears in graph-based reasoning, where chains of edges represent chains of implications.
exclusive-or, XOR, ⊕, biconditional, if and only if, iff, logical equivalence proof, algebraic proof, identity-based proof, transitivity, hypothetical syllogism, implication chaining, truth table proof, CNF conversion, propositional logic, forward chaining, rule-based systems, parity, one-time pad, digital logic XOR