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       

• The negation of the sentence ``This morning, Dany ate an apple and an ornage'' is ``This morning, either Dany did not eat an apple or he did not eat an orange''.
• The negation of the sentence ``Theses seats are made either with leather or with velvet'' is ``These seats are made neither with leather nor with velvet.''