In plain words
Logic studies the form of an argument rather than its topic. A proposition is a declarative sentence that is either true (T) or false (F), not both: “7 is prime” is a proposition, while “Close the door” and “x + 2 = 5” are not (the second becomes one once x is fixed). Small propositions are joined by connectives into compound ones, and a truth table lists the value of a compound for every combination of values of its parts. Two formulas are equivalent when their truth tables match, and an argument is valid when its conclusion can never be false while all its premises are true. Predicate logic goes further: it talks about objects with variables, predicates such as P(x), and the quantifiers “for all” (∀) and “there exists” (∃).
Why it matters for NET
Mathematical logic is the first topic of Unit 1 and gives a steady supply of short questions. The recurring patterns are: identifying a tautology or contradiction; picking the formula equivalent to a given one; converse, inverse and contrapositive; the English reading of “only if”, “unless” and “necessary”; functionally complete sets; valid arguments and named rules of inference; and, most often in recent papers, translating English into predicate logic and negating or reordering quantifiers. The same ideas return in Unit 10 (resolution and first-order logic in AI) and Unit 7 (SAT and NP-completeness), so time spent here pays twice.
Concepts in depth: connectives and the conditional
| Connective | Symbol | Read as | False exactly when |
|---|---|---|---|
| Negation | ¬p | not p | p is true |
| Conjunction | p ∧ q | p and q | at least one is false |
| Disjunction | p ∨ q | p or q (inclusive) | both are false |
| Exclusive or | p ⊕ q | p or q but not both | p and q have the same value |
| Conditional | p → q | if p then q | p is true and q is false |
| Biconditional | p ↔ q | p if and only if q | p and q differ |
| NAND | p ↑ q | not both | both are true |
| NOR | p ↓ q | neither | at least one is true |
The conditional causes most errors. p → q promises only that q holds whenever p holds; when p is false the promise cannot be broken, so the conditional is true (“vacuously true”). English has many ways to say p → q: “if p, q”, “q if p”, “p only if q”, “p is sufficient for q”, “q is necessary for p”, “q whenever p”. “p unless q” means ¬q → p, which is equivalent to p ∨ q.
From p → q we form the converse q → p, the inverse ¬p → ¬q and the contrapositive ¬q → ¬p. The contrapositive is equivalent to the original; the converse and inverse are equivalent to each other but not to the original. The usual precedence is ¬, then ∧, then ∨, then →, then ↔. The conditional is not associative: (p → q) → r and p → (q → r) differ at p = F, r = F, so always keep the brackets.
Concepts in depth: truth tables and classification
A formula with n variables has 2n rows. Because each row can be T or F independently, there are 22n different truth functions of n variables: 16 binary connectives, 256 functions of three variables. A formula is a tautology (valid) if it is true in every row, a contradiction (unsatisfiable) if it is false in every row, and a contingency otherwise. It is satisfiable if at least one row makes it true. Three links are worth memorising: A is a tautology exactly when ¬A is a contradiction; A ≡ B exactly when A ↔ B is a tautology; and A logically implies B (A ⇒ B) exactly when A → B is a tautology.
The fastest test for a tautology is the falsifying-row method. Suppose the formula is false and follow the consequences. An implication is false only with a true left side and a false right side, and a conjunction on the left forces every conjunct to be true. If the assumptions force a variable to be both T and F, no falsifying row exists and the formula is a tautology. If they succeed, you have found a counterexample in seconds.
Concepts in depth: laws of equivalence
| Law | Equivalence |
|---|---|
| Identity and domination | p ∧ T ≡ p, p ∨ F ≡ p; p ∨ T ≡ T, p ∧ F ≡ F |
| Idempotent, double negation | p ∨ p ≡ p, p ∧ p ≡ p; ¬¬p ≡ p |
| Complement (negation) | p ∨ ¬p ≡ T, p ∧ ¬p ≡ F |
| Commutative, associative | for ∧, ∨, ⊕ and ↔ (not for →) |
| 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 |
| Conditional | p → q ≡ ¬p ∨ q ≡ ¬q → ¬p; ¬(p → q) ≡ p ∧ ¬q |
| Biconditional | p ↔ q ≡ (p → q) ∧ (q → p) ≡ (p ∧ q) ∨ (¬p ∧ ¬q); ¬(p ↔ q) ≡ p ⊕ q ≡ p ↔ ¬q |
| Exportation | (p ∧ q) → r ≡ p → (q → r) |
| Common antecedent | (p → q) ∧ (p → r) ≡ p → (q ∧ r); (p → q) ∨ (p → r) ≡ p → (q ∨ r) |
| Common consequent | (p → r) ∧ (q → r) ≡ (p ∨ q) → r; (p → r) ∨ (q → r) ≡ (p ∧ q) → r |
The last row is the favourite trap: with a common consequent, “and” outside becomes “or” inside, and “or” outside becomes “and” inside. The duality principle says that if an equivalence uses only ¬, ∧, ∨, T and F, swapping ∧ with ∨ and T with F on both sides gives another valid equivalence. The dual of (p ∧ T) ∨ q is (p ∨ F) ∧ q.
Concepts in depth: functional completeness
A set of connectives is functionally complete if every truth function can be built from it. {¬, ∧, ∨} is complete because every truth function has a DNF. De Morgan then removes one of ∧ and ∨, so {¬, ∧} and {¬, ∨} are complete; {¬, →} is complete because p ∨ q ≡ ¬p → q; {→, F} is complete because ¬p ≡ p → F; and the single connectives NAND and NOR are each complete (¬p ≡ p ↑ p). A set is not complete if all its members share a property that composition preserves. {∧, ∨, →, ↔} can never produce F when all inputs are T, so it cannot express ¬. {∧, ∨} is also monotone. {¬, ↔, ⊕} only builds linear functions (XORs of variables plus a constant), so it cannot express ∧. These five properties (preserving F, preserving T, self-dual, monotone, linear) are Post’s criteria: a set is complete exactly when, for each property, some member lacks it.
Concepts in depth: normal forms
A literal is a variable or its negation. A DNF is an OR of ANDs of literals; a CNF is an AND of ORs of literals (each OR is a clause). Every formula has both. The principal (canonical) forms use full terms. A minterm contains every variable once and is true in exactly one row; the PDNF (sum of products) is the OR of the minterms of the true rows. A maxterm is an OR of every variable and is false in exactly one row; the PCNF (product of sums) is the AND of the maxterms of the false rows. For a false row, a variable that is 0 appears plain and a variable that is 1 appears negated. With n variables, the number of minterms in the PDNF plus the number of maxterms in the PCNF is always 2n, and the PCNF indices are exactly the indices missing from the PDNF.
Two facts connect normal forms to complexity. A CNF is a tautology exactly when every clause contains a complementary pair (easy to check), and a DNF is satisfiable exactly when some term has no complementary pair (also easy). Checking whether a CNF is satisfiable is the NP-complete SAT problem.
Concepts in depth: rules of inference
| Rule | From | Infer |
|---|---|---|
| Modus ponens | p, p → q | q |
| Modus tollens | ¬q, p → q | ¬p |
| Hypothetical syllogism | p → q, q → r | p → r |
| Disjunctive syllogism | p ∨ q, ¬p | q |
| Addition | p | p ∨ q |
| Simplification | p ∧ q | p |
| Conjunction | p, q | p ∧ q |
| Resolution | p ∨ q, ¬p ∨ r | q ∨ r |
| Constructive dilemma | p → q, r → s, p ∨ r | q ∨ s |
Each rule corresponds to a tautology; modus ponens is (p ∧ (p → q)) → q. Two invalid patterns look similar: affirming the consequent (from p → q and q, conclude p) and denying the antecedent (from p → q and ¬p, conclude ¬q). An argument whose premises are inconsistent is valid for every conclusion, because no row makes all premises true. Proof by resolution negates the conclusion, converts everything to clauses, and resolves until it reaches the empty clause, which shows the premises plus the negated conclusion are unsatisfiable.
Concepts in depth: predicates and quantifiers
A predicate P(x) becomes a proposition when x is given a value from the domain (universe of discourse). ∀x P(x) is true when P holds for every element; ∃x P(x) when it holds for at least one. Over a finite domain {a₁, …, aₙ}, ∀x P(x) is P(a₁) ∧ … ∧ P(aₙ) and ∃x P(x) is P(a₁) ∨ … ∨ P(aₙ). A variable inside the scope of a quantifier is bound; otherwise it is free, and a formula with free variables is not a proposition. Quantifiers bind more tightly than the connectives, so ∀x P(x) ∧ Q(x) has a free x in Q(x).
De Morgan for quantifiers: ¬∀x P(x) ≡ ∃x ¬P(x) and ¬∃x P(x) ≡ ∀x ¬P(x). To negate a long formula, move ¬ to the right across each quantifier, flipping it, then negate the inner formula. ∀ distributes over ∧ and ∃ over ∨, but only one direction holds for the other pairs: ∀x P(x) ∨ ∀x Q(x) implies ∀x (P(x) ∨ Q(x)), and ∃x (P(x) ∧ Q(x)) implies ∃x P(x) ∧ ∃x Q(x); the converses fail. When x is not free in A: ∀x (A → P(x)) ≡ A → ∀x P(x), but a quantifier in the antecedent flips: ∀x (P(x) → A) ≡ ∃x P(x) → A and ∃x (P(x) → A) ≡ ∀x P(x) → A.
Nested quantifiers. Quantifiers of the same kind commute (∀x∀y ≡ ∀y∀x). Mixed ones do not: ∃y∀x P(x, y) says one y works for every x, which is stronger than ∀x∃y P(x, y), where y may depend on x. So ∃y∀x P(x, y) → ∀x∃y P(x, y) is valid, and the converse is not. Over the integers, ∀x∃y (x + y = 0) is true (take y = −x), but ∃y∀x (x + y = 0) is false. The four quantifier rules are universal instantiation (∀x P(x) ⊢ P(c) for any c), universal generalisation (P(c) for an arbitrary c ⊢ ∀x P(x)), existential instantiation (∃x P(x) ⊢ P(c) for some new c) and existential generalisation (P(c) ⊢ ∃x P(x)).
Concepts in depth: translating English
| English | Formula | Common wrong form |
|---|---|---|
| All S are P | ∀x (S(x) → P(x)) | ∀x (S(x) ∧ P(x)) says everything is S and P |
| Some S are P | ∃x (S(x) ∧ P(x)) | ∃x (S(x) → P(x)) is true if anything is not S |
| No S is P | ∀x (S(x) → ¬P(x)) ≡ ¬∃x (S(x) ∧ P(x)) | ¬∀x (S(x) → P(x)) means “not all” |
| Not all S are P | ∃x (S(x) ∧ ¬P(x)) | ∀x (S(x) → ¬P(x)) means “none” |
| Only S are P | ∀x (P(x) → S(x)) | ∀x (S(x) → P(x)) is the converse |
| Exactly one x has P | ∃x (P(x) ∧ ∀y (P(y) → y = x)) | ∃x P(x) allows many |
The rule of thumb is: ∀ goes with →, and ∃ goes with ∧.
Worked examples
Example 1: prove hypothetical syllogism is a tautology. Show that F = [(p → q) ∧ (q → r)] → (p → r) is a tautology.
Falsifying-row method. For F to be false we need p → r false, so p = T and r = F. We also need (p → q) true, which with p = T forces q = T, and (q → r) true, which with q = T forces r = T. But r = F, a contradiction. No row falsifies F, so it is a tautology.
Check with the truth table (L = (p → q) ∧ (q → r)):
| p | q | r | L | p → r | F |
|---|---|---|---|---|---|
| F | F | F | T | T | T |
| F | F | T | T | T | T |
| F | T | F | F | T | T |
| F | T | T | T | T | T |
| T | F | F | F | F | T |
| T | F | T | F | T | T |
| T | T | F | F | F | T |
| T | T | T | T | T | T |
L is true in 4 rows, and p → r is true in each of them, so the last column is all T.
Example 2: simplify with the laws. Simplify ¬(p ∨ (¬p ∧ q)).
- De Morgan: ¬p ∧ ¬(¬p ∧ q).
- De Morgan again and double negation: ¬p ∧ (p ∨ ¬q).
- Distribute: (¬p ∧ p) ∨ (¬p ∧ ¬q).
- Complement and identity: F ∨ (¬p ∧ ¬q) = ¬p ∧ ¬q.
Result: ¬p ∧ ¬q, which is ¬(p ∨ q) and also p ↓ q. The inner p ∨ (¬p ∧ q) had simplified to p ∨ q.
Example 3: PDNF and PCNF. Find both principal forms of (p ∨ q) → r, with rows numbered in the order p q r (p is the most significant bit).
The formula is false only when p ∨ q is true and r is false: rows 010 (2), 100 (4) and 110 (6). All other rows are true: 0, 1, 3, 5, 7.
PDNF = Σm(0, 1, 3, 5, 7) = (¬p ∧ ¬q ∧ ¬r) ∨ (¬p ∧ ¬q ∧ r) ∨ (¬p ∧ q ∧ r) ∨ (p ∧ ¬q ∧ r) ∨ (p ∧ q ∧ r).
PCNF = ΠM(2, 4, 6). For row 010 the maxterm is (p ∨ ¬q ∨ r); for 100 it is (¬p ∨ q ∨ r); for 110 it is (¬p ∨ ¬q ∨ r). So PCNF = (p ∨ ¬q ∨ r) ∧ (¬p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ r).
Check: 5 minterms + 3 maxterms = 8 = 2³. A shorter CNF is (¬p ∨ r) ∧ (¬q ∨ r), which is the common-consequent law (p → r) ∧ (q → r).
Example 4: test an argument. Premises: “If the server is patched (p), the audit passes (q). If the logs are complete (r), the report is signed (s). The server is patched or the logs are complete. The audit did not pass.” Conclusion: “The report is signed.”
- Premises: p → q, r → s, p ∨ r, ¬q. Conclusion: s.
- From p → q and ¬q: ¬p (modus tollens).
- From p ∨ r and ¬p: r (disjunctive syllogism).
- From r → s and r: s (modus ponens).
The argument is valid. Now change the last premise to “The audit passed (q)” and conclude “The server was patched (p)”. That is affirming the consequent: p = F, q = T, r = T, s = T makes every premise true and the conclusion false, so it is invalid.
Example 5: nested quantifiers on a finite domain. Domain D = {1, 2, 3, 4} and P(x, y): “x divides y”. Decide each statement.
- ∀x∃y P(x, y): true, take y = x.
- ∃y∀x P(x, y): we need a y in D divisible by 1, 2, 3 and 4, that is a multiple of 12. None exists, so false.
- ∃x∀y P(x, y): x = 1 divides everything, so true.
- ∀y∃x (x ≠ y ∧ P(x, y)): y = 1 has no divisor other than itself in D, so false.
Two are true and two are false. Statements 1 and 2 use the same predicate with the quantifiers swapped and get different answers, which is the whole point of nested-quantifier questions.
Example 6: translate and negate. “Every aspirant who revises daily clears the exam.” Let A(x): x is an aspirant, R(x): x revises daily, C(x): x clears the exam.
Formula: ∀x ((A(x) ∧ R(x)) → C(x)).
Negation: ∃x ¬((A(x) ∧ R(x)) → C(x)) = ∃x (A(x) ∧ R(x) ∧ ¬C(x)), “some aspirant revises daily and does not clear the exam”. It is not “every aspirant who revises daily fails”, which is the contrary, not the negation.
Interactive solver
Enter any problem, including the ones in your practice set, and the solver works it out step by step with the conventions stated. Use it to check your answers, not to replace doing them by hand: the exam gives you no solver.
Interactive solver: Truth table, normal forms and equivalence
The solver runs in your browser. Turn on JavaScript to use it.
Formula and fact sheet
| Item | Result |
|---|---|
| Rows, n variables | 2^n |
| Truth functions of n variables | 2^(2^n): 4 for n = 1, 16 for n = 2, 256 for n = 3 |
| p → q | ¬p ∨ q ≡ ¬q → ¬p; false only at p = T, q = F |
| Converse / inverse / contrapositive | q → p / ¬p → ¬q / ¬q → ¬p (only the contrapositive ≡ original) |
| “p only if q”, “q necessary for p” | p → q |
| “p unless q” | ¬q → p ≡ p ∨ q |
| Exportation | (p ∧ q) → r ≡ p → (q → r) |
| Common consequent | (p → r) ∧ (q → r) ≡ (p ∨ q) → r |
| Complete sets | {¬, ∧}, {¬, ∨}, {¬, →}, {→, F}, {↑}, {↓} |
| Not complete | {∧, ∨}, {∧, ∨, →, ↔}, {¬, ↔}, {⊕, ↔} |
| PDNF + PCNF terms | #minterms + #maxterms = 2^n |
| Valid argument | (P₁ ∧ … ∧ Pₙ) → C is a tautology |
| Quantifier negation | ¬∀x P ≡ ∃x ¬P; ¬∃x P ≡ ∀x ¬P |
| Distribution | ∀ over ∧, ∃ over ∨ (both ways); ∀P ∨ ∀Q ⇒ ∀(P ∨ Q); ∃(P ∧ Q) ⇒ ∃P ∧ ∃Q |
| Quantifier order | ∃y∀x P ⇒ ∀x∃y P (not conversely) |
NTA traps
- Converse for contrapositive. Wrong: “p → q is the same as q → p.” Fix: only ¬q → ¬p is equivalent; the converse and the inverse are equivalent to each other.
- Reading “only if” backwards. Wrong: “p only if q” is q → p. Fix: “only if” introduces the consequent: p → q. “p if q” is q → p.
- Common consequent. Wrong: (p → r) ∧ (q → r) ≡ (p ∧ q) → r. Fix: it is (p ∨ q) → r; the “or” form (p → r) ∨ (q → r) is (p ∧ q) → r.
- Treating → as associative. Wrong: p → q → r means (p → q) → r. Fix: the two bracketings differ (p = F, r = F); NTA writes the brackets, so read them.
- Negating a conditional into a conditional. Wrong: ¬(p → q) = ¬p → ¬q. Fix: ¬(p → q) = p ∧ ¬q.
- ∀ with ∧, ∃ with →. Wrong: “All S are P” as ∀x (S(x) ∧ P(x)). Fix: ∀ pairs with →, ∃ pairs with ∧.
- Swapping mixed quantifiers. Wrong: ∀x∃y ≡ ∃y∀x. Fix: only ∃y∀x ⇒ ∀x∃y holds.
- Quantifier in an antecedent. Wrong: ∀x (P(x) → A) ≡ ∀x P(x) → A. Fix: it is ∃x P(x) → A.
- Fallacies accepted as valid. Affirming the consequent and denying the antecedent are invalid; test them with the row p = F, q = T.
- Counting rows instead of functions. Three variables give 8 rows but 256 functions.
How NTA asks this
- Direct MCQ: which formula is a tautology, contradiction or equivalent to a given one; the negation of a quantified sentence; the correct translation of an English sentence. Use the falsifying-row method, and test equivalence by finding one row where the two formulas differ.
- Match the following: rules of inference with their forms, connectives with equivalent expressions, English sentence types with formulas, laws with their names.
- Assertion–Reason and Statement I/II: contrapositive and converse, functional completeness, validity of quantifier laws, CNF/DNF facts.
- Multiple select: which formulas are equivalent, which sets are functionally complete, which formulas are tautologies.
- Order: steps of CNF conversion or of a resolution proof.
Mini-example (match). List I: A. p → q, B. p ↔ q, C. p ⊕ q, D. p ↓ q. List II: I. ¬p ∧ ¬q, II. ¬p ∨ q, III. (p ∧ q) ∨ (¬p ∧ ¬q), IV. (p ∧ ¬q) ∨ (¬p ∧ q). Answer: A-II, B-III, C-IV, D-I. Fix the easiest pair first (NOR = “neither” = I), then eliminate every option that disagrees.
Mini-example (A-R). A: ∃y∀x P(x, y) → ∀x∃y P(x, y) is valid. R: Swapping ∀ and ∃ never changes the meaning. A is true (one y that works for all x certainly gives each x a y), but R is false (∀x∃y does not imply ∃y∀x). Answer: option 3.