Discrete Mathematics for Computer Science

112 CHAPTER 2 Formal Logic

Theorem 4.

(a) Suppose 4) and * are both tautologies. Then, 4) and * are logically equivalent.

(b) Suppose 4) and * are both unsatisfiable. Then, 4) and * are logically equivalent.

Proof. These proofs are left for Exercise 25 in Section 2.4. U

The result just says that since a tautology is T for every set of truth values of its

propositions, its truth value will match the truth value of any other tautology for those

same truth values. Similarly, the same holds for two unsatisfiable formulas.

In Table 2.6, we add a bit of notation; rather than just saying {p, p --+ q) ý= q, we

replace p and q with the symbols 4) and *, representing arbitrary formulas. What Table

2.6 really means is that if we replace 4), Vt, and X with any formulas, the results are logical

implications.

Table 2.6 Some Logically Valid Inferences and Their Traditional Names

Some Logically Valid Inferences

a. {4, ) • 4} Modus Ponens

b. X _ X Law of Syllogism

C. { V V 4,, --0) 4 Modus Tollendo Ponens

d. ""4) • 4 Double Negation

e. --, -- --,' •--, -- 4. Contrapositive

f. 4)-- 4 1=- --* 4 Contrapositive

g. {4 "* X, 4 - X )x} 1 - Proofby Contradiction

h. X-'4 x, -"4 "- "x} X 4I Proof by Contradiction

i. {X)v4', 4)--,, --* X} X Proofby Cases

j. {4) A 4'} * -,(",4 v -'-0 ) DeMorgan's Law

k. {-(4 A 4)} 1= (-4) V --,') DeMorgan's Law

1. (0) V 4r=-'(-4) A -4) DeMorgan's Law
   m. (-(4) V 40) • (",) A --,) DeMorgan's Law

Example 10.

(a) Let 4) denote "X is a cat" and * denote "X is an animal." Under the assumption that 4)

is true and 4) * 4 is true, we can use Modus Ponens to conclude that X is an animal.

(b) Let 4) denote "X is a cat" and ' denote "X is a bird." If we are given that 4) v t is true

and --4) is true, then we can use Modus Tollendo Ponens to conclude that "X is a bird."

U

As commented earlier, computer programs have been written to automate logical in-

ference. Some material relevant to this are discussed in the next section and in Section 2.4.

2.3.4 Combinatorial Networks

A combinatorial network is just another representation for a formula or a set of formulas

of propositional logic. Start with an assignment of truth values to the wires going into the

circuit-that is, to the proposition letters. The circuit computes a group of outputs that

correspond to the truth values of the corresponding formulas.