Determine the properties of ℛ below whether it is reflexive, symmetric, antisymmetric, and transitive. If the property does not hold, justify your answer. Hence, state if ℛ is a partial order or an equivalence relation. Let ������ = {1, 2, 3, 4} a) ℛb = {(1, 2), (2, 1), (2, 3), (3, 2)} • Not reflexive because1 ∈ ������ but (1,1) ∉ ℛb. • Symmetric • Not antisymmetric because (1, 2) and (2, 1) ∈ ℛb but 1 ≠ 2. • Not transitive because (2,3) and (3,2) ∈ ℛb but (2, 2) ∉ ℛb. ℛb is not a partial order and not an equivalence relation. b) ℛ3 = {(1, 1), (2, 2), (3, 3), (4, 3)} c) ℛI = {(1, 1), (2, 2), (3, 3), (2, 3), (3, 2), (4, 4)} 43
d) ℛd = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)} e) ℛk = {(1, 1), (1, 2), (1, 3), (3, 1), (3, 3), (4, 4)} f) ℛl = {(1, 1), (1, 2), (1, 3), (1, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 2)} 44
Exercise 3.2 For each relation in the following set a) ℛ = {(������, ������)|������, ������ ∈ ������, |������| = |������|} , if given ������ = {−2, −1, 0, 1, 2}. b) ℛ = {(������, ������)|������, ������ ∈ ������, ������ = ������} , if given ������ = {1, 2, 3, 4, 5}. c) ℛ is a relation on ������ such that (������, ������) ∈ ℛ if and only if ������ < ������, for ������ = {6, 7, 8, 9, 10}. d) ℛ = {(������, ������)|������, ������ ∈ ������, 2 divides (������ + ������)} , if given ������ = {1, 2, 3}. e) The relation ℛ on a set ������ = {������, ������, ������, ������, ������, ������} is given by ℛ = o(������, ������), (������, ������), (������, ������), (������, ������), (������, ������), (������, ������), (������, ������), (������, ������),p (������, ������), (������, ������), (������, ������), (������, ������), (������, ������), (������, ������), (������, ������) f) Let ������ = {1, 2, 4, 6, 8}, a relation ℛ on ������ with ������ℛ������, ������, ������ ∈ ������if and only if q is an integer. r 1. List all the elements of the relation ℛ, for sets (a), (b), (c), (d), and (f). 2. Determine whether the relation has the following properties (or not) and state the reason(s) for your answer: reflexive, symmetric, antisymmetric, transitive 3. Decide whether the relation is an equivalence relation or a partial order. 45
3.3 Equivalence Relations and Partitions Definition 3.9 A partition ������ on a set ������ is the set of all collections of subsets of ������ which satisfies ������ = {������b ∪ ������3 ∪ … ∪ ������u} ������v ∩ ������w = ∅, for all ������ ≠ ������ Elements of the set ������ are called cell or block of partition. If ������ = {������ ∈ ℤ|1 ≤ ������ ≤ 10}, then determine if the following subsets form a partition of ������. a) ������b = {2, 3, 5, 7}, ������3 = {1, 4, 6, 8, 9, 10} • ������b ∪ ������3 = ������ • ������b ∩ ������3 = ∅ Therefore, ������b and ������3 form a partition of ������. b) ������d = {1, 2, 3}, ������k = {4, 6, 7, 8}, ������l = {5, 8, 10} c) ������w = {������, ������ + 5}; where 1 ≤ ������ ≤ 5 46
Let ������ = {2, 4, 6, 8, 10, 14, 16}, and given ������b = {2, 4, 6, 8, 10}, ������3 = {8, 12, 14, 16}, ������I = {4, 6, 12}, ������d = {2, 8, 10} and ������k = {14, 16}. State whether the following collections are partitions of the set ������ and give your reason(s). a) {������b, ������3} b) {������b, ������k} c) {������I, ������d, ������k} 47
Theorem If ℛ is a relation defined by (������, ������) ∈ ℛ if and only if ������ and ������ are in the same block, then ℛ is an equivalence relation on ������. Given ������ = {1, 2, 4, 5} and partition of ������, ������ = }{2}, {1, 4, 5}~. Determine the elements of the equivalence relation on ������. *Since there are two blocks of which are {2} and {1, 4, 5}, by the above theorem, the relation ℛ that is an equivalence relation on ������ is ℛ = {(1,1), (1, 4), (1, 5), (2, 2), (4, 1), (4, 4), (4, 5), (5, 1), (5, 4), (5, 5)} Given the relation ℛ on ������ = {������, ������, ������, ������, ������} ℛ = {(������, ������), (������, ������), (������, ������), (������, ������), (������, ������), (������, ������), (������, ������), (������, ������), (������, ������), (������, ������), (������, ������), (������, ������), (������, ������)} Then the partition of ������ is ������ =_____________________________. Definition 3.10 Let a relation ℛ on a set ������ be an equivalence relation. If ������ ∈ ������, then [������] is called an equivalence class containing ������. [������] = {������|(������, ������) ∈ ℛ} The notation [������‚] denotes the set of all equivalence classes of ������ for the equivalence relation ℛ. Given ������ = {3, 6, 7, 9, 10} and partition ������ = }{3, 6}, {7, 9}, {10}~. Determine the set of all equivalence classes of ������ for the equivalence relation ℛ. We obtained ℛ= 48
So, all equivalence classes of ������ are [3] = {3, 6} [6] = {3, 6} [7] = {7, 9} [9] = {7, 9} [10] = {10} There are three distinct equivalence classes [3] = [6] = {3, 6} [7] = [9] = {7, 9} [10] = {10} Hence, the set of all equivalence classes [������‚] = {[3], [7], [10]} Theorem If ℛ is an equivalence relation on ������ , then defined by ������ = {[������]|������ ∈ ������} is a partition of ������. From the previous Example 3.20, ������ = {[3], [7], [10]}. Hence, [������‚] = ������ = }{3, 6}, {7, 9}, {10}~. Exercise 3.3 1. If ������ = {������, ������, ������, ������, ������, ������} and given sets ������b = {������, ������, ������} , ������3 = {������, ������} , and ������I = {������, ������} . Determine whether {������b, ������3, ������I} is a partition of ������. Give reason(s) for your answer. 2. Determine the elements of the equivalence relation on ������ = {2, 3, 5, 7} and partition ������ = }{2, 7}, {3, 5}~. 3. Given ������ = {2, 3, 4, 5}. Determine whether the following relation on set ������ is reflexive, symmetric and transitive. If yes, state all the equivalence classes and the partition of ������. ℛ = {(2, 2), (2, 4), (3, 3), (3, 5), (4, 2), (4, 4), (5, 3), (5, 5)} 4. Given ������ = {������ ∈ ℤ|1 ≤ ������ ≤ 7}, ℛ is a relation on ������ and ������ℛ������ such that 3 divides ������ − ������. a) Show that ℛ is an equivalence relation. b) List all the equivalence classes of ������. 49
3.4 Functions Definition 3.11 A function ������, or a mapping from ������ to ������, is a correspondence between two sets ������ and ������ that assigns every element ������ of ������ to one and only one element ������ of ������ , denoted by ������: ������ → ������, or ������(������) = ������, if (������, ������) ∈ ������ Definition 3.12 For the function ������: ������ → ������ , ������ is called the domain of ������ and ������ the codomain of ������. The set of images under ������ is the range of ������. For ������ = {1, 2, 3} and ������ = {������, ������, ������, ������} a) ℛb = {(1, ������), (2, ������), (3, ������)} is a function. 1∙ • w 2∙ • x 3∙ • y •z Domain of ������, ������‡ = Range of ������, ������‡ = b) ℛ3 = {(1, ������), (2, ������)} is not a function because __________________________. 50
c) ℛI = {(1, ������), (2, ������), (2, ������), (3, ������)} is not a function because __________________. a) Given ������: ℝ → ℝ, where ������(������) = ������3. Sketch the graph of ������, hence find the domain and range of ������. b) Given ������: ℝ → ℝ, where ������(������) = 2������ − 7. Sketch the graph of ������, hence find the domain and range of ������. 51
c) Given ℎ: ℤ → ℤ, where ℎ(������) = 2������ + 1. Sketch the graph of ℎ, hence find the domain and range of ℎ. d) Given ������: ℝ → ℝ, where ������(������) = 2������3 − 1. Sketch the graph of ������, hence find the domain and range of ������. Definition 3.13 A function ������: ������ → ������ is one-to-one if each element of ������ appears at most once as the image of an element of ������. The function ������ is one-to-one if and only if for all ������b, ������3 ∈ ������, ������(������b) = ������(������3) then ������b = ������3. If ������ = {1, 2, 3, 4} and ������ = {������, ������, ������, ������, ������} a) ������ = {(1, ������), (2, ������), (3, ������), (4, ������)} is a one-to one function. b) ������ = {(1, ������), (2, ������), (3, ������), (4, ������)} is not one-to-one because ___________________ ___________________________________________________________. 52
Consider the function ������: ℝ → ℝ where ������(������) = 3 − 2������ for all ������ ∈ ℝ. Then for all ������b, ������3 ∈ ℝ, then by definition ������(������b) = ������(������3) 3 − 2������b = 3 − 2������3 −2������b = −2������3 ������b = ������3 By using the horizontal line test, draw a horizontal line across the graph. û The horizontal line intersects the graph at only one point, which shows that one element in the domain has only one image. Therefore, ������ is ___________________. Suppose ������: ℝ → ℝ where ������(������) = ������3 for each real number ������ . Then ������(−4) = (−4)3 = 16 and ������(4) = (4)3 = 16, but −4 ≠ 4. ûû The horizontal line intersects at two points, which shows that two elements shares the same image. Therefore, ������ is ________________________. 53
Definition 3.14 For sets ������, ������, and ������: ������ → ������ is called an onto function if the range of ������ is the codomain of ������. The function ������ is onto if and only if the range of ������, ������‡ = ������‡. 1∙ • a 1∙ • a 2∙ • b 2∙ • b 3∙ 3∙ • c •c ������ ������ ������ ������ ������ ������ ������ is an onto function because ������ is _____________________ because ____________________________. _____________________________. Determine whether the functions below are onto functions. Provide the reason(s) for your answer. a) Given ������: ℝ → ℝ, where ������(������) = ������3. 54
b) Given ������: ℝ → [0, +∞), where ������(������) = ������3. c) Given ℎ: ℤ → ℤ, where ℎ(������) = 3������ + 1. 55
Finally, we introduce some of the many interesting functions in computer science. Definition 3.15 A floor function ������: ℝ → ℤ, is given by ������(������) = ⌊������⌋ = the greatest integer less than or equal to ������ a) ⌊3.8⌋ = 3 b) ⌊3⌋ = c) ⌊−3.8⌋ = d) ⌊−3⌋ = e) ⌊7.1 + 8.2⌋ = ⌊15.3⌋ = 15 f) ⌊5.6 − 9.8⌋ = Definition 3.16 A ceiling function ������: R→Z, is given by ������(������) = ⌈������⌉ = the least integer greater than or equal to x a) ⌈3⌉ = 3 b) ⌈3.8⌉ = c) ⌈−3⌉ = d) ⌈−3.5⌉ = e) ⌈3.3 + 4.5⌉ = ⌈7.8⌉ = f) ⌈2.3 − ������⌉ = Definition 3.17 A truncation function is another integer-valued function defined on ℝ. This function deletes the decimal part of a real number. a) ������������������������������(������b) = b) ������������������������������(0.01) = c) ������������������������������(−32.7999) = e) ������������������������������(−6.05) = d) ������������������������������(������) = f) ������������������������������ •3–3— = 56
Evaluate ������������������������������ ˜™⌊−8⌈.3−⌋4×.5⌈71⌉0.0⌉š⌊I.›l⌋œ Evaluate •⌊−17.8 + 1.9⌋ − ⌈1.4 + trunc (−2.7)⌉ž ⌊−2.7⌋ 57
Exercise 3.4 1. Sketch the function ������ = {(������, ������)|������ = 3������ + 3, ������, ������ ∈ ℤD}. Determine whether or not ������ is a one-to-one function and an onto function. State the reason for your answer. 2. Given the function ������: ℝD → ℝ defined by ������(������) = √������. a) State the domain and codomain b) Sketch the graph. c) Is it a one-to-one function? Why? d) Is it an onto function? Why? 3. Evaluate the following ⌈−4.53⌉ ×√tr1u3nc(7.001)¡⌈3.3⌉ a) b) ������������������������������[2.44 + 4.63] − ⌊������⌋ ⌈8.001 − 3.5⌉ c) ™⌊������5������.���9������8���������×¢£√⌈−−38..6979⌉¤⌋š⌊k.›⌋ ⌊3.7 − 5.9⌋ × (4.72 + ⌈0.01⌉) d) ¥£√17.8¦trunc(5.01) 58
CHAPTER 4: DIRECTED GRAPHS Introduction When we use a navigation app, we often concerned with seeing how to get from one place to another through roads indicated on the map. Here we are dealing with a relation, which is how the set of locations are related to using roads. As we have seen in the previous chapter, a relation is represented by listing the ordered pairs. However, in this case, it is more convenient to use a picture, or also known as a graph. Graphs, directed graphs, trees and binary trees appear in many areas of mathematics and computer science. Directed graphs are frequently useful in various dynamic systems such as digital computers or flow systems. This chapter gives the basic definitions and properties of directed graphs. Graphs Definition 4.1 Graph ������ consists of two things. • A set ������ = ������(������) whose elements are called vertices, points, or nodes of ������. • A set ������ = ������(������) of unordered pairs of distinct vertices called edges of ������. Such a graph is denoted by ������(������, ������) when both parts of ������ are to be emphasised. Figure 4.1 Figure 4.1 is an example of a directed graph on ������ = {������, ������, ������, ������, ������} with ������ = {(������, ������), (������, ������), (������, ������), (������, ������)}. The direction of an edge is indicated by placing an arrow on the edge. An edge with direction is called an arc. The edge (������, ������) is an example of a loop, and the vertex ������ has no connecting edge called an isolated vertex. 59
Figure 4.2 Figure 4.2 is an example of an undirected graph on ������ = {������, ������, ������, ������} with undirected edges, ������ = 0{������, ������}, {������, ������}, {������, ������}, {������, ������}1. Important The difference between directed edge and undirected edge. • Directed edge: (������, ������) ≠ (������, ������) • Undirected edge: {������, ������} = {������, ������} Definition 4.2 Suppose ������ is a directed graph. The out-degree of a vertex, v of ������, written out-degree (v), is the number of edges beginning at v. Definition 4.3 Suppose ������ is a directed graph. The in-degree of a vertex, v of ������ , written in-degree(v), is the number of edges ending at v. Since each edge begins and ends at a vertex, we have the following theorem: Theorem 4.1 The sum of the out degrees of the vertices of a directed graph ������ equals the sum of the in degrees of the vertices, which is equal to the number of edges in ������. 60
Given the graphs, ������3 and ������4, determine the degree, in-degree and out-degree for each vertex. Vertex ������3 Degree Vertex ������4 Degree In Out In Out Exercise 4.1 1. Consider the map of tourist attractions in Pahang. a) List down the elements of ������ such that the vertex is a tourist attraction on the map. b) List down all the possible roads that can be taken to travel from Raub to Berkelah Waterfalls. You may have to use Google Maps to refine your search. Figure 4.3: Points of interest in Pahang, image taken from travelmalaysiaguide.com/pahang-maps/ 2. Draw a map of UiTM Kampus Raub where ������ = {������| ������ is a building in UiTM Raub} and ������ = {������| ������ is the main road in UiTM Raub}. a) Determine the in-degree and out-degree for each of the vertices. b) Give an example of a loop and an isolated vertex, if any. 61
Relations, Functions and Directed Graphs If given set ������ and a relation ℛ on ������, we can draw a directed graph of ������ which contains the vertices of ������ and edges of set ������: ������ × ������ for every ������, ������ ∈ ������, (������, ������) ∈ ������. Given ������ = {1, 2, 3, 4} and ℛ = {(������, ������), (������, ������), (������, ������), (������, ������), (������, ������)}. The directed graph ������ is drawn as follows. Given ������ = {1, 2, 3,4, 5} and ������ = {(1, 2), (1, 4), (2, 3), (2, 5), (3, 4), (4, 5)}. The directed graph ������ is as follows. Given ������ = {1, 2, 3, 4} and directed graph ������ is as follows. List down the elements of ℛ. ℛ= Figure 4.3 62
Definition 4.4 We can identify the properties of a directed graph using the definitions below without listing down all the elements of a relation ℛ. A directed graph is • reflexive if it has a loop at every vertex. • symmetric if there is an arc from v to w, and then it also has an arc from w to v. • anti-symmetric if it has at most an arc between two vertices. • transitive if it has an arc from v to w and from w to y, and then there is an arc from v to y. Suppose ������ = {������, ������, ������, ������, ������} and ℛ = {(������, ������), (������, ������), (������, ������), (������, ������), (������, ������), (������, ������), (������, ������), (������, ������), (������, ������)}. a) Construct the graph of ℛ. b) State the properties of the graph. Give reason(s) for your answer. 63
Let ������ = {������|������ is a prime number less than 15} and a relation ℛ on ������ such that 2������ + ������ ≤ 30 for ������, ������ ∈ ������. a) List down all the elements of ℛ. b) Construct the graph of ℛ. c) Determine the properties of the graph. Give reason(s) for your answer. 64
Important A directed graph is called a function if there is precisely one out-degree for each vertex. ������3 ������4 The directed graph ������3 is a function because __________________________________ ________________________________________________________________ The directed graph ������4 is not a function because _______________________________ ________________________________________________________________ Definition 4.5 A graph ������ is a connected graph if given any distinct vertices v and w, there is a path from v to w. In other words, there is no isolated vertex/vertices. a) The graph is not connected because 65
b) The graph ������4 is connected because Definition 4.6 A graph ������_(������_, ������_) is a subgraph of ������(������, ������) denoted by ������_(������_, ������_) ≤ ������(������, ) E if ������_ ⊆ ������ and ������_ ⊆ ������. Thus every vertex in ������_ is a vertex in ������ and every edge in ������_ is an edge in ������. Given a graph ������(������, ������ ) Then the graphs below are some of the examples of subgraphs of ������. ������3_ ������4_ 66
������a_ ������b_ Find three different connected subgraphs for each of the graphs below, which consist of all vertices. 67
Exercise 4.2 1. State whether each of the following statements is True or False. Give a reason for each false statement. a) If every vertex of a directed graph has precisely one out-degree, then the directed graph is called a function. b) A directed graph is reflexive if and only if there is a loop at every vertex. c) A directed graph G is a function if there is only an arc leaving each vertex. d) If a graph G has an isolated vertex, then G is not a connected graph. 2. Let ������ = {1, 3, 5, 9} and ℛ is a relation on ������ such that ������ℛ������ if ������ ≤ ������. a) Construct a directed graph of ℛ. b) Determine if the graph is reflexive, symmetric and transitive. Give reason(s) to support your answer. 3. Given the function ������ = {(1, 7), (3, 7), (5, 1), (7, 8), (8, 3), (8,5)}. a) Draw a directed graph for the function. b) State the domain and range of the function. c) Determine if the function is one-to-one. Give a reason for your answer. d) Draw two different subgraphs of size 4 based on the given function. 4. Given a relation ℛ is a relation on ������ = {17, 26, 59, 62, 71,95} where ������ℛ������ if (������ − ������) < 50. a) Construct a directed graph to represent the relation. b) Determine if the graph is reflexive, symmetric, anti-symmetric and transitive. Give the reason(s) for your answer. c) State whether the graph is a partial order or an equivalence relation. d) Draw a subgraph containing all vertices. e) Draw a subgraph of size 5 such that the vertices 71 and 62 must be connected. 68
Paths and Cycles Definition 4.7 Suppose ������ is a directed graph, then • a path ������ in ������ is an alternating sequence of vertices and directed edges. • the length of ������ is determined by its number of edges. • a simple path is a path with distinct edges. • an elementary path is a path with distinct vertices. • a cycle (or circuit) is a closed path with distinct vertices (except the first and the last) with no edge occurs more than once. Consider the following graphs. a) ������3 is a path from v to y. 1. ������3 = ������ − ������ − ������ Figure 4.4 b) ������4 is a path from x to y. 2. c) ������a is a path from y to w that traverses all the vertices. Figure 4.5 d) The length of ������3, ������4, and ������a. e) ������3 and ������4 are simple paths because it does not traverse an edge more than once. f) ������a is not an elementary path because it traverses the vertex v more than once. a) ������b is a path from ������ to ������. ������b = ������ − ������ − ������ − ������ b) The path ������m = ������ − ������ − ������ − ������ − ������ − ������ has the length __________________. c) ������b is a simple path and an elementary path. d) ������m is ______________________________ _________________________________. 69
Given an undirected graph ������. Determine if the following are a cycle in graph ������. a) ������3 = ������ − ������ − ������ − ������ − ������ − ������ − ℎ − ������ is _________________________________. b) ������4 = ������ − ������ − ℎ − ������ − ������ − ������ is _______________________________________. c) ������a = ������ − ������ − ������ − ������ − ������ is __________________________________________. Consider the following graph. Find a cycle for each of the following condition. a) A cycle that goes through four vertices. b) A cycle that goes through all vertices. c) A cycle that starts at vertex ������ and has a length of 6. 70
Definition 4.8 Let ������ be an undirected graph with no isolated vertices, then • an Euler path is a path in ������ that traverses each edge exactly once. • an Euler circuit is a path that begins and ends at the same vertex and traverses each edge exactly once. It is possible to go through a vertex more than once. Theorem 4.2 Suppose ������ is a connected graph, then ������ has • no Euler path if it has more than two vertices with odd degree. • an Euler path if it has exactly two vertices with odd degree. Thus, any Euler path must begin and ends at the different vertices with odd degree. • no Euler circuit if it has at least a vertex with odd degree. • an Euler circuit if all vertices have even degree. For each of the following graph, determine if an Euler path or an Euler circuit exists. If the path or circuit exists, give an example. If not, justify your answer. a) An Euler path exists. Example: An Euler circuit does not exist because there are vertices with odd degree. b) c) 71
Definition 4.9 If ������ is a graph with at least three vertices, then ������ has • a Hamiltonian path is a path in ������ that passes through each vertex exactly once. • a Hamiltonian circuit is a circuit that passes through each vertex exactly once. Unlike Euler path (and circuit), there is no simple rule to determine the existence of Hamiltonian path (and circuit). A necessary condition for the Hamiltonian circuit is the graph must be strongly connected, i.e. there is an edge connecting every pair of vertices in the graph. For each of the following graph, determine if a Hamiltonian path and a Hamiltonian circuit exist. If the path or circuit exist, give an example. a) A Hamiltonian path exists. Example: ������ − ������ − ������ − ������ − ������ − ������ − ������ − ℎ − ������ A Hamiltonian circuit does not exist because there is no possible way for a path to return to its starting vertex after passing through all vertices exactly once. b) c) 72
Exercise 4.3 1. State whether each of the following statements is True or False. Give a reason for each false statement. a) The length of a path between two nodes is determined by the number of arcs between the two nodes. b) A simple path is a path from node v to node w with no repeating nodes. c) A directed graph ������(������, ������) with ������ = {������, ������, ������, ������} and ������ = {(������, ������), (������, ������), (������, ������), (������, ������)} is strongly connected. d) The length of a path is determined by its number of edges. e) If a graph ������ has an isolated vertex, then ������ is not a connected graph. 2. Let ������(������, ������) be the undirected graph in the figure below. How many paths are there in ������ from ������ to ℎ? How many of these paths have length 5? 3. Consider the graphs ������3 and ������4 as follows. ������3 ������4 a) Find the size of the graph. b) Determine the degree for each of the vertices. c) Give two examples of a spanning tree with the root of vertex f. d) Is there a Hamiltonian path? Give a reason for your answer. e) Is there a Hamiltonian circuit? Give a reason for your answer. f) Is there an Eulerian path? Give a reason for your answer. g) Is there an Eulerian circuit? Give a reason for your answer. 73
Trees Definition 4.10 A graph ������ is called a tree, ������ if ������ is connected and contains no cycle. Definition 4.11 A tree, ������ is a spanning tree for a graph ������, if ������ is a subgraph of ������, and ������ includes all the vertices of ������. Given the graphs, ������3, ������4, and ������a. ������3 ������4 ������a ������3 is a tree. ������4 is not a tree because it has a cycle. ������a is not a tree because it is not connected. But each component of ������a is a tree. Hence, we call ������a a forest. ������3 is a subgraph of ������4 such that ������3 contains all the vertices in ������4. Hence, ������3 is a spanning tree of ������4. Theorem 4.3 If a tree ������ has ������ edges and ������ vertices, then ������ = ������ + 1. Definition 4.12 A tree is a rooted spanning tree if there is a unique vertex ������ such that the ������������������������������(������) = 0 and there is a path from ������ to every vertex in the tree. 74
Given a graph ������, find three spanning trees. The following graphs are examples of rooted spanning tree. Spanning tree rooted at ������ Spanning tree with root ������ Draw two different spanning trees with vertex ������ as the root. 75
Given a rooted tree as follows. 1. Which vertices are the leaves? 2. Which vertex is the root? 3. Which vertices are the ancestors of h? 4. Which vertex is the parent of g? 5. Which vertices are the descendants of c? 6. Which vertices are the siblings of s? 7. What is the level number of vertex f? 8. Which vertices have level number 4? Definition 4.13 A binary tree is an ordered tree that has at most two children. For a binary tree, the vertex that goes down to the left of the parent vertex is called the left-child vertex. The vertex that goes down to the right is the right-child vertex. parent left-child right-child 76
Definition 4.14 A full binary tree is a binary tree which has two children or none. A full binary tree can be used to represent mathematical expressions. For instance a) 2 + ������ b) 10������ c) (3 − 5) × ������ d) 1/(4 − ������4) Draw a binary tree to represent the following mathematical expressions. a) v(������ + 7)/5w + v(������ − ������)^3w 77
b) y4 + v7 − (������ − 2)wz × v(������ + ������) − 8w c) √������4 − 2������������ Exercise 4.4 1. For each of the following mathematical expressions, answer the following questions: 3 4(���y������5+���z������)•a i) (3| − ������)(2������ + 5) ii) ~2 − 4������ − ������4 ������ iii) €������ + ������ + 3 iv) (������ − ℎ)4 + (������ − ������)4 5 − ������34 ������ a) Represent the above expression as a binary tree. b) Determine its root. c) Find all the leaves. d) Determine the size of the tree. 78
CHAPTER 5: FUNDAMENTALS OF LOGIC Introduction Logic is the essence of reasoning. We use logic in our everyday lives. We determine whether a statement is true or false. We use logical rules for control systems to define how they should operate. For example, in washing machines, the logical rule could be programmed as 'If the laundry weighs more than 5 kg, then fill the washing tub with 50 litres of water'. Apart from that, we also use logic to deduce the conclusion of an argument. In this chapter, we will look at the basics in the algebra of propositions. Basic Connectives and Truth Tables Definition 5.1 Statements (or propositions) are declarative sentences that are either true or false – but not both. We usually use the lowercase letters (e.g. ������, ������ and ������) to represent these statements: ������: This book has 100 pages. ������: The cover of this book is green in colour. ������: Three authors write this book. However, we don’t consider these sentences as statements because they are neither true nor false. Do your homework. Why is the world almost round? What a beautiful morning! The statements ������, ������ and ������, are examples of primitive statements. Compound statements are statements that contain logical connectives, such as not, and, or, if … then, and if and only if. The five logical connectives are denoted by their logical symbols. We use truth tables to represent all possible truth values of a statement. 79
Definition 5.2 Negation (¬) is translated as “not” or “it is not the case that”. The negation of statement ������ is denoted by ¬������. For the statement ������ above, ¬������ is the statement “This book does not have 100 pages.”. ¬������: ¬������: The effect of the symbol ¬ on the meaning of a sentence is illustrated by the following table, which is called a truth table for ¬: ������ ¬������ Truth values: T = true, F = false OR 1 = true, 0 = false Definition 5.3 Conjunction (Ù) is translated as “and” or sometimes “but”. The conjunction of the statement ������, ������ is denoted by ������ ∧ ������. In our example, the statement ������ ∧ ������ is read “This book has 100 pages, and its cover is green in colour.”. ������ ������ ������ ∧ ������ The statement ������ ∧ ������ is true when both ������ and ������ must be true. If either ������ or ������ is false, then ������ ∧ ������ is false. 80
Definition 5.4 Disjunction (Ú) is translated as “or”. The disjunction of the statements ������, ������ is denoted as ������ ∨ ������. From the previous example, the statement ������ ∨ ������ is read “This book has 100 pages or its cover is green in colour.”. Consequently, ������ ∨ ������ is true if one or the other or both of the statements p and q are true. ������ ������ ������ ∨ ������ Definition 5.5 Implication (®) is translated as “if … then …”. If we write ������ → ������ (also read as: ������ implies ������), then we say: • If ������, then ������ • ������ only if ������ • ������ is sufficient for ������ • ������ is necessary for ������ • ������ is a sufficient condition for ������ • ������ is a necessary condition for ������ Consider the statement ������ → ������: If I eat ice cream every day, then I will be happy. The statement ������ is called the hypothesis of the implication; ������ is called the conclusion. ������ ������ ������ → ������ The truth value of ������ → ������ is false only when the hypothesis ������ is true, and the conclusion ������ is false. For other cases, the truth value of ������ → ������ is true. 81
Definition 5.6 Biconditional («) is translated as “if and only if” (or “iff”). From the previous example, the statement ������ ↔ ������ is read \"This book has 100 pages if and only if its cover is green in colour.”. ������ ������ ������ ↔ ������ The statement ������ ↔ ������ is true whenever ������ and ������ have the same truth values. Consider the following primitive statements: ������: My computer is high-speed. ������: I will finish my project on time. ������: I will pass the course. Express the following sentences as symbolic expressions: a) My computer is not high-speed, or I would finish my project on time. b) I will not finish my project on time and pass the course. c) It is not true that I will finish my project on time and pass the course. d) My computer is high-speed, or I will not finish my project on time and pass the course. 82
Complete the truth table below: ������ ¬������ ¬������ ¬������ ∧ ������ T a) ¬������ ∧ ������ F T ������ F T T F F b) (¬������ ∧ ������) ∨ ������ q r ¬r ¬r Ù p (¬������ ∧ ������) ∨ ������ T T p T F T F T T F F T T T T T F F F T F F F F F c) ¬(������ ∧ ������) d) (������ → ¬������) ∨ (������ ∧ ¬������) 83
Exercise 5.1 1. State which of the following statements are propositions. Give the truth values of the propositions. a) All even numbers are divisible by 2. b) Load the packages in the car. c) This statement cannot possibly be true. d) Jupiter is the closest planet to the sun. e) Hard disks should never be stored in the microwave. 2. Let ������, ������, and ������ be the following statements: ������: He reads comics. ������: He loves science fiction. ������: He wants to be a computer scientist. Express the following sentences as symbolic expressions. a) If he reads comic books and loves science fiction, then he wants to be a computer scientist. b) He loves science fiction is a necessary condition to be a computer scientist. c) Only if he wants to be a computer scientist, then he must love science fiction. Express the following logical expressions as English sentences. d) ¬(������ → ������) e) (������ ∨ ������) → ¬������ f) (������ → ������) ∧ (¬������ → (¬������ ∨ ������)) 3. If the truth values of proposition ������ and ������ are true, and the truth values of proposition ������ and ������ are false, find the truth values for the following propositions. a) ������ ∨ (������ ∧ ������) b) (������ ∧ (������ ∨ ������)) → ((������ ∨ ������) ∨ (������ ↔ ������)) 4. Determine the truth value of the following statements. a) If ������ < 0 then ������^3 is a negative number. b) If 3 − 4 = 1 then 3 + 4 = 7. 84
Logical Equivalence and The Laws of Logic Definition 5.7 Two statements ������ and ������ are said to be logically equivalent, and we write ������ ⟺ ������ when the statement ������ is true (respectively, false) if and only if the statement ������ is true (respectively, false). Equivalence of two propositions can easily be established by constructing both tables for both propositions and then comparing the two. Let ������: Today is Sunday. ¬������: Today is not Sunday. ¬¬������: It is not true that today is not Sunday. ������ ¬������ ¬¬������ Hence, ������ is logically equivalent to ¬¬������, or ������ ⇔ ¬¬������. Let ������: Tony Stark is a billionaire. ������: Tony Stark is Iron Man. ������ ∧ ������: ¬(������ ∧ ������): ¬������: ¬������: ¬������ ∨ ¬������: 85
������ ������ ������ ∧ ������ ¬(������ ∧ ������) ¬������ ¬������ ¬������ ∨ ¬������ ¬(������ ∧ ������) logically equivalent to ¬������ ∨ ¬������ ¬(������ ∧ ������) ⇔ ¬������ ∨ ¬������ Definition 5.8 Tautology is a propositional statement that is TRUE for all cases. Let ������: It is raining. ������ ∨ ¬������: Let ������: Socrates is a philosopher. ������: Socrates is a joker. (������ ∧ ������) → ������: 86
The following logical expression is a tautology. ((������ ∧ ������) → ������) ↔ (������ → (������ → ������)) The final column of the truth table shows that all the values are true. Definition 5.9 Contradiction is a propositional statement that is FALSE for all cases. Let ������: It is raining. ������ ∧ ¬������: Let Tommy is a singer. ������: Tommy is an actor. ������: 87
(������ ∨ ������) ∧ (¬������ ∧ ¬������): Definition 5.10 Contingent: a propositional statement that is neither a tautology nor a contradiction. Let ������: Fitri loves to drive fast. ������: Fitri is a professional racer. (������ ∨ ������) ∧ ¬������: A conditional statement of the form ������ → ������ is associated with three other statements: converse, inverse and contrapositive. ������ → ������ Conditional ������ → ������ Converse ¬������ → ¬������ Inverse ¬������ → ¬������ Contrapositive 88
The truth tables for the above statements are as follows: ������ ������ ¬������ ¬������ ������ → ������ ������ → ������ ¬������ → ¬������ ¬������ → ¬������ TT F F TF F T FT T F FF T T From the table, we can conclude the following statement. • An implication is logically equivalent to its contrapositive (������ → ������) ⟺ (¬������ → ¬������) • A converse of an implication is logically equivalent to an inverse of an implication (������ → ������) ⟺ (¬������ → ¬������) Given the statement, “If Amin is mindful of his spending, then he can save money.”. We have the following statement. Converse: Inverse: Contrapositive: Write the converse, inverse and contrapositive of the statement, “If a pizza topping has pepperoni and zucchini, then the pizza is delicious.” Converse: Inverse: Contrapositive: 89
Laws of logic Using the concepts of logical equivalence, tautology, and contradiction, the following is the list of rules for the algebra of propositions. Suppose that ������ , ������ , and ������ are arbitrary statements; ������> is any tautology, and ������> is any contradiction. a) Double Negation ¬¬������ ⟺ ������ b) De Morgan’s Law c) Commutative Law ¬(������ ∧ ������) ⟺ ¬������ ∨ ¬������ d) Associative Law ¬(������ ∨ ������) ⟺ ¬������ ∧ ¬������ e) Distributive Law f) Idempotent Law ������ ∧ ������ ⟺ ������ ∧ ������ g) Identity Law ������ ∨ ������ ⟺ ������ ∨ ������ h) Dominance Law (������ ∧ ������) ∧ ������ ⟺ ������ ∧ (������ ∧ ������) i) Inverse Law (������ ∨ ������) ∨ ������ ⟺ ������ ∨ (������ ∨ ������) j) Absorption Law (������ ∧ ������) ∨ ������ ⟺ (������ ∨ ������) ∧ (������ ∨ ������) k) Implication (������ ∨ ������) ∧ ������ ⟺ (������ ∧ ������) ∨ (������ ∧ ������) ������ ∧ ������ ⟺ ������ ������ ∨ ������ ⟺ ������ ������ ∧ ������> ⟺ ������ ������ ∨ ������> ⟺ ������ ������ ∧ ������> ⟺ ������> ������ ∨ ������> ⟺ ������> ������ ∧ ¬������ ⟺ ������> ������ ∨ ¬������ ⟺ ������> (������ ∧ ������) ∨ ������ ⟺ ������ (������ ∨ ������) ∧ ������ ⟺ ������ ������ → ������ ⟺ ¬������ ∨ ������ l) Biconditional ������ ↔ ������ ⟺ (������ → ������) ∧ (������ → ������) 90
Simplify (������ ∨ ������) ∧ ¬(¬������ ∧ ������) using the laws of logic. (������ ∨ ������) ∧ ¬(¬������ ∧ ������) Reasons ⟺ (������ ∨ ������) ∧ (¬¬������ ∨ ¬������) ⟺ (������ ∨ ������) ∧ (������ ∨ ¬������) ⟺ ������ ∨ (������ ∧ ¬������) ⟺ ������ ∨ ������> ⟺ ������ By using the laws of logic, simplify the following logical expression. (������ → ������) ∧ (������ → ¬������) (������ → ������) ∧ (������ → ¬������) Reasons Prove the following logical equivalence. ¬B¬B(������ ∨ ������) ∧ ������C ∨ ¬������C ⟺ ������ ∧ ������ ¬B¬B(������ ∨ ������) ∧ ������C ∨ ¬������C Reasons 91
This section shows how the ideas of the laws of logic can be used in simplifying switching networks (or circuit diagrams). Switching network A network made up of wires and switches connecting two terminals, ������D and ������E. In such a network, each switch is either open (F) = no current flow, or closed (T) = current flow ������ ������D ������ ������E ������D ������E ������D ������ ������ ������E ������ (c) (a) (b) A series network A network with one A parallel network ������ ∧ ������ switch ������ ∨ ������ Give the logical expression corresponding to the following switching networks. p a) T1 q T2 ������ ∨ ������ ∨ ������ r b) T1 p T2 qr s p c) T1 q T2 r 92
Search
Read the Text Version
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132