Question

In Exercises 35–42, use the laws in Definition \(1\) to show that the stated properties hold in every Boolean algebra.

39. Show that De Morgan's laws hold in a Boolean algebra.

That is, show that for all \(x\) and \(y\), \(\overline {(x \vee y)} {\bf{ = }}\bar x \wedge \bar y\) and \(\overline {(x \wedge y)} = \bar x \vee \bar y\).

Short answer

The given \(\overline {\left( {x \vee y} \right)} = \bar x \wedge \bar y\) and \(\overline {\left( {x \wedge y} \right)} = \bar x \vee \bar y\) is proved.

Step-by-step solution

Definition

Identity laws

\(\begin{array}{c}x \vee 0 = x\\x \wedge 1 = x\end{array}\)

Complement laws

\(\begin{array}{c}x \vee \bar x = 1\\x \wedge \bar x = 0\end{array}\)

Associative laws

\(\begin{array}{c}x \vee \left( {y \vee z} \right) = \left( {x \vee y} \right) \vee z\\x \wedge \left( {y \wedge z} \right) = \left( {x \wedge y} \right) \wedge z\end{array}\)

Distributive laws

\(\begin{array}{c}x \vee \left( {y \wedge z} \right) = \left( {x \vee y} \right) \wedge \left( {x \vee z} \right)\\x \wedge \left( {y \vee z} \right) = \left( {x \wedge y} \right) \vee \left( {x \wedge z} \right)\end{array}\)

De Morgan's laws

\(\begin{array}{c}\overline {\left( {x \vee y} \right)} = \bar x \wedge \bar y\\\overline {\left( {x \wedge y} \right)} = \bar x \vee \bar y\end{array}\)

 Step 2: Using the associative, commutative, complement, distributive and identity laws

To proof: \(\overline {\left( {x \vee y} \right)} = \bar x \wedge \bar y\)

PROOF

\(y\)is the complement of \(x\)if and only if \(x \vee y = 1\)and\(x \wedge y = 0\).

Note: The complement is also unique, which was proven in one of the previous solutions.

Thus, you need to show that \(\bar x \wedge \bar y\) is the complement of \(x \vee y\).

\(\begin{aligned}\left( {x \vee y} \right) \vee \left( {\bar x \wedge \bar y} \right) &=& \left( {y \vee x} \right) \vee \left( {\bar x \wedge \bar y} \right)\\& =& y \vee \left( {x \vee \left( {\bar x \wedge \bar y} \right)} \right)\\&=& y \vee \left( {\left( {x \vee \bar x} \right) \wedge \left( {x \vee \bar y} \right)} \right)\\ &=& y \vee \left( {1 \wedge \left( {x \vee \bar y} \right)} \right)\end{aligned}\)

\(\begin{aligned}&=& y \vee \left( {\left( {x \vee \bar y} \right) \wedge 1} \right)\\ &=& y \vee \left( {x \vee \bar y} \right)\\&=& y \vee \left( {\bar y \vee x} \right)\\&=& \left( {y \vee \bar y} \right) \vee x\end{aligned}\)

\(\begin{aligned}&=& 1 \vee x\\&=& x \vee 1\\& = &1\end{aligned}\)

Using the associative, commutative, complement, distributive and identity laws

\(\begin{aligned}\left( {x \vee y} \right) \wedge \left( {\bar x \wedge \bar y} \right) &=& \left( {\left( {x \vee y} \right) \wedge \bar x} \right) \wedge \bar y\\& =& \left( {\left( {x \wedge \bar x} \right) \vee \left( {y \wedge \bar x} \right)} \right) \wedge \bar y\\ &=& \left( {0 \vee \left( {y \wedge \bar x} \right)} \right) \wedge \bar y\\& =& \left( {\left( {y \wedge \bar x} \right) \vee 0} \right) \wedge \bar y\end{aligned}\)

\(\begin{aligned} &=& \left( {y \wedge \bar x} \right) \wedge \bar y\\ &=& \left( {\bar x \wedge y} \right) \wedge \bar y\\ &=& \bar x \wedge \left( {y \wedge \bar y} \right)\\ &=& \bar x \wedge 0\\ &=& 0\end{aligned}\)

Thus \(\bar x \wedge \bar y\) is the (unique) complement of \(x \vee y\).

Therefore, it gets \(\overline {(x \vee y)} {\bf{ = }}\bar x \wedge \bar y\)

Step 4:Using the associative, commutative, complement, distributive and identity laws

To proof: \(\overline {\left( {x \wedge y} \right)} = \bar x \vee \bar y\)

PROOF

\(y\)is the complement of \(x\)if and only if \(x \vee y = 1\)and\(x \wedge y = 0\). Note: The complement is also unique, which was proven in one of the previous solutions.

Thus, you need to show that \(\bar x \vee \bar y\) is the complement of \(x \wedge y\).

\(\begin{aligned}\left( {x \wedge y} \right) \wedge \left( {\bar x \vee \bar y} \right) &=&\left( {y \wedge x} \right) \wedge \left( {\bar x \vee \bar y} \right)\\ &=& y \wedge \left( {x \wedge \left( {\bar x \vee \bar y} \right)} \right)\\ &=& y \wedge \left( {\left( {x \wedge \bar x} \right) \vee \left( {x \wedge \bar y} \right)} \right)\\ &=& y \wedge \left( {0 \vee \left( {x \wedge \bar y} \right)} \right)\end{aligned}\)

\(\begin{aligned} &=& y \wedge \left( {\left( {x \wedge \bar y} \right) \vee 0} \right)\\ &=& y \wedge \left( {x \wedge \bar y} \right)\\ &=& y \wedge \left( {\bar y \wedge x} \right)\\ &=&\left( {y \wedge \bar y} \right) \wedge x\end{aligned}\)

\(\begin{aligned} &=&0 \wedge x\\ &=& x \wedge 0\\ = 0\end{aligned}\)

Using the associative, commutative, complement, distributive and identity laws

Using the associative, commutative, complement, distributive and identity laws

\(\begin{aligned}\left( {x \wedge y} \right) \vee \left( {\bar x \vee \bar y} \right) &=& \left( {\left( {x \wedge y} \right) \vee \bar x} \right) \vee \bar y\\ &=& \left( {\left( {x \vee \bar x} \right) \wedge \left( {y \vee \bar x} \right)} \right) \vee \bar y\\ &=& \left( {1 \wedge \left( {y \vee \bar x} \right)} \right) \vee \bar y\\ &=& \left( {\left( {y \vee \bar x} \right) \wedge 1} \right) \vee \bar y\end{aligned}\)

\(\begin{aligned} &=& \left( {y \vee \bar x} \right) \vee \bar y\\&=& \left( {\bar x \vee y} \right) \vee \bar y\\ &=& \bar x \vee \left( {y \vee \bar y} \right)\\ &=& \bar x \vee 1\\ &=& 1\end{aligned}\)

Thus,\(\bar x \vee \bar y\) is the (unique) complement of \(x \wedge y\).

Therefore, it gets \(\overline {(x \wedge y)} {\bf{ = }}\bar x \vee \bar y\)