Discrete Mathematics for Computer Science

110 CHAPTER 2 Formal Logic

Definition 4. Let S be a set of formulas. An interpretation I satisfies S if I (4) = T for

every 0p E S. A set S of formulas is satisfiable if there is an interpretation I that satisfies S.

For example, {p, q, r} is satisfiable. It is satisfied by any interpretation I where I (p) =

I (q) = I (r) = T. However, Ip, -pp} is not satisfiable.

One intuition is that I describes the actual state of the world and that S is a set of

formulas, which can be thought of as assertions about the world. I satisfies S if each

formula in S is a true statement about (the state of) the world. Another intuition is that I is

a possible state of the world. Suppose it is known that all statements in S are T. Then, one

can check whether a possible state I of the world matches what is known-that is, whether

I satisfies the known facts S.

Theorem 2.

(a) Every interpretation satisfies 0.

(b) If S = 101, ..... ,k} and I is an interpretation, then I satisfies S if and only if

1(0b1 A ... A 00k = T_

Proof. This Proof is left for Exercise 23 in Section 2.4. U

Definition 5.

(a) For formulas and X, ' logically implies, X, or * tautologically implies X, if, for

every interpretation I,

if I(*) = T, then I(X) = T

We denote i/ logically implies X as 4' -X.

(b) Formulas * and X are logically equivalent, or tautologically equivalent, or equiva-

lent, if, for every interpretation I, we have I(*) = I (X).

As a natural extension of one formula logically implying another formula, we say that

for a set of formulas S, S • x means that inferring X from S is logically valid.

Example 9.

(a) pAqkpvq.

(b) p A q is logically equivalent to -'(--p v --q).

(c) p A q and p V q are not logically equivalent.

Solution.

(a) Suppose I is any interpretation. We need to show that if I (p A q) = T, I (p V q) = T.

So, suppose I (p A q) = T. Then, I (p) = T, and I (q) = T. So, I (p V q) = T, as

desired.