Propositional Logic

“If it rains, the picnic is off.” You’ve just stated a logical implication — and you can already feel that “it rains” tells you about “picnic off,” but not the other way around. Propositional logic is the math behind that feeling.

Each simple statement (“it rains”, “picnic is off”) is an atomic proposition — a variable that’s either true or false. You glue them together with five connectives, and the whole apparatus of “what follows from what” reduces to one boring 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 up is →. p → q is false in exactly one row: p true, q false. In all three other rows it’s true — even when p is false (“vacuously true”). Remember 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 such assignments. 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’s 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 simultaneously).

Worked example — a real 2024 question

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 we need

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

That’s the single row (A, B, C) = (F, T, F) — exactly one falsifying assignment. Every other row is a model.

8 − 1 = 7, so the answer is 7. (This is GATE DA 2024, Q2.)

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 of several equivalences S₁ ≡ S₃, etc. hold. 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 for 4-variable formulas.

GATE DA 2026’s Q24 asked which is equivalent to “X entails Y”. 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.

Quick check