 | Garnier R. Discrete mathematics: proofs, structures, and applications / R.Garnier, J.Taylor. - 3rd ed. - Boca Raton: CRC Press, 2010. - xxi, 821 p.: ill. - Ind.: p.798-821. - ISBN 978-1-4398-1280-8
|
Preface to the Third Edition ................................... ix
Preface to the Second Edition .................................. xi
Preface to the First Edition ................................. xiii
List of Symbols .............................................. xvii
Chapter 1: Logic ................................................ 1
1.1 Propositions and Truth Values .............................. 1
1.2 Logical Connectives and Truth Tables ....................... 2
1.3 Tautologies and Contradictions ............................ 13
1.4 Logical Equivalence and Logical Implication ............... 15
1.5 The Algebra of Propositions ............................... 22
1.6 Arguments ................................................. 26
1.7 Formal Proof of the Validity of Arguments ................. 29
1.8 Predicate Logic ........................................... 35
1.9 Arguments in Predicate Logic .............................. 45
Chapter 2: Mathematical Proof .................................. 50
2.1 The Nature of Proof ....................................... 50
2.2 Axioms and Axiom Systems .................................. 51
2.3 Methods of Proof .......................................... 55
2.4 Mathematical Induction .................................... 69
Chapter 3: Sets ................................................ 79
3.1 Sets and Membership ....................................... 79
3.2 Subsets ................................................... 85
3.3 Operations on Sets ........................................ 91
3.4 Counting Techniques ...................................... 100
3.5 The Algebra of Sets ...................................... 104
3.6 Families of Sets ......................................... 111
3.7 The Cartesian Product .................................... 122
3.8 Types and Typed Set Theory ............................... 134
Chapter 4: Relations .......................................... 154
4.1 Relations and Their Representations ...................... 154
4.2 Properties of Relations .................................. 164
4.3 Intersections and Unions of Relations .................... 171
4.4 Equivalence Relations and Partitions ..................... 175
4.5 Order Relations .......................................... 188
4.6 Hasse Diagrams ........................................... 198
4.7 Application: Relational Databases ........................ 205
Chapter 5: Functions .......................................... 220
5.1 Definitions and Examples ................................. 220
5.2 Composite Functions ...................................... 238
5.3 Injections and Surjections ............................... 246
5.4 Bijections and Inverse Functions ......................... 260
5.5 More on Cardinality ...................................... 270
5.6 Databases: Functional Dependence and Normal Forms ........ 277
Chapter 6: Matrix Algebra ..................................... 291
6.1 Introduction ............................................. 291
6.2 Some Special Matrices .................................... 294
6.3 Operations on Matrices ................................... 296
6.4 Elementary Matrices ...................................... 308
6.5 The Inverse of a Matrix .................................. 318
Chapter 7: Systems of Linear Equations ........................ 331
7.1 Introduction ............................................. 331
7.2 Matrix Inverse Method .................................... 337
7.3 Gauss-Jordan Elimination ................................. 342
7.4 Gaussian Elimination ..................................... 355
Chapter 8: Algebraic Structures ............................... 361
8.1 Binary Operations and Their Properties ................... 361
8.2 Algebraic Structures ..................................... 370
8.3 More about Groups ........................................ 379
8.4 Some Families of Groups .................................. 384
8.5 Substructures ............................................ 396
8.6 Morphisms ................................................ 404
8.7 Group Codes .............................................. 418
Chapter 9: Introduction to Number Theory ...................... 436
9.1 Divisibility ............................................. 437
9.2 Prime Numbers ............................................ 449
9.3 Linear Congruences ....................................... 460
9.4 Groups in Modular Arithmetic ............................. 473
9.5 Public Key Cryptography .................................. 479
Chapter 10: Boolean Algebra ................................... 492
10.1 Introduction ............................................. 492
10.2 Properties of Boolean Algebras ........................... 496
10.3 Boolean Functions ........................................ 503
10.4 Switching Circuits ....................................... 520
10.5 Logic Networks ........................................... 529
10.6 Minimization of Boolean Expressions ...................... 536
Chapter 11 Graph Theory ...................................... 548
11.1 Definitions and Examples ................................. 548
11.2 Paths and Cycles ......................................... 561
11.3 Isomorphism of Graphs .................................... 575
11.4 Trees .................................................... 582
11.5 Planar Graphs ............................................ 591
11.6 Directed Graphs .......................................... 600
Chapter 12: Applications of Graph Theory ...................... 611
12.1 Introduction ............................................. 611
12.2 Rooted Trees ............................................. 612
12.3 Sorting .................................................. 626
12.4 Searching Strategies ..................................... 643
12.5 Weighted Graphs .......................................... 652
12.6 The Shortest Path and Travelling Salesman Problems ....... 660
12.7 Networks and Flows ....................................... 673
References and Further Reading ................................ 687
Hints and Solutions to Selected Exercises ..................... 692
Index ......................................................... 798
|
|
