Term
|
Definition
| encompasses the representation and study of collections of distinct objects |
|
|
Term
|
Definition
| is the classical notion of ‘logic:’ The study of thought and reasoning |
|
|
Term
|
Definition
| is the use of formal languages and grammars to represent the syntax and semantics of computation |
|
|
Term
| A Well-Formed Formula (wff) |
|
Definition
| is a correctly structured expression of a language |
|
|
Term
| A proposition (a.k.a. statement) |
|
Definition
is a claim that is either true or false with respect to an associated
context. |
|
|
Term
|
Definition
| A proposition that contains no logical operators. |
|
|
Term
|
Definition
| A claim that is a combination of multiple propositions |
|
|
Term
|
Definition
Two propositions p and q are (Logically) Equivalent (p ≡ q) when both evaluate to the same result when
presented with the same input |
|
|
Term
|
Definition
| a proposition that always evaluates to true |
|
|
Term
|
Definition
| a proposition that always evaluates to false |
|
|
Term
|
Definition
| a proposition that is neither a tautology nor a contradiction |
|
|
Term
|
Definition
| The Inverse of p → q is p → q |
|
|
Term
|
Definition
| The Converse of p → q is q → p |
|
|
Term
|
Definition
| The Contraposition of p → q is q → p |
|
|
Term
|
Definition
| p and q are (Logically) Equivalent, written p ≡ q, if p ↔ q is a tautology |
|
|
Term
| Predicate (a.k.a. Propositional Function) |
|
Definition
A statement that includes one or more variables and will evaluate to either true or false when the variables
are assigned values |
|
|
Term
Domain of Discourse
(a.k.a. Universe of Discourse) |
|
Definition
| The collection of values from which a variable’s value is drawn is known as the |
|
|
Term
|
Definition
| A quantified variable in a predicate |
|
|
Term
| Free (a.k.a. Unbound) variables |
|
Definition
|
|
Term
|
Definition
| connected series of statements to establish a definite proposition |
|
|
Term
|
Definition
| An argument that moves from specific observations to a general conclusion |
|
|
Term
|
Definition
| An argument that uses accepted general principles to explain a specific situation |
|
|
Term
|
Definition
| Any deductive argument of the form (p1 ^ p2 ^ . . . ^ pn) → q is Valid if the conclusion must follow from the hypotheses |
|
|
Term
|
Definition
| A valid argument that also has true premises |
|
|
Term
|
Definition
| an argument constructed with an improper inference |
|
|
Term
|
Definition
| a statement with an unknown truth value |
|
|
Term
|
Definition
| conjecture that has been shown to be true |
|
|
Term
|
Definition
| A sound argument that establishes the truth of a theorem |
|
|
Term
|
Definition
| a simple theorem whose truth is used to construct more complex theorems |
|
|
Term
|
Definition
| a theorem whose truth follows directly from another theorem |
|
|
Term
|
Definition
| an unordered collection of unique objects |
|
|
Term
|
Definition
| Set A is a subset of set B (written A ⊆B) if every member of A can be found in B. |
|
|
Term
|
Definition
| A is a proper subset of B (written A ⊂ B) if A ⊆B and A != B |
|
|
Term
|
Definition
| power set of a set A (written P(A)) is the set of all of A’s subsets, including the empty set cardinality of |P(A)|=2^|A| |
|
|
Term
|
Definition
| Two sets are disjoint if their intersection is ∅ |
|
|
Term
|
Definition
| A partition of a set divides its members into disjoint subsets |
|
|
Term
|
Definition
| An ordered pair is a group of two items (a, b) such that (a, b) != (b, a) unless a = b |
|
|
Term
|
Definition
The Cartesian Product (symbol: ×) of two sets A and B is the set of all ordered pairs (a, b) such that
a ∈A and b ∈ B |
|
|
Term
|
Definition
| A matrix is an n-dimensional collection of values |
|
|
Term
|
Definition
| Two matrices A and B are equal if they share the same dimensions and each pair of corresponding elements is equal. |
|
|
Term
|
Definition
| A matrix A is symmetric if A = AT . |
|
|
Term
|
Definition
| A (binary) relation from set X to set Y is a subset of the Cartesian Product of the domain X and the codomain Y . |
|
|
Term
|
Definition
| A relation R on set A is reflexive if (a, a) ∈ R, ∀a ∈ A. |
|
|
Term
|
Definition
| A relation R on set A is symmetric if (a, b) ∈ R whenever (b, a) ∈ R for a, b ∈ A. |
|
|
Term
|
Definition
| A relation R on set A is antisymmetric if (x, y) ∈ R and x != y, then (y, x) ∉ R, ∀x, y ∈ A. |
|
|
Term
|
Definition
| A relation R on set A is transitive if whenever (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈R, for a, b, c ∈ A |
|
|
Term
|
Definition
The inverse of a relation R, denoted R−1, contains all of the ordered pairs of R with their components
exchanged. (That is, R−1 = {(b, a) | (a, b) ∈ R}.) |
|
|
Term
|
Definition
| Let G be a relation from set A to set B, and let F be a relation from B to set C. The composite of F and G, denoted F ◦ G, is the relation of ordered pairs (a, c), a ∈A, c ∈C, such that b ∈ B, (a, b) ∈ G and (b, c) ∈ F |
|
|
Term
|
Definition
| A relation R on set A is a (reflexive/weak) partial order if it is reflexive, antisymmetric, and transitive |
|
|
Term
|
Definition
| A relation R on set A is irreflexive if for all members of A, (a, a) ∉ R |
|
|
Term
|
Definition
A relation R on set A is an irreflexive (or strict) partial order if it is irreflexive, antisymmetric, and
transitive. |
|
|
Term
|
Definition
| A relation R on set A is an equivalence relation if it is reflexive, symmetric, and transitive. |
|
|
Term
|
Definition
denoted [b], of an element b ∈ B and an equivalence relation R on B is {c ∈ B |
(b, c) ∈ R}. That is, the equivalence class is the set of all elements of the base relation equivalent to a
given element as defined by the relation. |
|
|
Term
|
Definition
Let R be a partial order on set A. a and b are said to be comparable if a, b ∈ A and either a ≼ b or b ≼ a
(that is, (a, b) ∈ R or (b, a) ∈ R). |
|
|
Term
|
Definition
| • A partially-ordered relation R on set A is a total order if every pair of elements a, b ∈ A are comparable. |
|
|
Term
|
Definition
A function from set X to set Y , denoted f : X → Y , is a relation from X to Y . If (x, y) ∈ f, then y is
the only value returned from f(x). Further, f(x) is defined ∀x ∈ X |
|
|
Term
let f : X → Y be a function, and assume f(n) = p
domain
codomain
mapping
image
pre-image
range |
|
Definition
• For each of the following,.
– X is the domain of f.
– Y is the codomain of f.
– f maps X to Y .
– p is the image of n.
– n is the pre-image of p.
– The range of f is the set of all images of elements of X. (Note that the range need not equal the
codomain.) |
|
|
Term
|
Definition
A function f : X → Y is injective (a.k.a. one-to-one) if, for each y ∈Y , f(x) = y for at most one
member of X |
|
|
Term
|
Definition
| A function f : X → Y is surjective (a.k.a. onto) if f’s range is Y (the range = the codomain). |
|
|
Term
|
Definition
| (a.k.a. a one-to-one correspondence) is both injective and surjective |
|
|
Term
|
Definition
| inverse of a bijective function f, denoted f−1, is the relation {(y, x) | (x, y) ∈ f} |
|
|
Term
|
Definition
Let f : Y → Z and g : X → Y . The composition of f and g, denoted f ◦ g, is the function h = f(g(x)),
where h : X → Z. |
|
|
Term
|
Definition
| A function f : X x Y → Z (or f(x, y) = z) is a binary function |
|
|
Term
|
Definition
| A positive integer p is prime if p ≥ 2 and the only factors of p are 1 and p |
|
|
Term
|
Definition
| A positive integer p is composite if p ≥ 2 and p is not prime |
|
|
Term
|
Definition
| Let x and y be integers such that x != 0 and y != 0. The Greatest Common Divisor (GCD) of x and y is the largest integer i such that i | x and i | y. That is, gcd(x,y) = i. |
|
|
Term
| Relatively prime & pairwise Relatively prime |
|
Definition
If the GCD of a and b is 1, then a and b are relatively prime
_________________________________________
When the members of a set of integers are all relatively prime to one another, they are pairwise relatively
prime |
|
|
Term
|
Definition
Let x and y be positive integers. The Least Common Multiple (LCM) of x and y is the smallest integer
s such that x | s and y | s. That is, lcm(x,y) = s |
|
|
Term
|
Definition
If a, b ∈Z and m ∈ Z+, then a and b are congruent modulo m (written a ≡ b (mod m)) iff a%m = b%m
(or, iff m| (a − b)). |
|
|
Term
|
Definition
| A sequence is the ordered range of a function from a set of integers to a set S. |
|
|
Term
| In an arithmetic sequence (a.k.a. arithmetic progression) |
|
Definition
| a, |an+1 − an| is constant. This constant is called the common difference of the sequence. |
|
|
Term
| geometric sequence (a.k.a. geometric progression) |
|
Definition
| g, gn+1/gn is constant. This constant is called the common ratio of the sequence |
|
|
Term
|
Definition
| A subsequence is a sequence formed from a subset of the elements of another sequence in which relative element order is retained |
|
|
Term
|
Definition
| a contiguous finite sequence of zero or more elements drawn from a set called the alphabet. |
|
|
Term
|
Definition
| A set is finite if there exists a bijective mapping between it and a set of cardinality n, n ∈ Z*. |
|
|
Term
| countably infinite (a.k.a. denumerably infinite) |
|
Definition
| if the bijective mapping is to either of the sets Z* or Z+ |
|
|
Term
|
Definition
| set is countable if it is either finite or countably infinite. If neither, the set is uncountable |
|
|
Term
| The Principle of Mathematical Induction: |
|
Definition
To prove that P(n) is true for every positive integer n, we
need to show that (1) P(1) is true, and (2) if P(i) is true for all 1 ≤ i ≤ n, then P(n + 1) is true. (1) is
called the basis step, and (2) is known as the inductive step |
|
|
Term
|
Definition
| P(i) must be true and, for any k ≥ i, if P(i) ∧ P(i + 1) ∧ . . . ∧ P(k − 1) ∧ P(k) is true, then P(k + 1) is true |
|
|
Term
|
Definition
| P(i) must be true and, for any k ≥ i, if P(k) is true, then P(k + 1) is true |
|
|
Term
| The (Generalized) Pigeonhole Principle |
|
Definition
| that if n items are placed in k boxes, then at least one box contains at least ⌈n/k ⌉ items |
|
|
Term
| The Multiplication Principle (a.k.a. the Product Rule): |
|
Definition
If there are s steps in an activity, with n1 ways
of accomplishing the first step, n2 of accomplishing the second, etc., and ns ways of accomplishing the
last step, then there are n1 xn2 x. . . xns ways to complete all s steps. |
|
|
Term
| The Addition Principle (a.k.a. the Sum Rule): |
|
Definition
If there are t tasks, with n1 ways of accomplishing the
first, n2 ways of accomplishing the second, etc., and nt ways of accomplishing the last, then there are
n1 + n2 + . . . + nt ways to complete one of these tasks, assuming that no two tasks interfere with one
another. |
|
|
Term
| The Principle of Inclusion-Exclusion for Two Sets |
|
Definition
says that the cardinality of the union of sets M and
N is the sum of their individual cardinalities excluding the cardinality of their intersection. That is:
|M ∪ N| = |M| + |N| − |M ∩ N| |
|
|
Term
| The Principle of Inclusion-Exclusion for Three Sets |
|
Definition
says that the cardinality of the union of sets M, N,
and O is the sum of their individual cardinalities excluding the sum of the cardinalities of their pairwise
intersections and including the cardinality of their intersection. That is:
|M ∪ N ∪ O| = |M| + |N| + |O| −(|M ∩ N| + |M ∩ O| + |N ∩ O|) + |M ∩ N ∩ O| |
|
|
Term
|
Definition
| An ordering of n distinct elements is |
|
|
Term
|
Definition
| An ordering of an r-element subset of n distinct elements |
|
|
Term
|
Definition
of X = {x1, x2, . . . , xn} is an r element subset of X, denoted C(n, r) or n
r_ and read “n choose r”. |
|
|
Term
|
Definition
| a set of instructions for performing a task |
|
|
Term
|
Definition
has two (sometimes three) parts:
1. The basis clause determines how trivial cases are to be handled.
2. The inductive clause explains how complex problems are answered in terms of simpler versions of
the same problem.
3. The extremal clause says that only cases covered by the basis and inductive clauses are covered by
the recursive definition. That is, the extremal clause provides boundaries for the definition. |
|
|
Term
|
Definition
| expresses the solution to a task in terms of a simpler case of the same problem |
|
|
Term
|
Definition
| The nth term of the Fibonacci sequence is the sum of terms n−1 and n−2, where F(0) = 0 and F(1) = 1 |
|
|
Term
|
Definition
A recurrence relation for the sequence a0, a1, . . . is an equation that expresses term ak in terms of one or
more of its preceding sequence members, one of more of which are explicitly stated initial conditions of
the sequence. |
|
|
Term
| A linear homogeneous recurrence relation with constant coefficients |
|
Definition
A linear homogeneous recurrence relation with constant coefficients of degree (or order) k (abbreviated:
LHRRWCC of degree k) has the form R(n) = c1R(n − 1) + c2R(n − 2) + . . . + ckR(n − k), where ci ∈ R
and ck != 0 |
|
|
Term
|
Definition
The probability that a specific event will occur is the ratio of the number of actual occurrences to the
number of possible occurrences |
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
Antecedent -> consequence
Hypothesis -> conclusion
Sufficient -> necessary |
|
|
Term
| wording for conditional proposition |
|
Definition
if p then q
p only if q
q unless ~p |
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
| Circular reasoning/ Begging the Question |
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
| P(d) for any d∈D / ∴ ∀xP(x) , X∈D |
|
|
Term
| Existential Instantiation |
|
Definition
| ∃xP(x) , X∈D/ ∴P(d) for some d∈D |
|
|
Term
| Existential generalization |
|
Definition
| P(d) for some d∈D/∴ ∃xP(x) , X∈D |
|
|
Term
|
Definition
|
|
Term
|
Definition
| to prove p->q; assume ~q prove ~p |
|
|
Term
|
Definition
| to prove p->q; assume( ~qvp) show a contradiction |
|
|
Term
|
Definition
| (AvB) Or of corresponding pair of values in a matrix |
|
|
Term
|
Definition
| (A^B) And of corresponding matrix element |
|
|
Term
|
Definition
quotient(q) dividend(n) divisor(s) remainder(r)
n=sxq+r
where 0<=r0 |
|
|
Term
|
Definition
quotient(q) dividend(n) divisor(s) remainder(r)
n=sxq+r
where 0<=r0 |
|
|
Term
|
Definition
Repetition no repetition
ordered r^n P(n,r)
unordered pips/pipes C(n,r)
C(n+r-1,r) |
|
|
Term
|
Definition
| solution can be described by an algorithm |
|
|
Term
|
Definition
| Algorithm is efficient(binary search) |
|
|
Term
|
Definition
| no efficient solution algorithm is known (playing chess) |
|
|
Term
|
Definition
| no algorithm will ever describe the solution ( halting problem ) |
|
|
Term
| characteristics of algorithm |
|
Definition
1) input- data from outside source
2) output- info produced bed execution of algorithm
3) Generality:the instructions can solve a collection of similar problem
4) definiteness: the set of instructions is not open to interpretation
5)correctness- output accepted output for the given input
6) finiteness: the complete output is produced after a finite # of instruction have been executed |
|
|
Term
|
Definition
|
|
Term
|
Definition
an=c1a(n-1)+ c2a(n-2)
characteristic equation:
w^2-c1w-c2=0 solve for W1 & W2
answer:
an=m1W1^n + m2W2^n
or an=m1W^n +m2nW^n when W1=W2 |
|
|
Term
|
Definition
| only or's and at most one non negated term |
|
|
Term
|
Definition
a recursive funcion in form of
T(n)=aT(n/b)+cn^d
T(n) is increasing n=b^k
a is a real is less then = to 1
b is an integer is less then 1
c is a r number is less then 1
d is a r number is less then = to 0 f(n)= O(n^d) -> a less b^d
f(n)= O(n^dlog2n) -> a=b^d
f(n)= O(n^(logba)) -> a greater b^d |
|
|
Term
|
Definition
| only or's and at most one non negative term |
|
|
Term
|
Definition
with big theta
if f(n) is big theta of g(n) then g(n) is big theta of f(n) |
|
|
