An increasing number of computer scientists from diverse areas are using discrete mathematical structures to explain concepts and problems. Based on their teaching experiences, the authors offer an accessible text that emphasizes the fundamentals of discrete mathematics and its advanced topics. This text shows how to express precise ideas in clear mathematical language. Students discover the importance of discrete mathematics in describing computer science structures and problem solving. They also learn how mastering discrete mathematics will help them develop important reasoning skills that will continue to be useful throughout their careers.

2), {2, {3}}, {1, (3)), (1,2, (3111. P({{1, 2, 3}1) = {0, {1, 2, 311. This is true, because the set {{1, 2, 3}} has only one element, {1, 2, 3}. So, there are only two subsets of {{1,2, 3}}, one that contains {1, 2, 31 and one that does not. Products of Sets The next operation on sets is familiar, because it is the formalism behind the way we are used to seeing points in two-dimensional space represented as ordered pairs. Definition 9. For any sets X and Y, the product X x Y is the set of all

every nonzero base 74 CHAPTER 1 Sets, Proof Templates, and Induction FastPower (2, 5) \return 32 base expont call: 2 5 \return 32 base expont call 2: 4 2 return 16 call 3: base expont 16 1 \return 1 call4: Figure 1.19 base expont 16 1 Flow of control for FastPower(2, 5). and every exponent. Using the Strong Form of Mathematical Induction, we now prove that the algorithm is correct for all cases. Theorem 2. n E N. The FastPower algorithm returns the value base' for base E R - {0},

n-n.To find a factor of n, we can focus on finding a value between 2 and In rather than a value from 2ton - 1. INPUT: Integer N > I OUTPUT-: Factors of N PrintFactors(N) /* Initial call */ PrintFactors(n) /* The recursive procedure *! RootN = TrialFactor= [RootNj while (mod(n, TrialFactor):A 0) do /* If TrialFactoris a divisor of n, the loop will be executed zero times. */ TrialFactor= TrialFactor- 1 if (TrialFactor< 1) then print n else PrintFactors(TrialFactor) PrintFactors(n/TrialFactor) The

with the assertion "0) logically implies *t." The first is just a formula. It may be T, or it may be F. We are just discussing, or mentioning, the formula. The second is an assertion that some logical relationship holds. Nevertheless, there is a connection between them. This connection is given in part (a) of Theorem 2.5. Theorem 3. (a) (b) (c) (d) (e) Let 4) and Vt be formulas. Then: 4) k Vf if and only if --)o* is a tautology. R [- * if and only if R U {-'Vf} is unsatisfiable. Let R = {[1,

formulas 01 and 02, (containing only proposition letters; the propositional constants T and F; the propositional connectives -- , v, and A; and parentheses) that are logically equivalent to p V q and p Iq. (Compare formula x in Table 2.5 in Section 2.3.1, where such a formula is given for p +- q.) (e) Repeat part (d) for p v p and pIp, but find the shortest formulas you can. (f) Find formulas logically equivalent to p A q, p V q, and -- p built from p and q using only I and parentheses. 23.