What are Boolean Theorems?
By BYJU'S Exam Prep
Updated on: September 25th, 2023
Boolean Theorems: Boolean algebra is a mathematical logic system developed by mathematician George Boole in 1854. Boolean algebra is distinct from traditional algebra and the binary number system. The Boolean theorems have the capability of performing binary and logical operations.
The Boolean theorems are applied to simplify various logical formulations. In a digital design, the truth table generates a unique logical statement. Designing gets easier when this logical phrase is reduced. Boolean theorems are mostly utilized in digital electronics, set theory, and digital electronics. Here, we will see various Boolean theorems in detail along with various types of theorems in it.
Formulas for GATE Computer Science Engineering – Digital Logic
Table of content
What is Boolean Algebra?
Before knowing about the Boolean theorems let us know the Boolean algebra in computer science. Boolean algebra is another name for switching algebra. Boolean algebra in computer science is employed in the analysis of digital gates and circuits. A mathematical operation on binary numbers, i.e. ‘0’ and ‘1’, is logical.
Basic operators in Boolean Algebra theorems include AND, OR, and NOT, among others. ‘.’ for AND and ‘+’ for OR are used to express operations. Operations can be done on variables represented by capital letters, such as ‘A,’ ‘B,’ and so on.
What are Boolean Theorems?
Theorems that modify the shape of a Boolean expression are known as Boolean theorems. These theorems are sometimes used to reduce the terms of the expression, and sometimes they are only used to shift the expression from one form to another.
The different types of Boolean theorems are as follows:
- De Morgan’s Theorem
- Transposition Theorem
- Redundancy Theorem
- Duality Theorem
- Complementary Theorem
GATE Computer Science Engineering Revision Sheet and Formulae
De Morgan’s Theorem
One of the most important Boolean theorems is Demorgan’s Theorem which encapsulates two of the most significant Boolean algebra theorem rules. Suppose there are two Boolean variables A and B for these variables Demorgan’s theorem is as follows:
(A . B)’ = A’ + B’
As a result, the complement of variables product equals the total of its separate complements.
(A + B)’ = A’ . B’
Thus, the total of variables’ complements is equal to the product of their individual complements.
Transposition Theorem
Suppose there are three variables X, Y, and Z. According to the transposition theorem,
XY + X’Z = (X + Z) (X’ + Y)
The proof of the transposition theorem is as follows:
RHS
= (X + Z) (X’ + Y)
= XX’ + X’Z + XY + ZY
= 0 + X’Z + XY + YZ
= X’Z + XY + YZ(X + X’)
= XY + XYZ + X’Z + X’YZ
= XY + X’Z
= LHS
Redundancy Theorem
Another one of the Boolean theorems is the redundancy theorem which is used to remove redundant terms. When a variable is related to one variable and its complement with another variable, and the following term is created by the remaining variables, the term becomes redundant.
Suppose there are three variables A, B, and C. The expression for the redundant theorem is as follows:
O = AB + BC + A’C
Duality Theorem
According to the Duality Principle, he Dual of the expression may be accomplished by replacing the AND operator with the OR operator, as well as replacing the binary variables, such as replacing 1 with 0 and 0 with 1.
The Duality principle, also known as De Morgan Duality, argues that interchanging Duals pairs in Boolean algebra results in the same output of the equation. For example, the Dual of A(B+C) is as follows:
= A+(B.C)
= (A+B)(A+C)
Complementary Theorem
In order to get complement expression using the complementary theorem, we will have to follow certain rules that are as follows:
- Replace each OR sign with an AND sign and vice versa.
- Complement any 0s or 1s in the expression.
- Individual literals should be complemented.
For example, the Complement expression using the complementary theorem of A(B+C) is as follows:
= A’+(B’.C’)
= (A’+B’)(A’+C’)
Important Topics for Gate Exam | |
Brittle Material | Capacitors in Parallel |
Capacitors in Series | Carnot Cycle |
Cement Test | Clamping Circuit |
Clipping Circuit | CMOS Fabrication |
CMOS Converter | Column Base |