Discrete Mathematics for Computer Science

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 01 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.