Discrete Mathematics

Duality

Duality: The identities in Table 5 come in pairs (except for the law of the double complement and the unit and zero properties). To explain the relationship between the two identities in each pair we use the concept of a dual. The dual of a Boolean expression is obtained by interchanging Boolean sums and Boolean products and interchanging 0s and 1s.

EXAMPLE 1 Find the duals of x(y 0) and x · 1 (y z).
Solution: Interchanging · signs and signs and interchanging 0s and 1s in these expressions produces their duals. The duals are x (y · 1) and (x 0)(yz), respectively.

The dual of a Boolean function F represented by a Boolean expression is the function represented by the dual of this expression. This dual function, denoted byFd , does not depend on the particular Boolean expression used to representF. An identity between functions represented by Boolean expressions remains valid when the duals of both sides of the identity are taken. (See Exercise 30 for the reason why this is true.) This result, called the duality principle, is useful for obtaining new identities.

EXAMPLE 2 Construct an identity from the absorption law x(x y) = x by taking duals.
Solution: Taking the duals of both sides of this identity produces the identity x xy = x, which is also called an absorption law and is shown in Table 5.