Discrete Mathematics for Computer Science

106 CHAPTER 2 Formal Logic

p q r -'p -pvq r-+p (-'pvq)- (r--+p)

Io T T T F T T T

I1 T T F F T T T

12 T F T F F T T

13 T F F F F T T

14 F T T T T F F

15 F T F T T T T

16 F F T T T F F

17 F F F T T T T

By convention, we put the truth value directly under the operation performed. The truth

values in the right-most column of the table are the truth values of each of the inter-

pretations of this formula. The truth tables show that 4) is T in the interpretations I0,

1,, 12, 13, 15, and 17. The truth table also shows that 0 is F in the interpretations 14

and 16. 0

2.3.1 Tautologies

Propositional logic is the study of propositions and the propositional connectives. It is the

study not only of one particular interpretation of a formula but also of what can be deduced

about all interpretations of a formula. Of particular interest are those formulas that are true

"by virtue of pure logic." Definition 3 captures the notion of "true by virtue of pure logic,"

at least as closely as is possible from the standpoint of propositional logic.

Definition 3. Let 4) be a formula. Then, 4) is a tautology, or is logically valid, if it is T in

every interpretation. 40 is satisfiable if it is T in some interpretation, and it is unsatisfiable

if it is T in no interpretation. Unsatisfiable formulas are also called contradictions.

A formula is a tautology if and only if all entries under the formula in its truth table

evaluation are T. For example, "John is married, or John is not married" is a logical truth.

"John is married, or John is a bachelor" is not a logical truth, since it depends on the

meaning of the word bachelor.

"John is married, and John is not married" is unsatisfiable, since the proposition "John

is married" cannot be both T and F. On the other hand, "John is married, or John is a

bachelor" is clearly satisfiable. Of course, every tautology is also satisfiable.

Example 4. Construct a truth table to show that (p A q) -) p is a tautology.

Solution. The truth table for (p A q) -) p is

p q p pAq ((p Aq) -+ p)

T T T T

T F F T

F T F T

F F F T

Since all entries under ((p A q) -+ p) are T, the formula is a tautology. 0