Mathematics for Computer Science

3.7. References 73 Problem 3.22. Find a counter model showing the following is not valid. Œ 9 x:P.x/AND 9 x:Q.x/çIMPLIES 9 x:ŒP. ...

Chapter 3 Logical Formulas74 (c) NOT.D.Claire//IMPLIES.G.Albert;Ben/AND 9 x:G.Ben;x// (d) 8 x 9 y 9 z .y¤z/ANDL.x;y/AND NOT.L.x; ...

3.7. References 75 (e)An elegant, slightly trickier way to defineNO-1S.x/is: PREFIX.x; 0 x/: (*) Explain why (*) is true only wh ...

Chapter 3 Logical Formulas76 which more clearly shows that the separate occurrences of 8 xin (3.28) are unre- lated. Renaming va ...

3.7. References 77 the propositional operators, variables and quantifiers, you may define predicates using addition, multiplicat ...

Chapter 3 Logical Formulas78 Exam Problems Problem 3.32. The following predicate logic formula is invalid: 8 x; 9 y:P.x;y/!9y; 8 ...

3.7. References 79 Problem 3.34. We want to find predicate formulas about the nonnegative integers,N, in which is the only pred ...

...

4 Mathematical Data Types We have assumed that you’ve already been introduced to the concepts of sets, se- quences, and function ...

Chapter 4 Mathematical Data Types82 4.1.1 Some Popular Sets Mathematicians have devised special symbols to represent some common ...

4.1. Sets 83  TheintersectionofAandB, denotedA\B, consists of all elements that appear inbothAandB. That is, x 2 A\B IFF x 2 AA ...

Chapter 4 Mathematical Data Types84 4.1.4 Set Builder Notation An important use of predicates is inset builder notation. We’ll o ...

4.1. Sets 85 Theorem 4.1.2.[Distributive Lawfor Sets] LetA,B, andCbe sets. Then: A\.B[C/D.A\B/[.A\C/ (4.1) Proof. The equality ( ...

Chapter 4 Mathematical Data Types86 are sets, then it is wrong to write “XANDY” instead of “X\Y.” ApplyingAND to sets will cause ...

4.3. Functions 87 4.3 Functions 4.3.1 Domains and Images Afunctionassigns an element of one set, called thedomain, to an element ...

Chapter 4 Mathematical Data Types88 f 5 .y/to be the length of a left to right search of the bits in the binary stringyuntil a 1 ...

4.4. Binary Relations 89 Abstractly, taking a step amounts to applying a function, and going step by step corresponds to applyin ...

Chapter 4 Mathematical Data Types90 domain element,a, there isat mostone pair in the graph whose first coordinate is a. As we sa ...

4.4. Binary Relations 91 A B a - 1 b PPP PPPq 2 c PP PP PPq 3 d     3 4 e     3 A B a - 1 b PPP PPPq 2 c Q QQ Q QQs ...

Chapter 4 Mathematical Data Types92 Example4.4.3.The function defined by the formula1=x^2 has theŒ 1 outçprop- erty if its doma ...