next up previous contents
Next: Tautologies and contradictions Up: Logical connectors Previous: Distributivity   Contents

De Morgan Laws

Proposition 2.3.9   Let $ p$ and $ q$ be two propositions. Then the two following properties hold:
(i)
$ \overline{p \vee q}$ is logically equivalent to $ \Bar{p} \wedge
\Bar{q}$.
(ii)
$ \overline{p \wedge q}$ is logically equivalent to $ \Bar{p} \vee
\Bar{q}$.

Proof. We use truth tables.
(i)
$ p$ $ q$ $ p \vee q$ $ \overline{p \vee q}$ $ \overline{p}$ $ \overline{q}$ $ \overline{p} \wedge \overline{q}$
T T T F F F F
T F T F F T F
F T T F T F F
F F F T T T T
(ii)
$ p$ $ q$ $ p \wedge q$ $ \overline{p \wedge q}$ $ \overline{p}$ $ \overline{q}$ $ \overline{p} \vee \overline{q}$
T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T
In each truth table, the fourth column is identical to the last one, therefore the claim is true. $ \qedsymbol$

Example 2.3.10       


next up previous contents
Next: Tautologies and contradictions Up: Logical connectors Previous: Distributivity   Contents
root 2002-06-10