Discrete Mathematics - Formula & Short Notes
Unit I: Logic and Proofs
Propositional Logic: Deals with statements that are either true or false.
Logical Connectives: (and), (or), (not), (implies), (if and only if)
Truth Tables: Used to determine equivalences and validity.
Propositional Equivalences: Laws like De Morgan's, Double Negation, Contrapositive.
Quantifiers: (for all), (there exists)
Direct Proof: Use known facts and logical steps.
Contrapositive Proof: Prove Q P instead of P Q.
Vacuous Proof: If P is false, P Q is true.
Trivial Proof: If Q is true, P Q is true.
Proof by Contradiction: Assume negation of statement and derive contradiction.
Counterexample: One case where the statement fails.
Common Mistakes: Misuse of logical laws, assuming what you want to prove.
Discrete Mathematics - Formula & Short Notes
Unit II: Recurrence Relations
Recurrence Relation: Equation that defines sequence recursively.
Linear Homogeneous Recurrence: a_n = c1*a_{n-1} + c2*a_{n-2} + ... + ck*a_{n-k}
Non-Homogeneous: Has additional term like f(n).
Inverse Operator Method: Solve recurrence using operator algebra.
Generating Functions: G(x) = a0 + a1*x + a2*x^2 + ...
Solving using Generating Functions: Multiply both sides by x^n, sum, and simplify.
Discrete Mathematics - Formula & Short Notes
Unit III: Counting Principles and Relations
Inclusion-Exclusion: |A B| = |A| + |B| - |A B|
Pigeonhole Principle: If n+1 items in n boxes, at least one box has 2 items.
Generalized Pigeonhole: If N items in k boxes, one box has at least N/k items.
Relations: Set of ordered pairs.
Matrix Representation: 1 if (a,b) R, else 0.
Graph Representation: Nodes and edges.
Equivalence Relation: Reflexive, Symmetric, Transitive.
Partial Order: Reflexive, Antisymmetric, Transitive.
Lattice: Every pair has a lub and glb.
Hasse Diagram: Visual representation of poset.
Discrete Mathematics - Formula & Short Notes
Unit IV: Graph Theory I
Terminologies: Vertex, edge, degree, path, cycle.
Special Graphs: Complete (K_n), Cycle (C_n), Wheel (W_n), Cube, Bipartite, K_{m,n}
Representation: Adjacency matrix, incidence matrix.
Isomorphism: Graphs with same structure.
Connectivity: Path between nodes.
Dijkstras Algorithm: Greedy approach to find shortest path.
Discrete Mathematics - Formula & Short Notes
Unit V: Graph Theory II
Planar Graph: Can be drawn without edge crossings.
Euler Formula: V - E + F = 2 (for connected planar graph)
Coloring: Assign colors such that adjacent vertices differ.
Chromatic Number: Minimum number of colors.
Tree: Acyclic connected graph.
Rooted Tree: Tree with a designated root node.
Spanning Tree: Subgraph that is a tree including all vertices.
Minimum Spanning Tree: Tree with minimum total edge weight.
Traversals: Infix, Prefix, Postfix.
Discrete Mathematics - Formula & Short Notes
Unit VI: Number Theory & Cryptography
Divisibility: a divides b if b = ka.
Modular Arithmetic: a b (mod m)
GCD, LCM: Greatest and Least common multiple.
Euclidean Algorithm: Iterative method for GCD.
Bezout's Lemma: ax + by = gcd(a, b)
Linear Congruence: ax b (mod m)
Inverse Modulo: Find x such that ax 1 (mod m)
Chinese Remainder Theorem: Solve system of congruences.
Ciphers: Caesar (shift), Affine (ax + b mod m)
Fermats Little Theorem: a^(p1) 1 mod p, p is prime.
