Discrete Mathematics for Computer Science

Truth and Logical Truth 109

Proof. (=,) Let *' be a tautology, and let I be any interpretation of the proposition let-

ters in . Since is a tautology, I() = T, so I(-) = F. Hence, ---' is not satisfiable.

(€=) The converse is analogous. U

A proof by contradiction shows that if I(4) = T for an interpretation, then we prove

I(--*') = T in that interpretation, which is clearly a contradiction.

2.3.2 Substitutions into Tautologies

The formula 4 = (p A (p -- q)) -* q is a tautology. Now, replace each occurrence of p

in 4 with another formula, say pl V P2. The result is the formula

01 = ((P1 V P2) A ((Pl V P2) -- q)) -- q

The reader can easily write the truth table for 01 and see that it also is a tautology. Some-

thing more general, however, is taking place here. One can think of the substitution not as

substituting the formula P, v P2 into 4 for p but, rather, as substituting the truth value for

P1 V P2 for the truth value of p in 4. Since 4 is a tautology, any truth value for p together

with any truth value for q yields a truth value of T for 4. So, 01 should also be a tautology.

This intuitive argument can be formalized to prove the following theorem. (The interested

reader is invited to prove it.)

First Substitution Principle

Let 4 be a tautology; let P1, P2, ... , Pk be any proposition letters appearing in 4,

and let X1, X2 ..... Xk be formulas. Form a formula 4)1 by simultaneously replacing

P1 with X1, P2 with X2. Pk with Xk wherever they occur in 4. Then, 01 is a

tautology.

The requirement of simultaneous replacement is important, since it allows, say, X1 to

contain a P2 without forcing that P2 to be replaced with X2. For example, again let

4 = (p A (p -* q)) -). q

and replace p with X1 = q -* r and q with X2 = r - q. The result is

01 = (Xj A ((XI - X2)) "- X2

01l = (q -+ r) A ((q -- r) -- (r - q)) --- (r -- q)

Since 4 is a tautology, so is 01. The simultaneous replacement condition meant that the q

in X1 did not have to be replaced with X2.

2.3.3 Logically Valid Inferences

We began the study of logic to help distinguish valid from invalid arguments. We have now
covered enough material to present a formal notion of a valid argument for propositional
logic.