3.1.8
De Morgan's theorems batate hain ki NOT kaise AND ya OR ke across distribute hota hai. Jab tum ek bar (negation) ko kisi group ke andar push karte ho, toh operation flip ho jaata hai: AND ban jaata hai OR, OR ban jaata hai AND, aur har variable ko apna khud ka bar mil jaata hai.
A ⋅ B = A + B A + B = A ⋅ B Kyun important hai: yeh tumhe kisi bhi circuit ko sirf NAND ya sirf NOR form mein convert karne deta hai (sasta hardware), aur Boolean simplification ka yeh sabse kaam ka tool hai.
Definition De Morgan ke do theoremsKisi bhi Boolean variables A B
Theorem 1 (AND ko todo): A ⋅ B = A + B Theorem 2 (OR ko todo): A + B = A ⋅ B
Words mein: "Bar todo, sign badlo." Ek lamba bar do mein split karo, aur neeche ka operator swap karo.
Yeh kitne bhi variables tak generalise hota hai:
A ⋅ B ⋅ C ⋯ = A + B + C + ⋯ A + B + C + ⋯ = A ⋅ B ⋅ C ⋯
Hum inhe blind faith se accept nahi karte. Do Boolean expressions tab equal hote hain jab har input combination ke liye same output dete hain . Isliye hum truth table banate hain.
Theorem 1: prove karo A ⋅ B = A + B
A B A ⋅ B A ⋅ B A B A + B
0
0
0
1 1
1
1
0
1
0
1 1
0
1
1
0
0
1 0
1
1
1
1
1
0 0
0
0
Yeh step kyun? Do bold columns (A ⋅ B A + B har row par match karte hain → expressions provably equal hain. ∎
Theorem 2: prove karo A + B = A ⋅ B
A B A + B A + B A B A ⋅ B
0
0
0
1 1
1
1
0
1
1
0 1
0
0
1
0
1
0 0
1
0
1
1
1
0 0
0
0
Yeh step kyun? Yahan bhi dono bold columns charon rows par match karte hain → equal. ∎
Intuition Feynman "kyun yehhona hi chahiye sach"
A ⋅ B jab dono 1 hon . Toh iska NOT tab 1 hota hai jab kam se kam ek 0 ho — yaani "A B A + B A + B jab dono 0 hon , isliye iska NOT tab 1 hota hai jab "dono 0 hon" = A ⋅ B
Kisi bhi expression ko negate karne ke liye:
Har AND (⋅ + badlo aur har OR ko AND mein.
Har individual variable/term ko negate karo.
Agar constants hain toh 0↔1 bhi swap raho.
Yahi complement procedure hai — De Morgan hi "dualise and complement" ka engine hai.
Worked example Example 1 —A ⋅ B Step 1: Outer bar par Theorem 1 apply karo → A + B Kyun? Outer bar ek AND ke upar hai, isliye hum ise OR mein tod dete hain aur har factor negate karte hain.
Step 2: Double negation A = A A + B Kyun? Do baar negate karne se original value wapas aa jaati hai.
Result: A ⋅ B = A + B
Worked example Example 2 — OR-of-inverts se ek NAND gate banaoClaim: Ek NAND gate (A ⋅ B A ⋅ B = A + B Kyun matter karta hai: yahi "bubble-pushing" trick hai — ek NAND symbol ko OR gate ki tarah redraw kiya ja sakta hai jisme inputs par bubbles hain. Hardware designers sirf NAND gates use karte hain aur sab kuch rebuild karte hain.
Worked example Example 3 — poore 3-variable sum-of-products term ko negate karoF = A ⋅ B + C Step 1: Top-level operator + F = ( A ⋅ B ) ⋅ ( C ) Kyun? OR ko AND mein todo, har term negate karte hue.
Step 2: ( C ) = C A ⋅ B = A + B Kyun? Har piece simplify karo: double-negation, phir inner AND todo.
Result: F = ( A + B ) ⋅ C
A ⋅ B = A ⋅ B Kyun sahi lagta hai: "Bas har variable par bar lagao aur baaki sab chhod do." Yeh symmetric aur neat dikhta hai.
Kyun galat hai: tum operator flip karna bhool gaye. Check karo A = 1 , B = 0 1 ⋅ 0 = 0 = 1 1 ⋅ 0 = 0 ⋅ 1 = 0 Fix: Bar todo, sign badlo. AND ko OR banana hi padega.
Common mistake Galti: bar ko sirf aadha distribute karna →A + B = A + B Kyun sahi lagta hai: tumne pehli cheez negate ki aur wahan ruk gaye.
Fix: bar poore expression ko cover karta hai — andar ke har term ko negate kiya jaata hai, aur operator bhi badalta hai. A + B = A ⋅ B
Common mistake Galti: bar kascope respect na karna
A ⋅ B A ⋅ B bilkul alag hai. Bar ki length batati hai ki woh kis par apply hota hai. Pehle hamesha identify karo ki bar ke neeche top-level operator kaun sa hai.
Recall Answers chhupao aur khud test karo
Q: Do theorems kya hain? → A ⋅ B = A + B A + B = A ⋅ B
Q: 4-word slogan batao → "Break the bar, change the sign."
Q: Inhe rigorously kaise prove karte hain? → identical truth-table columns.
Q: Designers kyun care karte hain? → circuits ko sirf NAND ya sirf NOR mein convert karna (bubble pushing).
Q: A + B A ⋅ B
Recall Feynman: ek 12-saal ke bacche ko samjhaoSocho ek rule hai: "Tum bahar ja sakte ho sirf tab jab not (baarish AND thand) ho." Yeh same hai jaise kaho "Tum bahar ja sakte ho agar baarish nahi OR thand nahi hai." Ek "nahi" do conditions par spread hone se "aur" "ya" mein badal jaata hai. Yahi flip De Morgan's theorem karta hai — yeh bas common sense hai jo symbols mein likhi gayi hai.
"Line todo, sign badlo; har term ko apna chhota sa vine (bar) milta hai."
Lamba bar do chhote bars mein split hota hai, aur neeche ka operator flip ho jaata hai.
Boolean Algebra Laws — De Morgan distributive, commutative, absorption laws ke saath baithta hai.Logic Gates - AND OR NOT — woh physical gates jo negate ho rahe hain.NAND and NOR Universal Gates — De Morgan hi wajah hai ki woh universal hain.Karnaugh Maps — grouping/complement steps justify karne ke liye use hote hain.Complement of a Function — De Morgan complement lene ki general recipe hai.Bubble Pushing — circuit diagrams par De Morgan ki graphical form.
De Morgan Theorem 1 A ⋅ B = A + B
De Morgan Theorem 2 A + B = A ⋅ B
De Morgan ka 4-word slogan Break the bar, change the sign
De Morgan's theorems rigorously kaise prove hote hain Truth table se — dono sides sab input rows ke liye identical outputs deti hain
A ⋅ B A + B
Hardware mein De Morgan's theorems kyun matter karte hain Yeh circuits ko sirf NAND ya sirf NOR gates se rebuild karne dete hain (bubble pushing)
A ⋅ B A ⋅ B
A ⋅ B + C ( A + B ) ⋅ C
N variables ke liye Generalised Theorem 1 A ⋅ B ⋅ C ⋯ = A + B + C + ⋯
NOT distributes over group
Theorem 1: bar A.B = barA + barB
Theorem 2: bar A+B = barA . barB
Break the bar, change the sign
Equal iff same output all rows
Generalises to N variables
Complement / dualise procedure
NAND-only or NOR-only circuits
