ENS1161 Computer Fundamentals

ASSIGNMENT 1

Semester 2, 2014

Topics covered:
Logic, sets, Boolean algebra, Karnaugh maps and circuits.

Source material:
Lectures 1 to 4 and tutorial exercise sheets available on the Blackboard.

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.

2
ENS1161_A1_ECU_v12_2_2014.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]

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.

3
ENS1161_A1_ECU_v12_2_2014.doc     Page 3 of 6
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.

(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.

…
.
.
?
A  B
C
?
?
?
?
?
?  ?
1  There is at least one movie that some person has seen.
2  For each movie there is somebody who has not seen it.
3  There is some movie that nobody has seen.
4  There is at least one movie that everybody has seen.
5  For each movie there is somebody who has seen it.
6  There is some person who has not seen any of the movies.
7  There is at least one movie that some person has not seen.
8  Nobody has seen any of the movies.
9  For each person there is some movie that they have not seen.
10  Everybody has seen at least one movie.
11  There is some person who has seen all the movies.
12  Everybody has seen all of the movies.

4
ENS1161_A1_ECU_v12_2_2014.doc     Page 4 of 6
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 k
th
element of U is in S, then the k
th
bit of the bit string is 1.
If the k
th
element of U is not in S, then the k
th
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 1
st
element of U is in A, so the 1
st
element of the bit string is 1;
the 2
nd
element of U is not in A, so the 2
nd
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 1
st
element of the bit string is 0, so the 1
st
element of U, that is 1, is not in C;
the 2
nd
element of the bit string is 1, so the 2
nd
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  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,
5
ENS1161_A1_ECU_v12_2_2014.doc     Page 5 of 6
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}

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)  Find the bit string that represents the set L = { Brazil, Fiji, Ghana, Greece }

(ii)  Find the set M represented by the bit string   0000 0110 1001 0001

(iii)  Let P, Q, R and S be sets represented by the following four bit strings respectively:

P  1  1  0  1  0  1  0  0  1  0  1  0  1  1  1  0
Q  0  1  1  1  1  1  0  0  0  1  0  0  1  0  1  1
R  0  1  0  1  1  1  0  1  1  0  0  1  1  0  0  1
S  1  1  0  1  0  0  1  1  0  1  1  0  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, 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
b
d
c  e
f
g
6
ENS1161_A1_ECU_v12_2_2014.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 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)  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

PLACE THIS ORDER OR A SIMILAR ORDER WITH US TODAY AND GET AN AMAZING DISCOUNT