Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
54 Cards in this Set
- Front
- Back
The Rule of Sum |
If the first task can be performed in m ways, while a second task can be performed in n ways, and two task can not be performed simultaneously, then performing either task can be accomplished in any one of m+n ways. |
|
The Rule of Product |
If a procedure can be broken down into first and second stages, and if there are m possible outcomes for the first stage, and n possible outcomes for the second stage, then the total procedure can be carried out in mn ways. |
|
Factorial |
For an integer n ≥ 0, n factorial is defined by 0! = 1, n! = n(n-1)(n-2)(n-3)...(3)(2)(1). |
|
Permutation |
A permutation of a set X is a bijection from X to itself. The number of permutation of size r for n objects is P(n,r)=n!/(n−r)!, 0 ≤ r ≤ n |
|
Arrangement with Repeated Symbols |
If there are n objects with n1 indistinguishable objects of a first type, n2 indistinguishable objects of a second type,..., and nr indistinguishable objects of an rth type, where n1+n2+...+nr = n, then there are, n! n1!n2!....nk!
|
|
Combination |
A combination is a selection of all or part of a set of objects, without regard to the order in which objects are selected. |
|
Binomial Theorem |
If x and y are variables and n ∈ ℤ+, then,
|
|
Multinomial Theorem |
|
|
Statement |
A statement (proposition) is a sentence that is either true or false, but not both. |
|
Tautology |
A statement is a tautology iff it is true for all truth values assignments of its components. Example : p → (p v q) |
|
Contradiction |
A statement is a contradiction iff it is flase for all truth value assignment of its component. Example: p ᴧ ⌐p |
|
Valid Argument |
Statement of the form (p1ᴧ p2ᴧ ···ᴧ pn)→q that is also a tautology is called a valid argument. |
|
Logical Equivalence |
Two propositions are logically equivalent if they have the same truth table for every possible assignment of primitive components. Example: p Vs ⌐⌐p |
|
De Morgan's Law |
For statements p and q, ⌐(p ᴧ q) ⇔ ⌐p v ⌐q ⌐(p v q) ⇔ ⌐p ᴧ ⌐q |
|
Distributive Laws |
p ᴧ (q v r) ⇔ (p ᴧ q) v (p ᴧ r) p v (q ᴧ r) ⇔ (p v q) ᴧ (p v r) |
|
Transitivity |
For any primitive statement p,q,r: p ⇔ q and q ⇔ r imply p ⇔ r. |
|
Implication |
p → q |
|
Contrapositive |
⌐q → ⌐p |
|
Converse |
q → p |
|
Inverse |
⌐p → ⌐q |
|
Modus Ponens |
p p → q OR (p ᴧ (p → q)) → q ----------- q |
|
Syllogism |
p → q q → r OR ((p → q ) ᴧ (q → r)) → (p → r) ----------- p → r |
|
Modus Tollens |
p → q ⌐q OR ((p → q) ᴧ (⌐q)) → ⌐p ----------- ⌐p |
|
Conjuction |
p q ------- p ᴧ q |
|
Disjunctive Syllogism |
p v q ⌐q OR ((p v q) ᴧ ⌐q ) → p --------- p |
|
Contradiction |
⌐p → F ------------- p |
|
Quantifiers |
An open sentence contains variables, is neither true or false and when the variables are replaced with an actual quantity (from some universe), becomes true or false. |
|
Set |
A set is an unordered collection of objects. The objects in the set are called the ELEMENTS of the set. If x is an element of a set S, we denote this by x Є S. If x is not an element of a set S, we denote this by x Ɇ S. |
|
Empty Set |
The empty set is the set with no elements, and it is denoted by Ø. |
|
Subset |
A set B is said to be a subset of a set A if every element of B is also an element of A. In other words, x Є B implies x Є A. To denote that B is a subset of A, we write B ⊆ A. |
|
Equal Sets |
Two Sets A and B are equal (A = B) iff A ⊆ B and B ⊆ A. |
|
Cardinality |
If A is the finite set, then the cardinality of A is the number of distinct elements in A, and is denoted by |A|. |
|
Power Set |
Power Set of A is the set containing all the subsets of A. |
|
Union |
The union of two sets A and B is the set whose elements are elements of A, B, or both. It is denoted by A U B. Therefore, A U B= {x | x Є A or x Є B}. |
|
Intersection |
The intersection of two sets A and B is the set whose elements are elements of both A and B. It is denoted by A ∩ B. Therefore, A ∩ B = { x | x Є A and x Є B}. |
|
Difference |
Let A and B be sets. The diffence of A and B is the set whose elements are elements of A but not elements of B. It is denoted by A - B. Therefore, A - B = { x |x Є A and x Є B }. |
|
Complement |
The complement of a set A is the set U - A whose elements are the elements of the universal set U that are not elements of A. It is denoted by Ā. Therefore, Ā = { x | x Ɇ A }. |
|
Sequence |
A Sequence is a list with items separated by commas. |
|
Sample Space |
A set of all possible outcomes is called sample space. |
|
Event |
An event is a subset of Sample Space. |
|
Principle of Mathematical Induction |
Let P(n) be a statement involving some integer n ≥ 1. If, 1. P(1) is true, and (Base Step) 2. ∀k ≥ 1, P(k) → P(k+1) (Inductive Step) then ∀n ≥ 1, P(n) is true. |
|
Pascal's Identity |
|
|
Recursive Definition of Function |
A recursive definition of a function defines values of the function for some inputs in terms of the values of the same function for other inputs. |
|
Principle of Strong Mathematical Induction |
Let P(n) be a statement involving some integer n ≥ N. If, 1. P(N) is true, and 2. if P(N), P(N+1),..., P(k) all hold, then P(K+1) must hold, then for all n ≥ N, P(n) is true. |
|
Divides |
If a and b are integers and there is an integer c such that b = a • c, then we say a divides b or b is divisible by a, and write a|b. In this case, we say that a is a factor or divisor of b and that b is a multiple of a. If a does not divide b, we write a ł b. |
|
Properties of Divisibility |
For all integers a, b and c, the following properties hold. 1) If a | b and b | c, then a | c 2) if a | b and a | c, then a | ( b + c) 3) if a | b, then a | bc |
|
Prime Number |
A prime Number is an integer greater than 1 whose only positive divisors are 1 and itself. An integer greater than 1 that is not prime is called a composite number. |
|
Test for Primality |
If n is a compiste number, then n has a prime divisor that is less than or equal to √n. |
|
The Division Algorithm |
Given any integer a and positive integer d, there exists unique integers q and r such that a = dq + r with 0 ≤ r < d. |
|
Greatest Common Divisor |
Let a and b be integers that are not both 0. The greatest common divisor of a and b, denoted gcd(a,b), is the largest integer d such that d | a and d | b. |
|
Relatively Prime |
Two integers a and b are said to be relatively prime if gcd(a,b) = 1. |
|
Euclidean Algorithm |
Used to find the greatest common divisor of a and b. It is the last nonzero number. |
|
Common Multiple |
For a, b, c Є ℤ+, c is called common multiple of a, b if c is multiple of both a and b. |
|
Finite Set |
A set X is finite if ∃n∈Z+ and a bijection (1-to-1 and onto function) f:X→{1,..., n}. |