Computer Fundamentals.
ASSIGNMENT 1.
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.
2
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) (ii) (iii) (iv) State the argument in symbols. Rewrite the symbolic argument as a proposition Construct a truth table for the proposition. 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. 1 2 3 4 5 6 7 8 9 Either the light is not on or the system is ready. If the system is ready then the light is on. If the light is on then the system is not ready. If the light is not on then the system is not ready. If the system is not ready then the light is not on. Either the system is not ready or the light is on. If the light is on then the system is ready. If the system is ready then the light is not on. Either the system is not ready or the light is not on.
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]
ENS1161_A1_ECU_v12_2_2014.doc
Page 2 of 6
3
Question 2
A group of 100 students is polled to see how many watched three TV shows, Action, Buzz and Calypso. The results showed that 59 watched Action, 68 watched Buzz, 52 watched Calypso, 41 watched Action and Buzz, 34 watched Action and Calypso, 38 watched Buzz and Calypso, and 11 did not watch any of the three. Let A denote the set of students who watched Action, and similarly define sets B and C. (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.
A ? ? ? ? ? ? B ?
… C . .
?
(b)
Hence find how many students watched: (i) Action and Calypso, but not Buzz; (ii) Buzz 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. 1 2 3 4 5 6 7 8 9 10 11 12 There is at least one movie that some person has seen. For each movie there is somebody who has not seen it. There is some movie that nobody has seen. There is at least one movie that everybody has seen. For each movie there is somebody who has seen it. There is some person who has not seen any of the movies. There is at least one movie that some person has not seen. Nobody has seen any of the movies. For each person there is some movie that they have not seen. Everybody has seen at least one movie. There is some person who has seen all the movies. Everybody has seen all of the movies.
ENS1161_A1_ECU_v12_2_2014.doc
Page 3 of 6
4 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]
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, then the kth bit of the bit string is 1. If the kth element of U is not in S, then the kth bit of the bit string is 0.
Example 1: 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. (This is just like constructing a truth table that is “turned on its side.”) Example 2: 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 A B A A A’ Then, from the table, B B 4 0 1 1 0 1 6 1 0 1 0 0 9 0 0 0 0 1 13 1 1 1 1 0 18 1 1 1 1 0 25 0 1 1 0 1
ENS1161_A1_ECU_v12_2_2014.doc
Page 4 of 6
5 A B is represented by: A B is represented by: A’ is represented by: 110111, so A B = {4, 6,13, 18, 25} 000110, so A B = {13, 18} 101001, so A’ = {4, 9, 25}
Your task: Let the universal set U be the following set of 16 countries: U = {Argentina, Australia, Belgium, Brazil, Cameroon, Chile, Cuba, Denmark, Egypt, Ethiopia, Fiji, France, Germany, Ghana, Greece, Haiti} (i) (ii) (iii) Find the bit string that represents the set L = { Brazil, Fiji, Ghana, Greece } Find the set M represented by the bit string 0000 0110 1001 0001 Let P, Q, R and S be sets represented by the following four bit strings respectively:
P Q R S 1 0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 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, with a row for each of Q’, P Q’, R’, … etc.) (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 f g e
ENS1161_A1_ECU_v12_2_2014.doc
b
c d
Page 5 of 6
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
Key w 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
Binary representation x 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 y 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 z 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Segment …
Fundamental product
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 d and g, and is as follows. For each of the two functions d(w, x, y, z) and g(w, x, y, z): (i) (ii) (iii) construct a truth table for the function (like the one shown above); construct the corresponding Karnaugh map; 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]
PLACE THIS ORDER OR A SIMILAR ORDER WITH US TODAY AND GET AN AMAZING DISCOUNT :