HCMUT MIDTERM

FACULTY OF CS AND ENGINEERING Subject: Discrete Structures (CO1007)

Classes: CT14QUEE + CT14KTMT + CT14KHMT
Time: 60 minutes (Closed book test)
Test date: July 09, 2015

Student’s Full 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. Suppose that P (x, y) means “x is a parent of y” and M (x) means “x is male.” If F (v, w) equals

M (v) ∧ ∃x∃y(P (x, y) ∧ P (x, v) ∧ (y 6= v) ∧ P (y, w)),

then what is the meaning of the expression F (v, w)?

 
A
v is a brother of w. C
v is an uncle of w.
 
B
v is a nephew of w. D
v is a grandfather of w.
Answer to Question 1:

C

Question 2. In this question, assume the following predicate and constant symbols:

W (x, y) : x wrote y h : Hardy p : Pride and Predjudice.

L(x, y) : x is longer than y a : Austen
N (x) : x is a novel j : Jude the Obscure

Given these specifications, which of the predicate logic formulas below represent the sentence, “Hardy wrote a
novel which is longer than any of Austen’s” in predicate logic?
 
A
∀x(W (h, x) → L(x, a))). C
∀x∀y(W (h, x) ∧ W (a, y) → L(x, y))).

 D
∃x(N (x) ∧ W (h, x) ∧ ∀y(N (y) ∧ W (a, y) →
B

∀x∃y(L(x, y) → W (h, y) ∧ W (a, x)). L(x, y))).
Answer to Question 2:

D

Question 3. Which of the following predicate calculus formulas must be true under all interpretations?

I. (∀xP (x) ∨ ∀xQ(x)) −→ ∀x(P (x) ∨ Q(x)). III. (∃xP (x) ∨ ∃xQ(x)) −→ ∃x(P (x) ∨ Q(x)).
II. ∀x(P (x) ∨ ∀xQ(x)) −→ (∀xP (x) ∨ ∀xQ(x)).
   
A

I only. B
III only. C
I and II. D
I and III.
Answer to Question 3:

C

Question 4. Which of these is NOT a valid inference rule, where A, B and C are any propositional formula?
 
A

From ¬B and A −→ B infer ¬A. C
From A and A −→ B infer B.
 
B
From A infer A ∧ B. D
From A infer ¬¬A.
Answer to Question 4:

Page 1 of 4
 
D

Question 5. Which formula captures the following statement most accurately?

“When the next large bank gets into trouble (t), the financial system collapses (c) unless the
Central Bank buys the bank (b).”
   
A
(¬c → b) → t B
(c ∧ ¬b) → ¬t C
(c ∧ ¬b) → t D
t → (¬c → b)
Answer to Question 5:

D

Question 6. Which of the following propositional formulas has value T by assigning p 7→ T , and q, r 7→ F ?
   
A
¬p ∨ ¬r −→ q B
¬r −→ (p ∧ q) C
¬(¬r −→ (p ∧ q)) D
¬p ∨ q ∨ r
Answer to Question 6:

C

Question 7. Of all the students at HCMUT, 55% were born in HCMC. Of those born in HCMC, 85% speak
English well. Of those not born in HCMC, 32% speak English well. A student was selected at random. What
is the probability that this student was born in HCMC or speaks English well?
   
A
0.55 × 0.85 × 0.32. B
0.55 + 0.45 × 0.32. C
0.55 + 0.32. D
0.55 × 0.85 + 0.32.
Answer to Question 7:

B

Question 8. A newspaper sports reporter has a 58% accuracy for predicting the winners in V-league 2015.
A radio sports reporter has a 65% accuracy for predicting the winners. For a particular match, what is the
probability that at least one of these reporters will make a correct prediction?
 
A
1 − 0.58 × 0.65. C
0.58 + 0.65 − 0.58 × 0.65.
 
B
0.58 + 0.65. D
0.58 × 0.65.
Answer to Question 8:

C

Question 9. Suppose the monthly demand for tomatoes (a perishable good) in a small town is random. With
probability 1/2, demand is 50; with probability 1/2, demand is 100. You are the only producer of tomatoes in
this town. Tomatoes sell for a fixed price of 1 USD, cost 0.50 USD to produce, and can only be sold in the local
market. If you produce 60 tomatoes, your expected profit is:
   
A
15 USD. B
25 USD. C
45 USD D
50 USD
Answer to Question 9:

B
E(PROFIT) = E(REVENUE - COST) = 1/2 × (50 − 30) + 1/2 × (60 − 30) = 25 USD.

Question 10. Let S be the collection of all sets with at most 5 elements. Then
 
A

An element of S is a set with 1, 2, 3, 4, or 5 C
An element of S is a set with 25 elements.
elements.
 
B
An element of S is a number which is not greater D
An element of S is a set with an arbitrary number
than 5. of elements.
Answer to Question 10:

A

Page 2 of 4
Question 11. Let A = {all diet soda pops}, B = {all cola soda pops}, and D = {all caffeine-free soda pops}.
Describe the set (A − D) ∩ B in words.
 
A
All diet soda pops that contain caffeine and all C
All diet caffeine-free cola soda pops
cola soda pops
 
B
All non-diet, caffeine-free cola soda pops D
All diet cola soda pops that contain caffeine
Answer to Question 11:

D

Question 12. Say that two real numbers a and b are related if the sum of their squares is 2015. Then this
relation is
 
A

A function. C
Symmetric.
 
B
An equivalence relation. D
Anti-symmetric.
Answer to Question 12:

C

Question 13. Say that two functions f and g, with domain R, are related if f (x) ≤ g(x) for every x ∈ R.
Then
 
A

This is an equivalence relation. C
This is a function.

 D
This does not allow us to compare any two func-
B

This is an order relation. tions.
Answer to Question 13:

D

Question 14. Exactly which of the relations R1 , R2 , and R3 on {1, 2, 3, 4} that are given below are anti-
symmetric?

R1 ={(1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (3, 4), (4, 4), (4, 1)};
R2 ={(1, 1), (1, 2), (2, 3), (3, 3), (3, 2), (4, 2)};
R3 =∅.
   
A
R1 , R2 B
R1 , R3 C
R2 , R3 D
R2
Answer to Question 14:

B

Question 15. The number of functions f : {1, 2, ..., 2015} −→ {1, 2, ..., 100} is:
   
2015 100
A
100 . B
2015 . C
2015 × 100. D
2015! + 100!.
Answer to Question 15:

A

Question 16. The number of relations from {1, 2, ..., 5} to {1, 2, ..., 100} is:
   
5 100 105 500
A
100 . B

5 . C
2 . D
2 .
Answer to Question 16:

D

Page 3 of 4
Question 17. The number of increasing functions f : {1, 2, ..., 15} −→ {1, 2, ..., 2015} is:
   
2015 15 2015! 2015!
A
15 . B
2015 . C
15!2000! . D
15! .
Answer to Question 17:

C

Question 18. The number of surjective (onto) functions f : {1, 2, ..., 5} −→ {1, 2, ..., 100} is:
   
100 5 100!
A
0. B
5 . C
100 . D
5! .
Answer to Question 18:

A

Question 19. Let f : A −→ B and g : B −→ C be functions. Which of the following statements is incorrect?
 
A

If f and g are one-to-one, then g ◦f is one-to-one. C
If g ◦ f is one-to-one, then f is one-to-one.

 D
If f is onto and g ◦ f is one-to-one, then g is
B
If g ◦ f is onto, then f is onto. one-to-one.
Answer to Question 19:

B

Question 20. How many solutions are there of the equation x1 +x2 +x3 = 12 with x1 , x2 , x3 positive integers?
   
14 13 12 11





A

2 . B

2 . C

2 . D
2 .
Answer to Question 20:

D

THE END
Test Approved by: Test Prepared by:

Nguyen An Khuong, PhD

Page 4 of 4