1 Logic 1.4 Truth values for WFFs 1.6 Useful logical equivalences

1.5 Logical equivalence

To motivate the idea of logical equivalence, consider the two WFFs

	$\displaystyle\phi$	$\displaystyle=(p\wedge q)$
	$\displaystyle\psi$	$\displaystyle=(q\wedge p).$

These are different WFFs because a WFF is purely a sequence of symbols and these are two different sequences of symbols. However, given any truth assignment, no matter what it is, $\phi$ and $\psi$ always get equal truth values. You can see this by looking at the truth table for $\wedge$ , Table 1.1 which is symmetrical in $p$ and $q$ , in the sense that if you swap the truth values for $p$ and $q$ , the truth value of $(p\wedge q)$ stays the same.

Definition 1.5.1.

Two WFFs $\phi$ and $\psi$ are called logically equivalent, and we write $\phi\equiv\psi$ , if and only if they have the same truth value under every possible truth assignment.

Since the truth table for a WFF displays its truth values under every possible truth assignment, two WFFs are logically equivalent if and only if they have the same truth table.

When two WFFs are logically equivalent they may look different but they always have the same truth value, no matter what the truth values of their variables. This concept is useful in practise because if you want to prove something is true, you can prove some logically equivalent formula instead.

Theorem 1.5.1.

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

1.

$(\phi\wedge\psi)\equiv(\psi\wedge\phi)$ ,
2.

$(\phi\vee\psi)\equiv(\psi\vee\phi)$ ,
3.

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

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

The first two parts of this theorem are referred to as the commutativity properties for $\wedge$ and $\vee$ , and the second two parts as the associativity properties.

Proof.

Parts 1 and 2 are very easy to check as they follow straight from the truth tables for $\wedge$ , Table 1.1 and $\vee$ , Table 1.3.

Parts 3 and 4 are tedious to check, but very easy. I will work out the truth values for one truth assignment and leave the others to you. Let $v$ be a truth assignment such that $v(\phi)=v(\psi)=T$ and $v(\theta)=F$ . For the left hand side of part 3 we have

	$\displaystyle v(\phi\wedge(\psi\wedge\theta))$	$\displaystyle=v(\phi)\wedge v(\psi\wedge\theta)$
		$\displaystyle=T\wedge(v(\psi)\wedge v(\theta))$
		$\displaystyle=T\wedge(T\wedge F)$
		$\displaystyle=T\wedge F$
		$\displaystyle=F$

and for the right hand side

	$\displaystyle v((\phi\wedge\psi)\wedge\theta)$	$\displaystyle=v(\phi\wedge\psi)\wedge v(\theta)$
		$\displaystyle=(v(\phi)\wedge v(\psi))\wedge F$
		$\displaystyle=(T\wedge T)\wedge F$
		$\displaystyle=T\wedge F$
		$\displaystyle=F.$

Continuing like this you can show that the truth tables for both $(\phi\wedge(\psi\wedge\theta))$ and $((\phi\wedge\psi)\wedge\theta)$ are as follows.

$\phi$	$\psi$	$\theta$
T	T	T	T
T	T	F	F
T	F	T	F
T	F	F	F
F	T	T	F
F	T	F	F
F	F	T	F
F	F	F	F

Part 4 can be done similarly. ∎

What the associativity laws, parts 3 and 4, do, is to allow us to drop some brackets while remaining logically unambiguous. Something like $p\wedge q\wedge r$ isn’t a WFF — because it has $\wedge$ symbols but no brackets — but part 3 guarantees us that any two ways we choose to bracket it give logically equivalent WFFs. Similarly

	$\displaystyle p_{1}\wedge p_{2}\wedge\cdots p_{n}$
	$\displaystyle p_{1}\vee p_{2}\vee\cdots p_{n}$

may not be WFFs, but any bracketings that do turn them into WFFs give logically equivalent formulas. For this reason, we often omit bracketings when they don’t cause ambiguity, even though when we miss out the brackets we don’t strictly speaking have a WFF.

Example 1.5.1.

Sometimes brackets are essential. The WFFs

	$\displaystyle\phi$	$\displaystyle=(p\wedge(q\vee r))$
	$\displaystyle\psi$	$\displaystyle=((p\wedge q)\vee r)$

are not logically equivalent. Before you look at the truth tables below you should prove this by finding a truth assignment for the variables $p, q, r$ which makes one of these WFFs true and the other false.

Here are the truth tables:

$p$	$q$	$r$	$(p\wedge(q\vee r))$	$((p\wedge q)\vee r)$
T	T	T	T	T
T	T	F	T	T
T	F	T	T	T
T	F	F	F	F
F	T	T	F	T
F	T	F	F	F
F	F	T	F	T
F	F	F	F	F

so they differ under the truth assignment making $p$ false, $q$ true, and $r$ true, and also under the truth assignment making $p$ false, $q$ false, and $r$ true.