Discrete Mathematics for Computer Science

Truth and Logical Truth 105

In Example 2, if I is the interpretation with I(p) = T and I(q) = I(r) = F, then

(-p V q) -). (r -- p) is true in I.

Example 3. Let

0 = ((-p V q) -- (r -+ p))

Find I (0b) for all interpretations 1.

Solution. Three proposition letters-p, q, and r-are in the formula. Hence, the truth of

the formula depends only on I(p), I(q), and I(r). Each of I(p), I(q), and 1(r) can be

one of T or F, so there are 23 = 8 possible interpretations.

The calculation of the truth value for each of the eight interpretations can be shown

concisely in a truth table. Start out with a truth table that has eight rows, one for each

interpretation:

p q r

1o T T T

I1 T T F

12 T F T

13 T F F

14 F T T

(^15) F T F

16 F F T

17 F F F

Next, assign truth values to larger and larger subformulas until the formula itself is evalu-

ated.

We now repeat the evaluation of the formula

0 = (--p V q) -+ (r -+ p)

using this method. Evaluating -p and r -+ p, we get

p q r -p --pVqr- p (-ppvq)- (r- p)

Io T T T F T

Il T T F F T

12 T F T F T

13 T F F F T

14 F T T T F

15 F T F T T

16 F F T T F

17 F F F T T

and in two more steps, we complete the evaluation of the formula: