Discrete Mathematics

1. Introduction to Discrete Mathematics and Propositional Logic 1; 1.1 Discrete MathematicsA Brief Introduction; 1.2 Introduction to Propositional Logic; 1.3 Proposition; 1.4 Logical Operators; 1.4.1 Negation (~); 1.4.2 Disjunction (OR/?); 1.4.3 Exclusive OR; 1.4.4 Conjunction (and/?); 1.4.5 Conditional (?); 1.4.6 Biconditional (?); 1.4.7 NAND (?); 1.4.8 NOR (?); 1.4.9 Well-formed Formula; 1.4.10 Rules of Precedence; 1.5 Tautology; 1.6 Contradiction; 1.7 Logical Equivalence; 1.8 Tautological Implication; 1.9 Converse, Inverse, and Contrapositive; 1.10 Functionally Complete Set of Connectives; 1.11 Normal Forms; 1.11.1 Elementary Product; 1.11.2 Elementary Sum; 1.11.3 Disjunctive Normal Form; 1.11.4 Conjunctive Normal Form; 1.11.5 Principal Disjunctive Normal Form; 1.11.6 Principal Conjunctive Normal Form; 1.12 Argument; 1.12.1 Checking the Validity of an Argument by Constructing Truth Table; 1.12.2 Checking the Validity of an Argument without Constructing Truth Table; 1.13 Predicates; 1.13.1 Quantifiers; 1.13.2 Free and Bound Variables; 1.13.3 Negation of Quantifiers; 1.13.4 Removing Quantifiers from Predicates; 1.14 Nested Quantifiers; 1.14.1 Effect of Order of Quantifiers; 1.15 Inference Theory of Predicate Calculus; 1.15.1 Universal Specification; 1.15.2 Existential Specification; 1.15.3 Universal Generalization; 1.15.4 Existential Generalization; 1.15.5 Substitution; 1.15.6 First-order and Second-order Logic; 1.16 Methods of Proof; 1.16.1 Trivial Proof; 1.16.2 Vacuous Proof; 1.16.3 Direct Proof; 1.16.4 Proof by Contradiction; 1.16.5 Proof by Contraposition; 1.16.6 Proof by Cases; 1.16.7 Exhaustive Proof; 1.16.8 Proof by Mathematical Induction; 1.16.9 Proof by Minimal Counter Example; 1.17 Satisfiability and Consistency; 1.18 Mechanization of Reasoning; 1.18.1 Russells Paradox; 2. Set Theory; 2.1 Introduction; 2.2 Sets; 2.2.1 Roster Notation; 2.2.2 Set-builder Notation; 2.2.3 Cardinality of Sets; 2.3 Some Standard Sets; 2.3.1 Empty Set; 2.3.2 Singleton Set; 2.3.3 Finite and Infinite Sets; 2.3.4 Countable and Uncountable Sets; 2.3.5 Universal Set; 2.4 Subset and Proper Subset; 2.5 Equality of Sets; 2.6 Power Set; 2.7 Venn Diagrams; 2.8 Operations on Sets; 2.8.1 Union; 2.8.2 Intersection; 2.8.3 Difference of Two Sets; 2.8.4 Symmetric Difference of Two Sets; 2.8.5 Complement of a Set; 2.8.6 Generalized Union and Intersection; 2.9 Some Other Classes of Sets; 2.9.1 Disjoint Sets; 2.9.2 Partition; 2.9.3 Ordered Set; 2.9.4 Cartesian Product of Sets; 2.10 Algebra of Sets; 2.11 Multisets; 2.12 Fuzzy Sets; 2.12.1 Operations on Fuzzy Sets; 2.12.2 ?? Cut and Strong ?? Cut; 2.12.3 Support, Core, and Height of Fuzzy Sets; 3.Relations; 3.1 Introduction; 3.2 Relation; 3.2.1 Domain and Range; 3.2.2 Inverse of Relation; 3.3 Combining Relations; 3.3.1 Composition of Relations; 3.4 Different Types of Relations; 3.4.1 Reflexive Relation; 3.4.2 Symmetric Relation; 3.4.3 Transitive Relation; 3.4.4 Compatible Relation; 3.4.5 Equivalence Relation; 3.4.6 Irreflexive Relation; 3.4.7 Asymmetric Relation; 3.4.8 Anti-symmetric Relation; 3.4.9 Partial Order Relation; 3.5 Pictorial or Graphical Representation of Relations; 3.6 Matrix Representation of Relations; 3.7 Closure of Relations; 3.7.1 Reflexive Closure; 3.7.2 Symmetric Closure; 3.7.3 Transitive Closure; 3.8 Warshalls Algorithm; 3.9 n-Ary Relations; 4. Functions; 4.1 Introduction; 4.2 Definition of Function; 4.3 Relations Vs Functions; 4.4 Types of Functions; 4.4.1 OneOne Function; 4.4.2 ManyOne Function; 4.4.3 Onto Function; 4.4.4 Identity Function; 4.4.5 Constant Function; 4.4.6 Invertible Function; 4.5 Composition of Functions; 4.6 Sum and Product of Functions; 4.7 Functions Used in Computer Science; 4.7.1 Floor Function; 4.7.2 Ceiling Function; 4.7.3 Remainder Function/Modular Arithmetic; 4.7.4 Characteristic Function; 4.7.5 Hash Function; 4.8 Collision Resolution; 4.8.1 Open Addressing; 4.8.2 Chaining; 4.9 Investigation of Functions; 5. Properties of Integers; 5.1 Introduction; 5.2 Basic Properties of Z; 5.3 Well-Ordering Principle; 5.4 Elementary Divisibility Properties; 5.5 Greatest Common Divisor; 5.6 Least Common Multiple; 5.7 Linear Diophantine Equation; 5.8 Fundamental Theorem of Arithmetic; 5.8.1 Primes and Composites; 5.8.2 Relatively Prime Integers; 5.9 Congruence Relation; 5.10 Residue Classes; 5.11 Linear Congruence; 6. Counting Techniques; 6.1 Introduction; 6.2 Basic Counting Principle; 6.2.1 Sum Rule; 6.2.2 Product Rule; 6.2.3 InclusionExclusion Principle; 6.3 Permutations and Combinations; 6.3.1 Permutation; 6.3.2 Combination; 6.4 Generalized Permutation and Combination; 6.4.1 Permutation with Repetition; 6.4.2 Permutations with Identical Objects; 6.4.3 Combination with Repetition; 6.5 Binomial Coefficients; 6.6 Partition; 6.7 Pigeonhole Principle; 6.7.1 Generalized Pigeonhole Principle; 6.8 Arrangements with Forbidden Positions; 6.8.1 Rook Polynomial; 6.8.2 Derangement; 7. Fundamentals of Probability; 7.1 Introduction; 7.2 Random Experiment; 7.3 Sample Space; 7.4 Event; 7.4.1 Equally Likely Events; 7.4.2 Mutually Exclusive Events; 7.4.3 Exhaustive Events; 7.4.4 Independent Events; 7.4.5 Dependent Events; 7.4.6 Complementary Event; 7.5 Measurement of Probability; 7.5.1 Classical or Priori Approach of Probability; 7.5.2 Relative Frequency Approach of Probability; 7.6 Axioms of Probability; 7.7 Conditional Probability; 7.8 Bayes Theorem; 7.9 Discrete Probability Distributions; 7.9.1 Expectation of Random Variable; 7.9.2 Variance and Standard Deviation of Random Variables; 7.9.3 Binomial Distribution; 7.9.4 Poisson Distribution; 7.9.5 Negative Binomial Distribution; 7.9.6 Geometric Distribution; 8. Discrete Numeric Functions and Generating Functions; 8.1 Introduction; 8.2 Manipulation of Numeric Functions; 8.2.1 Sum and Product of Two Numeric Functions; 8.2.2 Multiplication with Scalar; 8.2.3 Modulus of Numeric Function; 8.2.4 Siar and S-iar of Numeric Function; 8.2.5 Forward and Backward Differences of Numeric Functions; 8.2.6 Accumulated Sum; 8.2.7 Convolution of Two Numeric Functions; 8.3 Generating Functions; 8.3.1 Properties of Generating Functions; 8.3.2 Solution of Combinatorial Problems Using Generating Functions; 9. Recurrence Relations; 9.1 Introduction; 9.2 Recursive Definition; 9.2.1 Recursively Defined Functions; 9.2.2 Recursively Defined Sets; 9.3 Recurrence Relation; 9.4 Solution of Recurrence Relations; 9.4.1 Iterative Method; 9.4.2 Recursive Method; 9.4.3 Generating Function; 9.5 Structural Induction; 9.6 Order and Degree of Recurrence Relations; 9.7 Linear Recurrence Relation with Constant Coefficients; 9.7.1 Linear Homogeneous Recurrence Relation with Constant Coefficients; 9.7.2 Linear Non-homogeneous Recurrence Relation with Constant Coefficients; 10. Algebraic Structures; 10.1 Introduction; 10.2 Binary Operations; 10.2.1 Semi-Group; 10.2.2 Monoid; 10.2.3 Group; 10.3 Addition and Multiplication Modulo m; 10.4 Subgroup; 10.4.1 Cosets; 10.5 Permutations and Symmetric Group; 10.5.1 Cyclic Permutation; 10.5.2 Stabilizer of an Element; 10.5.3 Orbit of an Element; 10.5.4 Invariant Elements under Permutation; 10.6 Cyclic Group; 10.7 Normal Subgroup; 10.8 Quotient Group; 10.9 Dihedral Group; 10.10 Homomorphism and Isomorphism; 10.10.1 Kernel of Homomorphism; 10.11 Ring; 10.11.1 Commutative Ring; 10.11.2 Ring with Unity; 10.11.3 Zero Divisor of a Ring; 10.11.4 Subrings; 10.11.5 Ring Homomorphism; 10.12 Integral Domain; 10.13 Division Ring or Skew Field; 10.14 Field; 10.15 Polynomial Ring; 10.16 Boolean Algebra; 10.16.1 Duality; 10.16.2 Boolean Functions; 10.16.3 Simplification of Boolean Functions; 10.16.4 Canonical Form; 10.16.5 Standard Form; 10.16.6 Other Logic Operations; 10.16.7 Karnaugh Map; 10.16.8 QuineMccluskey Method; 10.16.9 Free Boolean Algebra; 11. Posets and Lattices; 11.1 Introduction; 11.2 Partially Ordered Set; 11.3 Diagrammatic Representation of Poset (Hasse Diagram); 11.4 Elements in Posets; 11.4.1 Least and Greatest Elements; 11.4.2 Minimal and Maximal Elements; 11.4.3 Lower and Upper Bounds; 11.4.4 Greatest Lower Bound and Least Upper Bounds; 11.5 Linearly Ordered Set; 11.6 Well-Ordered Set; 11.7 Product Order; 11.8 Lexicographic Order; 11.9 Topological Sorting and Consistent Enumeration; 11.10 Isomorphism; 11.11 Lattices; 11.12 Properties of Lattices; 11.12.1 Principle of Duality; 11.12.2 Sublattice; 11.13 Some Special Lattices; 11.13.1 Modular Lattice; 11.13.2 Distributive Lattice; 11.13.3 Bounded Lattice; 11.13.4 Complemented Lattice; 11.13.5 Complete Lattice; 11.14 Product of Lattices; 11.15 Lattice Homomorphism; 11.16 Boolean Algebra and Lattices; 11.17 Stones Representation Theorem; 12. Formal Languages and Finite Automata; 12.1 Introduction; 12.2 Alphabet and Words; 12.3 Language; 12.4 Operations on Languages; 12.5 Finite Automata; 12.5.1 Deterministic Finite State Automata; 12.5.2 Non-Deterministic Finite Automata; 12.5.3 Conversion from Non-Deterministic Finite Automata to Deterministic Finite Automata; 12.5.4 Minimization of Finite Automata; 12.6 Finite Automata with Outputs; 12.6.1 Mealy Machine; 12.6.2 Moore Machine; 12.6.3 Equivalence of Mealy and Moore Machines; 12.6.4 Conversion from Mealy to Moore Machine; 12.6.5 Conversion from Moore to Mealy Machine; 12.7 Regular Expression; 12.8 Regular Expression and Finite Automata; 12.9 Generalized Transition Graph; 12.10 Grammar of Formal Languages; 12.10.1 Phrase Structure Grammar; 12.10.2 Chomsky Hierarchy; 12.11 Other Machines; 13. Graph Theory; 13.1 Introduction; 13.2 Graph and its Related Definitions; 13.3 Different Types of Graphs; 13.3.1 Simple Graph; 13.3.2 Multigraph, Trivial Graph, and Null Graph; 13.3.3 Complete Graph; 13.3.4 Regular Graph; 13.3.5 Bipartite Graph; 13.3.6 Weighted Graph; 13.4 Subgraphs; 13.5 Operations on Graphs; 13.5.1 Union of Two Graphs; 13.5.2 Intersection of Two Graphs; 13.5.3 Ring Sum of Two Graphs; 13.5.4 Decomposition of a Graph; 13.5.5 Deletion of a Vertex; 13.5.6 Deletion of an Edge; 13.5.7 Complement of a Graph; 13.6 Walk, Path, and Circuit; 13.6.1 Walk; 13.6.2 Path; 13.6.3 Circuit; 13.7 Connected Graph, Disconnected Graph, and Components; 13.8 Homomorphism and Isomorphism of Graphs; 13.9 Homeomorphic Graphs; 13.10 Euler and Hamiltonian Graphs; 13.10.1 Euler Line and Euler Graph; 13.10.2 Hamiltonian Path and Hamiltonian Circuit; 13.10.3 Travelling Salesman Problem; 13.11 Planar Graph; 13.11.1 Kuratowskis Two Graphs; 13.11.2 Region and its Degree; 13.11.3 Eulers Formula; 13.12 Tree; 13.12.1 Rooted Tree; 13.12.2 Binary Tree; 13.12.3 Height of Binary Tree; 13.12.4 Spanning Tree; 13.12.5 Branch and Chord; 13.12.6 Rank and Nullity; 13.12.7 Fundamental Circuits; 13.12.8 Finding All Spanning Trees of a Graph; 13.12.9 Spanning Trees in a Weighted Graph; 13.12.10 Kruskals Algorithm; 13.12.11 Prims Algorithm; 13.12.12 Dijkstra Algorithm; 13.12.13 Binary Search Tree; 13.13 Cut Set and Cut Vertex; 13.14 Colouring of Graphs; 13.14.1 Chromatic Number; 13.14.2 Chromatic Partitioning; 13.14.3 Independence Set and Maximal Independence Set; 13.14.4 Maximum Independence Set and Independence Number; 13.14.5 Clique and Maximal Clique; 13.14.6 Maximum Clique and Clique Number; 13.14.7 Perfect Graph; 13.14.8 Chromatic Polynomial; 13.14.9 Applications of Graph Colouring; 13.15 Matching; 13.15.1 Maximal Matching, Maximum Matching, and Matching Number; 13.15.2 Perfect Matching; 13.16 Matrix Representation of Graphs; 13.16.1 Incidence Matrix; 13.16.2 Circuit Matrix; 13.16.3 Cut Set Matrix; 13.16.4 Path Matrix; 13.16.5 Adjacency Matrix; 13.17 Traversal of Graphs; 13.17.1 Breadth-First Search; 13.17.2 Depth-First Search; 13.18 Traversing Binary Trees; 13.18.1 Pre-Order Traversal; 13.18.2 In-Order Traversal; 13.18.3 Post-Order Traversal; 13.19 Digraph or Directed Graph; 13.20 Network Flow; 13.20.1 Cut in a Transport Network; 13.20.2 Flow Augmenting Path; 13.21 Enumeration of Graphs; 14. Applications of Discrete Mathematical Structures; 14.1 Introduction; 14.2 Asymptotic Behaviour of Numeric Functions; 14.2.1 Big-Oh (O) Notation; 14.2.2 Omega (?) Notation; 14.2.3 Theta (q) Notation; 14.3 Analysis of Algorithms; 14.3.1 Space Complexity; 14.3.2 Time Complexity; 14.4 Analysis of Sorting Algorithms; 14.4.1 Insertion Sort; 14.4.2 Bubble Sort; 14.4.3 Selection Sort; 14.5 Divide-and-Conquer Approach; 14.5.1 Merge Sort; 14.5.2 Quick Sort; 14.6 Analysis of Searching Algorithms; 14.6.1 Linear Search; 14.6.2 Binary Search; 14.7 Tractable and Intractable Problems; 14.8 Logic Gates; 14.8.1 Switching Circuits and Logic Gates; 14.8.2 NAND and NOR Implementations; 14.9 Combinational Circuits; 14.9.1 Half Adder; 14.9.2 Full Adder; 14.9.3 Half Subtractor; 14.9.4 Full Subtractor; 14.10 Information and Coding Theory; 14.10.1 Discrete Information Sources; 14.10.2 Entropy; 14.10.3 Mutual Information; 14.10.4 Coding Theory; 14.10.5 Hamming Distance; 14.10.6 Error-Detecting and Error-Correcting Codes; 14.10.7 Group Codes; 14.10.8 Generator Matrices; 14.10.9 Parity Check Matrices; 14.10.10 Coset Decoding; 14.10.11 Prefix Codes; 14.10.12 Cyclic Code; Appendices