Many students can recite the symbols for implication and quantifiers but still confuse a formula's truth under one valuation with an argument's validity over every valuation. That confusion survives any amount of symbol drill and dies the moment a claim is checked on concrete values: a filled truth table, a named countervaluation, a domain small enough to enumerate. The propositional and predicate logic explainer states the connectives and the equivalence laws. Canonical forms, quantifier order and layered negation are the harder half, and they are where GATE CS preparation loses marks.
Propositions, predicates and the language of logic
A proposition is a declarative sentence with a definite truth value. “7 is prime” is true, while “10 is divisible by 3” is false. “Close the door” is a command and “Is 7 prime?” is a question, so neither is a proposition.
A predicate contains a variable. For example, E(x): x is even becomes a proposition only after a domain and a value or quantifier are supplied.
The main connectives are NOT (¬), AND (∧), inclusive OR (∨), implication (→) and biconditional (↔). Their precedence is ¬, then ∧, then ∨, then →, then ↔. Parentheses are still safer whenever scope could be doubted.
At p=T, q=F, r=T, evaluate ¬p ∨ (q ∧ r) one subexpression at a time: ¬p=F, q∧r=F, and finally F∨F=F.
Truth tables, implication and logical equivalence
Use the row order TT, TF, FT, FF consistently:
p | q | ¬p | ¬p∨q | p→q | p↔q |
|---|---|---|---|---|---|
T | T | F | T | T | T |
T | F | F | F | F | F |
F | T | T | T | T | F |
F | F | T | T | T | T |
Matching columns prove p→q ≡ ¬p∨q. Logical equivalence requires agreement on every valuation, not one.
An implication is false only for T→F. At p=T, q=F, the original is p→q=F. Its contrapositive is ¬q→¬p = T→F = F, while the converse is q→p = F→T = T and the inverse is ¬p→¬q = F→T = T. The implication and its contrapositive agree on every valuation, so p→q ≡ ¬q→¬p. The converse and the inverse are contrapositives of each other, so q→p ≡ ¬p→¬q, and neither pair settles the other.
One formula as a truth table, canonical DNF and CNF
Consider H(p,q,r) = (p∧q) ∨ (¬p∧r). Treat pqr as a three-bit binary row index:
pqr | p∧q | ¬p∧r | H |
|---|---|---|---|
000 | 0 | 0 | 0 |
001 | 0 | 1 | 1 |
010 | 0 | 0 | 0 |
011 | 0 | 1 | 1 |
100 | 0 | 0 | 0 |
101 | 0 | 0 | 0 |
110 | 1 | 0 | 1 |
111 | 1 | 0 | 1 |
H is 1 on exactly four of the eight rows, and never through both disjuncts at once: p∧q needs p=1, while ¬p∧r needs p=0.
The output sequence is 0,1,0,1,0,0,1,1. The 1-rows give the canonical DNF:
H = Σm(1,3,6,7) = ¬p¬qr ∨ ¬pqr ∨ pq¬r ∨ pqr.
Combine the first two minterms as ¬pr(¬q∨q)=¬pr. Combine the last two as pq(¬r∨r)=pq. Therefore the compact DNF is H=(¬p∧r)∨(p∧q).
The 0-rows give H = ΠM(0,2,4,5), and the compact CNF is H=(¬p∨q)∧(p∨r). At row 001, the DNF gives 1 and the CNF gives (1∨0)∧(0∨1)=1. At row 101, the DNF gives 0 and the CNF gives (0∨0)∧(1∨1)=0. Operationally, when p=0, H takes r; when p=1, H takes q.
Valid arguments, inference rules and counterexamples
Truth belongs to a statement under a valuation. Validity belongs to an argument across all valuations. An argument is valid when no valuation makes every premise true and the conclusion false.
The useful inference shapes include modus ponens (p→q, p, therefore q), modus tollens (p→q, ¬q, therefore ¬p), hypothetical syllogism (p→q, q→r, therefore p→r) and disjunctive syllogism (p∨q, ¬p, therefore q).
For premises p→q, q→r and p, first derive q by modus ponens. Then derive r from q→r and q. The single test formula [((p→q)∧(q→r)∧p)→r] is a tautology.
If all three premises are true, p yields q and q yields r, so the conclusion cannot be false. If any premise is false, the test implication is true by definition.
Now test the invalid pattern p→q, q, therefore p at p=F, q=T. Here p→q=T and q=T, but the proposed conclusion p=F. One countervaluation is enough to refute validity.
Predicates, domains, free variables and quantifiers
Quantifiers have meaning only after the domain is fixed. ∀x P(x) says P holds for every x in that domain. ∃x P(x) says P holds for at least one x in it.
On U={1,2,3,4}, let E(x): x is even and L(x): x<4. The universal claim ∀x(E(x)→L(x)) is false because x=4 gives E(4)=T and L(4)=F, so its implication is false. The existential claim ∃x(E(x)∧L(x)) is true because x=2 is a witness.
In E(x) ∨ ∃y(y<x), the occurrence of y is bound by ∃y, while x remains free. The entire expression is not yet a proposition. It becomes one only when x is assigned or quantified.
A universal claim must hold for every domain element, while an existential claim needs one witness. Conversely, one counterexample refutes a universal claim. The choice of domain is part of the statement, which is why sets, relations and domains matter before quantifier manipulation begins.
Nested quantifiers and negation, worked on a finite domain
Let D={1,2,3} and R(x,y): x+y=4. The claim ∀x∃y R(x,y) is true. For x=1, choose y=3; for x=2, choose y=2; for x=3, choose y=1. In words, every element has some partner in D whose sum with it is 4.
Write the predicate values as a matrix:
x \ y | 1 | 2 | 3 |
|---|---|---|---|
1 | F | F | T |
2 | F | T | F |
3 | T | F | F |
Each row has one T, satisfying ∀x∃y. No column is all T, so no fixed y works for every x.
Swap the quantifiers. The claim ∃y∀x R(x,y) says that one fixed y works for every x, and it is false. y=1 fails at x=1, y=2 fails at x=1, and y=3 fails at x=2. The same predicate and domain therefore produce different results when quantifier order changes.
Negate the original one layer at a time:
¬∀x∃y R(x,y) ≡ ∃x¬∃y R(x,y) ≡ ∃x∀y¬R(x,y) ≡ ∃x∀y(x+y≠4).
This says, “There is an element for which no element in D gives a sum of 4.” It is false on D because each x has one of the witnesses listed above.
Common traps and how exams test them
Six confusions account for most of the marks lost on this topic, and each one has a mechanical check:
If p→q looks interchangeable with q→p, test p=F, q=T.
When negating quantifiers, swap the quantifier and negate the predicate: ¬∀xP(x)≡∃x¬P(x) and ¬∃xP(x)≡∀x¬P(x).
If ∀x∃y and ∃y∀x seem identical, draw the finite-domain matrix.
Never omit the domain from a predicate claim.
Treat OR as inclusive, including the row where both inputs are true.
“Satisfiable” means true for at least one valuation. “Tautology” means true for every valuation.
Realistic tasks ask you to complete a truth table, identify an equivalent formula, find a countervaluation, test an argument, translate English into quantified notation, negate a nested statement, or compare quantifier orders under pressure.
KnowledgeGate carries over 300 practice questions on propositional and predicate logic in Discrete Mathematics. Use the GATE Test Series to turn these checks into exam-style practice.
The short version and what to practise next
Fix the domain, identify atomic statements, parenthesise the formula, evaluate inner connectives, compare complete truth-table columns, seek a countervaluation for validity, and push negation through quantifiers one layer at a time. Remember H(0,0,1)=1 and the witness pairs (1,3), (2,2), (3,1) for x+y=4.
Next, rebuild the eight-row H table and the 3×3 matrix from memory. Then change the domain to {1,2,3,4} and re-evaluate both quantified statements: x=4 now has no partner summing to 4, so ∀x∃y R(x,y) flips to false. For the rest of the Discrete Mathematics syllabus in teaching order, follow GATE Guidance by Sanchit Sir.
