Theory of computation or computer science is the version evolved from the mathematics set theory. We have discussed many things so far in this blog website.

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

1. 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.
2. The set of natural numbers is N = {1, 2, 3, . . .}.
3. The set of integers is Z = {. . . ,−3,−2,−1, 0, 1, 2, 3, . . .}.
4. The set of rational numbers is Q = {m/n : m  ∈ Z, n ∈ Z, n ≠ 0}.
5. The set of real numbers is denoted by R.
6. 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.
7. 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).
8. 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 }
9. A binary relation on two sets A and B is subset of A x B.
10. 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 ƒ.
11. 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.
12. 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.
13. 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: K₅ (the complete graph on five vertices), K_3,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.
14. 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}.
15. 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.
16. A language is a set of strings.
17. 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 ⇒.
18. The following table explain the meanings of the boolean operation discussed above.

Read Also: What is Machine Learning?