Discrete Mathematics for Computer Science

Exercises 117 Find the expression tree for the formula p -- ((--p) -- q) Evaluate the expression tree if proposition p is T an ...

118 CHAPTER 2 Formal Logic (d) (p- (r V q)) ((p r) v (p q)) (e) (p- (rAq)) ((p r) v(p q)) (f) ((p- q) --> q) -+ p Construct ...

Exercises 119 Find all truth values for which the following combinatorial circuit gives a value of T. Interpret this combinator ...

120 CHAPTER 2 Formal Logic (b) Let 0 be the formula ( ... ((P I <+- P2) ++ P3) +- .)•Pn for n > 1. For what interpretation ...

Normal Forms 121 substituting always stops. Consider, for example, the substitution in the formula (p -•* q) +- (r +-* s) If the ...

122 CHAPTER 2 Formal Logic 2.5.1 Disjunctive Normal Form Consider the following two formulas: =(p -- (q V r)) +* (q - p) and = ( ...

Normal Forms 123 Example 1. (a) a A b A -c is a term. (b) The formula (a A b A c) V (-a A -,b A --c) V (a A --c A q) is in disju ...

124 CHAPTER 2 Formal Logic The reader should observe that these terms have the desired properties. That is, Io satisfies p A q A ...

Normal Forms 125 Example 4. Let x, y be elements of a boolean algebra. Use the DNF for the boolean expression (x A y) V (-x A -' ...

126 CHAPTER 2 Formal Logic Example 5. (a) a v b v -c is a clause. (b) T is in CNF. It is a conjunction of zero clauses. (c) F is ...

Normal Forms 127 Example 7. Let * be the formula * = -((p -- (q V r)) A (-q) A (-r) A p) Find a CNF for *1. Solution. The negati ...

128 CHAPTER 2 Formal Logic Example 9. (a) Show that 4 = (a A -'b) V (-'a A -"C A b) V (a A -'a) is satisfiable. (b) Show that ¢ ...

Normal Forms 129 Then, Oi is a tautology if and only if Oi contains two literals, )Xa and Xb, where X-a = ')b and 1 <a A b &l ...

130 CHAPTER 2 Formal Logic p v -q and r v q are given. What conclusion is possible for the conjunction of these two clauses as a ...

Exercises 131 Example 13. Let S = {p V q, p V --q, -p v q, --p V -q}. Give a resolution refutation for S (plus comments, as note ...

132 CHAPTER 2 Formal Logic (e) p q r s Truth Value (f) p q r s Truth Value T T T T F T T T F T T T F T T T T F F F T F T F T T F ...

Exercises 133 Find a CNF for each of the following formulas, and prove that each formula is a tautology. (a) (p Ap) +-p (b) (p ...

134 CHAPTER 2 Formal Logic (a) 1p, -p V q, --p V -q V r, -•r (b) {-p, p V q, -q v -r, p V r} (c) {p V q, -'p v r, -q V r, -p V s ...

Predicates and Quantification 135 not fixed for all time. We want to allow variables (or variable symbols), such as p and q, whi ...

136 CHAPTER 2 Formal Logic The second kind of quantification is existential quantification for the predicate P, such as 3x (P(x) ...