← Back to Mathematical Logic, Set Theory and Combinatorics
Course: MAT1MN104 — Mathematical Logic, Set Theory and Combinatorics Hours: 15 | Textbook Sections: 1.1–1.4 (Thomas Koshy, Discrete Mathematics with Applications, 1/e)
Notation used throughout (Koshy’s convention): negation is $\sim p$ (a tilde), not $\neg p$. Conjunction $\land$, disjunction $\lor$, conditional $\to$, biconditional $\leftrightarrow$, universal quantifier $\forall$, existential quantifier $\exists$, “therefore” $\therefore$.
1. Propositions
A proposition is a declarative sentence that is either true or false, but not both. We write $t(p) = T$ or $t(p) = F$ for the truth value of proposition $p$.
- “2 + 2 = 4” — a proposition (true).
- “The moon is made of cheese” — a proposition (false).
- “x + 1 = 5” — not a proposition until $x$ is fixed.
- “Please close the door” — not a proposition (not declarative).
1.1 Conjunction, Disjunction, Negation
| Name | Symbol | Read as | True when |
|---|---|---|---|
| Conjunction | $p \land q$ | “p and q” | both p and q are true |
| Disjunction | $p \lor q$ | “p or q” | at least one of p, q is true |
| Negation | $\sim p$ | “not p” | p is false |
Example. p: “Kochi is in Kerala” (T), q: “5 is even” (F).
- $p \land q = F$ (since q is false)
- $p \lor q = T$ (since p is true)
- $\sim q = T$
A truth table for an expression with n propositional variables has $2^n$ rows.
1.2 The Conditional p → q
$p \to q$ (“if p then q”) is false only when p is true and q is false; true in every other case. p is the hypothesis, q is the conclusion.
\[\begin{array}{cc|c} p & q & p \to q \\ \hline T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \\ \end{array}\]Think of it as a promise: “If you wax my car (p), I’ll pay you $25 (q).” The promise is broken only if you wax the car and I don’t pay. If you never wax the car, the promise was never tested — so when p is false, p → q is vacuously true.
⚠️ Unlike English, $p \to q$ does not require p to cause q. “If the power is on, then $3 + 5 = 8$” is a true implication (the conclusion is true regardless), even though the two halves are unrelated.
Worked example. Let $p(n)$: “n is prime”, $q(n)$: “n is odd”. Evaluate $p(n) \to q(n)$ for $n = 2, 9, 15$.
- $n = 2$: $p = T$ (2 is prime), $q = F$ (2 is even) $\to p\to q = $ F.
- $n = 9$: $p = F$ (9 = 3×3, not prime), $q = T$ (9 is odd) $\to p\to q = $ T (vacuously true).
- $n = 15$: $p = F$ (15 = 3×5, not prime), $q = T$ (15 is odd) $\to p\to q = $ T (vacuously true).
The last two cases are vacuously true: whenever the hypothesis is false, the conditional is automatically true, regardless of the conclusion.
1.3 Converse, Inverse, Contrapositive
From $p \to q$ we build:
- Converse: $q \to p$ (swap)
- Inverse: $\sim p \to \sim q$ (negate both)
- Contrapositive: $\sim q \to \sim p$ (negate both, then swap)
Example. p → q: “If △ABC is equilateral, then it is isosceles.”
- Converse: “If isosceles, then equilateral.” — false in general!
- Inverse: “If not equilateral, then not isosceles.” — false in general!
- Contrapositive: “If not isosceles, then not equilateral.” — true.
Key fact: a conditional and its contrapositive are always logically equivalent ($p \to q \equiv \sim q \to \sim p$); a conditional and its converse generally are not.
Worked example. p → q: “If $x = 3$, then $x^2 = 9$.”
- Converse ($q\to p$): “If $x^2 = 9$, then $x = 3$.” — false ($x = -3$ is a counterexample: $(-3)^2 = 9$ but $-3 \neq 3$).
- Inverse ($\sim p\to\sim q$): “If $x \neq 3$, then $x^2 \neq 9$.” — false (same counterexample, $x = -3$).
- Contrapositive ($\sim q\to\sim p$): “If $x^2 \neq 9$, then $x \neq 3$.” — true (logically equivalent to the original statement).
The converse and inverse fail on the same counterexample — no coincidence, since the inverse of $p\to q$ is always logically equivalent to its converse.
1.4 The Biconditional p ↔ q
$p \leftrightarrow q$ (“p if and only if q”) is true exactly when p and q have the same truth value.
\[\begin{array}{cc|c} p & q & p \leftrightarrow q \\ \hline T & T & T \\ T & F & F \\ F & T & F \\ F & F & T \\ \end{array}\]Example. Let $S$ = digit sum of 2034 = 9. “2034 is divisible by 3 iff S is divisible by 3” — true, since both halves happen to be true together.
1.5 Order of Precedence
Highest to lowest: $\sim, \land, \lor, \to, \leftrightarrow$. Equal-precedence operators evaluate left to right; parenthesised parts evaluate first.
Example: $p \to q \land \sim q \to \sim p$ groups as $[p \to (q \land \sim q)] \to \sim p$, since $\land$ binds tighter than $\to$, and the two remaining $\to$’s (equal precedence) chain left to right.
1.6 Tautology, Contradiction, Contingency
- Tautology — true for every combination of truth values (e.g. $p \lor \sim p$).
- Contradiction — false for every combination (e.g. $p \land \sim p$).
- Contingency — neither; true for some rows, false for others (e.g. $p \to q$).
Worked example. Classify (a) $(p\land q)\to p$, (b) $(p\lor q)\land(\sim p\land\sim q)$, (c) $p\lor(q\land\sim q)$.
\[\begin{array}{cc|c|c|c} p & q & \text{(a)}\ (p\land q)\to p & \text{(b)}\ (p\lor q)\land(\sim p\land\sim q) & \text{(c)}\ p\lor(q\land\sim q) \\ \hline T & T & T & F & T \\ T & F & T & F & T \\ F & T & T & F & F \\ F & F & T & F & F \\ \end{array}\](a) is a tautology (always T — it’s exactly the simplification inference rule from Section 4). (b) is a contradiction (always F — it says “p or q” and “neither p nor q” at once). (c) is a contingency (matches p exactly, since $q\land\sim q$ is always false).
(Exam scope: Section 1.1 is fully examinable except the switching-network material and Example 1.16 of the textbook.)
2. Logical Equivalences
Two propositions P and Q are logically equivalent ($P \equiv Q$) if they have identical truth tables — equivalently, $P \leftrightarrow Q$ is a tautology.
Worked example. Show $p \to q \equiv \sim q \to \sim p$.
\(\begin{array}{cc|c|cc|c} p & q & p\to q & \sim q & \sim p & \sim q\to\sim p \\ \hline T & T & T & F & F & T \\ T & F & F & T & F & F \\ F & T & T & F & T & T \\ F & F & T & T & T & T \\ \end{array}\) Columns match → equivalent. (This exact question appeared on the Oct 2024 paper.)
2.1 The Laws of Logic (Koshy’s Table 1.13)
Let p, q, r be propositions, t a tautology, f a contradiction.
| Law | Statement |
|---|---|
| Idempotent | $p\land p \equiv p$ $p\lor p \equiv p$ |
| Identity | $p\land t \equiv p$ $p\lor f \equiv p$ |
| Inverse | $p\land(\sim p) \equiv f$ $p\lor(\sim p) \equiv t$ |
| Domination | $p\lor t \equiv t$ $p\land f \equiv f$ |
| Commutative | $p\land q \equiv q\land p$ $p\lor q \equiv q\lor p$ |
| Double negation | $\sim(\sim p) \equiv p$ |
| Associative | $p\land(q\land r) \equiv (p\land q)\land r$ $p\lor(q\lor r) \equiv (p\lor q)\lor r$ |
| Distributive | $p\land(q\lor r) \equiv (p\land q)\lor(p\land r)$ $p\lor(q\land r) \equiv (p\lor q)\land(p\lor r)$ |
| De Morgan’s | $\sim(p\land q) \equiv \sim p\lor\sim q$ $\sim(p\lor q) \equiv \sim p\land\sim q$ |
| Implication conversion | $p\to q \equiv \sim p\lor q$ |
| Contrapositive | $p\to q \equiv \sim q\to\sim p$ |
| Reductio ad absurdum | $p\to q \equiv (p\land\sim q)\to f$ |
⚠️ Parentheses matter in the distributive laws — $p\land(q\lor r)$ is not the same as $p\land q\lor r$ (which parses as $(p\land q)\lor r$ by precedence).
Worked example — simplification. \(\begin{aligned} &\sim(p \lor \sim q) \lor (\sim p \land \sim q) \\ &\equiv (\sim p \land \sim(\sim q)) \lor (\sim p \land \sim q) && [\text{De Morgan}] \\ &\equiv (\sim p \land q) \lor (\sim p \land \sim q) && [\text{double negation}] \\ &\equiv \sim p \land (q \lor \sim q) && [\text{distributive}] \\ &\equiv \sim p \land t && [\text{inverse law}] \\ &\equiv \sim p && [\text{identity law}] \end{aligned}\)
(Exam scope: you will not be asked to prove the 20 laws, only to apply/simplify with them.)
3. Quantifiers
- Universal quantifier ∀ (“for all/each/every”): $(\forall x)\, P(x)$.
- Existential quantifier ∃ (“there exists/for some/at least one”): $(\exists x)\, P(x)$.
Examples:
- “All apples are green” → $(\forall x)(x \text{ is an apple} \to x \text{ is green})$. (Just $(\forall x)\, P(x)$ with $P(x)$: “x is green” would claim everything in the universe is green — the “if it’s an apple” condition has to be written in.)
- “For each integer x, there exists an integer y such that x + y = 0” → $(\forall x)(\exists y)(x + y = 0)$. (Oct 2024 paper.)
- “There exists an even prime number” → $(\exists x)(x \text{ is even} \land x \text{ is prime})$.
- “No birds are black” → $(\forall x)(x \text{ is a bird} \to \sim(x \text{ is black}))$.
Subsets are already quantified statements: $A \subseteq B$ means $(\forall x)(x \in A \to x \in B)$.
3.1 Optional / Not Examined — Negating Quantified Statements
$\sim(\forall x)\, P(x) \equiv (\exists x)\, \sim P(x)$ and $\sim(\exists x)\, P(x) \equiv (\forall x)\, \sim P(x)$ — mirrors De Morgan’s laws for $\land$/$\lor$ ($\forall$ behaves like a big $\land$, $\exists$ like a big $\lor$). This is Koshy’s Example 1.29 / De Morgan’s laws for quantifiers, both marked optional in the syllabus and not externally examined.
(Exam scope: translating English ↔ quantified symbolic form is examinable; the quantifier De Morgan’s laws are not.)
4. Arguments
An argument is a list of premises followed by a conclusion. It is valid if, whenever all premises are true, the conclusion must be true — i.e., $(p_1 \land p_2 \land \cdots \land p_n) \to q$ is a tautology.
Method: (1) symbolise the premises and conclusion, (2) assume the premises true, (3) see if the inference rules/laws of logic force the conclusion.
4.1 Inference Rules (Koshy’s Table 1.17)
| Rule | Statement |
|---|---|
| Conjunction | $p\land q \to (p\land q)$ |
| Simplification | $p\land q \to p$ |
| Addition | $p \to p\lor q$ |
| Law of detachment (modus ponens) | $[p \land (p\to q)] \to q$ |
| Law of the contrapositive (modus tollens) | $[(p\to q) \land (\sim q)] \to \sim p$ |
| Disjunctive syllogism | $[(p\lor q) \land (\sim p)] \to q$ |
| Hypothetical syllogism | $[(p\to q) \land (q\to r)] \to (p\to r)$ |
The law of detachment in inferential form: \(\begin{array}{c} p \\ p \to q \\ \hline \therefore q \end{array}\)
Worked example.
If the computer was down Saturday afternoon, then Mary went to a matinee. Either Mary went to a matinee or she took a nap that afternoon. Mary did not take a nap that afternoon. ∴ The computer was down Saturday afternoon.
Let p: computer down, q: Mary went to matinee, r: Mary napped. Premises: $p\to q$, $q\lor r$, $\sim r$. Conclusion: $p$. From $q\lor r$ and $\sim r$ (disjunctive syllogism): $q$. But we only know $p\to q$, not $q\to p$ — knowing $q$ does not let us conclude $p$. Invalid (fallacy of affirming the consequent), even though the conclusion sounds plausible.
Worked example. Check the validity: “If Meera studies, she will pass. If she passes, she gets the scholarship. Meera did not get the scholarship. ∴ Meera did not study.”
Let p: Meera studies, q: Meera passes, r: Meera gets the scholarship. Premises: $p\to q$, $q\to r$, $\sim r$. Conclusion: $\sim p$. From $p\to q$ and $q\to r$ (hypothetical syllogism): $p\to r$. From $p\to r$ and $\sim r$ (modus tollens): $\sim p$ — exactly the conclusion. Valid, no fallacy this time.
⚠️ The most common trap: from $p \to q$ and $q$ (true), concluding $p$. That is not a valid rule — compare with the law of detachment, which needs $p$ (not $q$) as the known premise.
(Exam scope: Section 1.4 is fully examinable except Example 1.33.)
Chapter Summary
- Proposition: declarative sentence, definite truth value.
- Connectives: $\land, \lor, \sim$ (tilde, not $\neg$), $\to, \leftrightarrow$. Precedence: $\sim, \land, \lor, \to, \leftrightarrow$.
- From $p\to q$: converse $q\to p$, inverse $\sim p\to\sim q$, contrapositive $\sim q\to\sim p$ (always equivalent to $p\to q$ itself).
- Tautology / contradiction / contingency.
- Logical equivalence and the 20 laws of logic (De Morgan’s laws are the most-used).
- Quantifiers $\forall, \exists$; translating English ↔ symbols.
- Valid arguments via inference rules, especially the law of detachment.
Practice Problems
- Give truth tables for conjunction and disjunction of two propositions.
- Write the negation of “The exam is easy and the hall is cool.”
- Rewrite symbolically: “For each real number x, there exists a real number y such that x + y = 0.”
- Define contradiction and give an example other than $p \land \sim p$.
- Construct the truth table for $(p\to q) \land (q\to p)$. Which biconditional does it match?
- State the converse, inverse, contrapositive of “If a number is divisible by 6, it is divisible by 3.” Which is guaranteed true?
- Simplify $(p\land q) \lor (p\land \sim q)$ using the laws of logic, naming each law used.
- Verify $\sim(p\lor q) \equiv \sim p\land\sim q$ using a truth table.
- Translate: “Every student who studies passes, but some student who studies did not pass.” Is this consistent?
- Check validity: “If it rains, the match is cancelled. It did not rain. Therefore the match was not cancelled.” Name the fallacy, if any.
- Using the laws of logic (not a truth table), show $p\to(q\to r) \equiv (p\land q)\to r$.
- Asha says “Bala did it.” Bala says “Chithra did it.” Chithra says “Bala is lying.” Exactly one is telling the truth. Who ate the mango?
- Determine the truth value of $p\to q$, where p: “10 is a prime number” and q: “10 is an even number.”
- Classify $(p\land\sim p)\lor q$ as a tautology, contradiction, or contingency.
- State the converse, inverse, and contrapositive of “If $x = 3$, then $x^2 = 9$.” Determine which of the three is guaranteed to be true.
- Translate into symbols: “There exists a student who has not submitted the assignment.”
- Using the laws of logic, simplify $(p\to q)\land(p\to\sim q)$.
- Check the validity of the argument: “Either the flight is delayed or I miss the meeting. The flight is not delayed. Therefore, I miss the meeting.” Name the rule used if the argument is valid.
- Using the laws of logic, prove that $\sim(p\leftrightarrow q) \equiv (p\land\sim q)\lor(\sim p\land q)$.