Question

Show that you obtain De Morgan's laws for propositions (in Table \(6\) in Section \(1.3\)) when you transform De Morgan's laws for Boolean algebra in Table \(6\) into logical equivalences.

Short answer

You get transformed form of De Morgan’s law for Boolean algebra into logical equivalence \(\neg \left( {p \wedge q} \right) \equiv \neg p \vee \neg q,\neg \left( {p \vee q} \right) \equiv \neg p \wedge \neg q\).

Step-by-step solution

Definition

The complement of an element: \(\bar 0 = 1\) and \(\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 (Boolean algebra)

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

De Morgan's laws (Logical equivalences):

\(\begin{array}{c}\neg \left( {p \wedge q} \right) \equiv \neg p \vee \neg q\\\neg \left( {p \vee q} \right) \equiv \neg p \wedge \neg q\end{array}\)

Using the first De Morgan’s law

\(\overline {\left( {xy} \right)} = \bar x + \bar y\)

Note: \(\overline {\left( {xy} \right)} \) implies \(\overline {\left( {x \cdot y} \right)} \)

\(\overline {\left( {x \cdot y} \right)} = \bar x + \bar y\)

Transform to logical equivalence

Replace \( \cdot \) by \( \wedge \)

Replace \( + \) by \( \vee \)

Replace \( - \) by \(\neg \) (and place \(\neg \) in front of the expression that it relates to)

Replace \( = \) by \( \equiv \)

\(\neg \left( {p \wedge q} \right) \equiv \neg p \vee \neg q\)

Therefore, itobtains the first De Morgan's law for logical equivalences.

Using the second De Morgan’s law

\(\overline {\left( {x + y} \right)} = \bar x\bar y\)

Note: \(\bar x\bar y\) implies \(\bar x \cdot \bar y\).

\(\overline {\left( {x + y} \right)} = \bar x \cdot \bar y\)

Transform to logical equivalence

Replace \( \cdot \) by \( \wedge \)

Replace \( + \) by \( \vee \)

Replace \( - \)by \(\neg \) (and place \(\neg \) in front of the expression that it relates to)

Replace \( = \) by \( \equiv \)

\(\neg (p \vee q) \equiv \neg p \wedge \neg q\)

Therefore, it obtains the second De Morgan's law for logical equivalences