Discrete Mathematics for Computer Science

xx Preface PREFACE Chapter 1: Sets, Proof Templates and Induction Chapter 2: Formal Logic Chapter 3: Relations Chapter 4: Functi ...

Preface xxi Outline for One-Semester Course This text contains much more material than can be covered in a typical one-semester ...

xxii Preface however, this material gives a good overview of the relationship between programs and their complexity. Many variat ...

Preface xxiii Connected Graphs The Konigsberg Bridge Problem Trees Spanning Trees Chapter 7: Counting and Combinatorics (4 lectu ...

Sets, Proof Templates, and Induction The concept of a set underlies most of modem mathematics and much of computer sci- ence. To ...

2 CHAPTER 1 Sets, Proof Templates, and Induction is usually called a stamp collection. The set of past presidents of the United ...

Basic Definitions 3 Set-Theoretic Notation Three methods to describe the set with elements 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9 are: ...

4 CHAPTER 1 Sets, Proof Templates, and Induction We often list the elements of a set in a way that shows an obvious association ...

Basic Definitions 5 Definition 1. Let A and B be sets. Then, A = B or A is equal to B if both A and B have the same elements. Th ...

6 CHAPTER 1 Sets, Proof Templates, and Induction Definition 2. Let A and B be sets. A is a subset of B, written as A C B, if eve ...

Basic Definitions 7 are used in the standard mathematical expression if and only if. The statement a if and only if b means that ...

8 CHAPTER 1 Sets, Proof Templates, and Induction U I CM Figure 1.2 Sample Venn diagram. Venn diagrams are frequently used to bui ...

Basic Definitions 9 of another set, and that two sets are or are not equal. First, we state a template for proving that an eleme ...

10 CHAPTER 1 Sets, Proof Templates, and Induction j e N, which would prove that 2k 0 + 5 = 2j + 1 E B. The algebra needed to see ...

Basic Definitions 11 Example 7. Let A = {n c N n > 2 and n = 4j - 5 for some j e N} and B = in E N n > 0 and n = 2k + 1 fo ...

12 CHAPTER 1 Sets, Proof Templates, and Induction of B, say, 2ko + 2 for some k0 E Z and ko > -1, is an element of A, we must ...

Exercises 13 To prove "if a, then b" and "a if and only if b" results, use one of the two forms: Form 1: To prove "if a, then b, ...

14 CHAPTER 1 Sets, Proof Templates, and Induction Write three descriptions of the elements of the set {2, 5, 8, 11, 14). How ma ...

Operations on Sets 15 Describe in words the difference between 0 and {0}. Let A, B, and C be sets. (a) Prove that if A C B and ...

16 CHAPTER 1 Sets, Proof Templates, and Induction Example 1. (a) 11, 2, 31 U 13, 4, 5) = 11, 2, 3, 3, 4, 5} = {1, 2, 3, 4, 5}. ( ...