# 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. 1.

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

2. 2.

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

###### Proof.

Here are the truth tables for the four WFFs:

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. 1.

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

2. 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:

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. 1.

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

2. 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.