Discrete Mathematics for Computer Science

Introduction to Propositional Logic 97 Solution. The subtrees Tp and T(-(pvq)) are as shown: 0 (-~(p vq)) TP vq)q(p p q T(-•(p v ...

98 CHAPTER 2 Formal Logic 2.1.4 Using Gates to Represent Formulas At the basic hardware level, computer memory has two states, w ...

Exercises 99 yY X y r S Bl t z Figure 2.8 Multiple formula representation. Exercises Translate the following expressions into p ...

100 CHAPTER 2 Formal Logic (a) (p A q A r) --> s (b) (t A u) -- v (c) -s -) -'v (d) p A (q A r) V (t A u) V (--S V --V) (e) ( ...

Exercises 101 (e) -r --*(p A q) (f) (p -q) - -r (g) ((p A r) -+ (-q v p)) --* (q v r) Find the expression tree for the followin ...

102 CHAPTER 2 Formal Logic x (a) _ z (b) Y x z (c) Z Yz Prove Theorem 1, the Principle of Induction on Formulas. (Hint: If ¢ V ...

Truth and Logical Truth 103 How can the truth value for the formula be determined? Since this discussion is formal logic, one mu ...

104 CHAPTER 2 Formal Logic Now, use these truth values to move up the tree toward the root, using the truth tables for the propo ...

Truth and Logical Truth 105 In Example 2, if I is the interpretation with I(p) = T and I(q) = I(r) = F, then (-p V q) -). (r -- ...

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

Truth and Logical Truth 107 The reader should note that, intuitively, (p A q) -* p "asserts" that if p and q are both T, then p ...

108 CHAPTER 2 Formal Logic Table 2.5 lists many commonly used tautologies. The reader should study them care- fully and determin ...

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

110 CHAPTER 2 Formal Logic Definition 4. Let S be a set of formulas. An interpretation I satisfies S if I (4) = T for every 0p E ...

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

112 CHAPTER 2 Formal Logic Theorem 4. (a) Suppose 4) and * are both tautologies. Then, 4) and * are logically equivalent. (b) Su ...

Truth and Logical Truth 113 Gates and Boolean Algebra In Section 1.3.5, the axiom system for a boolean algebra was introduced. E ...

114 CHAPTER 2 Formal Logic Example 11. Use logic to show that (-,p A q) V (p A -'q) V (p A q) is logically equiv- alent to the f ...

Truth and Logical Truth 115 Since the subformula 41 = -p -- q is logically equivalent to 42 = p V q (see Example 9 in Section 2. ...

116 CHAPTER 2 Formal Logic This is an application of the Second Substitution Principle. Then, eliminate all --*'s as follows: Re ...