Discrete Mathematics

Chapter 1 Propositional Logic 1 1.1 The Basics of Propositional Logic 1 1.1.1 Propositions and Operators 1 1.1.2 Propositional Formulas 6 1.2 Propositional Equivalence 9 1.2.1 Equivalence and Some Basic Properties 9 1.2.2 Normal Form 12 1.3 Rules of Inference and Proof for Propositional Logic 19 1.3.1 Valid Arguments 19 1.3.2 Building Arguments and Proofs 23 Exercise 1 29 Chapter 2 Predicate Logic 33 2.1 The Basics of Predicate Logic 34 2.1.1 Language of Predicate Logic 34 2.1.2 Predicate Formulas 38 2.2 Predicate Equivalences 42 2.2.1 Equivalences 42 2.2.2 Prenex Normal Form 44 2.3 Rules of Inference for Predicate Logic 45 Exercise 2 48 Chapter 3 Sets 52 3.1 The Basics of Sets 52 3.1.1 The Set Concept and Set Description 52 3.1.2 Set Equality and Relationship between Sets 53 3.1.3 Some Special Sets 54 3.2 Operations on Sets 56 3.2.1 The Basic Operation 56 3.2.2 Set Identities 58 3.3 Principle of InclusionExclusion 60 Exercise 3 62 Chapter 4 Relations 66 4.1 The Basics of Relations 66 4.1.1 Order Pairs and Cartesian Product 66 4.1.2 Concept and Representations of Binary Relations 68 4.1.3 Operations on Relations 70 4.1.4 Properties of Relations 74 4.1.5 Closures of Relations 76 4.2 Equivalence Relations 82 4.2.1 Definition of Equivalence Relations 82 4.2.2 Partitions 84 4.3 Partial Order Relations 85 4.3.1 Definition of Partial Order 85 4.3.2 Hasse Diagrams 86 4.3.3 Special Elements in Posets 88 Exercise 4 89 Chapter 5 Functions 93 5.1 The Basics of Function 93 5.1.1 Concept and Properties of Functions 93 5.1.2 Inverse Function and Composition of Functions 96 5.2 Countability of Sets 97 5.2.1 Cardinality of Sets 97 5.2.2 Countable Sets and Uncountable Sets 99 Exercise 5 101 Chapter 6 Graphs 103 6.1 The Basics of Graphs 103 6.2 Graph Terminology 109 6.2.1 The Path 109 6.2.2 Connectivity 111 6.3 Representing Graph Using Matrices 113 6.3.1 Incidence Matrices 113 6.3.2 Adjacency Matrices 115 6.3.3 Reachability Matrices 116 6.4 Tree 117 6.5 Euler Graphs and Hamilton Graphs 119 6.5.1 Euler Graphs 119 6.5.2 Hamilton Graphs 123 6.6 Planar 125 6.6.1 The Concepts of Planar 126 6.6.2 Eulers Formulas 127 6.6.3 Kuratowskis Theorem 128 Exercise 6 129 Chapter 7 Algebra 132 7.1 Algebraic Structures 132 7.1.1 Binary Operations 132 7.1.2 Algebra 133 7.2 Groups 134 7.2.1 Concept of a Group 134 7.2.2 Subgroups 135 7.3 Rings and Fields 137 Exercise 7 138 References 140