Laws of Logic: Propositional Rules with Truth Tables

The laws of logic are the standard equivalences every logician keeps at their fingertips. Just as arithmetic has a + b = b + a, logic has p ∧ q ≡ q ∧ p and ¬(p ∨ q) ≡ ¬p ∧ ¬q. Each is provable by truth table and then usable as a trusted shortcut.

These laws turn logic into algebra: instead of rebuilding truth tables, you manipulate symbols with the laws until the statement simplifies. This is how digital circuits are minimized and long proofs are shortened.

Key Concepts

• Commutative laws: p ∧ q ≡ q ∧ p and p ∨ q ≡ q ∨ p. Order does not matter.
• Associative laws: (p ∧ q) ∧ r ≡ p ∧ (q ∧ r), and likewise for ∨. Grouping does not matter.
• Distributive laws: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r), and also p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) (∨ distributes over ∧ too).
• Identity and domination: p ∧ T ≡ p, p ∨ F ≡ p, p ∨ T ≡ T, p ∧ F ≡ F.
• Idempotent laws: p ∧ p ≡ p and p ∨ p ≡ p.
• Double negation: ¬(¬p) ≡ p.
• De Morgan's laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q.
• Absorption laws: p ∨ (p ∧ q) ≡ p and p ∧ (p ∨ q) ≡ p.
• Negation laws: p ∨ ¬p ≡ T and p ∧ ¬p ≡ F.

Formulas

• Contrapositive: p → q ≡ ¬q → ¬p
• Implication as disjunction: p → q ≡ ¬p ∨ q
• Negation of implication: ¬(p → q) ≡ p ∧ ¬q
• Biconditional split: p ↔ q ≡ (p → q) ∧ (q → p)

Each formula is a genuine equivalence, usable left to right or right to left.

Worked Example

Prove the absorption law p ∧ (p ∨ q) ≡ p with a truth table:

• Row 1 (T, T): p ∧ (p ∨ q) = T ∧ T = T; right side p = T. Match.
• Row 2 (T, F): p ∧ (p ∨ q) = T ∧ T = T; right side p = T. Match.
• Row 3 (F, T): p ∧ (p ∨ q) = F ∧ T = F; right side p = F. Match.
• Row 4 (F, F): p ∧ (p ∨ q) = F ∧ F = F; right side p = F. Match.

The left column is T, T, F, F, exactly the column for p. Absorption is proved: AND-ing p with (p ∨ q) changes nothing.

Common Misconceptions

• "Distributivity works like arithmetic." In arithmetic only multiplication distributes over addition. In logic, AND distributes over OR and OR distributes over AND.
• "De Morgan's law just moves the negation inside." It also flips the connective: ¬(p ∧ q) becomes ¬p ∨ ¬q, not ¬p ∧ ¬q.
• "p → q ≡ ¬p → ¬q." That is the inverse and it is not equivalent. Only the contrapositive ¬q → ¬p is.

Real-World Applications

• Logic minimization: chip designers use absorption, idempotent and distributive laws to shrink circuits, saving silicon area and power.
• Compiler optimization: compilers apply these laws to simplify boolean expressions before generating machine code.
• Proof writing: replacing a hypothesis by an equivalent simpler form often unlocks a proof.

The laws of logic are truth-table-proved equivalences for manipulating statements algebraically. Memorize the shapes, practise simplifying with them, and remember the two traps: OR distributes over AND, and De Morgan flips the connective.