-
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 n-m+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) = (A-B)∩(A-C)
- A - (B ∩ C) = (A-B)∪(A-C)
-
Let P(n,r) denote the number of r-permutations of a set of n elements. What is the value of P(n,r)?
P(n,r) = 
-
The Inclusion-Exclusion 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 r-combination 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
-
r-combinations with repetition allowed
n: n-1 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 non-negative 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.
|
|
