Discrete Mathematics for Computer Science

Predicates and Quantification 137 Solution. (a) Vi E V (A[i] > 0) (b) Vi e V (A[i] <A[30]) (c) Vi E V (A[i] 0) M If V = 0, ...

138 CHAPTER 2 Formal Logic Generally, if 3x (Vy (P(x, y))) is true, so is Vy (3x (P(x, y))): If the first is true, then one can ...

Predicates and Quantification 139 If we go beyond pure logic and use English synonyms, we can further simplify that last express ...

140 CHAPTER 2 Formal Logic Example 7. For the universal set N, is 3x ((x - 3 = 1) A (x > 3)) true? Solution. Since the quanti ...

Predicates and Quantification 141 Note that in two of the lines in Table 2.10 we said "." and that in two we said just "=." We l ...

142 CHAPTER 2 Formal Logic A formula that states this property is intuitively easy to understand, but it is not so easy to state ...

Exercises 143 for i < j and j > 0, A[i] < A[j]-that is, that the elements of A are in increasing or- der. The loop inva ...

144 CHAPTER 2 Formal Logic For the following formulas, let the universe be R. Translate each of the following sentences into a ...

Exercises 145 (e) "Some athletes are young females." (f) "All athletes are young males." (g) "Some athletes are female and are n ...

146 CHAPTER 2 Formal Logic (e) 3x((P(x) v Q(x)) -+ R(x)) (f) 3x((P(x) -+ Q(x)) A R(x)) Find a formula in negation normal form e ...

Chapter Review 147 INPUT: An array A [ 0. .2N - I] of 2N integers OUTPUT: The same array, with its elements sorted into nondecre ...

148 CHAPTER 2 Formal Logic satisfiable propositions, and logically equivalent propositions give a fuller understanding of the pr ...

Chapter Review 149 THEOREMS First Substitution Principle Second Substitution Principle 2.5 and 2.6 Summary TERMS 2-CNF excess li ...

150 CHAPTER 2 Formal Logic Write in symbolic form the statement "Claudia will sail in the regatta if the crew is ready and the ...

Chapter Review 151 Form a truth table for the proposition p V -,(p A q). Use the substitution rule with p --* q for p, and prov ...

152 CHAPTER 2 Formal Logic (b) Find a formula equivalent to a -* (b A C A d) using only the connectives NAND (and not the consta ...

Chapter Review 153 (b) Find a formula equivalent to if a then if b then c else d else if e then d else c in CNF. (c) Find a form ...

154 CHAPTER 2 Formal Logic Next, for each satisfying truth assignment I, let T, be the set of truth variables assigned the value ...

Chapter Review 155 (b) If Harry, Hermione, and Frodo are all experienced in potions and each of them prefers potions to at least ...

...