Question 2 (24 marks)
(a) Using a truth table verify that:5 marks
(? ∧ ?) → ? ≡ ? → (¬? ∨ ?). (1)
(b) Use the laws of logic to show that:5 marks
(? ∧ ?) → ? ≡ ? → (¬? ∨ ?). (2)
(c) A digital circuit takes three logical inputs ?, ?, ? and produces the logical
output ?(?, ?, ?) as set out in Table 1.
Table 1: Logical output of ?(?, ?, ?), for values of the logical input variables ?, ?
and ? .
? XXXXXXXXXX
? XXXXXXXXXX
? XXXXXXXXXX
?(?, ?, ? XXXXXXXXXX
(i) Write down the disjunctive normal form for the proposition with the4 marks
truth values given by ?.
(ii) Simplify the following logical expression using a Karnaugh map:5 marks
(? ∧ ? ∧ ¬?) ∨ (? ∧ ¬? ∧ ¬?) ∨ (¬? ∧ ? ∧ ?) ∨ (¬? ∧ ¬? ∧ ¬?) . (3)
(d) Write down the boolean expression which co
esponds to the following logic5 marks
circuit. Do not simplify.
1
Question 3 (24 marks)
(a) The following function ?(?) is defined recursively as:
?(?) =
⎧{
⎨{⎩
1, ? = 1
43, ? = 2
−2?(? − XXXXXXXXXX?(? − 2), ? ≥ 3
(1)
(i) Compute ?(3) and ?(4).2 marks
(ii) Find a general non-recursive formula for the recu
ence.5 marks
(iii) Find the particular solution which satisfies the initial conditions ?(1) =5 marks
1 and ?(2) = 43.
(b) Consider the following Venn diagram, illustrating the Universal Set ?, and
the sets ?, ?, and ?.
mouse,horse camel
shark,dolphin,eel
? Bird
? ?
?
wolf
cat,pig
frog snake
Find and list the elements of the following:
(i) The set defined by ? ∪ ?.4 marks
(ii) The set defined by (? ∩ ?) − ?.4 marks
(iii) The elements of the Universal set ?.4 marks
1
Question 4 (16 marks)
(a) Consider the graph below.
(i) Write down the adjacency matrix for this graph.3 marks
(ii) Analysing the adjacency matrix, determine if the graph is Eulerian,3 marks
Semi-Eulerian or neither. Justify your answer in terms of the relevant
theory.
(b) Consider the following graph (Not to scale).
Find the following:
(i) Weight matrix for the graph.4 marks
(ii) Compute and list the vertices that make up the minimal spanning tree6 marks
for the above graph.
1
Question 1 (36 Marks)
(a) Convert the binary number XXXXXXXXXX XXXXXXXXXXto octal.4 marks
(b) Find the binary number representation for the hexadecimal number 3?.6B516.4 marks
(c) ASCII characters are mapped to 8-bits, using Table 1 (given at the end of
the exam). Answer the following questions.
(i) Find the bit-pattern which represents the following characters:4 marks
Ate
(ii) The hexadecimal representation of a two characters bit pattern is XXXXXXXXXXmarks
What characters does this represent?
(d) Suppose we have a computer in which every integer must be stored in 7-bits
with the same number of negative and non-negative integers (i.e. as signed
integers) find the following.
(i) The signed integer represented by the 7-bits: XXXXXXXXXXmarks
(ii) The range of signed integers that can be represented.5 marks
(e) In a computer where every real (floating point) number must be represented
in 11-bits, of which five (5) are assigned to the characteristic. Assuming
that the bias for a ?-bit characteristic is 2?−1 − 1, find the following:
(i) the 11-bit floating point representation for 68.5 marks
(ii) the real number represented by the following 11-bits:5 marks
XXXXXXXXXX
1
Table
1:
H
exadecim
alm
ap
ofthe
“C
ontrol,Basic
and
Supplem
entalLatin
1
C
haracte
set”
to
an
8-bit
encoding
schem
e,as
pe
U
nicode
10.
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
0
N
U
LL
SO
H
ST
X
ET
X
EO
T
EN
Q
A
C
K
BELL
BS
H
T
LF
V
T
FF
C
R
SO
SI
1
D
LE
D
C
1
D
C
2
D
C
3
D
C
4
N
A
K
SY
N
ET
B
C
A
N
EM
SU
B
ESC
FS
G
S
R
S
U
S
2
SP
!
”
#
$
%
&
’
(
)
*
+
,
-
.
3
0
1
2
3
4
5
6
7
8
9
:
;
=
?
4
@
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
5
P
Q
R
S
T
U
V
W
X
Y
Z
[
\
]
^
_
6
‘
a
c
d
e
f
g
h
i
j
k
l
m
n
o
7
p
q
s
t
u
v
w
x
y
z
{
|
}
~
D
EL
8
X
X
X
X
X
X
BPH
N
BH
IN
D
N
EL
SSA
ESA
H
T
S
H
T
J
V
T
S
PLD
PLU
R
I
SS2
SS3
9
D
C
S
PU
1
PU
2
ST
S
C
C
H
M
W
SPA
EPA
SO
S
X
X
X
SC
I
C
SI
ST
O
SC
PM
A
PC
A
N
BSP
¡
¢
£
¤
¥
¦
§
¨
©
ª
«
¬
SH
®
¯
B
°
±
²
³
´
µ
¶
·
¸
¹
º
»
¼
½
¾
¿
C
À
Á
Â
Ã
Ä
Å
Æ
Ç
È
É
Ê
Ë
Ì
Í
Î
Ï
D
Ð
Ñ
Ò
Ó
Ô
Õ
Ö
×
Ø
Ù
Ú
Û
Ü
Ý
Þ
ß
E
à
á
â
ã
ä
å
æ
ç
è
é
ê
ë
ì
í
î
ï
F
ð
ñ
ò
ó
ô
õ
ö
÷
ø
ù
ú
û
ü
ý
þ
ÿ
2