How Boolean Theorems Simplify Complex Algebra Problems
Boolean theorems are the fundamental tools of Boolean Algebra. Boolean theorems are either used to transform the expression or can be used to simplify the terms of the expression. In this article, we will discuss the important boolean postulates and theorems and Laws of Boolean Algebra in detail.
Boolean algebra is based on logical reasoning and hence removes the uncertainty of answers as being based on objectivity rather than subjectivity. Boolean algebra forms the basis of computer programming and binary systems.
Table of Contents
Boolean Laws and Theorems: An Introduction
History of Augustus De Morgan
Basic Theorems of Boolean Algebra
Laws of Boolean Algebra
Limitations of Boolean Theorem
Applications of Boolean Theorem
History of Augustus De Morgan
Augustus De Morgan
Image credit: Wikimedia
Name: Augustus De Morgan
Born: 27 June 1806
Died: 18 March 1871
Field: Mathematics
Nationality: British
Basic Theorems of Boolean Algebra
There are two most important Boolean Theorems also known as De Morgan’s Theorem or Laws.
De Morgan’s First Theorem: According to De Morgan’s First Theorem, the complement of the product of the variables is equal to the sum of the complements of variables separately.
Mathematically:
$(A . B)^{\prime}=A^{\prime}+B^{\prime}$
Truth table for First Theorem for verification of above expression:
Truth Table for First Theorem
From the last two columns, we have: $(A . B)^{\prime}=A^{\prime}+B^{\prime}$.
Hence, De Morgan’s First Theorem is proved.
De Morgan’s Second Theorem: According to De Morgan’s Second Theorem, the complement of the sum of the variables is equal to the product of the complements of the variables separately.
Expressing it mathematically:
$(A+B)^{\prime}=A^{\prime} . B^{\prime}$
Truth table for Second Theorem for verification of above expression:
Truth Table for Second Theorem
From the last two columns, we have: $(A+B)^{\prime}=A^{\prime} . B^{\prime}$
Hence, De Morgan’s second Theorem is proved.
Laws of Boolean Algebra
Commutative Law
Any binary operations satisfying the following expression are commutative operations. Commutative law does not have any effect on the output of a logic circuit.
$A.B=B.A$
$A+B=B+A$
Commutative law
Associative Law
According to this law, the order in which the logic operations are performed is irrelevant as their effect is the same.
A.(B.C)=(A.B).C
(A+B)+C=A+(B+C)
Distributive Law
The operations satisfying the following conditions are said to satisfy this law:
A.(B+C)=(A.B)+(A.C)
AND Law
The laws using the AND operation are called AND laws.
AND Operator
$A .0=0$
$A \cdot 1=A$
$A . A=A$
$A . \bar{A}=0$
OR Law
The laws using the OR operation are called OR laws.
OR Operator
$A+0=A$
$A+1=1$
$A+A=A$
$A+\bar{A}=1$
Inversion Law
The inversion law states that double inversion of a variable will give the original variable.
Limitations of Boolean Theorem
Boolean theorems are not applicable in case of ternary coding which uses base 3 instead of 2 as in binary coding.
Applications of Boolean Theorem
Boolean Theorem is a fundamental tool of Boolean Algebra.
Digital world is completely based on Boolean algebra. Everything works on binary coding.
Electronic systems and electronic circuits wholly work in principle of Boolean Algebra.
Solved Examples
1. Find the complement of $\bar{A} B+C \bar{D}$
Ans: $\overline{\bar{A} B+C \bar{D}}=\overline{(\bar{A} B}) \cdot(\overline{C \bar{D}})$
$\Rightarrow (A+\bar{B}) \cdot(\bar{C}+D)$
2. Find the complement of $A B+C D=0$
Ans: $A B+C D=0$
Taking complement on both sides.
$\Rightarrow \overline{A B+C D}=\bar{O} $
$\Rightarrow \overline{A B} \cdot \overline{C D}=1 $
$\Rightarrow (\bar{A}+\bar{B}) \cdot(\bar{C}+\bar{D})=1$
3. Simplify the Boolean expressions $(X+Y)(X+\bar{Y})(\bar{X}+Z)$
Ans: $(X+Y)(X+\bar{Y})=X X+X \bar{Y}+Y X+Y \bar{Y} $
$\Rightarrow X+X \bar{Y}+Y X+O, \text { as } X X=X \text { and } Y \overline{Y}= 0$
$\Rightarrow X+X(\bar{Y}+Y), \text { as } \bar{Y}+Y=1$
$\Rightarrow X+X \cdot 1, \text { as } X \cdot 1=X $
$\Rightarrow X+X $
$\Rightarrow X$
Now
$(X+Y)(X+\bar{Y})(\bar{X}+Z) $
$\Rightarrow X(\bar{X}+Z) $
$\Rightarrow X \bar{X}+X Z, \text { by distributive law }$
$\Rightarrow 0+X Z $
$\Rightarrow X Z$
Conclusion
In the article, we have discussed the detailed proof of Boolean Theorem and Boolean Laws. In the world of digitisation, everything works in the binary system and hence in Boolean algebra. So, for the growth of human society Boolean Algebra is a great tool and eases our day to day life.
Important Formulas to Remember
$(A . B)^{\prime}=A^{\prime}+B^{\prime}$
$(A + B)^{\prime}=A^{\prime}.B^{\prime}$
Important Points to Remember
Boolean Algebra works on logical reasoning.
Boolean Algebra has two trues either TRUE or FALSE i.e., $0,1$.
List of Related Links
FAQs on Boolean Theorems Explained: Definitions, Proofs & Examples
1. What are Boolean theorems?
Boolean theorems are a set of rules or laws used to simplify and manipulate Boolean expressions. These theorems are fundamental in digital logic design, as they allow for the reduction of complex logical expressions into simpler, equivalent forms. This simplification process is essential for creating more efficient, faster, and cost-effective digital circuits.
2. What is a Boolean expression? Give an example.
A Boolean expression is a logical statement constructed using Boolean variables (which can be TRUE (1) or FALSE (0)) and logical operators like AND, OR, and NOT. The entire expression evaluates to a single Boolean value. For example, the expression F = A.B + C' is a Boolean expression where F is the output, A, B, and C are input variables, '.' represents the AND operator, '+' represents the OR operator, and ' represents the NOT (complement) operator.
3. What are the fundamental laws of Boolean Algebra?
The fundamental laws of Boolean Algebra provide the rules for manipulating and simplifying logical expressions. The most important laws are:
- Commutative Law: A + B = B + A; A . B = B . A
- Associative Law: (A + B) + C = A + (B + C); (A . B) . C = A . (B . C)
- Distributive Law: A . (B + C) = A.B + A.C; A + (B.C) = (A+B).(A+C)
- Identity Law: A + 0 = A; A . 1 = A
- Complement Law: A + A' = 1; A . A' = 0
- De Morgan's Theorems: (A . B)' = A' + B'; (A + B)' = A' . B'
4. How are Boolean theorems applied in real life?
Boolean theorems are the backbone of modern digital electronics. Their primary real-world application is in the design and optimisation of logic circuits found in all digital devices, including computers, smartphones, and microprocessors. By using these theorems to simplify logical functions, engineers can create circuits with fewer components (logic gates). This makes the final product cheaper to manufacture, faster in operation, more energy-efficient, and more reliable.
5. What is the difference between the Duality Principle and De Morgan's theorems?
While both principles are used to transform Boolean expressions, they have distinct functions. The Duality Principle is used to find the 'dual' of an expression by interchanging AND and OR operators, as well as the identity elements '1' and '0', while keeping variables untouched. In contrast, De Morgan's theorems are specifically used to find the complement (inverse) of a Boolean function. This involves swapping AND/OR operators AND complementing every variable or term in the expression.
6. Why is simplifying a Boolean expression important?
Simplifying a Boolean expression is a crucial step in digital circuit design because it directly leads to a more efficient physical circuit. A complex expression requires more logic gates (the physical components performing the operations). A simplified, equivalent expression reduces the number of gates, which provides several key benefits:
- Lower Cost: Fewer components mean the circuit is cheaper to produce.
- Increased Speed: Signals travel through fewer gates, reducing processing delay and making the circuit faster.
- Reduced Power Consumption: Fewer active gates consume less electricity, improving battery life in portable devices.
- Higher Reliability: A simpler circuit has fewer potential points of failure.
7. How can you prove De Morgan's theorems?
De Morgan's theorems, (A + B)' = A'.B' and (A.B)' = A' + B', can be proven algebraically or by using a truth table. The truth table method is the most straightforward way to verify the theorem. To do this, you create a table that lists all possible combinations of inputs for variables A and B (00, 01, 10, 11). Then, you calculate the value of the left-hand side (LHS) and the right-hand side (RHS) of the equation for each combination. If the output columns for the LHS and RHS are identical for all input combinations, the theorem is proven to be true.
