3.1.7
Boolean algebra true/false ki algebra hai (1 aur 0). Jaise ordinary algebra mein aap
a + b = b + a logic expressions
ko rearrange aur regroup karne dete hain bina unka computation badle. Ye teen laws —
commutative, associative, distributive — "furniture move karne" ke rules hain: ye ek bekar-sa
circuit leke usse ek saste circuit mein badal dete hain jo bilkul wahi kaam karta hai.
WHY care? Kam gates = sasta, fast, aur kam heat produce karne wala hardware. Har
simplification aap karte ho wo physically ek chip se transistors hata deta hai.
A ⋅ B A B AND — output 1 sirf tab jab dono 1 hon.A + B OR — output 1 agar kam se kam ek 1 ho.A NOT — bit ko flip karo.Values sirf ==0 1 2 − 1
Definition AND/OR ke do "operations" jo hum follow karte hainA ⋅ B = min ( A , B ) A + B = max ( A , B )
WHY yeh sach hai: max ( A , B ) = max ( B , A ) min ( A , B ) = min ( B , A )
HOW prove karein — truth table (Derivation from scratch):
A B A + B B + A
0
0
0
0
0
1
1
1
1
0
1
1
1
1
1
1
Columns A + B B + A identical hain → law prove ho gayi. Yahi trick AND ke liye bhi kaam karti hai.
Worked example Ise use karnaSimplify karo B ⋅ A + A ⋅ C
Step: B ⋅ A = A ⋅ B Kyun? Commutative — isse common A
Result: A ⋅ B + A ⋅ C A
Grouping (brackets) matter nahi karti ek hi operation ki chain ke liye.
( A + B ) + C = A + ( B + C ) ( A ⋅ B ) ⋅ C = A ⋅ ( B ⋅ C )
WHY yeh sach hai: max ( max ( A , B ) , C ) = max ( A , B , C ) = max ( A , max ( B , C ))
HOW — truth table ka ek row verify karein:
Lo A = 1 , B = 0 , C = 0
( A + B ) + C = ( 1 + 0 ) + 0 = 1 + 0 = 1 A + ( B + C ) = 1 + ( 0 + 0 ) = 1 + 0 = 1
Worked example Hardware ko kyun fark padta hai3-input OR gate = ek gate. Lekin agar aapke paas sirf 2-input OR gates hain, to associativity
kehti hai aap ise OR(OR(A,B),C) ya OR(A,OR(B,C)) se bana sakte ho — dono ka output
identical hai, to aap jo bhi wiring convenient ho wo chuno. Yeh step kyun? Law guarantee
karta hai ki dono builds logically equal hain, isliye aap layout optimize karne ke liye free ho.
Definition Distributive (do forms!)A ⋅ ( B + C ) = A ⋅ B + A ⋅ C (AND over OR — normal algebra jaisa hi) A + ( B ⋅ C ) = ( A + B ) ⋅ ( A + C ) (OR over AND — yeh Boolean wala "ajeeb" hai)
WHY pehla sach hai (Feynman-style): "A A aur
kam se kam ek B , C A B A C A
HOW — doosra prove karein (jo logon ko confuse karta hai) truth table se:
A B C B ⋅ C A + ( B ⋅ C ) A + B A + C ( A + B ) ( A + C )
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
0
0
1
1
1
1
1
1
1
1
0
0
0
1
1
1
1
1
0
1
0
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
1
1
Columns A + ( B ⋅ C ) ( A + B ) ( A + C ) har row mein match karte hain → law from scratch prove ho gayi.
Worked example Poora simplification chainSimplify karo A ⋅ B + A ⋅ C
A ⋅ B + A ⋅ C = A ⋅ ( B + C ) Kyun? Distributive (ulti direction = factoring).Gate count: LEFT ko 2 AND + 1 OR = 3 gates chahiye. RIGHT ko 1 OR + 1 AND = 2 gates chahiye.
Same truth table, ek gate kam → sasta chip. Yahi poora point hai.
A + ( B ⋅ C ) = ( A + B ) ⋅ C A Kyun sahi lagta hai: Ordinary algebra mein aap sirf ek taraf distribute karte ho, isliye
students ek copy ki aadat copy kar lete hain. Fix: Boolean OR-over-AND mein, A dono
brackets mein aana chahiye: A + B C = ( A + B ) ( A + C ) A = 1 , B = 0 , C = 0 1 ( 1 + 0 ) ⋅ 0 = 0
Common mistake Yeh sochna ki associativity AND aur OR mix karti haiKyun sahi lagta hai: "Grouping matter nahi karti" universal lagti hai. Fix: Associativity
sirf ek hi operator ke andar hold karti hai. ( A + B ) ⋅ C = A + ( B ⋅ C ) distributive law chahiye, associative nahi.
Common mistake Yeh assume karna kiA + B = B + A Kyun sahi lagta hai: Logically dono equal hain. Fix: Logically haan, lekin wire delays
aur layout alag ho sakte hain. Commutativity sirf same output value guarantee karti hai,
identical timing nahi.
Recall Feynman: ek 12-saal ke bachche ko samjhaoSocho do light switches hain. Commutative: Koi fark nahi padta ki aap kaunsa switch "pehla"
bolte ho — switch-A-phir-B ya switch-B-phir-A flip karna same light deta hai. Associative:
Agar teen doston ko SABHON ko agree karna ho (AND) park jaane ke liye, to koi fark nahi padta
ki pehle do decide karein ya baad ke do — phir bhi teeno ko haan kehna padega. Distributive:
"Main cake khaaunga agar (party ho) AND (chocolate OR vanilla ho)" yahi hai jaise "(party aur
chocolate) OR (party aur vanilla)". Same rules, bas do tarah likhe gaye — aur chhota wala choose
karna matlab factory machine ko kam parts se bana sakti hai.
"COMmute = seats badlo, ASsociate = doston ko re-group karo, DIStribute = sabko share karo."
Tricky OR-form ke liye: "OR distribute karta hai aur duplicate karta hai" — akela term
dono brackets mein copy ho jaata hai.
Recall Answers dhako aur unhe zor se bolo
AND ke liye commutative law batao.
Kya ( A ⋅ B ) ⋅ C = A ⋅ ( B ⋅ C )
A + B C A ⋅ B + A ⋅ C
Commutative law (OR form) A + B = B + A
Commutative law (AND form) A ⋅ B = B ⋅ A
Associative law (AND) ( A ⋅ B ) ⋅ C = A ⋅ ( B ⋅ C )
Distributive law (AND over OR) A ( B + C ) = A B + A C
Distributive law (OR over AND) A + B C = ( A + B ) ( A + C )
Why does A + B C = ( A + B ) ( A + C ) ( A + B ) ( A + C ) = A + A C + A B + B C A ⋅ A = A 1 + X = 1 A + B C
Gates saved by factoring A B + A C → A ( B + C ) 3 gates (2 AND + 1 OR) se 2 gates (1 AND + 1 OR) ho jaate hain.
Kya associativity AND aur OR mix karne deti hai? Nahi — yeh sirf same operator ke andar apply hoti hai; operators cross karne ke liye distributive chahiye.
A ⋅ B A + B min ( A , B ) max ( A , B )
A + B C ( A + B ) ⋅ C ( A + B ) ( A + C ) A
Boolean Algebra Identity & Null Laws (upar ke proofs mein A ⋅ A = A 1 + X = 1 De Morgan's Theorems (in laws ke baad simplification ka agla tool)Logic Gates AND OR NOT (⋅ + A Karnaugh Maps (visual method jo distributive factoring automate karta hai)Combinational Circuit Simplification (jahan kam gates = payoff milta hai)
