Discrete Mathematics (COME3109)
Computer Engineering - COM
Semester: First Semester
Level: 300
Year: 2019
REPUBLIC OF CAMEROON
Peace-Work- Fatherland
TILE UNIVERSITY OF BAMENDA
P.O. Box 39 Bambili
END OF SEMESTER EXAMINATION
SCHOOL
N A T IO N A L H I G H ER PO L Y T E CHN I C IN ST I T UT E
DEPARTMENT
CO M PU T E R E NG I NE ERI NG
LEVEL
300 ( Y EAR 2)
SEMESTER
1
COURSE TITLE
DI SCR ET E M AT HS
TIME ALLOWED
2 HOURS
SESSION
M A R CH 2 019
General instructions
You are reminded of the necessity for good English and orderly presentation of your material.
Write all your answers in your answer sheet.
Exercise 1: Mathematical logic
(7 marks)
1. Define the following terms: model, tautology. (1 mark)
2. Consider the proposition ((P Q) —> P) —> Q)
a. Write out a truth table to determine for which assignments of truth values to
P
and
Q
this proposition is true. (1 mark)
b.
Convert this proposition into conjunctive normal form
using standard logical
equivalences. (1 mark)
c. Show that the proposition (P —> (Q —> (P —> Q)) is
not
logically equivalent to
((P —> Q) —› P) Q. (I mark)
3. Use the refutation method to show that:
{p V q V r, ¬p V q V r, ¬qv r}⊨ r.
(1 mark)
4. Find the formulas in first order logic that can be used to interpret the following
sentences. (2 marks)
a. All what shines is gold.
b. All what shines is not gold.
c. All birds fly except ostriches which are birds but don't fly.
d. If Eric is a serious student, then all students are serious.
Exercise 2: Set theory
(7 marks)
1. Let
R, S,
and
T
be sets. Using the definitions of
⊆
,
∪,
∩
and
\,
prove or disprove each
of the following statements: (3 marks)
a. R
is a subset of
S
if and only if
R
⊆
(S
\
T)
∪
(R
∩
T).
b. R
is a subset of
S
if and only if
R
⊆
R
∪
S.
c. R
is a subset of
S I R
if and only if
R =
ø
2. Suppose
A, B,
and
C
are all sets. In each of the following situations, show one of (a)
A
must be an element of
C
but is not necessarily a subset of C; (b)
A
must be
a subset of
C
but is not necessarily an element of
C;
(c) A must be both an element and a subset of
C;
or (d)
A
is not necessarily either an element or subset of
C.
(4 marks)
www.schoolfaqs.net
a. A ∈ B ∈ C.
b. A ∈ B
⊆
C..
c. A
⊆
B ∈ C.
d. A
⊆
B
⊆
C.
Exercise 3: Asymptotic notation
(6 marks)
1.
Show that
2
= ʘ (n
2
x 2
n
) (2 marks)
2.
Let
f
:
N
—>
N
be defined by:
f(n) =
1
if n is odd, and
If n is even
a.
Prove or disprove: f (n) is 0 (n). (2 marks)
b.
Prove or disprove: f (n) is Ω (n). (2 marks)
www.schoolfaqs.net
