Discrete Mathematics for Computer Science

104 CHAPTER 2 Formal Logic

Now, use these truth values to move up the tree toward the root, using the truth tables for

the propositional connectives (see Tables 2.2 and 2.3 in Section 2.1). First, work one level

up from the leaves. The truth table for - says that if p is T, then -p is F. The truth table

for --* says that if r is F and p is T, then r -) p is T.

Next, use the truth table for v to compute a truth value for -p v q. Since the truth

value of -p is F and the truth value of q is F, the result is F.

Finally, use the truth table for --+ to assign a truth value to the entire formula. The truth

value of an implication for which the hypothesis is F and the conclusion is T is just T.

Therefore, T is the truth value of 4). The steps of this evaluation are shown in Figure 2.10.

((-p) v q) - (r - p) T

((-p) vq F r-p

(-'p) F q FTr F T

PT

Figure 2.10 Step 3 of evaluating a formula.

The truth value of the entire formula 4) is denoted by I (4)). In the case shown here,

1 (4) = T. 0

Formally, what happened in Example 2 is an induction on formulas. The interpretation

I specified the truth values for the proposition letters. The truth I (0) for more complex

formulas 4) is defined using the truth values for simpler formulas and the truth tables for -,

A, V, --*, and --* as shown here:

1. 1(T) = T, and I(F) = F

2. I(-0) = T ifI(0)=F
   I F ifl()=IT

F otherwise

SF if1(0)==I(*)=F

4.(v )} = T otherwise

5. 1 F ifI(0)=Tandl( )=F

T otherwise

6.^1 T ifI(4)=(i)

F if I(4))#(Ifr)

Since each formula 4) has exactly one expression tree and these rules define the truth

value of each node on the tree in terms of the truth values of the nodes with edges joining

them to this node, there is only one way to calculate I (4)).

Definition 2. Let I be an interpretation of P. A formula 4) is true in I if 1(4)) = T, and

0 is false in I if 1 (4) = F.