We now discuss a few basic laws used in logic simplification. Each of these basic laws is stated along with its complementary law. It may be seen that these laws can be proved using either truth tables or the basic rules given above.
2.16.1 Idempotent Laws
Idempotent laws state that :
x + x = x (2.14a)
x × x = x (2.14b)
The word idempotent (same power) was coined by the American professor of computer science Benjamin C. Pierce. It was derived from the words idem (same) and potent (power). Proofs of the relations stated above are given in Table 2.10. Inspection of columns 3 and 4 of Table 2.10 reveals that the summation x + x and the product xx results in x itself.
Table 2.10 Truth table proving Eqs. (2.14a) and (2.14b)
Table 2.10 Truth table proving Eqs. (2.14a) and (2.14b)
x | x | x + x = x | x× x = x |
0 1 | 0 1 | 0 1 | 0 1 |
2.16.2 Absorption Laws
Let x and y be Boolean variables. Then, absorption laws state that:
x + xy = x (2.15a)
x(x + y) = y (2.15b)
Proof of absorption laws using truth table: As stated above, these laws can be proved by using truth tables, or otherwise. Proof of the first of the two absorption laws (i.e., x + x y = x) is given in Table 2.11. Similar steps can be used to prove the remaining relations. The first and last columns of Table 2.11 agree showing the validity of the proof. Here, the variable y is absorbed by the variable x, and hence the name absorption law.
Table 2.11 Truth table to prove x + xy = x
x | Y | x y | x + x y |
0 0 1 1 | 0 1 0 1 | 0 0 0 1 | 0 0 1 1 |
Proof of Absorption law using algebraic method: We can prove the first of the absorption laws by using basic algebra also. For this, we write the LHS of the given equation:
LHS = x + x y = x (1 + y) = x∙1 = x = RHS
where we have used the basic rule 1 + y = 1. It can be seen that this proof is comparatively faster. However, it may be simpler and faster only for equations containing a smaller number of variables.
Proof of the complement of the absorption law: LHS of Eq. (2.15b) is given by
LHS = x (x + y) = x + x y = x(1 + y) = x = RHS
where for proving the law, we have used two basic relations, viz., x x = x, and 1 + y = 1.
2.16.3 Laws Related to Absorption Laws
There are a few other laws associated with the absorption law. These are discussed below.
(a) Subsidiary 1: This law states that
x + x′y = x + y (2.16a)
Proof: The LHS of the given expression may be written in the form:
LHS = x+x′y = x(1+y)+ x′y = x+xy+ x′y = x+y(x+x′) = x + y = RHS
where we have introduced the term 1 + y = 1 into the LHS part of the equation for the simplification.
(b) Subsidiary 2 (Complementary of law a): This law states that:
x(x′ + y) = xy (2.16b)
Proof: The LHS of the given expression may be written in the form:
LHS = x(x′ + y) = xx′ + xy = xy = RHS
(c) Subsidiary 3: This law states that
x′ + xy = x′ + y (2.17a)
Proof: The LHS of the given expression may be written in the form:
LHS = x′ + xy = x′(1+y)+ xy = x′+x′y + xy = x′+y(1+x) = x′ + y = RHS
(d) Subsidiary 4 (Complementary of law c): This law states that
x′(x+y) = x′y (2.17b)
Proof: The LHS of the given expression may be written in the form:
LHS = x′(x+y) = x′x + x′y = x′y = RHS
2.16.4 Commutative Laws
Commutative laws state that:
x + y = y + x (2.18a)
x y = y x (2.18b)
2.16.5 Associative Laws
Associative laws state that:
x + (y + z) = (x + y) + z (2.19a)
x(y z) = (x y)z (2.19b)
2.16.6 Distributive Laws
Distributive laws state that:
x(y + z) = x y + x z (2.20a)
x + yz = (x + y) (x +z) (2.20b)
The second law given by Eq. (2.20b), viz., x + y z = (x + y)(x +z) is not found to conventional algebra and is special of Boolean algebra alone.