Question 1 [17] Question 1.1 (3) Consider the relation R = {(x,y) ? ?? +???? | ?? = ?? ?????? 5 } Motivate your answer in each case. 1.1.1 Is 2R2? 1.1.2 Is -3R2? 1.1.3 Is 13R3? Question 1.2 Consider the relations and answer the questions that follow: (4) Owner Surname Firstname Id number Mahlangu Peter 9101115463081 Mahlangu Peter 9804145321083 Ngwete Shahieda 9606280435084 Property Id number Property nr StartDate Enddate 9101115463081 Prop 1 2020-02-01 2020-12-31 9804145321083 Prop 2 2019-08-01 2021-01-01 9804145321083 Prop 1 2019-08-01 2021-01-01 1.2.1 Identify a suitable primary key (PK) for Owner and Property. Motivate your answer. /2/ 1.2.2 Write the contents of J1 of Owner and Property in set-roster notation. Call the set OWNS. /2/ 1.3 Consider the arrow diagrams for the relations R and S and answer the questions related to them. (5) 1.3.1 Is R a function? Motivate your answer /1.5/ 1.3.2 Is S a function? Motivate your answer /1.5/ 1.3.3 Is the relation y = v?? 2 + 1 defined on x ? [-2,2] a function? Motivate your answer.
ADS216D Assignment X Total marks: 155 Due date: 9 August (12PM) Submission platform: D2L Submission format: PDF Please note that all questions will not be marked. The lecturers will select a few representative questions to mark. You must attempt all questions, since leaving out a few may result in a very poor mark. Ensure that you follow submission guidelines as specified in the study guide regarding naming of the document, font size etc. Question 1 [17] Question 1.1 (3) Consider the relation R = {(x,y) ∈ ?+?? | ? = ? ??? 5 } Motivate your answer in each case. 1.1.1 Is 2R2? 1.1.2 Is -3R2? 1.1.3 Is 13R3? Question 1.2 Consider the relations and answer the questions that follow: (4) Owner Surname Firstname Id number Mahlangu Peter 9101115463081 Mahlangu Peter 9804145321083 Ngwete Shahieda 9606280435084 Property Id number Property nr StartDate Enddate 9101115463081 Prop 1 2020-02-01 2020-12-31 9804145321083 Prop 2 2019-08-01 2021-01-01 9804145321083 Prop 1 2019-08-01 2021-01-01 1.2.1 Identify a suitable primary key (PK) for Owner and Property. Motivate your answer. /2/ 1.2.2 Write the contents of J1 of Owner and Property in set-roster notation. Call the set OWNS. /2/ 1.3 Consider the arrow diagrams for the relations R and S and answer the questions related to them. (5) 1.3.1 Is R a function? Motivate your answer /1.5/ 1.3.2 Is S a function? Motivate your answer /1.5/ 1.3.3 Is the relation y = √?2 + 1 defined on x ∈ [-2,2] a function? Motivate your answer. /2/ Question 1.4 (5) Study the sets A = {1,2,3,4} and B = {-7, -3, 1, 2, 3, 8} a) The relation R is defined as R = { (x,y) ∈ ? ? ?| ? ≡ ? (??? 4)}. Write the elements of R in set-roster notation b) The relation R is defined as R = { (x,y) ∈ ? ? ?| ? = −? ??? 4}. Write the elements of R in set-roster notation Question 2 [19] Question 2.1 Complete the last 5 columns of the following truth table and answer the following questions. Remember to motivate each answer using the table contents. (8) a) Are there any two expressions that are logically equivalent? Motivate your answer. b) Is there an expression that is a tautology? Motivate your answer. c) Does p∪q → (? → ~?)? Motivate your answer. p q r ~p ~q ~r p∪q p→~q ~q→r q→ ~? (p∪q) ∪ (? → ~?) ∪ (~q→ ?) T T T F F F T T F F F T T F T F T F T F F F T T F T T T F F F T F T F T F F T T T F F F F T T T 2.2 Write the following statements in symbolic form using universal and existential quantifiers and and suitable predicates and logical operators, using the following: Let B be the set of all books Let P(b) be the predicate “The book b is available” Let Q(b) be the predicate “The book b is ordered”. Write statements for the following: (5) 2.2.1 Some books are not available /1/ 2.2.2 If a book is not available, it is ordered /2/ 2.2.3 Not all books that are ordered, are unavailable /2/ 2.2.4 Write the contrapositive form of statement 2.2.2 in natural language, and then in symbolic form. 2.3 Prove the conclusion from the premises, using valid argument forms. (6) 1 Step 1 2 3 4 Step 2 5 6 7 Step 3 8 9 10 Step 4 11 12 13 Step 5 14 15 Question 3 [19] Prove the following. Supply reasons or every step, using only theorems provided in the appendix and definitions as applicable. Question 3.1 Prove that, for all integers a and b, if a is odd and b is odd, then a + 2b is odd using direct proof. (5) Question 3.2 Prove that, if a and b are rational numbers, and s a non-zero irrational number, then a + sb is irrational using indirect proof. (5) Question 3.3 (use strong induction) (9) Question 4 [29] Question 4.1 (8) Consider a pin containing 3 or 4 numeric digits. Show all your calculations and formulas used. Round your answers to two decimal digits. For this question, a pin starting with 0 is valid, for example 012 and 0432 are both valid pins. Of course they can also start with other digits like 5 or 7. a) Determine the total number of pins that can be created if duplicate digits are allowed – call this N(A) b) Determine the total number of pins that can be created if no repetition of characters/ digits are allowed – call this N(U) c) Determine the total number of pins that can be created if at least one duplicate digit is allowed – call this N(1D) d) Determine the probability that at least one duplicate digit can be found in a randomly generated pin. Question 4.2 (10) Consider constructing a team with 6 members out of a group of 9 people. You may leave your answer in factorial form. Use P(n,r), C(n,r) or nk in your answer, but then also substitute the actual values (e.g. 6! or 32). You do not need to calculate final answers. a) Determine how many teams can be formed if there is no other constraint on the construction of the team. b) Determine how many teams can be formed if there are three group members that want to work together, or be left out of the team together. c) If the group consists of 5 analysts and 4 programmers, how many teams containing exactly 4 analysts and 2 programmers can be created? d) A team of 10 must be created from a group of 5 women and 12 men. How many teams can be created with at least one woman? Question 4.3 (7) a) In how many ways can 4 people be seated at 6 desks? b) If two people always need to sit at the 2 isles, in how many ways can 6 people be seated at 6 desks? c) If 6 people are seated randomly at 6 desks, what is the probability that 2 specific people will sit at the isles? Question 4.4 (4) a) If there are 15 people in a room, what is the minimum number of people that will have their birthday on the same day of the week (e.g. Monday)? Explain what principle you are using. b) If you draw cards from a deck of cards, how many cards must you draw to ensure you get two cards of the same colour? State the principle that you are using. Question 5 [41] Question 5.1 (6) Determine the order of the vertices visited in the following tree: a) If pre-order traversal is used /2/ b) If in-order traversal is used /2/ c) If post-order traversal is used /2/ Question 5.2 (3) Write down the incidence matrix of the following graph. Question 5.3 (7) a) Prove that the following two matrices are isomorphic by finding a suitable onto function that maps the elements of graph 1 to those of graph 2. /5/ b) Determine the total degree of Graph 1, showing all steps. /1/ c) Is this a simple graph? Motivate your answer. /1/ Question 5.4 (3) Create a spanning tree from the following graph, using breadth-first traversal, and removing circuits, where necessary. Use vertex a as the root of the tree and use alphabetic ordering of the vertices. Draw the spanning tree. Question 5.5 (7) a) Convert the following graph to a bipartite graph. Show the bipartite nature clearly using suitable drawing of the graph. b) Draw the adjacency matrix for the