MIDTERM

BKU, VNU-HCM Subject: Discrete Structures for Computing

FACULTY OF CSE
(CO1007)
Class: CC16KHMT Group: CC01
Time: 60 minutes (Closed book test)
Test date: March 14, 2016

Student’s Name: Student’s ID:

Final Score: Examiner: Examiner’s Signature:

(There are 20 MCQs, each question is worth 0.5 points. Answers in bold : ; cancel out to deselect: @
 .)

Question 1. Determine the number of 5-letter words with exactly two distinct letters. (For example, AAFAFF
counts, but not AAFAFX or AAAAA, since the latter two words contain three, respectively one,
distinct letters.)



 26


26 5 26 5 26 2
A 2 ·2 . B 2 · (2 − 2). C 2 · 3!. D
3!
.

The2 number of all relations

Question 2. on a set consisting of 2017
 2017·2018  elements, which are reflective,
 is
A 2 2017 . B 2 2 . C 2 2016·2017 . D 2 2017·2018 .
Question 3. Fibonacci sequence is recursively determined by

Fn+2 = Fn+1 + Fn for all natural numbers n ≥ 1,

and by two initial conditions F1 = F2 = 1.

For any n, two consecutive numbers Fn and Fn+1 then satisfy that

A both are primes.

B the difference Fn+1 − Fn is prime.

C their greatest common divisor is a natural number d > 1.

D their greatest common divisor is number 1.

Let R1 and R2 be two relations on a set S 6= ∅. Which of the following is correct?

Question 4.
A If both R1 and R2 are transitive then R1 ◦ R2 i also transitive.

B If both R1 and R2 are transitive then R1 ∪ R2 is also transitive.

C The relation R1 can not be both symmetric and antisymmetric.

D The relation R1 is transitive if and only if R1−1 = {(y, x)|(x, y) ∈ R1 } is also transitive.

Question 5. Let X and Y be two finite set such that |Y | = 2 and |X| = 2017. Then the number of surjective
function from X to Y is  
A 22017 . B 22017 − 2. C 20172 . D 2017


2 .

Question 6. Consider a binary relation R on the set Z defined by xRy ⇔ x2 = y 2 . Then R is

 
A reflexive and symmetric. B an equivalence relation.
 
C a partial order relation. D reflexive and transitive.

Question 7. By assigning p = r = 0, and q = 1, the true value of the following propositions

(p −→ q) ∧ (q −→ r); p −→ q −→ r

are, respectively,
   
A 0; 0. B 1; 1. C 0; 1. D 1; 0.

Student’s Signature: . . . . . . . . . . . . . . Code 1431 Page 1

 Question 8. Let {Un }n be a sequence defined by Un = n(−1)n for n = 1, 2, 3, ... and let S be the sum of first
Xn
n items of that sequence: S = Uk . Which is the correct statement?
k=1
 
A S = n/2 if n is odd. B S = (n − 1)/2 + n if n is odd.
 
C S = (n − 1)/2 − n if n is odd. D S = (n + 1)/2 + n if n is odd.

Which of the following is correct for functions?

Question 9.
A If f1 and f2 are two functions form A to B and g is a surjective function from B to
 C such that g ◦ f1 = g ◦ f2 , then f1 = f2 .
B If f : X −→ Y and g : Y −→ X are two functions such that f ◦ g = IdY , where IdY
 is the identity map on Y , then f is an injection.
C If f : X −→ Y and g : Y −→ X are two functions such that g ◦ f = IdX , where IdX
 is the identity map on X, then f is a surjection.
D If f1 and f2 are two functions from A two B and g is an injective function from B
to C such that g ◦ f1 = g ◦ f2 , then f1 = f2 ..
Question 10. Let A and B be two sets. Then the difference set A\B is equal to
   
A B\A. B B ∪ A. C B ∩ A. D A∪B

Question 11. There are three suspects for a murder: Adam, Brown, and Clark. It has been established beyond
any reasonable doubt that exactly one of them is the killer. [So, two are innocents, one is guilty.]
Your task is to figure out which one. You questioned Adam, Brown, and Clark one-by-one. Adam
says “I didn’t do it. The victim was old acquaintance of Brown’s. But Clark hated him.” Brown
states “I didn’t do it. I didn’t know the guy. Besides I was out of town all week.” Finally, Clark
says “I didn’t do it. I saw both Adam and Brown downtown with the victim that day; one of
them must have done it.” Assuming that the innocent men are telling the truth, but that the
guilty man might not be, discover the killer.
 
A Adam is the killer. B Brown is the killer.
 
C Clark is the killer. D The given information is insufficient to
discover the killer.
Question 12. Let f and g be two functions from R to R. Then the negation of the formula “For each s in R,
there exists r in R such that if f (r) > 0, then g(s)
> 0” is the following formula.
A For every s in R, there exists r in R such B For every s in R, there does not exist r in
that f (r) > 0 and g(s) ≤ 0. R such that if f (r) > 0, then g(s) > 0.
C There exists s in R and there exists r in R D There exists s in R such that for every r
such that f (r) ≤ 0 and g(s) ≤ 0. in R, f (r) > 0 and g(s) ≤ 0.
Question 13. Let φ be a propositional formula. Consider the following statements on φ.

I. φ is satisfiable or ¬φ is satisfiable.

II. φ is a tautology or ¬φ is a tautology.

Then 
A Both I and II are correct. B Both I and II are incorrect.
 
C I is correct and II is incorrect. D I is incorrect and II is correct.

Question 14. Suppose that A and B play a chess match consisting of several consecutive games. The first player
who win consecutively two games or win three games in total will win the match. Suppose that
there is no draw in eachgame. How many scenarios in this match? giải này?
A 10. B 11. C 9. D 8.

Student’s Signature: . . . . . . . . . . . . . . Code 1431 Page 2

Question 15. Given the following predicates

• Q(x) : x is a politician,

• P (y) : y is a person,

• T (z) : z is a time,

• F (x, y, z) : person x fools person y at time z.

Represent the following sentences in predicate logic:

“Politicians can’t fool all of the people all of the time.”


A ∀x[Q(x) → ∀y∀z((P (y) ∧ T (z)) → ¬F (x, y, z))].

B ∀x[Q(x) → ∃y∃z((P (y) ∧ T (z)) → ¬F (x, y, z))].

C ∀x∃y∃z[Q(x) → (P (y) ∧ T (z) ∧ F (x, y, z))].

D ∀x[Q(x) → ∃y∃z(P (y) ∧ T (z) ∧ ¬F (x, y, z))].

Question 16. Determine the number of points (x, y, z) with integer coordinates in the first octant (i.e., with
x, y, z ≥ 0) for which the sum of all three coordinates is at most 13. (For example, (2, 1, 3) or
(0, 3, 10) count, but (1, 3,
10) or (1, 2, 6) do not count.)
 
A 1365. B 455. C 560. D 680.

Which of the following is correct about power sets?

Question 17. 
A P(A ∩ B) = P(A) ∩ P(B). B P(A ∪ B) = P(A) ∪ P(B).
 
C P(A × B) = P(A) × P(B). D P(A\B) = P(A)\P(B).

Let A = {1, 2} and B = {1}. Then,

Question 18. 
A P(A\B) ⊆ P(A)\P(B). B P(A)\P(B) ⊆ P(A\B).
 
C ∅ ∈ P(A)\P(B). D |P(A\B)| = |P(A)\P(B)|.

Question 19. Consider the following statement: “Suppose F and G are families of sets. If ∪F and ∪G
are disjoint, then so are F and G.”

And consider a proof for that statement as follows.

“Suppose ∪F and ∪G are disjoint. Suppose F and G are not disjoint. Then we can choose some
set A such that A ∈ F and A ∈ G. Since A ∈ F, it is clear that A ⊆ ∪F, so every element of A
is in ∪F. Similarly, since A ∈ G every element of A is in ∪G. But then every element of A is in
both ∪F and ∪G, and this is impossible since ∪F and ∪G are disjoint. Thus, we have reached a
contradiction, so F and G must be disjoint. QED.”

Then,
A The statement is correct and its proof if also correct.

B The statement is incorrect and the proof is also incorrect, since the claim that all
elements of S are also in ∪F and ∪G does not contradict to the fact that ∪F and
∪G
 are disjoint.
C The statement is incorrect. The proof is correct, but that is a proof for different
statement.
D The proof is incorrect since the statement is incorrect, as we can take a counterex-
ample with F = {{1}, ∅} and G = {{2}, ∅}.

Student’s Signature: . . . . . . . . . . . . . . Code 1431 Page 3

Question 20. Let a set S ⊂ N that the cardinality |S| = 12. Then


A S must contain two distinct number s1 , s2 such that s1 − s2 is a multiple of 10.

B S must contain two distinct number s1 , s2 such that s1 − s2 is a multiple of 11.

C S must contain two distinct number s1 , s2 such that s1 − s2 is a multiple of 12.

D S must contain two distinct number s1 , s2 such that s1 − s2 is a multiple of 13.

Student’s Signature: . . . . . . . . . . . . . . Code 1431 Page 4

 MIDTERM ANSWER KEYS
BKU, VNU-HCM Subject: Discrete Structure for Computing
FACULTY OF CSE
(CO1007)
Class: CC16KHMT Group: CC01
Time: 60 minutes (Closed book test)
Test date: March 14, 2015

Code: 1431
   
Question 1. B Question 6. B Question 11. B Question 16. C
   
Question 2. C Question 7. C Question 12. D Question 17. A
   
Question 3. D Question 8. C Question 13. C Question 18. D
   
Question 4. D Question 9. D Question 14. A Question 19. B
   
Question 5. B Question 10. D Question 15. D Question 20. B

Student’s Signature: . . . . . . . . . . . . . . Code 1431 Page 1