Propositional logic and truth tables
Learning objectives and scope
Translate conditions into formulas, construct a complete truth table, distinguish implication from its converse, test equivalence, and find counterexamples to arguments. Prerequisite: basic mathematical notation. This lesson covers classical two-valued propositional logic. Predicate logic, quantifiers, normal-form algorithms and proof systems require separate lessons; this is not complete Discrete Mathematics coverage.
1. Start with statements
A proposition is a declarative statement with a definite truth value in the situation being discussed: true (T) or false (F). “7 is prime” is a true proposition. “8 is prime” is also a proposition, but false. “Open the file” is a command, not a proposition. “x is even” is an open predicate until x is assigned a value or quantified.
Let p mean “the token is valid” and q mean “access is granted.” We manipulate these as abstract truth values. Logical implication does not itself describe causation, execution order or a program. A real system may have conditions not represented by these variables.
Negation ¬p reverses p. Conjunction p ∧ q requires both statements true. Disjunction p ∨ q is inclusive: one or both may be true. Exclusive OR p ⊕ q requires exactly one true statement. Parentheses matter: ¬(p ∧ q) differs from (¬p) ∧ q. Parenthesize mixed expressions rather than relying on differing precedence conventions.
2. Build the complete table
n distinct variables have 2^n assignments; count distinct variables, not occurrences. With two variables list TT, TF, FT, FF systematically.
| p | q | ¬p | p ∧ q | p ∨ q | p ⊕ q | p → q | p ↔ q |
|---|---|---|---|---|---|---|---|
| T | T | F | T | T | F | T | T |
| T | F | F | F | T | T | F | F |
| F | T | T | F | T | T | T | F |
| F | F | T | F | F | F | T | T |
p → q means “if p, then q.” It is false only when p is true and q false; equivalently, p → q ≡ ¬p ∨ q. A false antecedent makes material implication true, but does not establish q. The biconditional p ↔ q requires equal truth values and equals (p → q) ∧ (q → p).
A useful promise analogy is “If you submit the form, I will send a receipt.” Submission without a receipt breaks that promise. Without submission, the conditional promise is not broken whether a receipt arrives or not. The formal truth definition, rather than a causal interpretation of this analogy, decides the answer.
3. Direction and negation
For p → q, the converse is q → p, the inverse is ¬p → ¬q, and the contrapositive is ¬q → ¬p. Only the contrapositive is always equivalent to the original. At p = F, q = T, the original is T but the converse is F: one counterexample disproves equivalence. Both the original and contrapositive reduce to ¬p ∨ q.
Negating an implication is a different operation: ¬(p → q) ≡ p ∧ ¬q. This picks exactly the broken-promise case. Translate “p only if q” as p → q: q is necessary for p. Translate “p if q” as q → p: q is sufficient for p. “If and only if” requires both directions.
4. Worked example: simplify, then verify
Let F = (p → q) ∧ p. Replacing implication and distributing gives
F ≡ (¬p ∨ q) ∧ p ≡ (¬p ∧ p) ∨ (q ∧ p) ≡ p ∧ q.
The contradictory term ¬p ∧ p is false; OR with false leaves the other term. Check independently:
| p | q | p → q | (p → q) ∧ p | p ∧ q |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | F | F |
| F | T | T | F | F |
| F | F | T | F | F |
The final columns agree on every assignment. Agreement on just one row would not prove equivalence.
5. Classifying formulas
A tautology is true on every assignment, such as p ∨ ¬p. A contradiction is false on every assignment, such as p ∧ ¬p. A contingency is true on some assignments and false on others, such as p → q. Satisfiable means true on at least one assignment, so tautologies and contingencies are both satisfiable. Here, a valid formula means a tautology, not merely a satisfiable formula.
To prove F and G equivalent by tables, compare all assignments. To disprove equivalence, one differing assignment suffices. Equivalently, F ↔ G must be a tautology. Testing a few favorable examples is not exhaustive proof.
6. Worked example: argument validity
Premises p → q and q → r imply conclusion p → r. Suppose both premises are true. If p is false, the conclusion is true automatically. If p is true, the first premise forces q true and the second then forces r true; the conclusion is again true. No assignment makes all premises true and the conclusion false.
In contrast, p → q and q do not imply p. Choose p = F, q = T. Both premises are true but p is false. This is the fallacy of affirming the consequent. Validity means truth is preserved under the premises; it does not assert that the real-world premises actually hold.
Quick reference and common errors
- n distinct variables give 2^n rows.
- p → q ≡ ¬p ∨ q ≡ ¬q → ¬p.
- ¬(p → q) ≡ p ∧ ¬q.
- De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q.
- ↔ means matching truth values; ⊕ means differing truth values.
- Invalid argument: at least one row with all premises T and conclusion F.
Do not read inclusive OR as “exactly one,” infer an antecedent from its consequent, or replace negation with inverse. Use this workflow: identify distinct variables, add parentheses, list all assignments, evaluate inner expressions first, and finally apply the requested test. A false premise by itself tells you nothing about the actual truth of a conclusion.
7. A decision procedure for argument questions
For premises P₁,…,Pₖ and conclusion C, test (P₁ ∧ … ∧ Pₖ) → C. The argument is valid exactly when this conditional is a tautology. Equivalently, try to satisfy P₁ ∧ … ∧ Pₖ ∧ ¬C: one satisfying assignment is a counterexample; no satisfying assignment means the argument is valid. This is a test for truth preservation, not a claim that the premises describe reality.
For p→q and ¬q, concluding ¬p is valid (modus tollens). To make the conclusion false requires p=T. With ¬q true, q=F; then p→q is false, so no counterexample can keep both premises true. By contrast, p→q and ¬p do not justify ¬q: choose p=F, q=T. Do not confuse this invalid denial of the antecedent with modus tollens.
If the premises are p and ¬p, no row makes both true. Such inconsistent premises make the argument vacuously valid for any conclusion in classical logic. “Valid” therefore does not mean “the premises are jointly possible” or “a useful real-world explanation.”
Original practice: six single-correct MCQs
Original questions, not previous-year questions. Choose exactly one option.
C01. For p=F and q=T, what are the truth values of p→q and q→p, respectively?
A. T, T B. T, F C. F, T D. F, F
Answer: B
A: The converse has a true antecedent and false consequent, so it is false.
B: The first implication is true because p is false; the converse is false because q is true and p false.
C: This reverses the two values; false antecedents do not make implication false.
D: Only q→p is false; p→q has a false antecedent.
C02. Which formula is equivalent to ¬(p→q)?
A. ¬p∨q B. ¬p∧q C. p∧¬q D. ¬q→¬p
Answer: C
A: This is p→q itself, not its negation.
B: This describes p false and q true, where p→q is true.
C: Negating ¬p∨q gives p∧¬q by De Morgan; it selects the only false implication row.
D: The contrapositive is equivalent to the original implication, not its negation.
C03. How many rows are needed in a complete truth table for (p∨q)∧(p→r)?
A. 4 B. 6 C. 16 D. 8
Answer: D
A: Four rows suffice for two distinct variables, but this formula has three.
B: Rows count all combinations, not twice the number of variables.
C: Repeated p is not a fourth independent variable.
D: The distinct variables are p,q,r; 2^3=8 assignments are required.
C04. Which classification applies to (p→q)∨(q→p)?
A. Tautology B. Contradiction C. Contingency D. Unsatisfiable but not a contradiction
Answer: A
A: Its expansion ¬p∨q∨¬q∨p contains q∨¬q, so every assignment makes it true.
B: It is never false, so cannot be a contradiction.
C: A contingency needs both true and false rows; there are no false rows here.
D: In classical two-valued logic an unsatisfiable formula is a contradiction; this formula is satisfiable on every row.
C05. Which assignment disproves the argument: p→q and q, therefore p?
A. p=T, q=T B. p=T, q=F C. p=F, q=F D. p=F, q=T
Answer: D
A: The conclusion is true, so this cannot refute validity.
B: The premise q and the implication are false, so this is not a counterexample with all premises true.
C: The premise q is false; an invalidity witness needs every premise true.
D: p→q and q are both true, while the conclusion p is false: exactly the required counterexample.
C06. Let p mean “a request is accepted” and q mean “its token is valid.” Translate “a request is accepted only if its token is valid.”
A. q→p B. p→q C. p↔q D. p∧q
Answer: B
A: This says a valid token is sufficient for acceptance; that is not stated.
B: Validity is necessary for acceptance, so acceptance implies validity: p→q.
C: The reverse implication is an extra condition not supplied by “only if.”
D: A conditional rule does not assert that either event actually occurs.
Source and scope
This introductory lesson aligns with Discrete Mathematics in Section 1 of the official GATE 2027 CS syllabus. It is not full-topic or full-syllabus coverage. The source establishes syllabus relevance; teaching examples and questions are original.
Official GATE 2027 CS syllabus (verified 2026-10-14).
Sign in to keep your progress. Sign in