Simplification of Boolean Expression by Boolean Postulates and Theorems
Boolean algebra is a mathematical framework for analyzing and simplifying digital logic circuits. The goal of Boolean simplification is to reduce a given Boolean expression to its simplest form, which can lead to more efficient logic circuits. Simplification is typically achieved using Boolean postulates (axioms) and Boolean theorems.
Boolean Postulates (Axioms)
These are the basic rules that form the foundation of Boolean algebra. They are used to derive and prove theorems for simplifying Boolean expressions.
-
Identity Law:
- A + 0 = A
- A · 1 = A
This law states that adding zero to a Boolean variable does not change its value, and multiplying a variable by 1 also doesn't change its value.
-
Null Law:
- A + 1 = 1
- A · 0 = 0
This law states that adding 1 to a variable always results in 1, and multiplying a variable by 0 always results in 0.
-
Idempotent Law:
- A + A = A
- A · A = A
This law states that adding or multiplying a variable by itself results in the variable itself.
-
Complement Law:
- A + ¬A = 1
- A · ¬A = 0
This law states that a variable ORed with its complement is always 1, and a variable ANDed with its complement is always 0.
-
Domination Law:
- A + 1 = 1
- A · 0 = 0
This law states that if a variable is ORed with 1, the result is always 1; if a variable is ANDed with 0, the result is always 0.
-
Double Negation Law:
- ¬(¬A) = A
This law states that the double negation of a variable is the variable itself.
-
Commutative Law:
- A + B = B + A
- A · B = B · A
This law states that the order of operands in AND and OR operations does not affect the result.
-
Associative Law:
- (A + B) + C = A + (B + C)
- (A · B) · C = A · (B · C)
This law states that when three or more variables are combined with AND or OR, the grouping of the variables does not change the result.
-
Distributive Law:
- A · (B + C) = (A · B) + (A · C)
- A + (B · C) = (A + B) · (A + C)
This law states that AND distributes over OR, and OR distributes over AND.
Boolean Theorems
Boolean theorems are derived from the postulates, and they are used to simplify Boolean expressions. Some important theorems include:
-
Absorption Law:
- A + (A · B) = A
- A · (A + B) = A
This law states that a term combined with its own conjunction or disjunction simplifies to the term itself.
-
DeMorgan's Theorems (as discussed earlier):
- ¬(A · B) = ¬A + ¬B
- ¬(A + B) = ¬A · ¬B
These theorems help simplify expressions involving negations of AND and OR operations.
-
Involution Law:
- ¬(¬A) = A
This theorem states that the negation of a negation gives the original variable.
-
Redundancy Law:
- A + A · B = A
- A · (A + B) = A
This law states that if a term is combined with its conjunction or disjunction with another term, the result is simply the first term.
-
Consensus Theorem:
- A · B + A · C + B · C = A · B + A · C
This theorem is useful for removing redundant terms from a Boolean expression.
Simplification of Boolean Expressions
To simplify a Boolean expression, you apply these postulates and theorems systematically. Let’s look at an example:
Example 1: Simplify the expression A · (A + B)
-
Apply the Distributive Law:
A⋅(A+B)=A⋅A+A⋅B
-
Apply the Idempotent Law (A · A = A):
A⋅A+A⋅B=A+A⋅B
-
Apply the Absorption Law (A + A · B = A):
A+A⋅B=A
Thus, the simplified expression is A.
Example 2: Simplify the expression A · B + A · C + B · C
- Apply the Consensus Theorem (
A · B + A · C + B · C = A · B + A · C):
A⋅B+A⋅C+B⋅C=A⋅B+A⋅C
Thus, the simplified expression is A · B + A · C.
Example 3: Simplify the expression ¬(A + B) · (A + C)
-
Apply DeMorgan’s Theorem to ¬(A + B):
¬(A+B)=¬A⋅¬B
So the expression becomes:
(¬A⋅¬B)⋅(A+C)
-
Distribute:
(¬A⋅¬B)⋅A+(¬A⋅¬B)⋅C
This simplifies to:
¬A⋅A⋅¬B+¬A⋅¬B⋅C
-
Apply the Complement Law (¬A · A = 0):
0+¬A⋅¬B⋅C=¬A⋅¬B⋅C
Thus, the simplified expression is ¬A · ¬B · C.
Conclusion
Simplifying Boolean expressions is an essential skill in digital logic design and circuit optimization. By applying Boolean postulates and theorems such as the Identity Law, Complement Law, Absorption Law, DeMorgan’s Theorems, and others, complex expressions can be reduced to simpler forms that are easier to implement in hardware, leading to more efficient circuits. By systematically applying these rules, we can ensure that Boolean expressions are in their most optimized form for logic circuit design.