During answering many questions of the future engineers. We come across that many of them required to understand the mathematical part of the theory of computation.
Mathematical preliminaries
- A set is a collection of well-defined objects. Examples are (i) the set of all Dutch Olympic Gold Medallists, (ii) the set of all pubs in Ottawa,and (iii) the set of all even natural numbers.
- The set of natural numbers is N = {1, 2, 3, . . .}.
- The set of integers is Z = {. . . ,−3,−2,−1, 0, 1, 2, 3, . . .}.
- The set of rational numbers is Q = {m/n : m ∈ Z, n ∈ Z, n ≠ 0}.
- The set of real numbers is denoted by R.
- 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 A and B are two sets, then
- there union is defined as A ∪ B = { x : x ∈ A or x ∈ B },
- their intersections is defined as A ∩ B = { x : x ∈ A and x ∈ B }
- their difference is defined as A \ B = {x: x ∈ A and x ∉ B }
- the Cartesian product of A and B is defined as A x B = { (x,y): x ∈ A and y ∈ B }
- the complement of A is defined as Ā = { x : x ∉ A }
- A binary relation on two sets A and B is subset of A x B.
- A function ƒ from A to B, denoted by ƒ: A → B, is a binary relation R, having the property that for each element a ∈ A, there is exactly one ordered payer in R, whose first element is a. We will also say that ƒ(a) = b,or ƒ maps a to b, or the image of a under ƒ is b. The set A is called the domain of ƒ, and the set { b ∈ B : there is an a ∈ A with ƒ(a) = b } is called the range of ƒ.
- A function ƒ: A → B is one-to-one or injective, if for any two distinct elements a and a’ in A, we have ƒ(a) ≠ ƒ(a’). The function ƒ is onto or surjective, if for each element b ∈B,there exists an element a ∈ A, such that ƒ(a) = b; in other words, the range of ƒ is equal to the set of B. A function ƒ is a bijection, if ƒ is both injective and surjective.
- A binary relation R ⊆ A x A is an equivalence relation, if it satisfies the following three conditions:
- R is reflexive: For every element in a ∈ A, we have (a,a) ∈ R.
- R is symmetric: For all a and b in A, if (a,b) ∈ R , then also (b,a) ∈ R.
- 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 graft G = (V, E) is a pair of 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.
- 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}.
- 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 ε, is the string having length zero. For example, if the alphabet Σ is equal to {0,1}, then 10, 001, 0, 101, and ε are strings over Σ, having lengths 2, 3, 1, 3, and 0, respectively.
- A language is a set of strings.
- The Boolean values are 1 and 0, that represent true and false, respectively. The basic Boolean operations include
- negation (or NOT), represented by ¬,
- conjunction (or AND), represented by ∧,
- disjunction (or OR), represented by ∨,
- exclusive-or (or XOR), represented by ⊕,
- equivalence, represented by ↔ or ⇔,
- implication, represented by → or ⇒.
- The following table explain the meanings of the boolean operation discussed above.
Read Also: What is Machine Learning?
