Logical Equivalences

Tom Kelliher, MA 190

Feb. 1, 2008

$p \wedge T \equiv p$	Identity laws
$p \vee F \equiv p$
$p \vee T \equiv T$	Domination laws
$p \wedge F \equiv F$
$p \vee p \equiv p$	Idempotent laws
$p \wedge p \equiv p$
$\neg(\neg p) \equiv p$	Double negation law
$p \vee q \equiv q \vee p$	Commutative laws
$p \wedge q \equiv q \wedge p$
$p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$	Distributive laws
$p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$
$\neg(p \wedge q) \equiv \neg p \vee \neg q$	De Morgan's laws
$\neg(p \vee q) \equiv \neg p \wedge \neg q$
$p \vee (p \wedge q) \equiv p$	Absorption laws
$p \wedge (p \vee q) \equiv p$
$p \vee \neg p \equiv T$	Negation laws
$p \wedge \neg p \equiv F$

$p \rightarrow q \equiv \neg p \vee q$	$p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p)$
$p \rightarrow q \equiv \neg q \rightarrow \neg p$	$p \leftrightarrow q \equiv \neg p \leftrightarrow \neg q$
$p \vee q \equiv \neg p \rightarrow q$	$p \leftrightarrow q \equiv (p \wedge q) \vee (\neg p \wedge \neg q)$
$p \wedge q \equiv \neg(p \rightarrow \neg q)$	$\neg(p \leftrightarrow q) \equiv p \leftrightarrow \neg q$
$\neg(p \rightarrow q) \equiv p \wedge \neg q$
$(p \rightarrow q) \wedge (p \rightarrow r) \equiv p \rightarrow (q \wedge r)$
$(p \rightarrow r) \wedge (q \rightarrow r) \equiv (p \vee q) \rightarrow r)$
$(p \rightarrow q) \vee (p \rightarrow r) \equiv p \rightarrow (q \vee r)$
$(p \rightarrow r) \vee (q \rightarrow r) \equiv (p \wedge q) \rightarrow r$

Exercises

1. (5) Verify using a truth table: $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$.

2. (7 a, c) Use De Morgan's laws to find the negation of
   1. Jan is rich and happy.
   2. Mei walks or takes the bus to class.

3. (9 a, d) Use truth tables to show that the following are tautologies
   1. $(p \wedge q) \rightarrow p$
   2. $(p \wedge q) \rightarrow (p \rightarrow q)$

4. (11 a, d) Use a series of logical equivalences to show that the previous two compound propositions are tautologies.

5. (15) Determine whether $(\neg q \wedge (p \rightarrow q)) \rightarrow \neg p$ is a tautology.

6. (23, 25) Show that the following compound propositions are logically equivalent by showing that both sides are true, or that both sides are false, for exactly the same combinations of truth values of the propositional variables in these expressions (whichever is easier).
   1. $(p \rightarrow r) \wedge (q \rightarrow r)$ and $(p \vee q) \rightarrow r$.
   2. $(p \rightarrow r) \vee (q \rightarrow r)$ and $(p \wedge q) \rightarrow r$.

Tom Kelliher