Mathematical preliminaries Flashcards
What is a set of rational numbers?
Q = { m/n : m is an integer, n is an integer, n does not equal 0 }
What denotes real numbers?
R
Subsets
If A and B are sets, then A is a subset of B, written as A⊆B, if every element of A is also an element of B. For example, the set of even natural numbers is a subset of the set of all natural numbers. Every set A is a subset of itself, i.e., A ⊆ A. The empty set is a subset of every set A, i.e., ∅ ⊆ A.
If B is a set, then the power set P(B) of B is defined to be the set of all subsets of B:
P(B) = {A : A ⊆ B}.
Observe that ∅ ∈ P(B) and B ∈ P(B).
If B is a set, then the power set P(B) of B is defined to be the set of all subsets of B:
P(B) = {A : A ⊆ B}.
Observe that ∅ ∈ P(B) and B ∈ P(B).
If A and B are two sets, then
(a) their union is defined as
A ∪ B = {x : x ∈ A or x ∈ B},
(b) their intersection is defined as
A ∩ B = {x : x ∈ A and x ∈ B},
(c) their difference is defined as
A \ B = {x : x ∈ A and x ̸∈ B},
(d) the Cartesian product of A and B is defined as
A × B = {(x, y) : x ∈ A and y ∈ B},
(e) the complement of A is defined as
A = {x : x ̸∈ A}
What is a binary relation?
A binary relation on two sets A and B is a subset of A×B.
A function f from A to B, denoted by f : A → B, is a binary relation R, having the property that for each element a ∈ A, there is exactly one ordered pair in R, whose first component is a. We will also say that f(a) = b, or f maps a to b, or the image of a under f is b. The set A is called the domain of f, and the set
{ b∈B: there is an a∈A with f(a) = b } is called the range of f.
A function f from A to B, denoted by f : A → B, is a binary relation R, having the property that for each element a ∈ A, there is exactly one ordered pair in R, whose first component is a. We will also say that f(a) = b, or f maps a to b, or the image of a under f is b. The set A is called the domain of f, and the set
{ b∈B: there is an a∈A with f(a) = b } is called the range of f.
A function f : A → B is one-to-one (or injective), if for any two distinct elements a and a′ in A, we have f(a) ̸= f(a′). The function f is onto (or surjective), if for each element b ∈ B, there exists an element a ∈ A, such that f(a) = b; in other words, the range of f is equal to the set B. A function f is a bijection, if f is both injective and surjective.
A function f : A → B is one-to-one (or injective), if for any two distinct elements a and a′ in A, we have f(a) ̸= f(a′). The function f is onto (or surjective), if for each element b ∈ B, there exists an element a ∈ A, such that f(a) = b; in other words, the range of f is equal to the set B. A function f is a bijection, if f is both injective and surjective.
A binary relation R ⊆ A × A is an equivalence relation, if it satisfies the following three conditions:
(a) R is reflexive: For every element in a ∈ A, we have
(a, a) ∈ R.
(b) R is symmetric: For all a and b in A, if (a,b) ∈ R, then also (b, a) ∈ R.
(c) R is transitive:
For all a, b, and c in A, if(a,b) ∈ R and (b,c) ∈ R,
then also (a, c) ∈ R.
A graph G = (V, E) is a pair consisting of a set V , whose elements are called vertices, and a set E, where each element of E is a pair of distinct vertices. The elements of E are called edges. The figure below shows some well-known graphs: K5 (the complete graph on five vertices), K3,3 (the complete bipartite graph on 2 × 3 = 6 vertices), and the Peterson graph.
The degree of a vertex v, denoted by deg(v), is defined to be the number of edges that are incident on v.
A path in a graph is a sequence of vertices that are connected by edges. A path is a cycle, if it starts and ends at the same vertex. A simple path is a path without any repeated vertices. A graph is connected, if there is a path between every pair of vertices.
A graph G = (V, E) is a pair consisting of a set V , whose elements are called vertices, and a set E, where each element of E is a pair of distinct vertices. The elements of E are called edges. The figure below shows some well-known graphs: K5 (the complete graph on five vertices), K3,3 (the complete bipartite graph on 2 × 3 = 6 vertices), and the Peterson graph.
The degree of a vertex v, denoted by deg(v), is defined to be the number of edges that are incident on v.
A path in a graph is a sequence of vertices that are connected by edges. A path is a cycle, if it starts and ends at the same vertex. A simple path is a path without any repeated vertices. A graph is connected, if there is a path between every pair of vertices.
what is an alphabet?
In the context of strings, an alphabet is a finite set, whose elements are called symbols. Examples of alphabets are Σ = {0,1} and Σ = {a,b,c,…,z}.
what is a string over an alphabet Σ?
A string over an alphabet Σ is a finite sequence of symbols, where each symbol is an element of Σ. The length of a string w, denoted by |w|, is the number of symbols contained in w. The empty string, denoted by
Ee, is the string having length zero. For example, if the alphabet Σ is equal to {0, 1}, then 10, 1000, 0, 101, and Ee are strings over Σ, having lengths 2, 4, 1, 3, and 0, respectively.
What i a language?
A language is a set of strings.
Boolean values
The Boolean values are 1 and 0, that represent true and false, respectively. The basic Boolean operations include
(a) negation (or NOT ), represented by ¬,
(b) conjunction (or AND), represented by ∧,
(c) disjunction (or OR), represented by ∨,
(d) exclusive-or (or XOR), represented by ⊕,
(e) equivalence, represented by ↔ or ⇔, (f) implication, represented by → or ⇒.
