KEMBAR78
Discrete Math Cheat Sheet | PDF
Scribd
Upload
296 views2 pages

Discrete Math Cheat Sheet

The document provides an overview of core concepts in discrete mathematics, including logic, set theory, functions, combinatorics, number theory, graph theory, recurrence relations, mathematical induction, algorithms, and Boolean algebra. Each section includes definitions, examples, and key principles such as the counting principle, GCD calculation, and algorithm complexity. The content serves as a foundational guide for understanding discrete mathematical structures and their applications.

Uploaded by

darekarpruthvi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
296 views2 pages

Discrete Math Cheat Sheet

The document provides an overview of core concepts in discrete mathematics, including logic, set theory, functions, combinatorics, number theory, graph theory, recurrence relations, mathematical induction, algorithms, and Boolean algebra. Each section includes definitions, examples, and key principles such as the counting principle, GCD calculation, and algorithm complexity. The content serves as a foundational guide for understanding discrete mathematical structures and their applications.

Uploaded by

darekarpruthvi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

DISCRETE MATHEMATICS - CORE THEORY + EXAMPLES

1. LOGIC & PROPOSITIONAL CALCULUS


---------------------------------
Proposition: Statement that is either True or False.
Operators:
NOTP (NOT), P AND Q (AND), P OR Q (OR), P -> Q (IMPLIES), P <-> Q (IFF)

Example:
P: It is raining.
Q: I stay home.
P -> Q means: If it is raining, I stay home.

2. SET THEORY
-------------
A = {1, 2, 3}, B = {3, 4, 5}
A union B = {1,2,3,4,5} (Union)
A intersection B = {3} (Intersection)
A - B = {1,2} (Difference)
P(A) = Power set of A

3. FUNCTIONS & RELATIONS


------------------------
Function: f(x) = x^2
Injective: One-to-one
Surjective: Onto
Bijective: Both

Relation: R = {(1,2), (2,3), (3,3)}


Reflexive? No (missing (1,1), (2,2))
Symmetric? No
Transitive? Yes

4. COMBINATORICS
----------------
Counting Principle: If 3 shirts and 2 pants, total = 3 * 2 = 6

Permutations: P(5, 3) = 60
Combinations: C(5, 3) = 10

Binomial Theorem:
(x + y)^2 = C(2,0)x^2 + C(2,1)xy + C(2,2)y^2

5. NUMBER THEORY
----------------
GCD(48, 18) using Euclidean Algorithm:
48 % 18 = 12
18 % 12 = 6
12 % 6 = 0 -> GCD = 6

Modular Arithmetic:
17 == 2 mod 5

6. GRAPH THEORY
---------------
Graph G = (V, E)
V = {A, B, C}
E = {(A,B), (B,C)}

Degree of B = 2

DFS Traversal: A -> B -> C


Bipartite: Yes if no odd-length cycles

7. RECURRENCE RELATIONS
-----------------------
T(n) = T(n-1) + 2, T(1) = 1
T(2) = 3, T(3) = 5...

Closed form: T(n) = 2n - 1

8. MATHEMATICAL INDUCTION
-------------------------
Prove: 1 + 2 + ... + n = n(n+1)/2

Base case: n = 1 -> 1 = 1(1+1)/2 = 1


Inductive step: Assume for n, prove for n+1

9. ALGORITHMS & COMPLEXITY


--------------------------
Bubble Sort = O(n^2)
Binary Search = O(log n)
Merge Sort = O(n log n)
Big-O: Worst-case upper bound

10. BOOLEAN ALGEBRA


-------------------
A = 0, B = 1
A AND B = 0
A OR B = 1
NOTA = 1

De Morgan:
NOT(A AND B) = NOTA OR NOTB

Simplify expressions using truth tables or Karnaugh maps

You might also like