ENS1161D_A1_v27_ECC_1_2017.doc School of Engineering ©ECU 3/02/2017 ENS1161 Computer Fundamentals ASSIGNMENT 1 Trimester 1, 2017 Topics covered: Logic, sets, Boolean algebra, Karnaugh maps and circuits. Source material: Lectures 1 to 4 and tutorial exercise sheets are available on Moodle. Marks: 15% of total marks for the unit. The assignment will be marked out of 40 and then scaled to a mark out of 15. Due date: Week 6 of semester (see Moodle or lecturer for details) A penalty for late submissions will apply as specified in the handbook. Submission instructions: Please ensure that you submit your assignment in the correct box. (No responsibility will be taken for assignments submitted incorrectly) If you are unsure, check with your lecturer or tutor. Applications for extension: Applications for extension (on medical or other grounds) should be made in writing to the unit coordinator before the due date, and should be accompanied by appropriate evidence (eg medical certificate) to support your application. Presentation: You may use a computer package to prepare your submission, but it is not essential. In some cases it may be preferable to put in diagrams and symbolic expressions by hand if you are not competent to produce an acceptable result using a computer package. You should use one side of each sheet only. Plastic covers are not required; in fact they usually complicate the processing of submissions. ENS1161D_A1_v27_ECC_1_2017.doc Page 2 of 6 Question 1 (a) Consider the following argument. If bears are brown then giraffes are not green. If bears are not brown then rabbits are red. Rabbits are red. Therefore giraffes are not green. Define the following propositions: b: bears are brown g: giraffes are green r: rabbits are red (i) State the argument in symbols. (ii) Rewrite the symbolic argument as a proposition (iii) Construct a truth table for the proposition. (iv) State whether the argument is valid. (b) The propositions below can be arranged in three groups so that each member of a group is logically equivalent to the other two. Find the three groups. Give your answer by listing the three groups, for example "2, 5 and 9" (which is not necessarily a correct answer) [ Hint: It may help to realise that the first three of the expressions p  q, ~q  ~p, ~p  q, q  p are logically equivalent to each other but they are not logically equivalent to the fourth (as you could verify using a truth table ). ] [5 + 3 = 8 marks] Question 2 A group of 140 students is polled to see how many watched three TV shows, Awesome, Bongo and Crikey. The results showed that 66 watched Awesome, 63 watched Bongo, 63 watched Crikey, 34 watched Awesome and Bongo, 31 watched Awesome and Crikey, 26 watched Bongo and Crikey, and 27 did not watch any of the three. Let A denote the set of students who watched Awesome, and similarly define sets B and C. 1 Either the light is not on or the system is ready. 2 If the system is ready then the light is on. 3 If the light is on then the system is not ready. 4 If the light is not on then the system is not ready. 5 If the system is not ready then the light is not on. 6 Either the system is not ready or the light is on. 7 If the light is on then the system is ready. 8 If the system is ready then the light is not on. 9 Either the system is not ready or the light is not on. ENS1161D_A1_v27_ECC_1_2017.doc Page 3 of 6 (a) Calculate the number of students in each of the eight subsets shown in the Venn diagram. Copy the Venn diagram and enter the number of students in each subset. (b) Hence find how many students watched: (i) Awesome and Crikey, but not Bongo; (ii) Bongo only; (iii) only two of the three shows; (iv) at least two of the shows. [8 + 2 = 10 marks] Question 3 Suppose that P is a set of people and M a set of movies. Define the predicate S(p, m) to mean "person p has seen movie m". Consider the following list of sentences. For each sentence, the negation is also in the list. Your task is to match each sentence with its negation. Give your answer by listing the number of each sentence and its negation, for example "4 and 10" (which is not necessarily a correct answer.) [6 marks] … . . ? A B C ? ? ? ? ? ? ? 1 There is at least one movie that some person has seen. 2 There is some movie that nobody has seen. 3 There is at least one movie that some person has not seen. 4 There is some person who has not seen any of the movies. 5 For each person there is some movie that they have not seen. 6 Nobody has seen any of the movies. 7 Everybody has seen all of the movies. 8 Everybody has seen at least one movie. 9 For each movie there is somebody who has seen it. 10 For each movie there is somebody who has not seen it. 11 There is at least one movie that everybody has seen. 12 There is some person who has seen all the movies. ENS1161D_A1_v27_ECC_1_2017.doc Page 4 of 6 Question 4 Introduction: There is a simple way of representing sets using so-called "bit strings". A bit string is simply a string of 0's and 1's. Suppose that U is the universal set. Then the rule for the bit string for a particular set S is: If the kth element of U is in S, the kth bit of the bit string is 1. If the kth element of U is not in S, the kth bit of the bit string is 0. (Usually the order of the elements of a set is irrelevant. However when using bit strings the order of the elements as specified in the universal set U must be adhered to.) Example: Suppose the universal set is U = {1, 2, 3, 4, …, 10}. Then the set A = {1, 3, 5, 9} is represented by the bit string 1010100010 because: the 1st element of U is in A, so the 1st element of the bit string is 1; the 2nd element of U is not in A, so the 2nd element of the bit string is 0, and so on. Similarly, the set {5, 6, 7} is represented by the bit string 0000111000. Conversely, the bit string 0110010001 represents the set C = {2, 3, 6, 10} because: the 1st element of the bit string is 0, so the 1st element of U, that is 1, is not in C; the 2nd element of the bit string is 1, so the 2nd element of U, that is 2, is in C; and so on. Similarly, the bit string 0000000110 represents {8, 9}, and the bit string 0101010101 represents {2, 4, 6, 8, 10}. The operations of union, intersection and complement may be carried out on the bit strings. The simplest way is to use a table and to work "bitwise", that is carry out the operations on the first bits, then the second bits, and so on. Example: Let the universal set be U = {4, 6, 9, 13, 18, 25}, and consider the sets A = { 6, 13, 18 } and B = {4, 13, 18, 25}. Suppose that we want to find A  B, A  B and A'. Using a table and performing the operations "bitwise": U 4 6 9 13 18 25 A 0 1 0 1 1 0 B 1 0 0 1 1 1 A  B 1 1 0 1 1 1 A  B 0 0 0 1 1 0 A' 1 0 1 0 0 1 Then, from the table, A  B is represented by: 110111, so A  B = {4, 6,13, 18, 25} A  B is represented by: 000110, so A  B = {13, 18} A' is represented by: 101001, so A' = {4, 9, 25} ENS1161D_A1_v27_ECC_1_2017.doc Page 5 of 6 Your task: Let the universal set U be the following set of 16 countries: U = {Angola, Benin, Chad, Djibouti, Eritrea, Ghana, Kenya, Libya, Mali, Namibia, Rwanda, Sudan, Tanzania, Uganda, Zaire, Zambia} (i) Find the bit string that represents the set L = { Djibouti, Mali, Tanzania, Uganda } (ii) Find the set M represented by the bit string 0110 0010 0110 0010 (iii) Let P, Q, R and S be sets represented by the following four bit strings respectively: P 0 1 1 1 0 1 0 1 0 1 1 0 1 0 0 1 Q 0 1 0 1 0 0 1 1 1 0 1 0 1 0 1 1 R 1 1 0 1 1 1 0 0 0 1 0 0 1 1 1 0 S 1 1 0 1 0 1 1 0 1 0 0 1 1 0 0 1 By using bitwise operations on the four bit strings, find the bit string that represents the set T = (P  Q')  (R'  S). (Set out your working in a table.) (iv) List the countries in the set T defined in (iii). [1+ 1 + 3 + 1 = 6 marks] Question 5 In the lecture notes there is an application of Karnaugh maps to a 7-segment display that is used in some calculators and similar digital devices. The display is sometimes extended to include all hexadecimal digits. A typical extended display is: Notice the display for the hexadecimal digits for 10 through 15. Some are shown as upper case and some lower case: A b c d E F. As in the lecture notes we label each of the seven segments as shown: a b d e c f g ENS1161D_A1_v27_ECC_1_2017.doc Page 6 of 6 When any one of the keys 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E or F is pressed, a 4-bit binary signal "wxyz" is generated, as shown in the table For each of the seven segments there is a corresponding Boolean function and a circuit that has output 0 or 1 as the various keys are pressed. Denote these functions by a(w, x, y, z), b(w, x, y, z), …, g(w, x, y, z). Your task concerns the two segments b and e, and is as follows. For each of the two functions b(w, x, y, z) and e(w, x, y, z): (i) construct a truth table for the function (like the one shown above); (ii) construct the corresponding Karnaugh map; (iii) find a minimal sum of products for the function. NOTE: Use the "simple" labelling on the Karnaugh maps and show your groups clearly. [10 marks] Key Binary representation Segment Fundamental w x y z … product 0 0 0 0 0 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 A 1 0 1 0 B 1 0 1 1 C 1 1 0 0 D 1 1 0 1 E 1 1 1 0 F 1 1 1 1