University of Cape Coast

College of Agriculture & Natural Sciences

School of Physical Sciences
Department of Computer Science & Information Technology

End of First Semester Examination - 2 0 19/2020

December 2019

CSC315: Discrete Mathematics

Duration: 2 hours

In stru ctio n : A n sw er all questions in the A n sw er B ook let provided.

A n sw er Q u estion 1 (4 0 m arks) and any oth er tw o (2 ) qu estion s (3 0 m arks each)
[M arks]

(a) A graph G with 13 edges is shown in Figure 1.

Figure 1: A graph G

The edges of G have weights given by the following table

Edge a b c d e f g h i j k m n
Weight 1 1 3 3 6 4 5 6 2 4 2 7 2

Use Prim’s algorithm to trace a minimum spanning tree S in G. ( Show every step)

(b) Let A = {a,b,c,d} and let R = {(a,b),(b,c),(c,d),(d,b)} be a relation on A. Draw the

directed graph representing R.

(c) Prove by mathematical induction that

1 1 1 1 3 1 w ^ o
1 + 23 + 3^ + 43 + " ■+ < " + n* ’
^ -

(d) Consider graphs X, Y and Z figure 2.

Graph X Graph Y Graph Z

Figure 2: G raphs X , Y , Z

Determine which of the graphs in Figures d are isomorphic. Show the isomorphism for
isomorphic pairs and a reason why the others are not.

(e) For each of these graphs explain whether it is a planar or a bipartite or both.
[M arks]

(a) Model the following situations as (possibly weighted, possibly directed) graphs. Draw each
graph, and give the corresponding adjacency matrices.
i. Adjoa and Boboo are friends. Adjoa is also friends with Comfort and Doku. Boboo,
Akosua and Eku are all friends of each other.
ii. It is well-known that in the Ghana, there is a 2-lane highway from Accra to Tema,
another 2-lane highway from Accra to Kasoa, a 3-lane highway from Tema to Ashiaman,
a 1-lane road from Tema to Nungua and another one from Ashiaman to Akosombo,
and a 5-lane superhighway from Kasoa to Akosombo.

(b) Is there a graph with the following degrees? With Yes, draw the graph and if N o, explain
why.
i. 0 ,1 ,2 ,3 ,4 ,5 ,6 , 7
ii. 3 ,3 ,3 ,3 ,3 ,3 ,3 ,3 , 7

(c) For the weighted graph H below(figure 3),

Figure 3: W eighted G raph

i. Construct an adjacency matrix for H.

ii. Treating the weights as labels for the edges, construct an incidence matrix for H.
iii. Find a Hamilton circuit in H , and write it down by listing the vertices in the order
they are visited.
iv. Does a noncyclic Euler path in H exist? If it exists write it down by listing the vertices
in the order they are visited. If it does not exist give your reasons.
[M arks]

(d) Consider the graph figure 4, representing the main science buildings at UCC.

i. Is this graph bipartite? Provide a brief argument for your answer. [3]
ii. Does this graph have an Euler circuit? Provide a brief argument foryour answer. [3]

Total for Question 2: 30

3. (a) Write down a truth table to show that ~ (p V q) is equivalent to ( ~ p) A ( ~ q) [5]

(b) Show that the argument [15]

P v ( ~ q) ~ r > ( ~ s ) v q> ( ~ P) (~ 0 ) p A ( ~ r)->s, 9

is valid by deducing the conclusion from the premise step by step through the use of basic
rules of inference or laws of logic.

(c) Translate the following into a sentence in English [3]

Vm, n € N((m 4- n) € N V (n -r m) E N)

(d) what is the negation of the following statement? [3]

Vx e R, 3yG K, ((x = y2) V (x < 0)))

(e) LetP(rr) be the statement ’’Student x knows calculus” and let Q(y) be the statement ’’Class
y contains a student who knows calculus.” Express each of these as quantifications of P(x)
and Q(y).
i. Some students know calculus. [1]
ii. Not every student knows calculus. [1]
iii. Every student in every class knows calculus. [1]
iv. There is at least one class with no studentswho know calculus. [1]

Total for Question 3: 30

P a cro A
[M arks]

(a) The reverse Polish notation of a mathematical expression is given below:

x y z 1 1 2 0 a: 6 t ~ t +

where | denotes exponentiation,

i. Find the corresponding mathematical expression (evaluate the expression). [3j
ii. Construct a parse tree for the expression. [5]
iii. Write the expression in Polish notation. [3]

(b) In scheduling a resit exams for level 100’s students at UCC, six different tests have to be
given to seven students. The table below shows the exams that each of the students must
take.
Exams Kofi Ato Yaa Kojo Esi Naa Kow
Comm. Skills / / / /
Intro to Computing / / /
Software Suite / / / /
Computer Hardware / / /
Programming / / / /
Calculus / / / / / /
i. Draw a graph that illustrates which exams have students in common with other exams. [6]
ii. What is the minimum number of time slots that will be needed to schedule the six [6]
exams? Which exams should be given in each of these time slots?

(c) Define a binary operation * on 1R4" U {0 } by

x * y = \Jx2 + y 2

i. Is the operation * associative? [4]

ii. What is the identity element for *? [3]
Total for Question 4: 30
[M arks]

E q u iv a l e n c e s and I m p l i c a t i o n E q u iv a l e n c e s R ules oi? I n f e r e n c e

Double negation law: -> (-*p) = p p

Identity laws: p V F = p , p A T =p pwq (Addition)

Domination laws: p V T s T, p A F s F p Aq
Negation laws: p V ~>p = T, p A ^p = F
P 0Simplification)
Idempotent laws: p\! p = p , p Ap =p P
Commutative laws: p V q = q V p, p A q = q A p q

Associative laws: p V (q V r) = {p V q) V r, PAq (Conjunction)

p A (q A r) = (p A q) A r p
p-^q
Distributive laws: p V (q A r) = (p V q) A (p V r),

p A (q V r) = {p A q) V (p A r) q (Modus ponens)
Absorption laws: p \/ (p A q)= p, p A (p\/ q ) = p -'q
p->q
DeMorgan ’s laws: -> (p V q) = ->p A —*q,

-« (p A q) s ->p V ~>q ->p (Modus tollens)

p-*q
q —> r
1. p - * q = -ip V q

2. P -* q = ~>q -* -TP (Hypothetical syllogism)

3- p\/ q = -'P q
pw q
^P
4. p A q = -,(p -V -,gr)

5. ^ ( p - y q ) = p A ^ q ••• q (Disjunctive syllogism)

pw q
6. ( p —* q ) A ( p —* r ) = p —* (q A r)
-ip v r
7. (p r) A (q —* r) = (p V q) —> r

8. ( p - + q ) V ( p -> r ) = p ^ (q V r) (Resolution)

9. (p r) V (q r) = (p A q) —* r

10. p q = (p—>q) A (q —*p)

11. p <r+ q = -*p <r* ~<q

12. p<r>q = ( pAq ) \/ (~>p A ->q)

13. ->(p <r* q) = p <->-*q

P o r ro fi