# Shared Flashcard Set

## Details

Discrete Math for Final
Discrete Math for Final
26
Mathematics
05/02/2012

Term
 Set
Definition
 A ________ is an unordered collection of objects, where each object can appear (counts) only once.
Term
 Onto (Surjective)
Definition
 A function f : A → B is called ___________ if and only if for every element y ∈ B there is an element x ∈ A such that y = f (x).
Term
 Bijective (One-to-One Correspondence)
Definition
 A function f is called a _________________ if f is both one-to-one and onto (both injective and surjective).
Term
 One to One (Injective)
Definition
 A function f is ______________ if an only if f (a)= f (b) implies that a = b for all elements a and b in the domain of f . We also say that f is an injection.
Term
 Increasing
Definition
 A function defined on a subset of real numbers is called ________ if for any x < y we have that f (x) ≤f (y).
Term
 Decreasing
Definition
 A function defined on a subset of real numbers is called  __________ if for any x < y we have that f(x) ≥ f(y).
Term
 Subset
Definition
 A set A is a _______ of a set B if for every x ∈ A we have also that x ∈ B.
Term
 Function
Definition
 A _________ is a rule that associates to every element in a set A (called domain), a single element in a set B (called range).
Term
 Geometric Progression
Definition
 A _____________ is a sequence: a, a · r , a · r², ..., a · rn, ...where a is called the initial term and r is called the common ratio.
Term
 Algorithm
Definition
 An _______ is a precise set of instructions (steps) for performing a computation or for solving a problem.
Term
 Arithmetic Progression
Definition
 An ________________ is a sequence: a, a + d, a + 2d, ..., a + nd, ...where a is called the initial term and d is called the common difference.
Term
 Factor/Multiple
Definition
 If a, b are integers, b ≠ 0, we say that b divides a if there exists an integer c such that a = b⋅c. We say that b is a factor of a and that a is a multiple of b.
Term
 Complement
Definition
 Let U specify the universal set. The ________ of a set A, denoted Ā, is Ā = U − A.
Term
 Big-Omega Notation
Definition
 Let f , g be functions from the set of reals or integers to the set of reals. We say that f (x) is Ω(g(x)) if there are constants C and k such that: f(x) ≥ C⋅g(x) for all x > k
Term
 Big-Theta Notation
Definition
 Let f , g be functions from the set of reals or integers to the set of reals. We say that f (x) is Θ(g(x)) if f (x) is both O(g(x)) and Ω(g(x)).
Term
 Big-O Notation
Definition
 Let f , g be functions from the set of reals or integers to the set of reals. We say that f (x) is O(g(x)) if there are constants C and k such that: f(x) ≤  C ⋅g(x) for all x > k
Term
 Division Algorithm Theorem
Definition
 Let a ∈ ℤ, d ∈ ℤ; d > 0. There exist unique integers q and r such that a = q⋅d + r , with 0 ≤r < d. a = dividend q = quotient d= divisor r= remainder
Term
 Representation of Integers Theorem
Definition
 Let b > 1 an integer. Then any positive integer n can be uniquely expressed as:   n = ak⋅bk + ak-1⋅bk-1+ ...+ a2⋅b2+ a1⋅b + a0 where k ≥ 0 and ak, a1, a0 are all nonnegative integers smaller than b.
Term
 Union
Definition
 The ______of sets A and B, denoted by A ∪ B, is the set that contains all elements that are either in A or in B, or in both.
Term
 Cardinality
Definition
 The _________ of a finite set A, denoted |A|, is an integer that represents the number of elements of A.
Term
 Power Set
Definition
 The _________ of a set S, denoted P(S), is the set of all possible subsets of S.
Term
 Difference
Definition
 The _________ of sets A and B, denoted by A − B, is the set that contains those elements that are in A but not in B.
Term
 Cartesian Product
Definition
 The __________ of two sets A and B, denoted A × B, is the set of all pairs (a, b) where a is an element from A and b is an element from B.
Term
 Intersection
Definition
 The ___________ of sets A and B, denoted by A ∩ B, is the set that contains all elements that are in both A and B.
Term
 Congruence
Definition
 We say that a ≡b( mod m), a is congruent b modulo m, if a mod m = b mod m.
Term
 Disjoint Sets
Definition
 We say that the sets A and B are ______ if A ∩B = ∅
Supporting users have an ad free experience!