SKEDSOFT

Discrete Mathematics

Identities of Boolean Algebra: There are many identities in Boolean algebra. The most important of these are displayed in Table 5. These identities are particularly useful in simplifying the design of circuits. Each of the identities in Table 5 can be proved using a table.We will prove one of the distributive laws in this way in Example 8. The proofs of the remaining properties are left as exercises for the reader.

EXAMPLE 8 Show that the distributive law x(y z) = xy xz is valid.
Solution: The verification of this identity is shown in Table 6. The identity holds because the last two columns of the table agree.

The reader should compare the Boolean identities in Table 5 to the logical equivalences in Table 6. All are special cases of the same set of identities in a more abstract structure. Each collection of identities can be obtained by making the appropriate translations. For example, we can transform each of the identities in Table 5 into a logical equivalence by changing each Boolean variable into a propositional variable, each 0 into a F, each 1 into a T, each Boolean sum into a disjunction, each Boolean product into a conjunction, and each complementation into a negation, as we illustrate in Example 9.

EXAMPLE 9 Translate the distributive law x yz = (x y)(x z) in Table 5 into a logical equivalence.
Solution: To translate a Boolean identity into a logical equivalence, we change each Boolean variable into a propositional variable. Here we will change the Boolean variables x, y, and z into the propositional variables p, q, and r.Next, we change each Boolean sum into a disjunction and each Boolean product into a conjunction. (Note that 0 and 1 do not appear in this identity and

complementation also does not appear.) This transforms the Boolean identity into the logical equivalence

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r).

This logical equivalence is one of the distributive laws for propositional logic in Table 6