
What is a statement that is either true or false
proposition

Negation
Conjunction
Disjunction
Exclusive OR
Implication
Biconditional
 Negation (¬p): not p
 Conjunction (p⋀q): p and q
 Disjunction (p⋁q): p or q
 Exclusive OR (p⊕q): p exclusive or q
 Implication (p→q): p implies q
 Biconditional (p↔q): p if and only if q


p is a sufficient condition for q means
p → q

p is a necessary condition for q means that
 ¬p → ¬q or equivalently q → p
 (p ∧ q is not the correct answer because p could still be true but q may be false, q still may happen without p)

p is a necessary and sufficient condition for q means
p iff q (p↔q)

Universal Quantifier (for all)
∀ statement is true for all elements in the domain of x

Existential quantifier (There exists)
∃ means that there is an element in the domain of x for which the predicate is true

When is an integer prime?
An integer n is prime iff n > 1 and for all positive integers r and s, if n = r x s, then r = 1 or s = 1. Otherwise n is composite.

For any set S, the empty set
∅⊆S and S⊆S.
If A⊆B and A≠B then we say that A is a proper subset of B (A⊂B). A is a proper subset of B if A is a subset of B and there is an element in B that does not belong to A.

Theorem of Number of Numbers between numbers
If m and n are integers and m ≤ n then there are nm+1 integers from m to n inclusive.

The number of elements in the Power set of set S, with n elements can be given by

The number of permutations of set S where S has n elements can be given by
n!

The union of sets A and B
A∪B is the set that contains those elements that are in A or in B or in both.

The intersection of sets A and B
A∩B is the set that contains those elements that are in both A and B.

Two sets are called ____ if their intersection is an empty set
disjoint

A collection of sets is a partition of a set A iff and only if
 1. A = union of all sets in the partition
 2. all the sets in the partition are mutually disjoint

The difference of sets A and B
A \ B is the set containing those elements that are in A but not in B.

The complement of set A
U \ A or ¬A is the set of elements not in A.

The cartesian product of A and B
A x B is the set of all ordered pairs formed by taking an element from A together with an element from B in all possible ways.

Let A and B be sets. Then A = B if and only if

A  (B ∪ C) =
A  (B ∩ C) =
 A  (B ∪ C) = (AB)∩(AC)
 A  (B ∩ C) = (AB)∪(AC)

Let P(n,r) denote the number of rpermutations of a set of n elements. What is the value of P(n,r)?
P(n,r) =

The InclusionExclusion Formula
If A, B, and C are any finite sets, then
A∪B∪C =
 A + B + C  A∩B  A∩C  B∩C + A∩B∩C
 Observe that if the sets are mutually disjoint then A∪B∪C = A + B + C (Sum Rule)

An rcombination of a set of n elements means an unordered selection of r of the n elements of S. is the value of

Fundamental Theorem of Arithmetic
 Given any integer n > 1, there exist a positive integer k, distinct prime numbers
 p1, p2, . . . , pk, and positive integers e1, e2, . . . , ek such that
 n = p1^e1 p2^e2 p3^e3...pk^ek
 and any other expression of n as a product of primes is identical to this except,
 perhaps, for the order in which the factors are written.

The elements of a multiset are ____ however, the elements of each element are _____.
 distinguishable
 indistinguishable

The permutations of a multiset S with nk elements of n total objects is

rcombinations with repetition allowed
n: n1 sticks
r: n crosses
The total number of possible ways to choose multisets of size r from a multiset of n objects with repetition of each object is
or

Steps for an Induction Proof
 1. Assert what you want to prove
 2. Base Case
 3. Induction Hypothosis
 4. Induction Step

Steps for a combinatorial proof
 1. Ask a question
 2. Show that LHS answers the question
 3. Show RHS answers the question
 4. Conclude they are equal

Pascal's Formula
 If n and k are positive ints with n >= k then

The Binomial Theorem
 For any real numbers a and b and nonnegative integer n

The Pigeonhole Principle
 If k + 1 or more objects are distributed among k bins then there is at least one bin that has
 two or more objects. For example, the pigeon hole principle can be used to conclude that
 in any group of thirteen people there are at least two who are born in the same month.

