Discrete Maths Proofs, Theorems/Rules, and Definitions to Memorize

PCC Math 022 Final Exams Pavitch

Universal Quantification

The universal quantification of P(x) is the statement
“P(x) for all values of x in the domain.”
The notation ∀xP(x) denotes the universal quantification of P(x). Here ∀ is called the universal quantifier. We read ∀xP(x) as “for all xP(x)” or “for every xP(x)”. An element for which P(x) is false is called a counterexample to ∀xP(x).

Function

Let A and B be nonempty sets. A function f from A to B is an asignment of exactly one element of B to each element of A. We write
f(a) = b
if b is the unique element of B assigned by the function f to the element a of A. If f is a function from A to B, we write f:A →B.

Prime Number

As integer p greater than 1 is called prime if the only positive factors of p are 1 and p. A positive integer that is greater than 1 and is not prime is called composite.

a divides b

Let a and b be integers where a ≢ 0. Suppose a divides b the notation would be a | b, with a being the factor and b being the dividend.

Algorithm

An algorithm is a finite sequence of precise instructions for performing a computation or solving a problem.

Tree

A tree is a connected undirected graph with no simple circuits.

Proof there are at most m^h leaves

Using Mathematical Induction.

Base Case: Consider m-ary trees at height = 1. This tree has roots of no more than m children/leaves. Thus m¹ = m leaves in m-ary tree of height 1.

Inductive Step:
Hypothesis: Assume this is true for all m-ary trees of height less than h.
Let T be an m-ary tree of height h. The leaves of this tree T, are the leaves of the subtrees of T, which are obtained by deleting the edges from the root to each of the vertices at level 1.

Each of the subtrees has a height ≤ h-1. By the inductive hypothesis, each of these rooted trees has at most m^h-1 leaves.

Keep in mind there are at most m amount of subtrees with m^h-1 leaves, so m(m^h-1) = m^h leaves. ∎

Big-O Estimate Theorem Proof

Proof: Using the triangle inequality

if x > 1:
|f(x)| = |a_nxⁿ + a_n-1x^n-1 + … + a₁ + a₀|
≤ |a_n|xⁿ + |a_n-1|x^n-1 + … + |a₁|x + |a₀|
= xⁿ( |a_n| + |a_n-1|/x + … + |a₁|/x^n-1 + |a₀|/xⁿ )
≤ xⁿ( |a_n| + |a_n-1| + … + |a₁| + |a₀| )
Let C = |a_n| + |a_n-1| + … + |a₁| + |a₀|
so |f(x) ≤ Cxⁿ whenever x > 1
Hence C = |a_n| + |a_n-1| + … + |a₁| + |a₀| and k = 1 show that f(x) is O(xⁿ). ∎

Full m-ary Tree Vertex Theorem

A full m-ary tree with i internal vertices contains n = mi + 1 vertices

The Transitive Closure

The transitive closure of a relation R equals the connectivity relation R*.

Pigeonhole Principle

If k is a positive integer and k + 1 or more objects are placed ino k boxes then there is at least one box containing two or more of the objects.

Big-O Estimate Theorem

Let f(x) = a_nxⁿ+a_n-1x^n-1+…+a₁x+a₀, where a₀,a₁,…,a_n-1,a_n are real numbers. Then f(x) is O(xⁿ).

Base-b Expansion Theorem

Let b be an integer greater than 1. Then if n is a positive integer, it can be expressed uniquely in the form.
n = a_kb^k + a_k-1b^k-1 + … + a₁b + a₀.
Where k is a non negative integer; a₀, a₁, …, a_k are non negative integers less than b, and a_k ≠ 0.

Schroeder-Berenstein Theorem

If A and B are sets with |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|. In other words, if there are one-to-one functions f from A to B and g from B to A, then there is a one-to-one correspondence between A and B.

De Morgans Law

~(p ^ q) ≡ ~p v ~q; ~(p v q) ≡ ~p ^ ~q.