Discrete Mathematics: Proofs, Structures and Applications (3rd Edition, 2010) – Solutions to Exercises – Garnier

ALL 12 CHAPTERS COVERED

,Contents

1 Logic 1
1.1 Solutions to Exercises 1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Solutions to Exercises 1.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Solutions to Exercises 1.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Solutions to Exercises 1.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Solutions to Exercises 1.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6 Solutions to Exercises 1.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.7 Solutions to Exercises 1.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.8 Solutions to Exercises 1.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2 Mathematical Proof 28
2.1 Solutions to Exercises 2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2 Solutions to Exercises 2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3 Solutions to Exercises 2.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3 Sets 34
3.1 Solutions to Exercises 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2 Solutions to Exercises 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3 Solutions to Exercises 3.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4 Solutions to Exercises 3.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.5 Solutions to Exercises 3.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.6 Solutions to Exercises 3.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.7 Solutions to Exercises 3.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

4 Relations 76
4.1 Solutions to Exercises 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.2 Solutions to Exercises 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.3 Solutions to Exercises 4.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.4 Solutions to Exercises 4.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.5 Solutions to Exercises 4.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
4.6 Solutions to Exercises 4.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.7 Solutions to Exercises 4.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

5 Functions 122
5.1 Solutions to Exercises 5.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.2 Solutions to Exercises 5.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

, 5.3 Solutions to Exercises 5.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
5.4 Solutions to Exercises 5.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
5.5 Solutions to Exercises 5.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
5.6 Solutions to Exercises 5.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

6 Matrix Algebra 179
6.1 Solutions to Exercises 6.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
6.2 Solutions to Exercises 6.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
6.3 Solutions to Exercises 6.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
6.4 Solutions to Exercises 6.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

7 Systems of Linear Equations 195
7.1 Solutions to Exercises 7.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
7.2 Solutions to Exercises 7.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
7.3 Solutions to Exercises 7.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202

8 Algebraic Structures 211
8.1 Solutions to Exercises 8.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
8.2 Solutions to Exercises 8.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
8.3 Solutions to Exercises 8.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
8.4 Solutions to Exercises 8.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
8.5 Solutions to Exercises 8.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
8.6 Solutions to Exercises 8.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249

9 Introduction to Number Theory 254
9.1 Solutions to Exercises 9.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
9.2 Solutions to Exercises 9.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
9.3 Solutions to Exercises 9.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
9.4 Solutions to Exercises 9.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260

10 Boolean Algebra 262
10.1 Solutions to Exercises 10.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
10.2 Solutions to Exercises 10.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
10.3 Solutions to Exercises 10.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
10.4 Solutions to Exercises 10.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
10.5 Solutions to Exercises 10.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278

11 Graph Theory 284
11.1 Solutions to Exercises 11.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
11.2 Solutions to Exercises 11.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
11.3 Solutions to Exercises 11.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
11.4 Solutions to Exercises 11.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
11.5 Solutions to Exercises 11.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
11.6 Solutions to Exercises 11.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315

, 12 Applications of Graph Theory 321
12.1 Solutions to Exercises 12.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
12.2 Solutions to Exercises 12.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
12.3 Solutions to Exercises 12.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
12.4 Solutions to Exercises 12.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
12.5 Solutions to Exercises 12.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
12.6 Solutions to Exercises 12.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358