4.1 Propositions and Connectives
A proposition is a declarative sentence that is definitively true (T) or false (F). "2 + 2 = 5" is a (false) proposition; "x + 1 = 3" and "Close the door" are not. Compound propositions are built with connectives, listed in decreasing precedence:
| Connective | Symbol | Read as | True exactly when |
|---|---|---|---|
| Negation | ¬p | not p | p is false |
| Conjunction | p ∧ q | p and q | both true |
| Disjunction | p ∨ q | p or q (inclusive) | at least one true |
| Exclusive or | p ⊕ q | exactly one of p, q | truth values differ |
| Implication | p → q | if p then q | every case except p = T, q = F |
| Biconditional | p ↔ q | p iff q | truth values match |
The implication row surprises students: when p is false, p → q is vacuously true. "If 1 = 2, then I am the President" is a true proposition. Related forms of p → q: converse q → p, inverse ¬p → ¬q, contrapositive ¬q → ¬p. Only the contrapositive is equivalent to the original; converse and inverse are equivalent to each other.
4.2 Truth Tables, Tautologies and Contradictions
A truth table for n variables has 2^n rows. A proposition is a tautology if every row is T (e.g., p ∨ ¬p), a contradiction if every row is F (e.g., p ∧ ¬p), and a contingency otherwise. Two propositions are logically equivalent (P ≡ Q) when P ↔ Q is a tautology.
4.3 Worked Example 1 — Prove (p → q) ≡ (¬p ∨ q)
| p | q | p → q | ¬p | ¬p ∨ q |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
Columns 3 and 5 are identical in every row, hence p → q ≡ ¬p ∨ q. ∎ An immediate corollary by De Morgan: ¬(p → q) ≡ p ∧ ¬q — the only way an implication fails.
4.4 The Standard Equivalences (Law Table)
| Law | ∧-form | ∨-form |
|---|---|---|
| Identity | p ∧ T ≡ p | p ∨ F ≡ p |
| Domination | p ∧ F ≡ F | p ∨ T ≡ T |
| Idempotent | p ∧ p ≡ p | p ∨ p ≡ p |
| Commutative | p ∧ q ≡ q ∧ p | p ∨ q ≡ q ∨ p |
| Associative | (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) | (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) |
| Distributive | p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) | p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) |
| De Morgan | ¬(p ∧ q) ≡ ¬p ∨ ¬q | ¬(p ∨ q) ≡ ¬p ∧ ¬q |
| Absorption | p ∧ (p ∨ q) ≡ p | p ∨ (p ∧ q) ≡ p |
| Double negation | ¬(¬p) ≡ p | — |
4.5 Normal Forms: DNF and CNF
- DNF (Disjunctive Normal Form): an OR of AND-clauses, e.g., (p ∧ q) ∨ (¬p ∧ r).
- CNF (Conjunctive Normal Form): an AND of OR-clauses, e.g., (p ∨ q) ∧ (¬q ∨ r). SAT solvers consume CNF.
- Principal DNF (PDNF): OR of minterms — each clause contains every variable exactly once. One minterm per T-row of the truth table.
- Principal CNF (PCNF): AND of maxterms, one per F-row (negate each variable that is T in that row).
Truth-table method for F = p ↔ q: T-rows are (T,T) and (F,F); F-rows are (T,F) and (F,T).
- PDNF: (p ∧ q) ∨ (¬p ∧ ¬q)
- PCNF: (¬p ∨ q) ∧ (p ∨ ¬q)
4.6 Worked Example 2 — PDNF by the Algebraic Method
Problem: Expand F(p, q, r) = (p ∧ q) ∨ (¬p ∧ r) into PDNF (every clause must mention p, q, and r).
- p ∧ q is missing r; multiply by the tautology (r ∨ ¬r): p ∧ q ≡ (p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r).
- ¬p ∧ r is missing q: ¬p ∧ r ≡ (¬p ∧ q ∧ r) ∨ (¬p ∧ ¬q ∧ r).
- PDNF: (p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r) ∨ (¬p ∧ q ∧ r) ∨ (¬p ∧ ¬q ∧ r) — minterms m7, m6, m3, m1.
Quick CNF conversion example: p → (q → r) ≡ ¬p ∨ (¬q ∨ r) ≡ ¬p ∨ ¬q ∨ r, a single clause.
4.7 Common Mistakes & CS Applications
- Treating p → q as false when p is false — it is true.
- Confusing ≡ (a meta-statement about all rows) with ↔ (a connective inside a formula).
- Forgetting that "or" in logic is inclusive unless ⊕ is written.
- Applications: compiler optimizers apply De Morgan and absorption to simplify branch conditions; database query planners normalize WHERE clauses to CNF; model checkers and SAT/SMT solvers verify hardware by testing satisfiability; digital circuits are propositional formulas in silicon (Unit 4).
🎯 Exam Focus
- Construct the truth table of (p → q) ∧ (q → r) → (p → r) and show it is a tautology.
- Using laws only (no truth table), prove ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q. Name each law used.
- Define tautology, contradiction, and contingency with one example each.
- Obtain the PDNF and PCNF of (p ∧ q) ∨ (¬p ∧ r).
- Write the converse, inverse, and contrapositive of "If a number is divisible by 6, then it is divisible by 3." Which are true?
- Show that (p ⊕ q) ≡ (p ∨ q) ∧ ¬(p ∧ q).