Bài kiểm tra giữa kỳ môn Toán rời rạc

h đề P(x): ”x là sinh viên ”, Q(x,y): ”x học giỏi môn học y”. Dịch câu sau: “Mọi sinh viên đều học giỏi 
một môn học nào đó”. 
 a. b. ))y,x(Q)x(P)(x( →∀ ))y,x(Q)x(P)((x( ∧∀ 
c. d. ))y,x(Q)x(P)(yx( →∃∀ ))y,x(Q)x(P)(xy( ∧∃∀ 
e. Tất cả đều sai. 
4. Cho đồ thị phẳng G = (V, E), |V| = 3, |E| = 6 khi đó số miền được chia bởi đồ thị G là: 
a.6 b. 9 c. 5 d. 8 
5. Xác định số tập con của tập A={1,2,a}: 
a. 6 b. 7 c. 8 d. 9 e. Tất cả đều sai. 
6. Dạng chuẩn tắc hội của công thức )AB()BA( ¬→¬→→ là: 
a. b. )ABB()CBA( ∨¬∨∧∨∧ )ABB()CBA( ∨¬∨∨∨∨
c. )ABB()ABA( ∨¬∨∧¬∨∨ d. )ABB()CBA( ∨¬∨∧∨∨¬ 
7.Phương trình sau có bao nhiêu nghiệm nguyên không âm? x + y + z = 18 
 a. 200 b. 180 c. 150 d. 190 e. Tất cả đều sai. 
8. Có 5 nam, 2 nữ. Có bao nhiêu cách chọn 3 người và có ít nhất 1 nữ: 
a. 60 b. 65 c. 70 d. 55 e. Tất cả đều sai 
9. Điều kiện cần và đủ để một đa đồ thị liên thông có chu trình Euler là: 
 a. Đồ thị đó không có đỉnh treo. 
 b. Đồ thị đó có các đỉnh đều bậc lẻ. 
 c. Đồ thị đó có đúng hai đỉnh bậc lẻ. 
 d. Đồ thị đó có các đỉnh đều bậc chẵn. 
10. Cho tập A = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19} hỏi ta cần lấy ít nhất bao nhiêu phần tử từ tập A để chắc chắn rằng 
có một cặp có tổng bằng 20. 
a. 6 b. 7 c. 8 d. 9 
11. Cho tập S = {a, b, c, d} khi đó số phần tử của tập lũy thừa của tập S là: 
a. 4 b.16 c. 8 d. 5 
12. Cho 2 tập A={1, 2, 3}, B={a, b, c, 2}. Trong số các tập dưới đây, tập nào là một quan hệ 2 ngôi từ A tới B? 
a.{(1,a), (1,1), (2,a)} 
b.{(2, 2), (2,3), (3,b)} 
c.{(1,2), (2,2), (3,a)} 
d.{(2,c), (2,2), (b,3)} 
e.Tất cả đều sai. 
13. Cho G = (V, E) là đồ thị đầy đủ với |V| = 4. Khi đó phát biểu nào sau đây là SAI? 
 a. G là đồ thị liên thông. b. G là đơn đồ thị. 
ng_huu_bien@yahoo.com 095.624.5865 11
Discrete Marthematics 
 c. Tất cả các đỉnh của G đều có bậc 3. d. G không là đồ thị phẳng 
14. Cho tập A= {a, b, c, d}, hỏi quan hệ nào trong số các quan hệ trên A dưới đây có tính phản đối xứng? 
 a. R = {(a,a), (a,b), (b,c), (b,d), (c,c), (c,b), (d,a), (d,b)}. 
 b. R = {(a,a), (a,c), (a,d), (c, b),(c,c), (d,b), (d,c)} 
 c. R = {(a,a), (a,b), (a,c), (b,b), (b,c), (c,c), (c,a), (d,d), (d,b)} 
 d. R = {(a,a), (a,c), (b,b), (b,d), (c,c), (c,a), (d,d), (d,c)} 
15. Cho tập A = {-12, -11, , 11, 12}, và quan hệ R = {(a,b)| a ≡ b (mod 3)}. Hãy tìm [-8]R
 a. {-11, 4, -8, -5, 1, 7, 10, -2} b. {-12, 3, -8, 5, -2, 4, -10} 
c. {-1, 4, 6, 9, -8, -4, 3, 9} d. {-9, 6, 1, -8, 3, -5, 0, -12} 
16. Công thức A = )( pqp ∨→ tương đương với công thức nào trong số các công thức sau: 
a. b. 1 c. 0 d. q pq ∨
17. Xác định tích đề các của 2 tập A={1,a} và B={1,b}: 
a.{(1,1), (1,b), (a,1), (a,b)} b. {(1,b), (a,b)} 
c.{(1,1), (1,b), ( ,1), ( ,b), (a,b)} d.{(1,1), (1,b), (a,b), φ } φ φ
18. Cho đồ thị G = (V, E), |V| = n, khi đó cây khung của đồ thị G có: 
a. n – 1 cạnh b. n – 1 đỉnh c. n cạnh d. n đỉnh 
19. Cho G là một đồ thị đầy đủ bậc 5 (K5). Khi đó phát biểu nào trong số các phát biểu sau đây là đúng: 
a. Các đỉnh của G đều có bậc 4. b. Các đỉnh của G đều có bậc 5. 
c. Các đỉnh của G có bậc khác nhau d. G có ít nhất một đỉnh bậc 5. 
20. Cho mệnh đề: “Nếu tôi không ốm thì tôi đã đến dự cuộc họp”. Tìm mệnh đề đảo của mệnh đề đã cho: 
a. Nếu tôi ốm thì tôi đã không đến dự cuộc họp. 
b. Nếu tôi ốm thì tôi đã đến dự cuộc họp. 
c. Nếu tôi đã đến dự cuộc họp thì tôi không ốm 
d. Nếu tôi đã không đến dự cuộc họp thì tôi ốm 
e. Tất cả đều sai. 
Khoa CNTT 
Bộ môn KHMT 
Môn: Toán rời rạc 
Đề thi số: 0204TL1 
Thời gian: 90 phút 
Trưởng bộ môn 
Ký duyệt 
Chú ý:1, Ở phần câu hỏi trắc nghiệm, mỗi câu hỏi chỉ được chọn một phương án trả lời. 
A, Phần câu hỏi trắc nghiệm: 
1, Câu nào sau đây KHÔNG là một mệnh đề ? 
 a, Hôm nay không phải thứ hai. 
b, x là bạn cùng lớp với Lan. 
c, Nếu hôm nay trời nắng thì tôi sẽ đi chơi. 
 d, Có một người trong lớp không biết môn toán Rời rạc. 
trong đó x thuộc tập con người. 
2, Phương trình x + y + z = 15 có số nghiệm nguyên không âm là: 
 a,136 b, 455 c, 15 
3. Cho công thức logic mệnh đề : A = )( qprqp →∨∧→ 
với p = 1, q = 0, r =1, hãy cho biết giá trị của A là gì? 
 a. 1 b. Không xác định được 
 c. 0 d. a và c đều đúng 
4. Dạng chuẩn tắc hội của công thức )AB()BA( ¬→¬→→ là: 
a. )ABB()CBA( ∨¬∨∧∨∧
b. )ABB()CBA( ∨¬∨∨∨∨
c. )ABB()CBA( ∨¬∨∧∨∨¬ 
d. )ABB()ABA( ∨¬∨∧¬∨∨ 
e. Tất cả các công thức trên đều không phải. 
5, Khẳng định nào dưới đây là đúng? 
 a, W4 có chu trình Euler b, W4 có đường đi Euler 
 c, W4 có chu trình Hamilton d, Các phương án a, b, c đều sai 
6, Cho công thức logic A = . Hỏi khẳng định nào sau đây là đúng? )( pqp →∧¬
 a, A hằng đúng b, A hằng sai c, A thỏa được 
ng_huu_bien@yahoo.com 095.624.5865 12
Discrete Marthematics 
7, Cho tập A = {1,2,a}. Hỏi tập nào là tập lũy thừa của tập A? 
 a, {{1,2,a}} 
 b, {∅,{1},{2},{a}} 
 c, {∅,{1},{2},{a},{1,2},{1,a},{2,a},{1,2,a}} 
 d, {{1},{2},{a},{1,2},{1,a},{2,a},{1,2,a}} 
8, Cho quan hệ R = {(a,b) | a|b}trên tập số nguyên dương. Hỏi R KHÔNG có tính chất nào? 
 a, phản xạ b, đối xứng c, bắc cầu d, phản đối xứng 
9, Xét các hàm từ R tới R, hàm nào là khả nghịch: 
a, f(x) = b, f(x) = 5x4x2 +− 4x
c, f(x)= d, f(x)= 3x 2x6 −
10, Cho quy tắc f: ℝ → ℝ thỏa mãn f(x) = 2x2 + 5. Khi đó f là : 
 a, Hàm đơn ánh. b, Hàm toàn ánh. 
 c, Hàm số d, Hàm song ánh. 
11, Cho hàm số f(x) = 2x và g(x) = 4x2 +1, với x ∈ ℝ . Khi đó gof(-2) bằng: 
 a, 65 b, 34 c, 68 
12, Hãy cho biết thứ tự duyệt các đỉnh của cây có gốc a sau theo phương pháp duyệt trung thứ tự: 
 a, b c d a e g h b, a b e c d g h 
 c, e b a c g d h d, e g h a d c b 
13, Có bao nhiêu xâu nhị phân có độ dài bằng 5 hoặc có 2 bít đầu tiên là 0 hoặc có 2 bít cuối cùng là 1? 
 a, 16 b, 14 c, 2 d, 32 
14, Mỗi thành viên trong câu lạc bộ Toán tin có quê ở 1 trong 20 tỉnh thành. Hỏi cần phải tuyển bao nhiêu thành 
viên để đảm bảo có ít nhất 5 người cùng quê? 
 a, 81 b, 99 c, 101 d, 90 
15, Hệ nào sau đây KHÔNG phải là một hệ đầy đủ? 
 a, {∨ ,→ , } b, {¬ ∧ ,¬ } 
 c, {∧ ,∨ } d, { ,∨ ¬ } 
16, Có bao nhiêu hàm số khác nhau từ tập có 4 phần tử đến tập có 3 phần tử: 
a, 81 b, 64 c, 4 d, 12 
17, Số xâu khác nhau có thể tạo được từ các chữ cái của từ ORONO là: 
 a, 10 b, 20 c, 5 d, 100 
18, Cây tam phân đầy đủ có 12 đỉnh trong sẽ có số đỉnh là: 
 a, 34 b, 35 c, 36 d, 37 
19, Cho tập A = {2, 3, 4, 5}. Hỏi tập nào KHÔNG bằng tập A? 
 a, {4, 3, 5, 2} 
 b, {a | a là số tự nhiên >1 và <6} 
 c, {b | b là số thực sao cho 1<b2 <36} 
 d, {2, 2, 3, 4, 4, 4, 5} 
20, Cho tập A={1, 2, 3, 4}.Trong các quan hệ trên tập A cho dưới đây, quan hệ nào là quan hệ tương đương? 
n. {(1, 1), (1, 2), (1,3), (2,2), (2,1), (2,3), (3,3)} 
o. {(1, 1), (3,3), (2,3), (2,1), (3,2), (1,3)} 
p. {(1,1), (1,2), (2,1), (2,2), (3,3), (4,4)} 
q. {(1, 1), (2, 2), (3,3), (4,4), (2,1), (2,3), (3,1)} 
21, Cho quan hệ R = {(a,b)| a ≡ b(mod 4)} trên tập {-8, -7, ,7, 8}. Hãy xác định [1]4 ? 
 a, {-8, -4, 1, 4, 8} b, {-7, -3, 1, 5} 
 c, {-5, -1, 3, 7} d, {1} 
22, Cho tập A = {-12, -11,11, 12} và quan hệ tương đương trên A: R = {(a,b)| a≡b(mod 4)}. Hỏi R sẽ tạo ra một 
phân hoạch gồm bao nhiêu tập con trên A? 
 a. 3 b. 0 
 c. 2 d. 4 
23, Trong các đồ thị dưới đây, đồ thị nào có số đỉnh là 5 và số cạnh là 5? 
 a, K5 b, C5 c, W5 d, Q5
ng_huu_bien@yahoo.com 095.624.5865 13
Discrete Marthematics 
24, Cho tập không gian là U = {2, 4, 6, 7, 9}, P(x,y) = “x chia hết cho y”, cho biết mệnh đề nào sau đây nhận giá trị 
đúng: 
a. ∀x∀yP(x,y) b. ∀x∃yP(x,y) 
g. ∃x∀yP(x,y) d. ∃x∃yP(x,y) 
25, Cây là một đồ thị: 
 a, đơn và liên thông 
 b, đơn, liên thông và vô hướng 
 c, đơn, liên thông, vô hướng và không có chu trình 
 d, đơn, liên thông, có hướng và không có chu trình 
Khoa CNTT 
Bộ môn KHMT 
Môn: Toán rời rạc 
Đề thi số: 0204TL2 
Thời gian: 90 phút 
Trưởng bộ môn 
Ký duyệt 
Chú ý:, Ở phần câu hỏi trắc nghiệm, mỗi câu hỏi chỉ được chọn một phương án trả lời. 
A, Phần câu hỏi trắc nghiệm: 
1, Trong các phát biểu sau đây phát biểu nào KHÔNG là mệnh đề. 
p. Lan thích học toán. 
q. Lan không thích học toán 
r. Nên học toán. 
s. Mọi người trong lớp tôi đều thích học toán. 
2, Cho quan hệ R = {(a,b) | a|b}trên tập số nguyên dương. Hỏi R KHÔNG có tính chất nào? 
 a, phản xạ b, đối xứng c, bắc cầu d, phản đối xứng 
3. Cho công thức logic mệnh đề : A = )( qprqp →∨∧→ 
với p = 1, q = 0, r =1, hãy cho biết giá trị của A là gì? 
 a. 1 b. Không xác định được 
 c. 0 d. a và c đều đúng 
4, Trong các cặp mệnh đề sau, hỏi cặp nào là KHÔNG tương đương? 
 a, )(xxP∀ và )(xPx∃ b, qp → và pq → 
 c, qp → và pq ∨ d, )(xxP∃ và )(xPx∀ 
5, Cho quy tắc f: ℝ → ℝ thỏa mãn f(x) = 2x2 + 5. Khi đó f là : 
 a, Hàm đơn ánh. b, Hàm toàn ánh. 
 c, Hàm số d, Hàm song ánh. 
6, Cây là một đồ thị: 
 a, đơn và liên thông 
 b, đơn, liên thông và vô hướng 
 c, đơn, liên thông, vô hướng và không có chu trình 
 d, đơn, liên thông, có hướng và không có chu trình 
7, Cho tập A = {1, 2, {3,4}, (a,b,c), ∅}. Lực lượng của A bằng: 
 a, 8 b, 5 c, 7 d,4 
8, Phương trình x + y + z + t = 20 có số nghiệm nguyên không âm là: 
 a,1000 b, 1771 c, 2772 d, 3773 
9, Xét các hàm từ R tới R, hàm nào là khả nghịch: 
a, f(x) = b, f(n) = 5x4x2 +− 4x
c, f(n)= d, f(n)= 3x 2x6 −
10, Khẳng định nào dưới đây là đúng? 
 a, W4 có chu trình Euler b, W4 có đường đi Euler 
 c, W4 có chu trình Hamilton d, Các phương án a, b, c đều sai 
11, Cho hàm số f(x) = 2x và g(x) = 4x2 +1, với x ∈ ℝ . Khi đó gof(-2) bằng: 
 a, 65 b, 34 c, 68 
12, Hãy cho biết thứ tự duyệt các đỉnh của cây có gốc a sau theo phương pháp duyệt tiền thứ tự: 
ng_huu_bien@yahoo.com 095.624.5865 14
Discrete Marthematics 
 a, b c d a e g h b, a b e c d g h 
 c, e b a c g d h d, e g h a d c b 
13, Có bao nhiêu xâu nhị phân có độ dài bằng 5 mà hoặc có 2 bít đầu tiên là 0 hoặc có 2 bít cuối cùng là 1? 
 a, 16 b, 14 c, 2 d, 32 
14, Mỗi thành viên trong câu lạc bộ Toán tin có quê ở 1 trong 20 tỉnh thành. Hỏi cần phải tuyển bao nhiêu thành 
viên để đảm bảo có ít nhất 5 người cùng quê? 
 a, 81 b, 99 c, 101 d, 90 
15, Hệ nào sau đây KHÔNG phải là một hệ đầy đủ? 
 a, {∨ ,→ , } b, {¬ ∧ ,¬ } 
 c, {∧ ,∨ } d, { ,∨ ¬ } 
16, Có bao nhiêu hàm số khác nhau từ tập có 4 phần tử đến tập có 3 phần tử: 
a, 81 b, 64 c, 4 d, 12 
17, Cho tập A = {2, 3, 4, 5}. Hỏi tập nào KHÔNG bằng tập A? 
 a, {4, 3, 5, 2} 
 b, {a | a là số tự nhiên >1 và <6} 
 c, {b | b là số thực sao cho 1<b2 <36} 
 d, {2, 2, 3, 4, 4, 4, 5} 
18, Cây tam phân đầy đủ có 12 đỉnh trong sẽ có số đỉnh là: 
 a, 34 b, 35 c, 36 d, 37 
19, Đồ thị sau có bao nhiêu thành phần liên thông? 
 a, 1 b, 3 c, 5 d, 7 
20, Cho tập A={1, 2, 3, 4}.Trong các quan hệ trên tập A cho dưới đây, quan hệ nào là quan hệ tương đương? 
r. {(1, 1), (1, 2), (1,3), (2,2), (2,1), (2,3), (3,3)} 
s. {(1, 1), (3,3), (2,3), (2,1), (3,2), (1,3)} 
t. {(1,1), (1,2), (2,1), (2,2), (3,3), (4,4)} 
u. {(1, 1), (2, 2), (3,3), (4,4), (2,1), (2,3), (3,1)} 
21, Cho quan hệ R = {(a,b)| a ≡ b(mod 4)} trên tập {-8, -7, ,7, 8}. Hãy xác định [1]4 ? 
 a, {-8, -4, 1, 4, 8} b, {-7, -3, 1, 5} 
 c, {-5, -1, 3, 7} d, {1} 
22, Cho tập A = {-12, -11,11, 12} và quan hệ tương đương trên A: R = {(a,b)| a≡b(mod 4)}. Hỏi R sẽ tạo ra một 
phân hoạch gồm bao nhiêu tập con trên A? 
 a. 3 b. 0 
 c. 2 d. 4 
23, Đồ thị Wn có số đỉnh và số cạnh tương ứng là: 
 a, n, 2n b, n+1, 2(n+1) c, n, 2(n+1) d, n+1, 2n 
24, Số xâu khác nhau có thể tạo được từ các chữ cái của từ ORONO là: 
 a, 10 b, 20 c, 5 d, 100 
25, Cho công thức logic A = . Hỏi khẳng định nào sau đây là đúng? )( pqp →∧¬
 a, A hằng đúng b, A hằng sai c, A thỏa được 
ng_huu_bien@yahoo.com 095.624.5865 15
Discrete Marthematics 
Khoa CNTT 
Bộ môn KHMT 
Môn: Toán rời rạc 
Đề thi số: 0204TL3 
Thời gian: 90 phút 
Trưởng bộ môn 
Ký duyệt 
Chú ý:, Ở phần câu hỏi trắc nghiệm, mỗi câu hỏi chỉ được chọn một phương án trả lời. 
A, Phần câu hỏi trắc nghiệm: 
1, Cho Q(x,y) là vị từ: “x+y=0”, xác định trên tập số nguyên. Hỏi mệnh đề nào có giá trị chân lý là đúng? 
 a, ∃ x∀ y Q(x,y) b, ∀ x y Q(x,y) ∃
 c, d, ),( yxyQx∀∀ ),( yxxQy∀∃ 
2, Cho p, q, r là các mệnh đề: 
 p: Bạn nhận được điểm giỏi trong kì thi cuối khóa. 
 q: Bạn làm hết các bài tập trong cuốn sách này. 
 r: Bạn sẽ được công nhận là gỏi ở lớp này 
Hỏi biểu thức logic nào biểu diễn cho khẳng định: “Bạn nhận được điểm giỏi ở kì thi cuối khóa, nhưng bạn không 
làm hết các bài tập trong cuốn sách này, tuy nhiên bạn vẫn được công nhận là giỏi ở lớp này.” 
 a, p∧ q ∨ r b, p∨ q ∨ r 
 c, p∨ q ∧ r d, p∧ q ∧ r 
3, Cho công thức logic A = ( p ∧ q) → p . Hỏi khẳng định nào sau đây là đúng? 
 a, A hằng đúng b, A hằng sai c, A thỏa được 
4, Trong các cặp mệnh đề sau, hỏi cặp nào là KHÔNG tương đương? 
 a, )(xxP∀ và )(xPx∃ b, và qp → pq → 
 c, qp → và pq ∨ d, )(xxP∃ và )(xPx∀ 
5, Cho tập A có 6 phần tử, khi đó lực lượng của tập lũy thừa của tập A là: 
 a, 6 b, 36 
 c, 32 d, 64 
6, Tập lũy thừa của tập A có n phần tử là: 
 a, Tập các tập con của tập A 
 b, Tập con của tập A 
 c, Tập chứa tất cả các phần tử của tập A và tập rỗng 
 d, (n lần) AAA ××× ...
7, Cho tập A = {1,2,3} và tập B= {a,b,c,d}. Tập nào là tập con của tập A×B: 
 a, {(1,a),(2,b),(3,d)} b, {a, c, 2a, 2d, 3b} 
 c, {{1,a},{2,c},{2,d}} d, {(1,a), (1,c),(b,2)} 
8, Trong số các quy tắc sau, quy tắc nào là hàm số? 
 a, Lớp → Phòng học (quy tắc phân phòng học) 
 b, f : ℝ → ℝ sao cho f(x) = x 
 c, f(a) = b, sao cho a ≡ b (mod3), với a,b∈ℤ 
 d, Sinh viên → Tỉnh (quy tắc xác định quên quán của sinh viên) 
9, Cho quy tắc f: ℤ → ℝ thỏa mãn f(x) = 2x3. Khi đó : 
 a, f là hàm đơn ánh. b, f là hàm toàn ánh. 
 c, f là hàm song ánh d, f không là hàm số. 
10, Số xâu tam phân có độ dài bằng 6 là: 
 a,P(6,3) b, 36 c, 6! d, C(6,3) 
11, Có bao nhiêu hàm đơn ánh từ tập có 10 phần tử đến tập có 7 phần tử? 
 a, 70 b, 10 c, 7 d, 0 
12, Phương trình x + y + z < 15 có số nghiệm nguyên không âm là: 
 a,816 b, 817 c, 818 d, 819 
13, Cho quan hệ R = {(f,g)| f(x)-g(x) = 2} trên tập các hàm số từ ℤ →ℤ. Hỏi R có tính chất nào? 
 a, phản xạ b, đối xứng c, bắc cầu d, phản đối xứng 
14, Cho quan hệ R = {(a,b)| a ≡ b(mod 5)} trên tập {-12, -11, ,11, 12}. Hãy xác định [2]5 ? 
 a, {-8, -3, 2, 7, 12} b, {-9, -3, 2, 7, 12} 
 c, {-12, -7, -2, 2, 7, 12} d, {2} 
ng_huu_bien@yahoo.com 095.624.5865 16
Discrete Marthematics 
15, Cho quan hệ R = {(a,a),(a,b),(a,d),(b,b),(b,a),(b,c),(c,c),(c,b),(d,d),(d,a),(e,e)} trên tập {a, b, c, d, e}. Hỏi khẳng 
định nào sau đây là đúng? 
 a, R là quan hệ tương đương. 
 b, R là quan hệ thứ tự. 
 c, Cả a và b đều sai. 
16, Đồ thị K4 có số đỉnh và số cạnh tương ứng là: (n(n-1)/2 cạnh với n là đỉnh) 
 a, 4, 8 b, 4, 6 c, 5, 8 d, 4,4 
17, Cho đồ thị phẳng có số đỉnh bằng 5 và số cạnh bằng 7. Đồ thị này sẽ chia mặt phẳng thành: 
 a, 4 miền b, 5 miền c, 6 miền d, 7 miền 
18, Đồ thị Cn có số đỉnh và số cạnh tương ứng là: 
 a, n, n+1 b, n, n c, n,n-1 d, n, 2n 
19, Đồ thị sau có bao nhiêu thành phần liên thông? 
 a, 1 b, 3 c, 5 d, 7 
20, Một cây có n đỉnh thì có số cạnh là: 
 a, n b, n-1 c, n+1 d, n-2 
21, Hãy cho biết thứ tự duyệt các đỉnh của cây có gốc a sau theo phương pháp duyệt hậu thứ tự: 
 a, e b c g h d a b, a b e c d g h 
 c, e b a c g d h d, h g e d c b a 
22, Cây nhị phân đầy đủ có 19 đỉnh sẽ có số đỉnh trong là: 
 a, 7 b, 8 c, 9 d, 10 
23, Cây tam phân đầy đủ có 10 đỉnh trong sẽ có số lá là: 
 a, 20 b, 21 c, 22 d, 23 
24, Có 10 màu, cần ít nhất bao nhiêu viên bi để có ít nhất 25 viên cùng màu: 
a,255 b, 355 c, 455 d, 555 
25, Trong số các quan hệ hai ngôi dưới đây, quan hệ nào có tính phản đối xứng? 
 a. R = {(a,b)| a≤b} trên tập số nguyên 
 b. {(1,1), (1,2), (2,2), (2,3), (3,2), (3,3)} trên tập {1,2,3} 
 c. {(a,b), (a,c), (b,b), (b,c), (c,a)} trên tập {a,b,c} 
 d. R = {(a,b)| a≡b(mod 3)} trên tập {-15, -14, , 14, 15} 
Khoa CNTT 
Bộ môn KHMT 
Môn: Toán rời rạc 
Đề thi số: 0204TL4 
Thời gian: 90 phút 
Trưởng bộ môn 
Ký duyệt 
Chú ý: Ở phần câu hỏi trắc nghiệm, mỗi câu hỏi chỉ được chọn một phương án trả lời. 
A, Phần câu hỏi trắc nghiệm: 
1, Cho công thức logic A = ( p ∧ q) → p . Hỏi khẳng định nào sau đây là đúng? 
 a, A hằng đúng b, A hằng sai c, A thỏa được 
ng_huu_bien@yahoo.com 095.624.5865 17
Discrete Marthematics 
2, Đồ thị K4 có số đỉnh và số cạnh tương ứng là: 
 a, 4, 8 b, 4, 6 c, 5, 8 d, 4,4 
3, Cho Q(x,y) là vị từ: “x+y=0”, xác định trên tập số nguyên. Hỏi mệnh đề nào có giá trị chân lý là đúng? 
 a, ∃ x∀ y Q(x,y) b, ∀ x∃ y Q(x,y) 
 c, d, ),( yxyQx∀∀ ),( yxxQy∀∃ 
4, Hãy cho biết thứ tự duyệt các đỉnh của cây có gốc a sau theo phương pháp duyệt hậu thứ tự: 
 a, e b c g h d a b, a b e c d g h 
 c, e b a c g d h d, h g e d c b a 
5, Cho tập A có 6 phần tử, khi đó lực lượng của tập lũy thừa của tập A là: 
 a, 6 b, 36 
 c, 32 d, 64 
6, Có 10 màu, cần ít nhất bao nhiêu viên bi trong số các phương án dưới đây để có ít nhất 25 viên cùng màu: 
a,155 b, 255 c, 355 4, 555 
7, Cho tập A = {1,2,3} và tập B= {a,b,c,d}. Tập nào là tập con của tập A×B: 
 a, {(1,a),(2,b),(3,d)} b, {a, c, 2a, 2d, 3b} 
 c, {{1,a},{2,c},{2,d}} d, {(1,a), (1,c),(b,2)} 
8, Đồ thị Cn có số đỉnh và số cạnh tương ứng là: 
 a, n, n+1 b, n, n c, n,n-1 d, n, 2n 
9, Cho quy tắc f: ℝ → ℝ thỏa mãn f(x) = 2x3. Khi đó f là : 
 a, Hàm đơn ánh. b, Hàm toàn ánh. 
 c, Hàm số d, Hàm song ánh. 
10, Cây nhị phân đầy đủ có 19 đỉnh sẽ có số đỉnh trong là: 
 a, 7 b, 8 c, 9 d, 10 
11, Có bao nhiêu hàm đơn ánh từ tập có 10 phần tử đến tập có 7 phần tử? 
 a, 70 b, 10 c, 7 d, 0 
12, Phương trình x + y + z < 15 có số nghiệm nguyên không âm là: 
 a,816 b, 817 c, 818 d, 819 
13, Cho quan hệ R = {(f,g)| f(x)-g(x) = 2} trên tập các hàm số từ ℤ →ℤ. Hỏi R có tính chất nào? 
 a, phản xạ b, đối xứng c, bắc cầu d, phản đối xứng 
14, Cho quan hệ R = {(a,b)| a ≡ b(mod 5)} trên tập {-12, -11, ,11, 12}. Hãy xác định [2]5 ? 
 a, {-8, -3, 2, 7, 12} b, {-9, -3, 2, 7, 12} 
 c, {-12, -7, -2, 2, 7, 12} d, {2} 
15, Cho quan hệ R = {(a,a),(a,b),(a,d),(b,b),(b,a),(b,c),(c,c),(c,b),(d,d),(d,a),(e,e)} trên tập {a, b, c, d, e}. Hỏi khẳng 
định nào sau đây là đúng? 
 a, R là quan hệ tương đương. 
 b, R là quan hệ thứ tự. 
 c, Cả a và b đều sai. 
16, Cho p, q, r là các mệnh đề: 
 p: Bạn nhận được điểm giỏi trong kì thi cuối khóa. 
 q: Bạn làm hết các bài tập trong cuốn sách này. 
 r: Bạn sẽ được công nhận là gỏi ở lớp này 
Hỏi biểu thức logic nào biểu diễn cho khẳng định: “Bạn nhận được điểm giỏi ở kì thi cuối khóa, nhưng bạn không 
làm hết các bài tập trong cuốn sách này, tuy nhiên bạn vẫn được công nhận là giỏi ở lớp này.” 
 a, p∧ q ∨ r b, p∨ q ∨ r 
 c, p∨ q ∧ r d, p∧ q ∧ r 
17, Cho đồ thị phẳng có số đỉnh bằng 5 và số cạnh bằng 7. Đồ thị này sẽ chia mặt phẳng thành: 
 a, 4 miền b, 5 miền c, 6 miền d, 7 miền 
18, Trong số các quy tắc sau, quy tắc nào là hàm số? 
 a, Lớp → Phòng học (quy tắc phân phòng học) 
 b, f : ℝ → ℝ sao cho f(x) = x 
ng_huu_bien@yahoo.com 095.624.5865 18
Discrete Marthematics 
 c, f(a) = b, sao cho a ≡ b (mod3), với a,b∈ℤ 
 d, Sinh viên → Tỉnh (quy tắc xác định quên quán của sinh viên) 
19, Đồ thị sau có bao nhiêu thành phần liên thông? 
 a, 1 b, 3 c, 5 d, 7 
20, Một cây có n đỉnh thì có số cạnh là: 
 a, n b, n-1 c, n+1 d, n-2 
21, Trong các cặp mệnh đề sau, hỏi cặp nào là KHÔNG tương đương? 
 a, )(xxP∀ và )(xPx∃ b, qp → và pq → 
 c, qp → và pq ∨ d, )(xxP∃ và )(xPx∀ 
22, Số xâu tam phân có độ dài bằng 6 là: 
 a,P(6,3) b, 36 c, 6! d, C(6,3) 
23, Cây tam phân đầy đủ có 10 đỉnh trong sẽ có số lá là: 
 a, 20 b, 21 c, 22 d, 23 
24, Tập lũy thừa của tập A có n phần tử là: 
 a, Tập các tập con của tập A 
 b, Tập con của tập A 
 c, Tập chứa tất cả các phần tử của tập A và tập rỗng 
 d, (n lần) AAA ××× ...
25, Trong số các quan hệ hai ngôi dưới đây, quan hệ nào có tính phản đối xứng? 
 a. R = {(a,b)| a≤b} trên tập số nguyên 
 b. {(1,1), (1,2), (2,2), (2,3), (3,2), (3,3)} trên tập {1,2,3} 
 c. {(a,b), (a,c), (b,b), (b,c), (c,a)} trên tập {a,b,c} 
 d. R = {(a,b)| a≡b(mod 3)} trên tập {-15, -14, , 14, 15} 
ng_huu_bien@yahoo.com 095.624.5865 19