Discrete Math Important Definitions and Theorems

Proposition

A statement that can be either true or false, but not both.

Theorem *

(see image for definition)

Existential Quantifer

Universal Quantifier

Commutative Law (propositions)

Associativity

Distributive Laws

Identity Laws

Negation Laws

Double Negative Law

Universal Bound Laws

De Morgan’s Laws

Absorption Laws

Tautology and Contradiction Negation

Modus Ponens

Modus Tollens

Generalization

Specialization

Conjunction

Elimination

Transitivity

Proof By Cases

Proof by Contradiction

Negation of “p implies q”

“p and not q”

Negation of Universal Quantifier

Existential Quantifier

Negation of Existental Quantifier

Universal Quantifier

Even Integer

An integer n is even if, and only if, n = 2k for some integer k.

Odd Integer

An integer n is odd if, and only if, n = 2k + 1 for some integer

k.

Prime Number

An integer n is prime if, and only if, n > 1 and for all positive

integers r and s, if n = rs then either r = 1 and s = n, or r = n and s = 1.

Composite Number

An integer n is composite if, and only if, n > 1 and

there exist positive integers r and s such that n = rs and 1 < r < n and 1 < s < n.

Rational Number

A real number r is rational if, and only if, there exist

integers a and b such that r = a/b and b is not equal to 0.

Divisibility

Divisibility by a Prime

Fundamental Theorem of Arithmetic/Unique Factorization of Integers Theorem

Standard Factored Form

Quotient Remainder Theorem

Absolute Value

Triangle Inequality

Binomial Coefficient

Principle of Mathematical Induction

Floor

Ceiling

Greatest Common Divisor

Coprime

Least Common Multiple

Closed Form

Principle of Strong Mathematical Induction

Well Ordering Principle of the Integers (Requirements)

(tells us there is a least element of the set if all 3 requirements are filled)

Well Ordering Principle for the Integers (definition)

Element Method of Proof

Subset

Not a Subset

Proper Subset

Set Equality

Singleton

A set with only one element

Union

Intersection

Set Difference Definition

Complement

Interval Notations

Empty Set

Cartesian Product

Union of a Collection of Sets

Intersection of a Collection of Sets

Disjoint

Mutually Disjoint

Partition

Parititon

Power Set

Number of Elements in a Set

Number of Elements in a Power Set

Symmetric Difference

Definition of a Function

Image of a Subset

Inverse Image of a Subset

Inverse Image of a Singleton

Injective Function (One to One)

hint: passes the vertical line test

Not Injective function (not one to one)

hint: fails the horizontal line test

Surjective (Onto)

Not Surjective (not Onto)

Bijective

Being both Injective (one to one) and surjective (onto)

Definition of Function

Logarithmic Function

Definition of String

(n-place) Boolean Function

Definition of an Inverse Function

Properties of Inverses

Exponential Function