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.