Lesson 3 — Beginner

Propositional Logic & Truth Tables

Logic ka matlab hai sahi aur galat ki kala. Is lesson mein seekhenge proposition kya hota hai, connectives (AND, OR, NOT, IMPLIES) ki truth tables, aur kaise pata chalta hai ki koi statement hamesha true hai (tautology) ya nahi. Ye GATE ka sabse scoring section hai.

⏱ 15 min• Beginner• Set Theory

Proposition kya hai

WHAT

Proposition ek declarative statement hai jo true ya false ho sakta hai (par dono ek saath nahi). "Delhi India ki rajdhani hai" — proposition (true). "Kitna sundar hai!" — proposition nahi (judgment hai).

WHEN

Jab bhi programming mein if (a > 0 && b < 5) likhte ho — wahan do propositions ko AND joda gaya hai. Har condition, har rule, har proof isi par chalta hai.

WHERE

Digital circuits (logic gates), programs (conditions), mathematics (proofs) aur reasoning exams — sab jagah propositional logic backbone hai.

Proposition ko letters se represent karte hain: p, q, r — jaise variables. Inhe jodne ke liye connectives hote hain (AND, OR, NOT, IMPLIES) — inhi ki truth tables exam mein aati hain.

Connectives aur unki truth table

Connective     Symbol    Matlab
Negation        ¬p        ulta (NOT)
Conjunction     p ∧ q     dono true ho (AND)
Disjunction     p ∨ q     kam se kam ek true (OR)
Implication     p → q     agar p toh q (IF-THEN)
Biconditional   p ↔ q     dono same (IF AND ONLY IF)

p q | ¬p | p ∧ q | p ∨ q | p → q | p ↔ q
-----+----+-------+-------+-------+-------
T  T |  F |   T   |   T   |   T   |   T
T  F |  F |   F   |   T   |   F   |   F
F  T |  T |   F   |   T   |   T   |   F
F  F |  T |   F   |   F   |   T   |   T

Sabse important row: p → q sirf EK baar false hota hai — jab p true aur q false. Baaki teeno cases mein true. Ye line GATE mein bar bar aati hai, ratta maar lo.

Implication — converse, contrapositive, inverse

Implication (→) ka confusion sabse zyada hota hai. p → ko chaar naam se jaante hain:

p → q        : original (if p then q)
q → p        : converse (sirf ulta)
¬p → ¬q      : inverse (sirf negation)
¬q → ¬p      : contrapositive (dono ulta)

Truth table p → q:
p=T, q=T → T
p=T, q=F → F    (sirf yahi false case hai)
p=F, q=T → T    (p hi false hai, farak nahi padta)
p=F, q=F → T    (false se kuch bhi follow ho sakta hai)

Key equivalence: (p → q) ≡ (¬p ∨ q)

Contrapositive hamesha equivalent hota hai: p → q ≡ ¬q → ¬p.
Converse equivalent NAHI hota: p → q se q → p nahi nikalta (counterexample: "agar barish hui toh road geeli" — road geeli, zaroori nahi barish se hi ho).
Biconditional p ↔ q: tabhi true jab dono ka value same ho.
¬(p → q) ≡ p ∧ ¬q: implication ka negation — tricky, par poochha jaata hai.

Tautology, contradiction aur equivalence

Tautology       : truth table ka har row TRUE (jaise p ∨ ¬p)
Contradiction   : har row FALSE (jaise p ∧ ¬p)
Contingency     : kuch row true, kuch false

Equivalent statements : dono ki truth table SAME ho

Verify: (p → q) ≡ (¬p ∨ q)
p q | p→q | ¬p | ¬p∨q
T T |  T  |  F |  T
T F |  F  |  F |  F
F T |  T  |  T |  T
F F |  T  |  T |  T   → dono column same ✓

Logical equivalences ka fayda — complicated expression ko chhota kar sakte ho (waise hi jaise boolean algebra mein circuit simplify hota hai — wahi cheez, Module 3 mein detail mein). De Morgan, distributive, associativity — sab logic mein bhi lagti hain.

Pro Tip: Koi bhi expression ho — truth table banao, sab clear. 2 variables = 4 rows, 3 variables = 8 rows. Ek baar table banane ki practice karo, GATE ka objective question 10 second mein solve ho jaayega.

Exercise

Question: p → q kab FALSE hota hai? (p true + q false / p false + q true / hamesha true)

Question: 3 propositional variables ki truth table mein kitne rows honge? Sirf number daalo.

Question: p → q ka contrapositive kya hai? (q → p / ¬q → ¬p / ¬p → ¬q)

Common mistakes

p → q ko ulta samajhna: p → q FALSE sirf tab hai jab p TRUE aur q FALSE. p false ho toh statement automatically true — isliye "false se kuch bhi follow" hota hai.
Converse aur contrapositive mix: Converse = q → p (equivalent nahi), contrapositive = ¬q → ¬p (hamesha equivalent). Dono mein ek NOT ka farak hai.
Tautology aur contradiction ulta: Tautology = hamesha TRUE (har row T), contradiction = hamesha FALSE. Yaad rakho T se Tautology, C se Contradiction.

Desi example: Marks aur party ka implication

Teacher ne kaha: "Agar tum pass ho toh party milegi." Ye p → q hai. Ab socho — pass ho aur party mili (T), pass ho aur party nahi mili (F — wada toota), fail ho aur party phir bhi mili (T — condition hi false thi):

p = tum pass ho,  q = party mili
T T → T   (pass + party)
T F → F   (pass par party nahi — WADE KA TOD)
F T → T   (fail par party — condition false thi)
F F → T   (fail + nahi mili — koi wada toota nahi)

Exam mapping (GATE / CUET)

GATE: truth table + implication equivalence — har saal 1-2Q.
CUET/B.Sc: tautology/contradiction ki definition direct aati hai.
Trap: "p → q false when p is false" — galat, sirf p true + q false mein false.
Trap: "contrapositive of p→q is q→p" — galat, wo converse hai.

Lesson complete?

Propositional logic clear. Agla lesson — Predicates & Quantifiers — mein dekhenge variables wale statements (∀ aur ∃) kaise handle karte hain.