192
Digital Electronics
Example 6.2
Simplify AAB + CCDDDDDA + BBBBC + DDDD
Solution
• Let AAB + CCDD = X.
• Then the given expression reduces to XXX.
• Therefore, AAB + CCDDDDDA + BBBBC + DDD = 0.
6.2 Postulates of Boolean Algebra
The following are the important postulates of Boolean algebra:
1. 11 = 1 0 + 0 = 0.
2. 10 = 01 = 0 0 + 1 = 1 + 0 = 1.
3. 00 = 0 1 + 1 = 1.
4. 1 = 0 and 0 = 1.
Many theorems of Boolean algebra are based on these postulates, which can be used to simplify
Boolean expressions. These theorems are discussed in the next section.
6.3 Theorems of Boolean Algebra
The theorems of Boolean algebra can be used to simplify many a complex Boolean expression and
also to transform the given expression into a more useful and meaningful equivalent expression. The
theorems are presented as pairs, with the two theorems in a given pair being the dual of each other.
These theorems can be very easily verified by the method of ‘perfect induction’. According to this
method, the validity of the expression is tested for all possible combinations of values of the variables
involved. Also, since the validity of the theorem is based on its being true for all possible combinations
of values of variables, there is no reason why a variable cannot be replaced with its complement, or
vice versa, without disturbing the validity. Another important point is that, if a given expression is
valid, its dual will also be valid. Therefore, in all the discussion to follow in this section, only one of
the theorems in a given pair will be illustrated with a proof. Proof of the other being its dual is implied.
6.3.1 Theorem 1 (Operations with ‘0’ and ‘1’)
(a) 0X = 0 and (b) 1 + X = 1
(6.11)
where X is not necessarily a single variable – it could be a term or even a large expression.
Theorem 1(a) can be proved by substituting all possible values of X, that is, 0 and 1, into the given
expression and checking whether the LHS equals the RHS:
• For X = 0, LHS = 0.X = 0.0 = 0 = RHS.
• For X = 1, LHS = 0.1 = 0 = RHS.
Thus, 0.X = 0 irrespective of the value of X, and hence the proof.
Theorem 1(b) can be proved in a similar manner. In general, according to theorem 1, 0.(Boolean
expression) = 0 and 1 + (Boolean expression) = 1. For example, 0AAB + BBC + CCDD = 0 and 1 +
AAB + BBC + CCDD = 1, where A, B and C are Boolean variables.
Digital Electronics
Example 6.2
Simplify AAB + CCDDDDDA + BBBBC + DDDD
Solution
• Let AAB + CCDD = X.
• Then the given expression reduces to XXX.
• Therefore, AAB + CCDDDDDA + BBBBC + DDD = 0.
6.2 Postulates of Boolean Algebra
The following are the important postulates of Boolean algebra:
1. 11 = 1 0 + 0 = 0.
2. 10 = 01 = 0 0 + 1 = 1 + 0 = 1.
3. 00 = 0 1 + 1 = 1.
4. 1 = 0 and 0 = 1.
Many theorems of Boolean algebra are based on these postulates, which can be used to simplify
Boolean expressions. These theorems are discussed in the next section.
6.3 Theorems of Boolean Algebra
The theorems of Boolean algebra can be used to simplify many a complex Boolean expression and
also to transform the given expression into a more useful and meaningful equivalent expression. The
theorems are presented as pairs, with the two theorems in a given pair being the dual of each other.
These theorems can be very easily verified by the method of ‘perfect induction’. According to this
method, the validity of the expression is tested for all possible combinations of values of the variables
involved. Also, since the validity of the theorem is based on its being true for all possible combinations
of values of variables, there is no reason why a variable cannot be replaced with its complement, or
vice versa, without disturbing the validity. Another important point is that, if a given expression is
valid, its dual will also be valid. Therefore, in all the discussion to follow in this section, only one of
the theorems in a given pair will be illustrated with a proof. Proof of the other being its dual is implied.
6.3.1 Theorem 1 (Operations with ‘0’ and ‘1’)
(a) 0X = 0 and (b) 1 + X = 1
(6.11)
where X is not necessarily a single variable – it could be a term or even a large expression.
Theorem 1(a) can be proved by substituting all possible values of X, that is, 0 and 1, into the given
expression and checking whether the LHS equals the RHS:
• For X = 0, LHS = 0.X = 0.0 = 0 = RHS.
• For X = 1, LHS = 0.1 = 0 = RHS.
Thus, 0.X = 0 irrespective of the value of X, and hence the proof.
Theorem 1(b) can be proved in a similar manner. In general, according to theorem 1, 0.(Boolean
expression) = 0 and 1 + (Boolean expression) = 1. For example, 0AAB + BBC + CCDD = 0 and 1 +
AAB + BBC + CCDD = 1, where A, B and C are Boolean variables.