Practical No. 6

Title: To State and Prove De Morgan’s Theorem

Aim

To understand and mathematically prove De Morgan’s Two Theorems using truth tables, demonstrating their fundamental role in Boolean Algebra and digital logic simplification.

Introduction

De Morgan’s Theorems are two fundamental rules in Boolean Algebra that are essential for the simplification of Boolean expressions and for understanding relationships between logical operations.

·         Theorems: Convert expressions involving AND and OR gates with inversions into equivalent expressions with different gate combinations.

·         They define how the negation of a conjunction relates to the disjunction of negations, and vice versa.

·         Mastery of these theorems is essential for designing and optimizing digital circuits (Chapter 2.5.2 Theorems of Boolean Algebra).

Procedure / Example

De Morgan’s First Theorem

Statement: The complement of a sum equals the product of the complements.
Logical Expression: ¬(A + B) = ¬A · ¬B

Truth Table Proof:

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

Observation: Columns for ¬(A + B) and ¬A · ¬B are identical.
Conclusion: De Morgan’s First Theorem is proven.

De Morgan’s Second Theorem

Statement: The complement of a product equals the sum of the complements.
Logical Expression: ¬(A · B) = ¬A + ¬B

Truth Table Proof:

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

Observation: Columns for ¬(A · B) and ¬A + ¬B are identical.
Conclusion: De Morgan’s Second Theorem is proven.

Result / Conclusion

This practical successfully stated and proved both De Morgan’s Theorems using truth tables. These theorems are fundamental for understanding relationships between logical operations and are indispensable for simplifying Boolean expressions and designing efficient digital circuits.