Final Exam Flashcards
A countable set
Discrete set
A declarative sentence that is true or false, but not both
Proposition
A propositional form that is always true, denoted t
Tautology
A propositional form that is always false, denoted c
Contradiction
An argument where every case the premise (hypothesis) is proven true, the conclusion is also true
Valid argument
An integer n is ________ iff ∃k ε Z s.t. n = 2k.
Even integer
An integer n is ________ iff ∃k ε Z s.t. n = 2k + 1.
Odd integer
An integer n is ________ iff n > 1 and it has no positive divisor other than 1 and itself.
i.e. iff n > 1 and ∀r,s ε Z+ if n = r * s then r = 1 or s = 1.
Prime
An integer is __________ iff n > 1 and n is not prime.
i.e. iff n > 1 and ∃r,s ε Z+ s.t. n = r * s but r ≠ 1 and s ≠ 1.
Composite
r ε R is called a _____________ iff ∀a,b ε Z s.t. r = a/b and b ≠ 0.
Rational number
∀n ε Z ∀d ε Z s.t d ≠ 0 ______________, denoted d | n iff ∃k ε Z s.t. n = dk.
d divides n
Any integer n s.t. n > 1 is either a prime or it can be uniquely written as a product of primes in a non-decreasing order.
Fundamental Theorem of Arithmetic (FTA)
∀n ε Z ∀d ε Z+ ∃! q, r ε Z s.t. n = dq + r and 0 ≤ r < d
Quotient Remainder Theorem
An unordered collection of elements.
A set
A set A is a subset iff every element of A is also in B.
A ⊆ B
{x ε U| x ε A ∨ x ε B}
A ∪ B
{x ε U| x ε A ∧ x ε B}
A ∩ B
{x ε U| x ε B ∧ x ∉ A}
B - A
{x ε U| x ∉ A}
A^c
Let A and B be sets. The Cartesian Product of A and B is the set ___________ of ordered pairs defined {(a, b) | a ε A, b ε B}
A x B
A ____________ from a set A to a set B denoted f: A → B is a relation from A to B s.t. each element of A is assigned by f to one and only one element of B.
Function
A function f: A → B is ___________ iff ∀a1, a2 ε A if f(a1) = f(a2) then a1 = a2.
1-1
A function f: A → B is ___________ iff ∀b ε B ∃a ε A s.t. f(a) = b.
onto
Let f: A → B be a function. The ___________________ is the set {(a, b) | a ε A and b = f(a)}
graph of a function
Two sets A and B have the same _______________ iff there exists a bijection between them.
Cardinality
A set A is ______________ iff it is finite or it has the same cardinality as Z+.
Countable
A binary ___________________________ is a subset of A x B s.t. (a, b) ε R iff a is related to b under R, denoted aRb.
relation from a set to a set
Let m and n be any integers. Let d ε Z+. m is congruent to n modulo d, denoted ______________________.
m ≡ n mod d iff d | m - n
A relation R is called _______________ iff ∀a ε A (a, a) ε R.
Reflexive
A relation R on a set A is ______________ iff ∀a, b ε A (a, b) ε R → (b, a) ε R.
Symmetric
A relation R on a set A is _______________ iff ∀a, b, c ε A (a, b) ε R if (a, b) ε R and (b, c) ε R then (a, c) ε R.
Transitive
A relation on a set A is called an ______________________, iff it is reflexive, symmetric, and transitive.
Equivalence relation
