Truth and Logical Truth
111
(b) We show that I(p A q) always equals I(-(-p V -- q)) by building a truth table of all
possibilities:
p
q
pAq
-p
-'q -pV-'q
-- (-pV-q)
T T
T
F
F
F
T
T F
F
F
T
T
F
F
T
F
T
F
T
F
F
F
F
T
T
T
F
Note that all entries under p A q and -- (--p v -- q) are identical-that is, that I(p A q)
is always equal to I(--(--p V -- q)).
(c) Let I be the interpretation where I (p) = T and I (q) = F. Then, I (p A q) = F, and
I(p V q) = T. Because these two truth values are not the same, the two formulas are
not logically equivalent.
M
The intuitive content of logical implication is that if Vt # X, then it is correct to infer
X from Vi in any argument. The definition of logically implies can be extended to sets of
propositions in a straightforward way. At this point, we need to understand this notion at
the level of formulas only. For example, if we have two sets of formulas R and S, then R
logically implies S if, for every interpretation I, I satisfies R if and only if I satisfies S.
Compare the formula 4) -+ * with the assertion "0) logically implies *t." The first is
just a formula. It may be T, or it may be F. We are just discussing, or mentioning, the
formula. The second is an assertion that some logical relationship holds. Nevertheless,
there is a connection between them. This connection is given in part (a) of Theorem 2.5.
Theorem 3. Let 4) and Vt be formulas. Then:
(a) 4) k Vf if and only if -)
-- o* is a tautology.
(b) R [- * if and only if R U {-'Vf} is unsatisfiable.
(c) Let R = {[1, ,2 .... OPk}. R 1= * if and only if 0 1 A4 2 A ... A k -
is a tautology.
(d) 0 1= *t if and only if * is a tautology.
(e) ,) and *t are logically equivalent if and only if 4) ÷ r is a tautology.
Proof. (a) (=#)
First, suppose ) 1= *, and let I be any interpretation. It is necessary to
show that 1(0) -+ *-) = T. The only way that 1(0) --* *) can be F is for 1(4)) to be T and
I (*f) to be F. However, if 1(4b) = T, then, since 4) logically implies *, I (*) must also be
T. Hence, 1(4) -(0
) = T.
(.€=) Second, suppose ,) -- •r is a tautology. It is necessary to show that for any
interpretation I, if 1(4) = T, then I(*) = T as well. So, suppose I is an interpretation,
and suppose 1(4)) = T. Since 4) -- Vt is a tautology, 1(,) -- Vt) = T. By the truth table
for -+, if I(0) = T and I(0) -- * V)=T, then I(*) = T.
(b)-(e) These proofs are left for Exercise 24 in Section 2.4.
0
The next theorem tells us that if two propositions are either always T or always F,
then they are logically equivalent.