1 Logic 1.3 Truth tables 1.5 Logical equivalence

1.4 Truth values for WFFs

Suppose we have a truth assignment $v:V\to\{T,F\}$ . There is then a unique way to extend $v$ so that it gives a truth value to any WFF using the propositional variables $V$ such that for any WFFs $\phi$ and $\psi$ ,

$\displaystyle v((\phi\wedge\psi))$	$\displaystyle=v(\phi)\wedge v(\psi),$
$\displaystyle v((\phi\vee\psi))$	$\displaystyle=v(\phi)\vee v(\psi),$
$\displaystyle v((\phi\implies\psi))$	$\displaystyle=v(\phi)\implies v(\psi),$	and
$\displaystyle v(\neg\phi)$	$\displaystyle=\neg v(\phi).$

Recall that we use the connective symbols not just as parts of WFFs but as ways of combining truth values, for example $T\wedge F=F$ , $T\implies T=T$ , and $\neg F=T$ . For example, if $V=\{p,q\}$ and $v(p)=T,v(q)=F$ we would have

	$\displaystyle v((p\wedge q))$	$\displaystyle=v(p)\wedge v(q)$
		$\displaystyle=F\wedge T$
		$\displaystyle=F$

and

	$\displaystyle v((\neg p)\implies(p\vee q))$	$\displaystyle=v(\neg p)\implies v(p\vee q)$
		$\displaystyle=(\neg v(p))\implies((v(p)\vee v(q)))$
		$\displaystyle=F\implies(T\vee F)$
		$\displaystyle=F\implies T$
		$\displaystyle=T.$

It’s not completely obvious this really works, but you can read a proof in section 2.3 of the book by Goldrei mentioned in the further reading section at the end of this chapter.

This method of assigning truth values to WFFs can be thought of in a slightly different way: we just substitute in truth values in place of the propositional variables, and combine them using the truth tables for the connectives — exactly like how if you wanted to find the value of $x^{2}+y+3$ when $x=1$ and $y=2$ , you would substitute the values in to get $1^{2}+2+3$ and combine them using the usual arithmetic operations to get $6$ .

Example 1.4.1.

Let

\phi=((p\wedge q)\vee(\neg p\wedge\neg q)).

Let $v(p)=T,v(q)=F$ . We are going to find $v(\phi)$ .

The method of assigning truth values to WFFs above tells us

	$\displaystyle v(\phi)$	$\displaystyle=v((p\wedge q)\vee(\neg p\wedge\neg q))$
		$\displaystyle=v(p\wedge q)\vee v(\neg p\wedge\neg q)$		(1.1)

so we need to work out $v(p\wedge q)$ and $v(\neg p\wedge\neg q)$ .

We have $v(p\wedge q)=v(p)\wedge v(q)=T\wedge F$ . Looking at the $T, F$ row of Table 1.1, the truth table for $\wedge$ , we see that $T\wedge F$ is $F$ .

Next,

	$\displaystyle v(\neg p\wedge\neg q)$	$\displaystyle=v(\neg p)\wedge v(\neg q)$
		$\displaystyle=\neg v(p)\wedge\neg v(q)$
		$\displaystyle=\neg T\wedge\neg F$
		$\displaystyle=F\wedge T.$

The $F, T$ row of the same truth table tells us that this is $F$ .

Finally, substituting the values we have just worked out for $v(p\wedge q)$ and $v(\neg p\wedge\neg q)$ into (1.1)

v(\phi)=F\vee F.

Looking at the $F, F$ row of Table 1.3, the truth table for $\vee$ , we see that $v(\phi)=F$ .

Example 1.4.2.

Consider the WFF $\phi=(p\implies(p\implies p))$ and the truth assignment $v(p)=T$ . What is $v(\phi)$ ?

By definition,

	$\displaystyle v(\phi)$	$\displaystyle=v(p)\implies(v(p)\implies v(p))$
		$\displaystyle=T\implies(T\implies T).$

Looking at the $T, T$ row of the truth table for implies, Table 1.4, we see that $T\implies T$ is $T$ . So $v(\phi)=T\implies T$ . For the same reason, $v(\phi)=T$ .

If you work out the truth value of $\phi$ when $v(p)=F$ , you should find that the result is also $T$ .

$p$	$(p\implies(p\implies p))$
T	T
F	T

Notice that the WFF $\phi$ from the previous example is true for every truth assignment of its variables. A WFF with this property is called a tautology, and a WFF which is false under every truth assignment, for example $(p\wedge\neg p)$ , is a contradiction.

Example 1.4.3.

Let

\phi=((p\vee q)\wedge(p\vee\neg q)).

Given the truth assignment $v$ such that $v(p)=T,v(q)=F$ , let’s work out the truth value $v(\phi)$ . Since

v(\phi)=v(p\vee q)\wedge v(p\vee\neg q)

we can start by working out $v(p\vee q)$ and $v(p\vee\neg q)$ separately. From the truth table for $\vee$ , Table 1.1, we see that

v(p\vee q)=T\vee F=T.

We have $v(\neg q)=\neg v(q)=\neg F=T$ , so

v(p\vee\neg q)=T\vee T=T.

Finally $v(\phi)=T\wedge T=T$ .

The truth table for a WFF lists its truth value under all possible truth assignments for its propositional variables. The truth table for the formula $\phi$ from the previous example (and for some of the formulas that make up $\phi$ ) is given below. You should check that the following table is correct.

$p$	$q$	$(p\vee q)$	$\neg q$	$(p\vee\neg q)$	$\phi$
T	T	T	F	T	T
T	F	T	T	T	T
F	T	T	F	F	F
F	F	F	T	T	F