Discrete Math Formula Cheat Sheet for Logic and Sets

Discrete math formula cheat sheet includes logic, set theory, combinatorics, and graph formulas, helping in understanding computer science concepts and solving problems related to counting and structures.

Discrete Math Formula Cheat Sheet

Topic	Formula	Description
Set Union	A ∪ B	Elements in A or B
Set Intersection	A ∩ B	Common elements
Set Difference	A − B	In A not in B
Complement	A′ = U − A	Elements not in A
Subset	A ⊆ B	A inside B
Proper Subset	A ⊂ B	A strictly inside B
Power Set		P(A)
Cartesian Product	A × B	Ordered pairs
Cardinality	n(A)	Number of elements
Inclusion-Exclusion	n(A∪B)=n(A)+n(B)−n(A∩B)	Count elements
Three Sets	n(A∪B∪C)=Σn − Σn∩ + n(A∩B∩C)	Extended rule
De Morgan Laws	(A∪B)′ = A′∩B′	Set identity
De Morgan Laws	(A∩B)′ = A′∪B′	Set identity
Propositional Logic	p ∧ q	AND operation
Disjunction	p ∨ q	OR operation
Negation	¬p	NOT operation
Implication	p → q	If then
Biconditional	p ↔ q	If and only if
Tautology	Always true	Logical truth
Contradiction	Always false	Logical false
Permutation	nPr = n!/(n−r)!	Ordered arrangements
Combination	nCr = n!/[r!(n−r)!]	Unordered selection
Factorial	n! = n(n−1)…1	Product rule
Pigeonhole Principle	n items in k boxes ⇒ ≥⌈n/k⌉	Minimum distribution
Graph Degree	Σdeg(v) = 2E	Handshaking lemma
Complete Graph	Kn edges = n(n−1)/2	Fully connected
Path Length	Number of edges	Graph distance
Tree Edges	n−1	Tree property
Binary Tree Nodes	≤ 2ʰ − 1	Max nodes
Recurrence	T(n)=aT(n/b)+f(n)	General form
Master Theorem	Compare f(n) with n^(log_b a)	Solve recurrence
Divisibility	a	b if b=ak
Modular Arithmetic	a ≡ b (mod n)	Remainder relation
GCD	gcd(a,b)	Greatest divisor
LCM	(a×b)/gcd(a,b)	Least multiple
Boolean Algebra	A + A′ = 1	Identity
Boolean Algebra	A·A′ = 0	Complement rule
Boolean Algebra	A + 0 = A	Identity
Boolean Algebra	A·1 = A	Identity
Boolean Algebra	A + A = A	Idempotent
Boolean Algebra	A·A = A	Idempotent

Download PDF

Conclusion Discrete mathematics is mathematics of discrete and distinct structures. It encompasses such topics as logic, sets, graphs, and combinatorics. As opposed to continuous mathematics, discrete math concerns countable values. It is common in computer science, cryptography and data analysis. Discrete math aids in algorithms, networks and data structures. Other ideas such as graph theory and Boolean logic are fundamental in programming and technology. It enhances ability to think logically and solve problems. Computer systems and optimization problems are designed with the help of discrete mathematics. It also assists in the comprehension of associations and trends. Studying discrete math is a solid foundation to computer science and engineering. It is useful and applicable in various activities of the present. In general, discrete mathematics is a valuable discipline that is conducive to digital technology and logical thinking. To conclude, discrete mathematics is essential for computer science and logical thinking. It helps solve practical problems and supports modern technology.