Mathematics for Computer Science

3.6. Predicate Formulas 53 3.6.4 Variables Over One Domain When all the variables in a formula are understood to take values fro ...

Chapter 3 Logical Formulas54 For example, we already observed that the rule for negating a quantifier is captured by the valid a ...

3.6. Predicate Formulas 55 example, let the domain be the integers andP.x;y/meanx > y. Then the hy- pothesis would be true be ...

Chapter 3 Logical Formulas56 But when a mother says to her son, “If you don’t do your homework, then you can’t watch TV,” then l ...

3.6. Predicate Formulas 57 This 2-bit half-adder could be described by the following formulas: c 0 Db s 0 Da 0 XOR c 0 c 1 Da 0 ...

Chapter 3 Logical Formulas58 (a)A 1-bit add1 module just has inputa 0. Write propositional formulas for its outputscandp 0. (b)E ...

3.6. Predicate Formulas 59 .nC1/-bit add 1 2.nC2/-bit add 1 module .nC1/-bit add 1 a2nC 1 anC 2 anC 1 rn r 1 r 0 an a 1 a 0 p2nC ...

Chapter 3 Logical Formulas60 Problem 3.8. This problem^3 examines whether the following specifications aresatisfiable: If the f ...

3.6. Predicate Formulas 61 (a)Write formulas using onlyAND,OR,NOTthat are equivalent to each ofAIFFB andAXORB. Conclude that eve ...

Chapter 3 Logical Formulas62 we might use new variablesX 1 ,X 2 ,O, andAcorresponding to the the operator occurrences as follows ...

3.6. Predicate Formulas 63 (a) .:.D.Ben/_D.David///!.L.Albert;Ben/^L.Ben;Albert// (b) 8 x .xDClaire^:L.x;Emily//_.x¤Claire^L.x;E ...

Chapter 3 Logical Formulas64 (a)xconsists of three copies of some string. (b)xis an even-length string of 0’s. (c)xdoes not cont ...

3.6. Predicate Formulas 65 using addition, multiplication, and equality symbols, and nonnegative integercon- stants 0 , 1 ,... ) ...

...

4 Mathematical Data Types 4.1 Sets We’ve been assuming that the concepts of sets, sequences, and functions are already familiar ...

Chapter 4 Mathematical Data Types68 symbol set elements ; the empty set none N nonnegative integers f0;1;2;3;:::g Z integers f:: ...

4.1. Sets 69 For example, when the domain we’re working with is the real numbers, the com- plement of the positive real numbers ...

Chapter 4 Mathematical Data Types70 is true. In this case, an explicit description of the setBin terms of intervals would requir ...

4.3. Functions 71  The elements of a set are required to be distinct, but terms in a sequence can be the same. Thus,.a;b;a/is a ...

Chapter 4 Mathematical Data Types72 whereyandzrange over binary strings, or f 3 .x;n/WWDthe pair.n;x/ wherenranges over the nonn ...