Propositional Logic

Last lesson promised a turn from searching to reasoning — a language for facts and an exact notion of “follows from.” Here it begins. “If it rains, the picnic is off.” You have just stated a logical implication, and you can already feel that “it rains” tells you about “picnic off” but not the other way round. Propositional logic is the mathematics behind that feeling, and behind the doctor’s deduction and the verifier’s proof.

Each simple statement (“it rains”, “picnic is off”) is an atomic proposition — a variable that is either true or false. You glue them together with five connectives, and the entire apparatus of “what follows from what” collapses onto one humble object: the truth table. The payoff is everywhere in real systems — the same satisfiability and entailment reasoning drives SAT solvers, digital-circuit verification, and the rule engines behind feature flags and access-control checks.

The five connectives

• ¬p — not p
• p ∧ q — p and q (both true)
• p ∨ q — p or q (at least one true)
• p → q — p implies q (false only when p is true and q is false)
• p ↔ q — p iff q (true when p and q agree)

The one that trips people is →. p → q is false in exactly one row: p true, q false. In the other three rows it is true — even when p is false (“vacuously true”). Memorise the identity that makes most equivalence problems trivial: p → q ≡ ¬p ∨ q.

Truth assignments, models, and the words you’ll see on the exam

A truth assignment picks T or F for every variable; with n variables there are 2^n of them. A model of a formula is an assignment that makes the formula come out true. From models you get every other piece of vocabulary:

• Satisfiable — at least one model exists.
• Valid (a tautology) — every assignment is a model.
• Unsatisfiable (a contradiction) — no models at all.
• Logically equivalent — S₁ ≡ S₂ means they have exactly the same models.
• Entailment — X ⊨ Y means every model of X is also a model of Y.

How GATE asks this

Three flavours, all close to the surface of the truth table:

1. NAT — count the models of a small formula over 2–3 variables. Rule out the rows that make it false; what is left is the count.
2. MCQ — logical equivalence. Pick which pair of formulas have the same truth table. The lever is almost always p → q ≡ ¬p ∨ q or De Morgan.
3. MCQ/MSQ — entailment. Pick a true statement about ⊨. The key fact: X ⊨ Y if and only if X ∧ ¬Y is unsatisfiable (no row makes X true and Y false at once).

Worked example — GATE DA 2024

Over the three variables A, B, C, how many models does the formula A ∨ ¬B ∨ C have?

There are 2^3 = 8 truth assignments. A disjunction is false only when every disjunct is false. The three disjuncts are A, ¬B, C, so the formula fails only when

A = F   and   ¬B = F (i.e. B = T)   and   C = F

That is the single row (A, B, C) = (F, T, F) — exactly one falsifying assignment, and every other row is a model. So 8 − 1 = 7, and the answer is 7 (GATE DA 2024, Q2) — “most of them,” as the prompt hinted. The recipe generalises: for any disjunction of literals over n variables, count the rows that make every literal false (usually just one) and subtract from 2^n.

Equivalence and entailment — the two identities to memorise

GATE DA 2025’s Q15 asked which equivalences hold, and the single trick was rewriting every implication as a disjunction:

p → q   ≡   ¬p ∨ q

Once everything is in ¬/∧/∨ form, De Morgan and the absorption laws finish the job — no truth tables needed even for 4-variable formulas.

GATE DA 2026’s Q24 asked which statement is equivalent to “X entails Y”, and the answer hinges on this chain:

X ⊨ Y
   ⇔ every model of X is a model of Y
   ⇔ there is no assignment with X true and Y false
   ⇔ X ∧ ¬Y is unsatisfiable
   ⇔ X → Y is valid (a tautology)

Read those four lines twice. Every entailment MCQ in the syllabus is one of them in disguise.

In one breath

Propositional logic builds formulas from atomic true/false variables and the five connectives ¬, ∧, ∨, →, ↔ (with → false in exactly one row and p → q ≡ ¬p ∨ q), and reads every property off the truth table: a model is a satisfying assignment, a formula is satisfiable (≥1 model), valid/tautology (all 2^n are models), or unsatisfiable (none); two formulas are equivalent when they share all models, and X entails Y (X ⊨ Y) exactly when every model of X models Y — equivalently when X ∧ ¬Y is unsatisfiable, i.e. X → Y is valid.

Practice

A question to carry forward

Propositional logic is sharp, but its atom is too coarse. To it, “Socrates is mortal” is one indivisible variable, and “Plato is mortal” is another, wholly unrelated one — the logic cannot see that both ascribe the same property, mortality, to different beings. And so it cannot state the most ordinary kind of fact at all: “every human is mortal.” There is no “every” in a language whose only nouns are opaque true/false blobs.

To capture that, you must crack the atom open — name the objects (Socrates, Plato), name the properties and relations that hold of them (is-human, is-mortal, taller-than), and add words for all and some. Then “all humans are mortal; Socrates is human; therefore Socrates is mortal” becomes a proof a machine can check. Here is the thread onward: what does that richer language look like, what exactly do the quantifiers ∀ (“for all”) and ∃ (“there exists”) mean, and how does flipping their order quietly change everything a sentence says?