Scribd
Upload
2 views1 page

Essential Discrete Math Formulas

The document outlines key discrete math formulas related to counting, sets, relations, logic, induction, functions, and graphs. It includes definitions and properties such as factorials, permutations, combinations, and various logical equivalences. Additionally, it covers concepts of injective, surjective, and bijective functions, as well as properties of relations and graph theory.

Uploaded by

Bala Haripreetha
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
2 views1 page

Essential Discrete Math Formulas

The document outlines key discrete math formulas related to counting, sets, relations, logic, induction, functions, and graphs. It includes definitions and properties such as factorials, permutations, combinations, and various logical equivalences. Additionally, it covers concepts of injective, surjective, and bijective functions, as well as properties of relations and graph theory.

Uploaded by

Bala Haripreetha
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

Discrete Math Formulas Counting

n! = n × (n − 1) × · · · × 1 [web:2]
Sets n!
P (n, k) = (n−k)! [web:2]
n n!

A ∪ B = {x | x ∈ A ∨ x ∈ B} [web:2] C(n, k) = k = k!(n−k)! [web:2]
Pn
Binomial: (x + y) = k=0 nk xn−k y k [web:4]
n

A ∩ B = {x | x ∈ A ∧ x ∈ B} [web:2]
A \ B = {x ∈ A | x ∈ / B} [web:2]
|A ∪ B| = |A| + |B| − |A ∩ B| [web:2] Relations
P (A) = 2|A| [web:4]
R reflexive: ∀a, (a, a) ∈ R [web:5]
Symmetric: (a, b) ∈ R → (b, a) ∈ R [web:5]
Logic Transitive: (a, b), (b, c) ∈ R → (a, c) ∈ R [web:5]
¬(P ∧ Q) ≡ ¬P ∨ ¬Q (De Morgan) [web:3]
¬(P ∨ Q) ≡ ¬P ∧ ¬Q (De Morgan) [web:3] Induction
P → Q ≡ ¬P ∨ Q [web:3] Base: P (1) true [web:7]
P ↔ Q ≡ (P → Q) ∧ (Q → P ) [web:3] Assume P (k): ∀m ≤ k, P (m) [web:7]
Step: P (k) → P (k + 1) [web:7]
Functions
Graphs
f : A → B injective: ∀x1 ̸= x2 , f (x1 ) ̸= f (x2 ) [web:5]
Surjective: ∀y ∈ B, ∃x ∈ A, f (x) = y [web:5] |{u | {u, v} ∈ E}| [web:9]
Degree: d(v) =P
Bijective: injective ∧ surjective [web:5] Handshaking: d(v) = 2|E| [web:9]

You might also like