TRƯỜNG ĐẠI HỌC CẦN THƠ
TRƯỜNG CNTT&TT

KIỂM TRA HỌC PHẦN CT172
MÔN: TOÁN RỜI RẠC
Thời gian: 180 phút

Đề thi gồm 8 trang
I - Trắc nghiệm:
Câu 1: Tổng số phần tử của tập hợp {1, 2, 3, ..., 10} là bao nhiêu?
a. 55
b. 50
c. 45
d. 10
Câu 2: Có bao nhiêu cách chia 11 cái bánh cho 5 đứa trẻ trong đó mỗi đứa được ít
nhất một cái?
A. 210
B. 240
C. 180
D. 160
Câu 3: Tính giá trị của phép tính - 27 mod 5 là bao nhiêu?
A. 2
B. 3
C. 4
D.1
Câu 4: Để chứng minh “một số nguyên dương n là lẻ khi và chỉ khi 5n+6 là lẻ”, ta
dùng phương pháp chứng minh nào?
A. Trực tiếp

B. Gián tiếp

C. Phản chứng

D. Quy nạp

Câu 5: Có bao nhiêu chuỗi bit có độ dài 8 hoặc bắt đầu bằng 1 hoặc bắt đầu bằng 00
A. 192

B. 160

C. 180

D. 210

Câu 6: Giả sử cần chọn ra 1 đại diện học sinh tham gia dự thi Olympic Tin học. Biết
thể lựa chọn học sinh khối 11 và khối 12. Hỏi có bao nhiêu lựa chọn khác nhau, nếu
có 300 học sinh khối 11 và 260 em học sinh khối 12.
A. 560

B. 260

C. 300

Câu 7: Tìm chữ số hàng trăm của P = 292007 .
A. 1

B. 2

C. 3

D. 78000


D. 4

Câu 8: Các hoán vị của n phần tử:
A. Là một bộ không kể thứ tự gồm k thành phần khác nhau lấy từ n phần tử đã cho.
B. Là bộ có thứ tự gồm k thành phần lấy ra từ n phần tử đã cho. Các phần tử không
được lặp lại.
C. Là một cách xếp có thứ tự n phần tử đó thành một dãy.
D. Là bộ có thứ tự gồm k thành phần lấy từ n phần tử của tập đã cho.Câu 9: Cho tập
Câu 9: 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)}
Câu 10: Quan hệ tương đương là một quan hệ 2 ngơi và có các tính chất:2310
A. Phản xạ, phản đối xứng, đối xứng
B. Phản xạ, đối xứng, bắc cầu
C. Phản xạ, phản đối xứng, bắc cầu
D. Phản xạ, đối xứng, phản đối xứng, bắc cầu
Câu 11: Biểu thức logic không chứa thành phần nào dưới đây:
A. Các mệnh đề
B. Các vị từ
C. Các biến mệnh đề
D. Các phép toán logic
Câu 12: Có tất cả số nguyên tố p thõa �2 + 14 là số nguyên tố?
A. 0
B. 1

C. 2
D. 3
Câu 13: Gọi A là số tập hợp số cách chia bộ bài tú lơ khơ 52 quân thành 4 phần bằng
nhau. Tìm 2 chữ số cuối cùng của A.
A. 10

B. 20

C. 00

D. 30

Câu 14: Phương pháp chứng minh đi từ giả thiết đến kết luận thông qua các luật suy
diễn, các định lý, các nguyên lý hay các kết quả đã có từ trước được gọi là phương
pháp chứng minh:
A. Gián tiếp
B. Trực tiếp
C. Tầm thường
D. Theo giả thiết
Câu 15: Để chứng minh một quy tắc suy luận đúng ta thường sử dụng các phương
pháp:
A. Định nghĩa, biến đổi tương đương logic
B. Lập bảng giá trị chân lý và kết luận theo định nghĩa
C. Biến đổi tương đương logic
D. Chứng minh trực tiếp
Câu 16: Có bao nhiêu chuỗi bít độ dài bằng 8 hoặc bắt đầu bởi 00 hoặc kết thúc bởi 11
A. 112
B. 128
C. 64
D. 124

Câu 17: Phương trình x + y + z = 15 có số nghiệm nguyên không âm là:
A. 136

B. 455

C. 15

D. 30

Câu 18: Giả sử P và Q là 2 mệnh đề, chọn đáp án đúng cho định nghĩa mệnh đề P→Q?


A. Là một mệnh đề nhận chân trị đúng khi một trong hai hoặc cả 2 mệnh đề cùng
đúng, nhận chân trị sai trong các trường hợp còn lại.
B. Là một mệnh đề nhận chân trị đúng khi P và Q có cùng chân trị. Nhận chân trị sai
trong các trường hợp còn lại.
C. Là một mệnh đề nhận chân trị đúng khi P sai hoặc cả P và Q cùng đúng. Nhận chân
trị sai khi và chỉ khi P đúng Q sai
D. Là 1 mệnh đề nhận chân trị đúng khi P và Q cùng đúng, sai khi P và Q cùng sai.
Câu 19: 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?
a.
{(1, 1), (1, 2), (1,3), (2,2), (2,1), (2,3), (3,3)}
b.
{(1, 1), (3,3), (2,3), (2,1), (3,2), (1,3)}
c.
{(1,1), (1,2), (2,1), (2,2), (3,3), (4,4)}
d.
{(1, 1), (2, 2), (3,3), (4,4), (2,1), (2,3), (3,1)}
Câu 20: Cho tập không gian là U = {1, 2, 4, 6, 7}, 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)

c.xyP(x,y)

d. xyP(x,y)

Câu 21: 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 thỏa mãn cả phản xạ, đối xứng, bắc cầu?
A. {(1, 1), (1, 2), (1,3), (2,2), (2,1), (2,3), (3,3)}
B. {(1, 1), (3,3), (2,3), (2,1), (3,2), (1,3)}
C. {(1,1), (1,2), (2,1), (2,2), (3,3), (4,4)}
D. {(1, 1), (2, 2), (3,3), (4,4), (2,1), (2,3), (3,1)}
Câu 22: Biển số xe gồm 8 kí tự dạng

�� − ��
����

, ví dụ

�� − ��
����

.Hai số đầu là mã tỉnh , X

là chữ cái (gồm 26 chữ cái). N gồm các số từ 0, 1, …. 9. Hỏi một tỉnh cần đăng kí cho
10 triệu chiếc xe thì cần ít nhất bao nhiêu serial(X).
A. 4

B.5
C.6
D.7
Câu 23: Biểu thức hằng đúng là?
A. Biểu thức chỉ nhận chân trị đúng khi các biến mệnh đề nhận chân trị đúng.
B. Biểu thức nhận chân trị đúng trong mọi trường hợp về chân trị của bộ biến mệnh đề
C. Biểu thức nhận chân trị sai trong mọi trường hợp về chân trị của bộ biến mệnh đề
D. Biểu thức chỉ nhận chân trị sai khi các biến mệnh đề nhận chân trị sai.
Câu 24: Cho dãy số (an ) thõa a1 = 2 và an+1 = 2an . Tìm chữ số cuối cùng của a2023 :
a) 2
b) 4
c) 6
d) 8


Câu 25: Quan hệ trên tập A = {1, 2, 3} được xác định bởi {(1, 2), (2, 3), (3, 1)}. Quan
hệ này là:
a) Quan hệ phản đối xứng
b) Quan hệ đối xứng
c) Quan hệ không đối xứng
d) Quan hệ khác
Câu 26: Cho hai biến Boolean x và y. Hãy tính giá trị của biểu thức sau:
(x ∧ y) ∨ (x ∧ ¬y)
a) x
b) y
c) ¬x
d) x ∧ y
Câu 27: Cho số A = 20122013 . Tìm chữ số tận cùng của A.
A. 2
B. 3

C. 4
D. 5
Câu 28: Mệnh đề “Mỗi học sinh đều có một số điểm khác nhau” được phát biểu bằng
cách nào?
a. Tất cả học sinh, tồn tại số điểm khác nhau
b. Tồn tại học sinh nào có số điểm khác nhau
c. Một số học sinh có số điểm giống nhau
d. Khơng có học sinh nào có số điểm giống nhau
Câu 29: Câu sau dựa trên quy tắc nào: “Nếu hơm nay trời mưa thì cơ ta khơng đến,
nếu cơ ta khơng đến thì ngày mai cơ ta đến. Vậy thì, nếu hơm nay trời mưa thì ngày
mai cô ta đến.”
A. Tam đoạn luận tuyển
B. Tam đoạn luận giả định
C. Khẳng định
D. Phủ định
Câu 30: Cho biết quan hệ “lớn hơn hoặc bằng” trên tập Z có những tính chất nào?
A. Phạn xạ - đối xứng
B. Phản xạ - đối xứng – bắc cầu
C. Phản xạ - đối xứng – phản đối xứng
D. Phản xạ - phản đối xứng – bắc cầu
Câu 32: Đoạn dưới đây chứng minh “3n + 2 là lẻ thì n là lẻ”: Vì 3n + 2 lẻ là đúng ta
có 2 là số chẵn nên 3n là số lẻ, mà 3 là số lẻ nên n là số lẻ. Vậy ta đã có thể kết luận n
là lẻ. Đoạn trên sử dụng phương pháp chứng minh nào:
A. Gián tiếp
B. Trực tiếp
C. Phân chia trường hợp
D. Phản chứng
Câu 33: Cho quan hệ R = {(a,b)| a ≡ b(mod 5)} trên tập {-12, -11, …,11, 12}. Hãy xác
định [2]R?



A. {-9, -3, 2, 7, 12}
B. {-12, -7, -2, 2, 7, 12}
C. {-8, -3, 2, 7, 12}
D. {2}
Câu 34: Cho tập A = { 1, 2, 3, 4, 5, 6 } và quan hệ R ⊆ A x A được xác định như sau:
Với mọi a, b A, aRb khi và chỉ khi hiệu a - b là một số chẵn. Quan hệ R là:
A. R= {(1, 1), (2, 2), (3, 3),(4, 4), (5, 5), (6, 6), (1, 3), (3,1),(1, 5), (5, 1),(2, 4), (4, 2),
(2,6), (6,2), (3,5), (5,3), (4,6), (6,4)}
B. R= {(1, 1), (2, 2), (3, 3),(4, 4), (5, 5), (6, 6), (3,1),(5, 1), (4, 2), (6,2), (5,3), (6,4)}
C. R= {(1, 3), (3,1),(1, 5), (5, 1),(2, 4), (4, 2), (2,6), (6,2), (3,5), (5,3), (4,6), (6,4)}
D. R= {( (3,1), (5, 1), (4, 2), (6,2), (5,3), (6,4)}
Câu 35: Cho tập A= {5, 6, 7, 8}, 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 = {(5,5), (5,7), (5,8), (7,6), (7,7), (8,6), (8,7)}
B. R = {(5,5), (5,6), (6,7), (7,6) ,(6,8), (7,7), (8,5), (8,6)}
C. R = {(5,5), (5,6), (5,7), (7,5),(6,6), (6,7), (7,7), (8,8), (8,6)}
D. R = {(5,5), (5,7), (7,5), (6,6), (6,8), (7,7), (8,8), (8,7)}
Câu 36: Giả sử P và Q là 2 mệnh đề. Tuyển của 2 mệnh đề (P v Q) là một mệnh đề… ?
A. Chỉ đúng khi cả P và Q cùng đúng
B. Chỉ sai khi cả P và Q cùng sai
C. Chỉ đúng khi P đúng Q sai
D. Chỉ sai khi P đúng Q sai
Câu 37: Hãy cho biết khẳng định nào sau đây không phải là 1 mệnh đề?
A. 2 + 3 < 4
B. 3 là 1 số chẵn
C. Cho x là một số nguyên dương
D. 1 - 2 < 0
Câu 38: Giả sử P và Q là 2 mệnh đề, P→Q là một mệnh đề…?
A. Chỉ nhận chân trị sai khi P đúng Q sai. Nhận chân trị đúng trong các trường hợp

còn lại.
B. Chỉ nhận chân trị sai khi P sai Q đúng. Nhận chân trị đúng trong các trường hợp
còn lại.
C. Chỉ nhận chân trị đúng khi P sai Q đúng. Nhận chân trị sai trong các trường hợp
còn lại.
D. Nhận chân trị đúng khi 1 trong 2 mệnh đề nhận chân trị đúng, sai trong các trường
hợp còn lại.
Câu 39: 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)}
Câu 40: 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,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}
Câu 41: Cho quan hệ R = {(1,1), (1,2), (2,2), (2,3), (3,1), (3,3)} trên tập {1,2,3}. Hỏi
phát biểu nào sau đây là đúng?
A. R là quan hệ tương đương
B. R là quan hệ thứ tự
C. R có tính bắc cầu
D. R khơng có tính bắc cầu
Câu 42: Xác định chân trị của biểu thức ( X→ Y) ( Y → Z) và ( X → Z) khi X =
Y=0, Z= 1?
A. 1 và 1
B. 0 và 0

C. 1 và 0
D. 0 và 1
Câu 43: Câu nào sau đây KHÔNG là một mệnh đề:
A. Hôm nay không phải Thứ hai
B. Lan học giỏi Tin học
C. Không phải Hiếu được khen thưởng
D. Thật vui vì Lan ở nhà.
Câu 44: Câu 26: Xác định chân trị của biểu thức ( P → Q ) Λ ( P → R ) và (R→ P)
khi P = Q = 1, R=0?
A. 1 và 1
B. 0 và 0
C. 1 và 0
D. 0 và 1
Câu 45: Một tập đoàn JPN có ban hội đồng quản trị gồm chủ tịch tập đồn JPN và 2
cộng sự của mình là giám đốc tập đồn và phó giám đốc tập đồn JPN, các chức vụ
này cực kì quan trọng trong tập đồn, nếu một trong số chức vụ có vấn đề thì cả tập
đồn sẽ bị ảnh hưởng và có nguy cơ bị tan rã. Ngồi ra một số phịng ban cũng rất
quan trọng đối với tập đồn. Đó là những phịng ban sau: Phòng Nhân sự: quản lý các
hoạt động liên quan đến nhân sự, bao gồm tuyển dụng, đào tạo, trả lương, quản lý
chính sách và thực hiện các chính sách về việc làm. Phịng Kế tốn: quản lý các hoạt
động liên quan đến tài chính và kế tốn, bao gồm quản lý ngân sách, theo dõi thu chi,
quản lý tài sản và thuế. Phòng Bán hàng: quản lý các hoạt động liên quan đến bán


hàng, bao gồm định giá, khuyến mãi, quản lý đại lý và quản lý khách hàng. Phòng Kỹ
thuật: quản lý các hoạt động liên quan đến nghiên cứu và phát triển sản phẩm, quản lý
quy trình sản xuất và cải tiến chất lượng sản phẩm và cuối cùng là Phòng Tài chính:
quản lý các hoạt động liên quan đến tài chính của cơng ty, bao gồm quản lý đầu tư,
quản lý tài sản và quản lý rủi ro tài chính. Muốn cho tập đồn phát triển thì một trong
những hội đồng quản trị mỗi tuần phải xuống một phòng ban để phổ biến kế hoạch.

Vậy có bao nhiêu cách chọn người trong hội đồng quản trị để xuống phòng ban mỗi
tuần, để giúp công ty phát triển hơn?
A. 3
B. 7
C. 5
D. 8
**Điền công thức vào các câu sau:
1. Luật thống trị: ………
2. Luật kết hợp:………
3. Luật De Morgan’s:………
4. Luật khẳng định (Modus Ponens):………
5. Tam đoạn luận tuyển:………
II - Tự luận:
Câu 1: Mệnh đề sau đây, đâu là mệnh đề đúng?
a) [(r → s) → [( r → s) → ( ¬t ∨ u )]] → ( ¬t ∨ u)
b) (p → q) ∧ (q → r) ⇒ p → (q → r)
Câu 2: Xác định chân trị của các mệnh đề nếu biết p = 1
( p → [( ¬q ∨ r ) ∧ ¬s ]) ∧ [¬s → ¬r ∧ p]
Câu 4: Dùng quy nạp toán học chứng minh rằng:

n(n + 1) 2
]
2
Câu 3: Bài toán ”Trâu ăn cỏ” trong dân gian: “Một trăm bó cỏ; Một trăm con trâu;
Trâu đứng ăn 5; Trâu nằm ăn 3; Ba con trâu già ăn 1”. Hỏi có bao nhiêu trâu đứng,
trâu nằm, trâu già?
Câu 5: Cho p và q là hai mệnh đề:
p: “Điểm của bạn học mơn Tốn Rời Rạc trên 5.0”
q: “Bạn bị rớt học phần CT172”
Hãy viết mệnh đề sau bằng cách dùng p, q và các liên từ logic

a) Bạn sẽ rớt học phần CT172 nếu điểm của bạn học mơn Tốn Rời Rạc dưới 5.0
b) Điểm của bạn học mơn Tốn Rời Rạc dưới 5.0 là đủ điều kiện rớt học phần CT172
c) Bạn bị rớt học phần CT172 nhưng điểm của bạn học mơn Tốn Rời Rạc vẫn trên
5.0
d) Mỗi lần bạn bị rớt học phần CT172 là điểm của bạn học mơn Tốn Rời Rạc chưa
chắn chắc rằng bạn đã dưới 5.0 .
Câu 6: Tìm các bit x, y, z, u thõa:
P = 13 + 23 + 33 + . . . . + n3 = [


�( � ∨ � ) = 1
� ∨ � = ��
�� ∨ �� = 0
Câu 7: Giải hệ phương trình sau:
2� ≡ 3 (��� 4)
3� ≡ 4 (��� 5)
a)
4� ≡ 8 (��� 12)
6� ≡ 2 (��� 15)
� + � = 128
b)
(�. �) = 16
Câu 8: Cho p là số nguyên tố lớn hơn 3. Chứng minh rằng:
a) �2 − 1 chia hết cho 24
b) Nếu 8� + 1 là số nguyên tố thì 8� − 1 là hợp số.
Câu 9: Bạn Khải sinh viên lớp Khoa học máy tính đã viết một số có hai chữ số mà
tổng các chữ số của nó là 14. Bạn Khải đem số đó chia cho 8 thì được số dư là 4,
nhưng khi chia cho 12 thì được số dư là 3.
a) Chứng minh rằng bạn Khải đã làm sai ít nhất một phép tính chia.
b) Nếu phép chia thứ nhất cho 8 là đúng thì phép chia thứ hai cho 12 có số dư là bao

nhiêu ? Hãy Tìm số bị chia.