1 Logic 1.5 Logical equivalence 1.7 The contrapositive

1.6 Useful logical equivalences

1.6.1 Distributivity

The property that for all numbers $a, b, c$ we have $a\times(b+c)=a\times b+a\times c$ is called distributivity of $\times$ over $+$ . Similar rules hold for $\wedge$ and $\vee$ .

Theorem 1.6.1.

Let $\phi$ , $\psi$ , and $\theta$ be WFFs. Then

1.

$(\phi\wedge(\psi\vee\theta))\equiv((\phi\wedge\psi)\vee(\phi\wedge\theta))$ , and
2.

$(\phi\vee(\psi\wedge\theta))\equiv((\phi\vee\psi)\wedge(\phi\vee\theta))$ .

Proof.

Here are the truth tables for the four WFFs:

$\phi$	$\psi$	$\theta$	$(\phi\wedge(\psi\vee\theta))$	$((\phi\wedge\psi)\vee(\phi\wedge\theta))$
T	T	T	T	T
T	T	F	T	T
T	F	T	T	T
T	F	F	F	F
F	T	T	F	F
F	T	F	F	F
F	F	T	F	F
F	F	F	F	F

$\phi$	$\psi$	$\theta$	$(\phi\vee(\psi\wedge\theta))$	$((\phi\vee\psi)\wedge(\phi\vee\theta))$
T	T	T	T	T
T	T	F	T	T
T	F	T	T	T
T	F	F	T	T
F	T	T	T	T
F	T	F	F	F
F	F	T	F	F
F	F	F	F	F

The last two columns are the same in both tables, so the formulas are logically equivalent. ∎

1.6.2 Double negation

Theorem 1.6.2.

Let $\phi$ be a WFF. Then $\neg\neg\phi\equiv\phi$ .

Proof.

Let $v$ be a truth assignment for the propositional variables involved in $\phi$ . If $v(\phi)=T$ then $v(\neg\phi)=\neg v(\phi)=F$ and so $v(\neg\neg\phi)=\neg v(\neg\phi)=\neg F=T$ . Similarly if $v(\phi)$ is false so is $v(\neg\neg\phi)$ . Therefore under any truth assignment $v$ we have $v(\phi)=v(\neg\neg\phi)$ . ∎

1.6.3 De Morgan’s laws

Theorem 1.6.3.

Let $\phi$ and $\psi$ be WFFs. Then

1.

$\neg(\phi\vee\psi)\equiv(\neg\phi\wedge\neg\psi)$ , and
2.

$\neg(\phi\wedge\psi)\equiv(\neg\phi\vee\neg\psi)$ .

You might find it clearer to write the right hand sides of these equivalences as $(\neg\phi)\wedge(\neg\psi)$ and $(\neg\phi)\vee(\neg\psi)$ , even though these are not well-formed formulas. From now on I will add or remove brackets from formulas where it helps to make them clearer or more readable even if it means that they are not strictly WFFs.

Proof.

Again, proving this is simply a matter of checking the possibilities for the truth values of $\phi$ and $\psi$ under any assignment. In a table:

$\phi$	$\psi$	$\neg(\phi\vee\psi)$	$(\neg\phi\wedge\neg\psi)$
T	T	F	F
T	F	F	F
F	T	F	F
F	F	T	T

The final columns are the same, so the two formulas have the same truth value no matter what truth assignment is used and are therefore logically equivalent. ∎

De Morgan’s laws can be generalized to more than two WFFs.

Theorem 1.6.4.

For any $n$ and any WFFs $\phi_{1},\ldots,\phi_{n}$ we have

1.

$\neg(\phi_{1}\wedge\cdots\wedge\phi_{n})\equiv\neg\phi_{1}\vee\cdots\vee\neg% \phi_{n}$ , and
2.

$\neg(\phi_{1}\vee\cdots\vee\phi_{n})\equiv\neg\phi_{1}\wedge\cdots\wedge\neg% \phi_{n}$ .

While $\phi_{1}\wedge\phi_{2}\wedge\phi_{3}$ , for example, isn’t a WFF, every way of adding brackets to make it into one produces a logically equivalent WFF because of the associativity of $\wedge$ , Theorem 1.5.1 part 3. Therefore it’s OK for us to omit brackets here for the sake of making the formula easier to read.