Question

Exercises 14-23 deal with the Boolean algebra \(\left\{ {{\bf{0,1}}} \right\}\) with addition,multiplication, and complement defined at the beginning of this section. In each case, use a table as in Example \(8\).

21. Verify De Morgan's laws.

Short answer

The given De Morgan’s law \(\overline {(xy)} = \bar x + \bar y,\overline {(x + y)} = \bar x\bar y\) is verified.

Step-by-step solution

Definition

The complement of an element:\({\bf{\bar 0 = 1}}\)and\({\bf{\bar 1 = }}0\)

The Boolean sum + or\(OR\)is 1 if either term is 1.

The Boolean product\( \cdot \)or\(AND\)is 1 if both terms are 1.

De Morgan's laws

\(\begin{array}{c}\overline {{\bf{(xy)}}} {\bf{ = \bar x + \bar y}}\\\overline {{\bf{(x + y)}}} {\bf{ = \bar x\bar y}}\end{array}\)

Using the De Morgan’s law

x and y can both take on the value of 0 or 1.

\(\begin{array}{*{20}{r}}x&y&{\bar x}&{\bar y}&{xy}&{\overline {(xy)} }&{\bar x + \bar y}\\0&0&1&1&0&1&1\\0&1&1&0&0&1&1\\1&0&0&1&0&1&1\\1&1&0&0&1&0&0\end{array}\)

The last two columns of the table are identical.

Therefore, you get\(\overline {(xy)} = \bar x + \bar y\).

Using the De Morgan’s law

\(\begin{array}{*{20}{r}}x&{ y}&{ \bar x}&{ \bar y}&{ x + y}&{ \overline {(x + y)} }&{ \bar x\bar y}\\0&0&1&1&0&1&1\\0&1&1&0&1&0&0\\1&0&0&1&1&0&0\\1&1&0&0&1&0&0\end{array}\)

The last two columns of the table are identical.

Therefore, you get\(\overline {(x + y)} = \bar x\bar y\).