17.4 THEOREMS
Now let us consider the theorems that help in simplifying Boolean functions.
- Idempotency Theorem
The idempotency theorem states that if P is a logical or Boolean variable such that P can take values ‘0’ or ‘1’ then P + P = P. This can be verified from the truth table given in Table 17.8. The dual of the idempotency theorem states that if P is a logical or Boolean variable such that P can take values ‘0’ or ‘1’ then P. P = P. This can be verified from the truth table given in Table 17.9.FIGURE 17.8 The realization of f = PQ + using switches
FIGURE 17.9 The realization of f = PQ + R using logic gates
TABLE 17.9 A verification of the dual of the idempotency theorem
P P P . P 0 0 0 . 0 = 0 1 1 1 . 1 = 1 TABLE 17.10 A verification of the theorem of union
P P + P 0 0+0 = 0 1 1+0 = 1 - Theorem of Union
The theorem of union states that if P is a logical or Boolean variable such that P can take the values ‘0’ or ‘1’, then P + 0 = P. This can be verified from the truth table given in Table 17.10. The dual of the theorem of union states that if P is a logical or Boolean variable such that P can take values ‘0’ or ‘1’, then P + 1 = 1. This can be verified from the truth table given in Table 17.11. - Theorem of Intersection
The theorem of intersection states that if P is a logical or Boolean variable such that P can take values ‘0’ or ‘1’, then P.0 = 0. This can be verified from the truth table given in Table 17.12. The dual of the theorem of intersection states that if P is a logical or Boolean variable such that P can take values ‘0’ or ‘1’ then P.1 = P. This can be verified from the truth table given in Table 17.13. - Complementation Theorem
The complementation theorem states that if P is a logical or Boolean variable such that P can take values ‘0’ or ‘1’ then, P + = 1. This can be verified from the truth table given in Table 17.14. The dual of the complementation theorem states that if P is a logical or Boolean variable such that P can take values’0’ or ‘1’ then, P. = 0. This can be verified from the truth table as shown in Table 17.15.FIGURE 17.10 The realization of the Boolean function f = PQ + (R + S) using switches
FIGURE 17.11 The realization of the Boolean function f = PQ + (R + S) using logic gates
TABLE 17.11 A verification of the dual of the theorem of union
P P + 1 0 0 + 1 = 1 1 1 + 1 = 1 TABLE 17.12 A verification of theorem of intersection
P P.0 0 0.0 = 0 1 1.0 = 0 - Absorption or Redundancy theorem:
Consider the Boolean relation,
f = P + PQ.
The absorption theorem states that if a Boolean function is expressed as the sum of products (SOP), if there is a product that contains all the factors of another product, then it is redundant and can be eliminated (absorbed). Thus, P + PQ = P. The proof of the theorem is discussed below. Consider the Boolean function
f = P + PQ
where, f is the sum of the two products and the Boolean function is expressed as sum of products (SOP). This can be written as:
f = P.1 + PQ
We know from the complementation theorem,
Q + = 1
Therefore,
f = P(Q + ) + PQ = PQ + P + PQ
Using the idempotency theorem, this can be written as (eliminating redundancy):
f = PQ + P, since PQ + PQ = PQ
TABLE 17.13 A verification of the dual of the theorem of intersection
P | P.1 |
---|---|
0 | 0.1 = 0 |
1 | 1.1 = 1 |
TABLE 17.14 A verification of the complementation theorem
P | P + | |
---|---|---|
0 | 1 | 0 + 1 = 0 |
1 | 0 | 1 + 0 = 1 |
TABLE 17.15 A verification of the dual of the complementation theorem
P | P. | |
---|---|---|
0 | 1 | 0.1 = 0 |
1 | 0 | 1.0 = 0 |
f = P(Q + )
Using the complementation theorem, f = P. Similarly consider the Boolean function
f = PS + PS + PQS = PS + PS( + Q) = PS + PS = PS
17.4.1 Dual and Complementary Functions
The dual of a Boolean function is obtained by replacing the OR operation by the AND operation and vice-versa. The complement of a Boolean function can be obtained by replacing the variables by their complements in the dual.
Consider the Boolean function f = P + R
The dual of this Boolean function is f_{d} = P( + R)
And the complementary function is = (Q + )
17.4.2 Boolean Algebraic Properties
In this section, we discuss communative, associative and distributive properties of Boolean functions.
Commutative Properties:
There are two commutative properties — logical addition and logical multiplication. These are briefly discussed below.
- Logical Addition:
Let P and Q be the two logical or Boolean variables such that P and Q can take values ‘0’ or ‘1’. The commutative law over logical addition is then defined as:P + Q = Q + P
This can be verified from the truth table given in Table 17.16.
- Logical Multiplication:
Let P and Q be the two logical or Boolean variables such that P and Q can take values ‘0’ or ‘1’, then the commutative law over logical multiplication is defined as:P.Q = Q.P
This can be verified from the truth table given in Table 17.17.
Associative Properties:
- Let P and Q be the two logical or Boolean variables such that P and Q can take values ‘0’ or ‘1’, then the associative property over logical addition is defined as:
P + (Q + R) = (P + Q) + R
TABLE 17.16 The truth table for the commutative property over logical addition
TABLE 17.17 The truth table for the commutative property over logical multiplication
This can be verified from the truth table given in Table 17.18.
- Let P and Q be the two logical or Boolean variables such that P and Q can take values ‘0’ or ‘1’, then the associative property over the logical multiplication is defined as:
P(QR) = (PQ)R
This can be verified from the truth table given in Table 17.19.
Distributive Property:
Let P and Q be the two logical or Boolean variables such that P and Q can take values ‘0’ or ‘1’ then, the distributive property is defined as:
P(Q + R) = PQ + PR
This can be verified from the truth table given in Table 17.20.
Table 17.21 gives some important properties and identities of Boolean algebra useful in the simplification of the given Boolean expression.
TABLE 17.18 The truth table for the associative property over logical addition
TABLE 17.19 The truth table for the associative property over logical multiplication
TABLE 17.20 The truth table for distributive property
TABLE 17.21 The important Boolean properties and identities
S.No | Property | |
---|---|---|
1 | P + Q = Q + P P.Q = Q.P |
Commutative law |
2 | (P + Q) + R = P + (Q + R) (P.Q).R = P.(Q.R) |
Associative law |
3 | P.(Q + R) = P.Q + P.R P + (Q.R) = (P + Q).(P + R) |
Distributive law |
4 | P + P = P P.P = P |
Idempotency Law |
5 | = P | Negation |
6 | P + (P.Q) = P P.(P + Q) = P |
Redundancy |
7 | 0 + P = P 1 + P = P |
Union |
8 | 1.P = P 0.P = 0 |
Intersection |