Quick summary
Mathematical logic studies statements and how they combine. You learn statements and truth values, logical connectives, truth tables, statement patterns, logical equivalence, tautology/contradiction/contingency, quantifiers, duality, negation, algebra of statements and application to switching circuits.
Key points
- A statement is a declarative sentence that is either true (T) or false (F), not both. Questions, commands, exclamations and open sentences are not statements.
- Connectives: conjunction p ∧ q (and), disjunction p ∨ q (or), negation ~p (not), conditional p → q (if…then), biconditional p ↔ q (if and only if).
- p ∧ q is true only when both are true. p ∨ q is false only when both are false.
- p → q is false only when p is true and q is false.
- p ↔ q is true when p and q have the same truth value.
- For p → q: converse q → p, inverse ~p → ~q, contrapositive ~q → ~p. A conditional is equivalent to its contrapositive.
- A tautology is always true; a contradiction is always false; a contingency is neither.
- Quantifiers: "for all" (∀) and "there exists" (∃). Negation swaps them.
- Dual: interchange ∧ and ∨, and T and F.
- Switching circuits: switches in series ↔ ∧, in parallel ↔ ∨.
Important terms
- Truth value – T or F of a statement.
- Statement pattern – a compound expression built from simple statements and connectives.
- Logical equivalence (≡) – two patterns with identical truth tables.
- Open sentence – sentence with a variable whose truth depends on the value, e.g. "x + 2 = 5".
Formulas
| Law | Statement |
|---|---|
| De Morgan's laws | ~(p ∧ q) ≡ ~p ∨ ~q; ~(p ∨ q) ≡ ~p ∧ ~q |
| Conditional | p → q ≡ ~p ∨ q |
| Negation of conditional | ~(p → q) ≡ p ∧ ~q |
| Biconditional | p ↔ q ≡ (p → q) ∧ (q → p) |
| Negation of biconditional | ~(p ↔ q) ≡ (p ∧ ~q) ∨ (q ∧ ~p) |
| Distributive | p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) |
| Complement | p ∨ ~p ≡ T; p ∧ ~p ≡ F |
| Double negation | ~(~p) ≡ p |
5 important questions
Q1. Using a truth table, show that p → q ≡ ~q → ~p.
| p | q | ~p | ~q | p → q | ~q → ~p |
|---|---|---|---|---|---|
| T | T | F | F | T | T |
| T | F | F | T | F | F |
| F | T | T | F | T | T |
| F | F | T | T | T | T |
The last two columns are identical, so the statements are equivalent.
Q2. Examine whether (p ∧ q) → p is a tautology.
p ∧ q is true only when both p, q are true; then p is true, so the conditional is true. In all other rows p ∧ q is false, so the conditional is true. All values are T, so it is a tautology.
Q3. Write the negation of: "If it rains, then the match is cancelled."
~(p → q) ≡ p ∧ ~q: "It rains and the match is not cancelled."
Q4. Write the converse, inverse and contrapositive of: "If x is a prime number, then x is odd."
Converse: If x is odd, then x is prime. Inverse: If x is not prime, then x is not odd. Contrapositive: If x is not odd, then x is not prime.
Q5. Write the negation of "∀ n ∈ N, n + 3 > 2" and write the dual of p ∨ (q ∧ r).
Negation: ∃ n ∈ N such that n + 3 ≤ 2. Dual: p ∧ (q ∨ r).
Exam tip
Truth tables carry easy marks; draw them neatly with every column. In circuit questions, first write the statement form, then simplify using laws.