CO1103 - 2020/2021

Class Test (4th December 2020)

There are 10 questions (and 11 pages) in total in the booklet.

There are 100 marks available in total for the test.

The number of marks allocated to each part of a question is shown.

This is an open book exam. You can use any of our module
material. You can use a calculator.
You are not allowed to discuss the questions or answers with others.

Convert your answers to a single pdf file. Submit this file via
blackboard.

1
Question 1

(i) Consider the proposition

It is not the case that if x > 5 or y > 5 then xy > 25.
Translate the proposition from informal notation to formal notation. Make it clear what
each propositional letter stands for. [3 marks]

(ii) Consider the proposition

(P ∧ Q) =⇒ ¬R
where P stands for ”x is even”, Q stands for ”y > 5” and R stands for ”x2 is odd”.

a) Translate the proposition from formal notation to informal notation. [3 marks]

b) Prove this proposition (for all x, y ∈ N) using a direct proof. [4 marks]

Solution.

(i) ¬((P ∨ Q) =⇒ R), where P stands for ”x > 5”, Q stands for ”y > 5”, and R stands for
”xy > 25”.

(ii) a) If x is even and y > 5 then it is not the case that x2 is odd.
b) We assume (P ∧ Q) is true and show that ¬R is true. By our assumption, x is even
and y > 5. As x is even, it can be written as a multiple of two: x = 2m for some
integer m. So x2 = (2m)2 = 4m2 = 2 × (2m2 ). So x2 is a multiple of two and hence
even. So it is not the case that x2 is odd. Hence ¬R is true.

2
Question 2

(i) For each of the following, say whether the statement is true or false, justifying your
answer briefly in each case.

a) N ∪ R ⊂ Z [2 marks]
b) Z − N ⊆ R − Z. [2 marks]
c) N ∈ P (Z). [2 marks]

(ii) Prove that, for all sets A, B and C, we have that

(A ∪ B) ∩ (C − B) = (A ∩C) − B. [4 marks]

Solution.

(i) a) This is false. For example 3.4 ∈ N ∪ R but 3.4 6∈ Z .

b) This is false. For example −3 ∈ Z − N but −3 6∈ R − Z .
c) This is true. Every natural number is also an Integer. Hence the N is a subset of
Z. So, N is an element of the power set of Z.

(ii) So, x ∈ (A ∪ B) ∩ (C − B) ⇔.

(x ∈ A or x ∈ B) and x ∈ C and x 6∈ B ⇔

x ∈ A and x ∈ C and x 6∈ B ⇔
x ∈ (A ∩C) − B

3
Question 3 Consider the regular expressions R = (x|y|z)4 xyz∗ and S = xyz4 (x|y|z)∗ .

(i) Give a word of length 8 that matches R but not S. If no such word exists, give a reason
why this is the case. [2 marks]

(ii) Give a word of length 8 that matches S but not R. If no such word exists, give a reason
why this is the case. [2 marks]

(iii) Give a word of length 8 that matches S and R. If no such word exists, give a reason
why this is the case. [2 marks]

(iv) A coffee machine creates logs of its operations. A log is a sequence over 6 different
actions, abbreviated by the letters a, b, c, d, e, f . The letter c stands for the action of a
cup change; the letter f stands for the action of filling up the cup with coffee.
Let L be the language of all logs that have at some point two fill actions without a cup
change between them. Give a regular expression R such that L(R) = L [4 marks]

Solution.

(i) xxxxxyzz

(ii) xyzzzzzz

(iii) Such a word cannot exist. The fifth letter of any word in R has to be an x. While the
fifth letter of any word in S has to be a z.

(iv) (a|b|c|d|e| f )∗ f (a, b, d, e)∗ f (a|b|c|d|e| f )∗

4
Question 4

(i) Consider the sets A = {0, 1, 2, 3}, B = {s,t, u, v} and C = {2, 3, 4, 5, 6}, and the relations
R ⊆ A × B with R = {(0, u), (1, s), (2,t), (2, v)} and S ⊆ B ×C with S = {(s, 2), (u, 2), (v, 5)}

a) State if R is single-valued; and also state if R is total. Justify your answers.

[2 marks]
b) State if S is single-valued; and also state if S is total. Justify your answers.
[2 marks]
c) Give the composition R; S ⊆ A ×C [2 marks]
d) State if R; S is single-valued; and state if R; S is total. Justify your answers.
[2 marks]

(ii) Let R be the relation {(x, y) ∈ N × N : x < y}.

Answer: If uRv and wRv (where u, v, w ∈ N) does it necessarily follow that uRw?
Justify your answer. [2 marks]

Solution.

(i) a) R is not single-valued as 2Rt and 2Rv; R is not total as 3 ∈ A is not related to any
element in B.
b) S is single-valued as no element in B is related to more than element in C. S is
not total as t ∈ B is not related to any element in C.
c) R; S = {(0, 2), (1, 2), (2, 5)}
d) R; S is single-valued as no element in A is related to more than element in C. R is
not total as 3 ∈ A is not related to any element in C.

(ii) No. 6R10, as 6 < 10; and 3R10, as 3 < 10, but 6 is not R related to 3 as 6 is not less
than 3.

5
Question 5

(i) Which of the following relations R ⊆ Z × Z are functions from Z to Z? Justify your
answers.
 2
x if x ≤ 0;
a) R = {(x, y) ∈ Z × Z : y = }. [1 marks]
x + 1 if x ≥ 0;
 x
if x is even;
b) R = {(x, y) ∈ Z × Z : y = 2x−1 }. [1 marks]
2 if x is odd ;
4
c) R = {(x, y) ∈ Z × Z : y = x−1 }. [1 marks]

(ii) Give the values of log2 (4200 ), 3log9 (a) and log3 (9a )? [3 marks]

(iii) Consider the following function f : N → Z is defined by f (x) = 2x+1 − 1. Give the
recursive definition of f . [4 marks]

Solution.

(i) a) R is not a function. As R is not single valued as 0R0 and 0R1.

b) R is a function. As R is single-valued. As x is either even or odd. Also R is total,
as 2x ∈ Z when x is even; and x+1
2 ∈ Z when x is odd.
c) R is not a function. As R is not total. The number 1 is not paired via R with any
number.
1 √
(ii) log2 (4200 ) = 200 log2 (4) = 400, 3log9 (a) = alog9 (3) = a 2 = a and log3 (9a ) = a log3 (9) = 2a

(iii) f (0) = 1 and f (n + 1) = 2 × f (n) + 1

6
Question 6 (i) Consider the directed graph G given by the set
A = {a, b, c, d, e}
and the relation
R = {(a, b), (a, d), (b, d), (b, e), (c, b), (c, c), (c, e), (d, e), (e, b)}
a) Draw a picture of the graph G. [2 marks]
b) Give the set of vertices that can be reached from vertex a using a path of length
at least 1. [2 marks]
(ii) Consider the following tree T : k

 
lx m n

 
o p

  
q r s t


u
a) Give the set of leaves of T . [1 marks]
b) Give the depth of T . [1 marks]
c) Draw the subtree of T rooted at m. [2 marks]
d) State how many paths of length 3 are there in T . [2 marks]

Solution.

(i) a) b] /c
?

   
d /e
b) The set is {b, d, e}
(ii) a) The set of leaves is {n, q, r, s, u}.
b) The depth of the tree is 4.
c) m


p

 
s t


u
d) There are 5 path of lenth 3 in T . Those are: k to q, k to r, k to s, k to t, and m
to u.

7
Question 7 Let A, B,C be the following sets:

A = {1, 2, 3, 4} , B = {1, 2} , C = {1, 2, 3} .

(i) Let R ⊆ A × B be the relation given by

R = { (1, 1), (1, 2), (2, 2), (3, 1), (3, 2)}.

Write down the adjacency matrix M of the relation R. [3 marks]

(ii) Let S ⊆ B ×C be the relation given by

S = { (1, 1), (1, 3), (2, 1), (2, 3) }.

Write down the adjacency matrix N of the relation S. [3 marks]

(iii) Calculate the matrix M × N and use it to write down the adjacency matrix of the
composition R; S ⊆ A ×C. [4 marks]

Solution.

(i) Since R ⊆ {1, 2, 3, 4} × {1, 2} is given by

R = { (1, 1), (1, 2), (2, 2), (3, 1), (3, 2)}.
 
1 1
 0 1 
the adjacency matrix of R is M =  1 1 .


0 0

(ii) Since S ⊆ {1, 2} × {1, 2, 3} is given by

S = { (1, 1), (1, 3), (2, 1), (2, 3) }.

 
1 0 1
the adjacency matrix of S is N = .
1 0 1
   
(iii) The matrix M × N is 1 1   2 0 2
 0 1  1 0 1  1 0 1 
M×N =    = 
1 1  1 0 1  2 0 2 
0 0 0 0 0

Therefore the adjacency matrix of the composition R; S, which is obtained from M × N

by replacing every entry greater than 1 with 1, is
 
1 0 1
 1 0 1 
 
 1 0 1 
0 0 0

8
Question 8 A marketing company runs a focus group survey on customer preferences for a
new electric car. The new car has a selection of three different types of engines and two
types of battery packs. There is the option for an enhance interior lighting package. To write
a computer system that supports the study,

• State the number of different versions for the new car. [5 marks]

• In the study each participant needs to list three different versions in order of preference.
State the number of different choices a participant can make. [5 marks]

Solution.

(i) The choices split into three parts: Engine, battery pack and lighting package. There are
three combination of engines, two combinations of battery packs and two combinations
for the lighting package (to have it or to not have it) By the rule product we get a total
of 3 × 2 × 2 = 12 versions.

(ii) There
are 12 different versions. A participant need to select three different version
( 12
3 = 12×11×10
2×3 = 2 × 11 × 10 = 220) and has to select an order of three selection
versions (3!). By rule of product there are 220 × 6 = 1320 different choices a participant
can make.

9
Question 9

(i) Suppose that we toss a fair coin six times. State the probability that:

a) we obtain exactly two heads. [2 marks]

b) we obtain at least one head. [2 marks]

Give justifications for your answers (showing how you work out your answers is quite
sufficient). You may express your answers as fractions.

(ii) Suppose that we roll a fair 6-sided dice three times. State the probability that two dice
will have the same number and the remaining dice has a different number. Give justifi-
cations for your answers (showing how you work out your answers is quite sufficient).
You may express your answers as fractions. [3 marks]

(iii) A high-tech lab company is using a software product to maintain a constant temper-
ature in their labs. The requirement for the software states that 95 % of the time
the temperature is between 23.8 and 24.7 celsius. Experimental data shows a normal
distribution with a mean of 24.3 celsius and variance of 0.09.
State if based on the experimental data, the software satisfies the requirement. Justify
your answer. [3 marks]

Solution.

(i) a) The number of sequences with exactly two heads tails is

 
6 6×5
= = 15
2 2

There are 26 = 64 sequences in total. So the probability of obtaining exactly two

heads is
15
.
64
b) There are 26 =
64 sequences in total. The number of sequences with less than
one head is 60 = 1. So there are 64 − 1 = 63 sequences with at least one head;
and the probablity of obtaining at least one head is 63
64

(ii) There are 32 = 3 different way to have the two equal numbers dice among our three

dice; and the two equal numbered dice can have 6 different values; and there are 5
different values for the dice that is different. By the rule of product we get a total
of 3 × 6 × 5 combination that satisfy the condition. The total number of equal likely
outcomes for rolling three 6-sided dice is 63 . So the probability to roll two dice with
the same number and the remainng dice with a different number is 3×6×5 3×5
6×6×6 = 6×6 = 36
15

p
(iii) The variance is 0.09. So the standard deviation is (0.09) = 0.3. Hence 90% of
the time the temperature lies between 23.7 and 24.9. Hence, 10% of the time the
temperature is either below 23.7 or above 24.9. So the requirement of lying 95% of the
time between 23.8 and 24.7 is not met.

10
Question 10 Put the sets
 10 
10 x
O (10x ) , O (log2 (x))10 x2 , O log2 (x10 )x2




O x , O ,
log2 (x)

in increasing order (in terms of containment), starting from the smallest one.
(No justification required.) [10 marks]
Solution.

x10
 
10 2 10 2
O x10 , O (10x ) ,




O log2 (x )x , O (log2 (x)) x , O ,
log2 (x)

11