دانلود کتاب Tale of Discrete Mathematics, A: A Journey Through Logic, Reasoning, Structures and Graph Theory

فهرست مطالب :

Contents
Preface
About the Author
1. Propositional Logic: The Foundation of Mathematical Reasoning
1.1 Introduction
1.2 Basic terminologies and logic connectives
1.2.1 Logic connectives
1.2.2 Truth table
1.2.2.1 The conjunction connective
1.2.2.2 The disjunction connective
1.2.2.3 The implication connective
1.2.2.4 The biconditional connective
1.2.2.5 The negation connective
1.2.2.6 Summary
1.2.3 Operations on binary strings
1.2.4 Exercises
1.3 Propositional logic: Formal point of view
1.3.1 Valuations and truth tables of logic formulas
1.3.2 Special types of logic formulas and coherency
1.3.3 Exercises
1.4 Logic formulas in natural language: Translation between English and propositional logic
1.4.1 Logic arguments
1.4.2 Exercises
1.5 The island of knights and knaves
1.5.1 Exercises
1.6 Logical equivalence
1.6.1 Using a truth table to write an expression for a logic formula
1.6.2 Exercises
1.7 The method of truth trees
1.7.1 Description of the method
1.7.2 Tautologies and the method of truth tree
1.7.3 Exercises
1.8 Validity of logic arguments
1.8.1 Exercises
1.9 Formal proof of validity of an argument: Rules of inference for propositional logic
1.9.1 Exercises
1.10 Normal forms
1.10.1 Exercises
2. Set Theory and Introduction to Boolean Algebra: A Naïve Approach
2.1 Introduction
2.2 Basic definitions and terminology
2.2.1 Describing sets
2.2.2 Set equality: Finite and infinite sets
2.2.3 Exercises
2.3 Subsets and power set
2.3.1 Intervals in R
2.3.2 Exercises
2.4 Operations on sets
2.4.1 Intersection
2.4.2 Union
2.4.3 Difference, complement and symmetric difference
2.4.4 Cartesian product
2.4.5 Exercises
2.5 Partition of a set
2.5.1 Exercises
2.6 Introduction to Boolean algebra
2.6.1 Boolean expressions
2.6.2 Exercises
2.7 Sum of products (SOP), product of sums (POS), and Karnaugh maps
2.7.1 Sum of products (SOP)
2.7.2 Product of sums (POS)
2.7.3 Karnaugh maps
2.7.4 Two-variable Karnaugh maps
2.7.5 Three-variable Karnaugh maps
2.7.6 Four-variable Karnaugh maps
2.7.7 Using Karnaugh to minimize a Boolean expression
2.7.8 Exercises
2.8 Logic gates
2.8.1 Exercises
3. Prove It: Mathematical Proof Techniques
3.1 Introduction
3.2 Proving an implication and a biconditional
3.2.1 Direct proof
3.2.2 Indirect proof
3.2.3 Exercises
3.3 Proving a biconditional
3.3.1 Exercises
3.4 Proof by contradiction
3.4.1 Exercises
3.5 Proof by separation of cases
3.5.1 Exercises
3.6 Proof by induction
3.6.1 The principle of weak induction
3.6.2 The principle of strong induction
3.6.3 Exercises
3.7 Recursive definition of sets and the principle of structural induction
3.7.1 Exercises
4. Introduction to Predicate Logic: One Step Further
4.1 Introduction
4.2 The basics of predicate logic
4.2.1 Exercises
4.3 Quantifiers: The language of predicate logic
4.3.1 Negation of a quantified statement
4.3.2 Multiple quantifiers
4.3.3 Syntax of the predicate logic language
4.3.4 Exercises
4.4 Translation from and to predicate logic
4.4.1 Exercises
4.5 Scope of a quantifier, bound and free variables
4.5.1 Exercises
4.6 Interpretation
4.6.1 Exercises
4.7 Reasoning with quantifiers: Arguments of predicate logic
4.7.1 The universal instantiation (UI)
4.7.2 The universal generalization (UG)
4.7.3 The existential instantiation (EI)
4.7.4 The existential generalization (EG)
4.7.5 Arguments of predicate logic
4.7.6 Exercises
5. Functions: Back to the Basics
5.1 Introduction
5.2 Basic definitions and terminology
5.2.1 Combining real-valued functions
5.2.2 Exercises
5.3 Some special functions
5.3.1 Exercises
5.4 Binary operations
5.4.1 Exercises
5.5 Functions defined recursively
5.5.1 Exercises
5.6 Injective, surjective and bijective functions
5.6.1 Exercises
5.7 Composition of functions and invertible functions
5.7.1 Invertible functions
5.7.2 Exercises
6. Elementary Number Theory
6.1 Introduction
6.2 Integers defined axiomatically
6.2.1 Order on the integers
6.2.2 Exercises
6.3 Division in Z: Prime numbers
6.3.1 Exercises
6.4 The division algorithm
6.4.1 Representing integers in different bases
6.4.2 Exercises
6.5 The Fundamental Theorem of Arithmetic, the gcd, the lcm and the Euclidean algorithm
6.5.1 The least common multiple
6.5.2 Finding the gcd and the lcm
6.5.2.1 Using the Fundamental Theorem of Arithmetic to find the gcd and the lcm
6.5.2.2 The Euclidean algorithm
6.5.3 Exercises
6.6 Introduction to modular arithmetic
6.6.1 Linear congruence equations
6.6.2 The Chinese remainder theorem
6.6.3 Exercises
6.7 The Euler phi function
6.7.1 Exercises
6.8 Caesar cipher: The RSA algorithm
6.8.1 The RSA scheme
6.8.2 Exercises
7. Binary Relations
7.1 Introduction
7.2 Basic definitions and terminology
7.2.1 Exercises
7.3 Representations of binary relations: Boolean matrices
7.3.1 Properties of Boolean matrices
7.3.2 Exercises
7.4 Functions as relations
7.4.1 Exercises
7.5 New relations from old
7.5.1 Composition of relations
7.5.2 Exercises
7.6 Paths and connectivity
7.6.1 Exercises
7.7 Properties of binary relations
7.7.1 Exercises
7.8 Closures of a relation
7.8.1 Warshall\'s algorithm
7.8.2 Exercises
7.9 Equivalence relations
7.9.1 Equivalence classes and partition of a set
7.9.2 Well-defined operations on the quotient set
7.9.3 Equivalence relation generated by an arbitrary relation
7.9.4 Exercises
7.10 Order relation
7.10.1 Digraph of a partial order: The Hasse diagram
7.10.2 Total order
7.10.3 Exercises
7.11 Special elements in a poset, lattices, well-ordering principle and topological sorting
7.11.1 Lattices
7.11.2 The well-ordering principle and the well-ordered sets
7.11.3 Application: The topological sorting
7.11.4 Exercises
8. Basic Combinatorics: The Art of Counting Without Counting
8.1 Introduction
8.2 Basic counting principles
8.2.1 The sum principle
8.2.2 The product principle
8.2.3 The principle of inclusion–exclusion
8.2.4 Exercises
8.3 The pigeonhole principle
8.3.1 Exercises
8.4 Permutation
8.4.1 Permutation without repetition
8.4.2 Circular permutation
8.4.3 Permutations of objects not all distinct
8.4.4 Permutations with repetitions
8.4.5 Exercises
8.5 Combinations
8.5.1 Number of surjective functions: Derangements
8.5.2 Exercises
8.6 The binomial theorem
8.6.1 Exercises
8.7 Combinations with repetition
8.7.1 Exercises
9. Basics of Graph Theory
9.1 Introduction and a bit of history
9.2 Basic definitions and terminology
9.2.1 Some common simple graphs
9.2.2 Adjacency and incidence matrices
9.2.3 Exercises
9.3 Degree of a vertex, the Handshaking lemma and graphical sequences
9.3.1 Graphical sequences
9.3.2 Exercises
9.4 Subgraphs and new graphs from old
9.4.1 Induced and spanning subgraphs
9.4.2 New subgraphs from old
9.4.3 Complement of a graph
9.4.4 Line graph, Hamiltonian closure of a graph
9.4.5 Exercises
9.5 Walks, trails, paths, cycles and graph connectivity
9.5.1 Graph connectivity
9.5.2 Vertex-connectivity, edge-connectivity
9.5.3 Exercises
9.6 Bipartite graphs
9.6.1 Exercises
9.7 Matching
9.7.1 Matching in general graphs
9.7.2 Exercises
9.8 Matching in bipartite graphs and Hall\'s Theorem
9.8.1 Exercises
9.9 Isomorphism of simple graphs
9.9.1 Exercises
9.10 Maximum ow in a network, the Ford–Fulkerson algorithm and maximum bipartite matching
9.10.1 Residual network
9.10.2 The Max-Flow Min-Cut theorem, the Ford–Fulkerson algorithm
9.10.3 Maximum bipartite matching
9.10.4 Exercises
10. More on Graph Theory
10.1 Planar graphs
10.1.1 Kuratowski\'s theorem
10.1.2 Exercises
10.2 Euler trails and Euler circuits
10.2.1 Exercises
10.3 Hamiltonian circuits and Hamiltonian paths
10.3.1 Exercises
10.4 Graph coloring
10.4.1 The chromatic polynomial
10.4.2 Coloring planar graphs: Five and four-color theorems
10.4.3 Exercises
11. Trees
11.1 Introduction
11.2 Basic definitions and terminology
11.2.1 Exercises
11.3 First results about trees
11.3.1 Exercises
11.4 Traversal of trees
11.4.1 Binary search tree
11.4.2 Exercises
11.5 Modeling with trees
11.5.1 Chemistry
11.5.2 Digital arithmetic expressions
11.5.3 Prefix, postfix and infix notations
11.5.4 Coding
11.5.4.1 Using binary trees to represent binary codes
11.5.5 Exercises
11.6 Spanning subtrees and graph search
11.6.1 Graph search
11.6.1.1 Depth-First search (DFS)
11.6.1.2 Breadth-First search
11.6.2 Search algorithms and graph connectivity
11.6.3 Minimal spanning tree
11.6.3.1 Kruskal\'s algorithm
11.6.3.2 Prim\'s algorithm
11.6.4 Exercises
Appendix: Solutions to Suggested Exercises
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
1.10
2.2
2.3
2.4
2.5
2.6
2.7
2.8
3.2
3.3
3.4
3.5
3.6
3.7
4.2
4.3
4.4
4.5
4.6
4.7
5.2
5.3
5.4
5.5
5.6
5.7
6.2
6.3
6.4
6.5
6.6
6.7
6.8
7.2
7.3
7.4
7.5
7.6
7.7
7.8
7.9
7.10
7.11
8.2
8.3
8.4
8.5
8.6
9.2
9.3
9.4
9.5
9.6
9.7
9.8
9.9
9.10
10.1
10.2
10.3
10.4
11.2
11.3
11.4
11.5
11.6
Index