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