State and prove De Morgan's theorem for Boolean Algebra. Simplify a given Boolean expression.

🔥 Asked 8/10 papers📅 Last: Jun 2023📚 Boolean Algebra

Jun 2019Dec 2019Jun 2020Dec 2020Dec 2021Jun 2022Dec 2022Jun 2023

Model Answer

Boolean Algebra is an algebraic structure dealing with binary variables (0 and 1) and logical operations (AND, OR, NOT). It was developed by George Boole and is fundamental to digital circuit design.

1De Morgan's Theorems

De Morgan's theorems provide a way to simplify Boolean expressions involving complement of OR and AND operations.

2Statement of De Morgan's Theorems

Theorem 1

The complement of the OR of two variables equals the AND of their complements: (A + B)' = A' · B'

Theorem 2

The complement of the AND of two variables equals the OR of their complements: (A · B)' = A' + B'

3Proof of Theorem 1: (A + B)' = A'B'

To prove two Boolean expressions are equal, we verify they produce identical truth table outputs.

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

Since columns (A+B)' and A'·B' are identical, the theorem is proved. ✓

4Example Simplification

Simplify: F = AB + A'B + AB' Step 1: F = B(A + A') + AB' [Factor out B] Step 2: F = B(1) + AB' [Complement Law: A + A' = 1] Step 3: F = B + AB' [Identity Law: B·1 = B] Step 4: F = B + A [Absorption: B + AB' = B + A] Therefore F = A + B ✓

5Key Boolean Laws (for simplification)

Identity Law

A + 0 = A and A · 1 = A

Null Law

A + 1 = 1 and A · 0 = 0

Complement Law

A + A' = 1 and A · A' = 0

Idempotent Law

A + A = A and A · A = A

Involution Law

(A')' = A

Absorption Law

A + AB = A and A(A+B) = A

Distributive Law

A(B+C) = AB + AC and A + BC = (A+B)(A+C)

Key Formulas

(A + B)' = A' · B' (De Morgan's 1)

(A · B)' = A' + B' (De Morgan's 2)

A + A' = 1 (Complement)

A · A' = 0 (Complement)

A + AB = A (Absorption)

💡 Exam Tip

Always prove De Morgan's theorem with a truth table — it's the clearest method and gets full marks. For simplification questions, write each step on a new line and mention the law used (e.g., 'By Complement Law'). Examiners award marks per step.

Resources

▶️

Boolean Algebra Laws & Simplification — Neso Academy

Clear explanation of all laws with examples

🔗

De Morgan's Theorem Proof — TutorialsPoint