← 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.
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.
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$.
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$).
(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)\, P(x)$, where $P(x)$: “x is green”.
- “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.
⚠️ 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?