Ôn tập Cấu trúc rời rạc | Trường Đại học CNTT Thành Phố Hồ Chí Minh

lOMoAR cPSD| 40425501 ÔN TẬP
Bài 1: Có 3 giỏ đựng các quả bóng xanh, đỏ, vàng. Biết rằng, mỗi giỏ chỉ chứa các quả bóng
cùng màu và chứa ít nhất 10 quả bóng. Hỏi:
a) Có bao nhiêu cách chọn 10 quả bóng?
b) Có bao nhiêu cách chọn 10 quả bóng sao cho đủ các màu?
Bài 2: Trên tập hợp X = {1, 2, 3, 5, 8, 10, 18, 21, 25, 30}, cho quan hệ hai ngôi R như sau:
x R y ⇔ 2x ≥ 2y, với x, y ∈ X.
a) Chứng minh rằng R là một quan hệ thứ tự trên X.
b) Hãy chỉ ra phần tươn tại điểm, tại tiêu, phần tươn lớn nhất, nhỏ nhất (nếu có) theo quan hệ R trên X. Bài 3:
a/ Hãy viết dạng phủ định của mệnh đề A cho biết chân trị của dạng phủ định đó:
A = "∀ x ∈ ℤ, ∃ y ∈ ℤ, (x^2 = y^2) → (x = -y)"
b/ Hãy viết dạng phủ định của mệnh đề B cho biết chân trị của dạng phủ định đó:
B = "∃ x ∈ ℤ, ∀ y ∈ ℤ, (x^4 < y^4) → (x = y)" Bài 4:
a/ Trong kỳ thi học sinh giỏi, điểm bài thi được đánh giá bởi một số nguyên từ 0 đến 100. Hỏi ít
nhất có bao nhiêu học sinh dự thi đảm bảo tìm được ít nhất 5 học sinh có điểm thi bằng nhau?
b/ Một trường Mầm non có 15 phòng học, cần lắp máy lạnh cho mỗi phòng. Hỏi cần phải lắp ít
nhất bao nhiêu máy lạnh để có ít nhất một phòng học (nào đó) được lắp 3 máy lạnh?
Bài 5: Trên tập hợp X = {1, 2, 3, 4, 5}, cho quan hệ
R = {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3), (4,2), (4,3), (4,4), (5,3), (5,5)}.
a) Quan hệ thứ tự R trên X có phải là quan hệ thứ tự không? Vì sao?
b) Vẽ biểu đồ Hasse cho (X, R) và tìm phần tử tại điểm, tại tiêu, phần tử tối đa, nhỏ nhất (nếu có) của (X, R).
Bài 6: Hãy kiểm tra xem suy luận sau có đúng hay không? lOMoAR cPSD| 40425501 Bài giải: B愃i 1: Giải:
Gọi x x x1, 2, 3 l n lượt l愃 s Ā quả bóng xanh, đỏ, v愃ng lấy ra từ các giỏ.
Ta có: x1 x2 x3 10 a/ Ta có x 10 10 10
1 0; x2 0; x3 0 nên đáp s Ā: K3 C3 10 1 C12 66 cách. b/
Ta có x1 1; x2 1; x3 1
+ Lấy 1 quả bóng từ giỏ m愃u xanh: có 1 cách;
+ Lấy 1 quả bóng từ giỏ m愃u đỏ: có 1 cách;
+ Lấy 1 quả bóng từ giỏ m愃u v愃ng: có 1 cách;
+ Lấy 7 quả bóng còn thiếu từ 3 giỏ tùy ý (xanh, đỏ, v愃ng): có
K37 C3 7 17 C97 36 cách. Đáp s Ā = 1*1*1*36 = 36 cách. B愃i 2:
a/ Chứng minh rằng R l愃 quan hê thứ tự trên ̣ X . * Tính phản xạ:
Vơꄁi mọi x X ta có xRx 2x 2x (luôn đúng)
Cho nên ta nói R có tính phản x愃⌀ (1).
* Tính phản đối xứng: Giả sư뀉 xRyyRx
2xy 22xy , vơꄁi x y X, . lOMoAR cPSD| 40425501 2
2x 2y 2x .
Theo nguyên lý kẹp ta có 2x 2y x y (do lấy log2 ở 2 vế pt) x y
Cho nên ta nói R có tính phản đ Āi xứng (2).
* Tính truyền (bắc cầu): , vơꄁi Giả sư뀉 xRyyRz
22xy 22yzx y z X, , .
2x 2y 2z 2x 2z xRz
Cho nên ta nói R có tính truyền (3) Từ
(1), (2), (3) suy ra R l愃 quan hệ thứ tự. b/
Ta có bi ऀ u đồ Hasse xét theo R trên X. 10 1 8 5 3 2 30 25 21 18 B愃i 3:
a/ Ta có A l愃 mệnh đề đúng, do: x
, ta chọn y x thì y thỏa
(x2 y2) (x y) (x2 y2) (x y) (( x)2 x2) ( y y) 0 1 1
Nghĩa l愃 (x2 y2) (x y) luôn đúng
Khi đó ta có (x2 y2) (x y) l愃 đúng
Cho nên A l愃 mệnh đề có chân trị = 1. Suy ra mệnh đề phủ định có chân trị bằng 0.
Ta có d愃⌀ng phủ định c n tìm l愃: A=" x , y
,(x2 y2) (x y)".
b/ Ta có d愃⌀ng phủ định của B l愃: lOMoAR cPSD| 40425501
B " x ¡ , y ¡ ,(x4 y4) (x y )" " x , y
,(x4 y4) (x y ) Lúc n愃y, x
, ta chọn y x thì (x4 y4) (x y ) (y4 y4) (y y ) 0 1 0
Cho nên mệnh đề phủ định sai, suy ra mệnh đề B luôn đúng. B愃i 4:
a/ Gọi n l愃 s Ā học sinh dự thi c n tìm trong kỳ thi học sinh giỏi. Ta có: n *
Theo nguyên lý chuồng bồ câu, ta có: kn
5, vơꄁi k 101 do các
s Ā nguyên từ 0 đến 100 có 101 s Ā. n 4 5 404 n 505 101 n 405 .
Đáp s Ā: có ít nhất 405 học sinh dự thi.
b/ Gọi n l愃 s Ā máy l愃⌀nh c n lắp cho một trường m m non. Ta có: n *
Theo nguyên lý chuồng bồ câu, ta có: kn 3, vơꄁi k 15 do
có tất cả 15 phòng học khác nhau. n 2 3 30 n 45 15 n 31.
Đáp s Ā: c n lắp ít nhất 31 máy l愃⌀nh. B愃i 5:
a/ Ta chứng tỏ R l愃 quan hệ thứ tự như sau: * Tính phản xạ:
Ta có (1,1),(2,2),(3,3),(4,4),(5,5) R nên xRx x X, Cho
nên ta nói R có tính phản x愃⌀ (1). lOMoAR cPSD| 40425501
* Tính phản đối xứng:
Ta có (1,2) R nhưng (2,1) R vì 1 2
Ta có (1,3) R nhưng (3,1) R vì 1 3
Ta có (2,3) R nhưng (3,2) R vì 2 3
Ta có (4,2) R nhưng (2,4) R vì 4 2
Ta có (4,3) R nhưng (3,4) R vì 4 3
Ta có (5,3) R nhưng (3,5) R vì 5 3 V愃
ta có: (1,1),(2,2),(3,3),(4,4),(5,5) R xRy
Nên ta có th ऀ kết luận
x y , vơꄁi x y X, . yRx
Cho nên ta nói R có tính phản đ Āi xứng (2). * Tính truyền: (1,2) R Ta có:
(1,3) R (l愃 đúng) (2,3) R (4,2) R Ta có: (4,3) R (l愃 đúng) (2,3) R Cho nên ta kết luận: xRy Giả sư뀉
xRz , vơꄁi x y z X, , . yRz
Cho nên ta nói R có tính truyền (3)
Từ (1), (2), (3) suy ra R l愃 quan hệ thứ tự trên X. b/ 1 2 3 5 4 lOMoAR cPSD| 40425501
+ Ph n tư뀉 t Āi đ愃⌀i: 3
+ Ph n tư뀉 t Āi ti ऀ u: 1, 4, 5
+ Ph n tư뀉 cực đ愃⌀i: 3
+ Ph n tư뀉 cực ti ऀ u: không có (do có nhiều t Āi ti ऀ u).
B愃i 6: Gợi ý: các b愃⌀n viết ra mô hình suy diễn tương ứng rồi ki ऀ m chứng tính đúng đắn
của mô hình lập được nha.
a/ Ta gọi các mệnh đề:
p = Nam l愃m việc chăm chỉ, hiệu
quả q = Nam được thăng chức r =
Nam được tăng lương s = Nam mua xe mơꄁi
Ta có mô hình suy diễn sau:
(p q) r r s s p q
Ta ki ऀ m chứng mô hình suy diễn n愃y như sau:
Ta có: r s tiền đề v愃 s tiền đề nên r pp phủ định
Ngo愃i ra,( p q ) r tiền đề Nên ( p q ) pp phủ định Hay p q luật DeMorgan
Ta có mô hình suy diễn l愃 đúng; cho nên ta có suy luận ban đ u l愃 hợp lệ. b/ Tương tự….
ĐỀ BÀI ÔN TẬP GIỮA KỲ I NĂM HỌC 2022-2023 MÔN CTRR Câu 1:
a/ Dùng các luật logic đ ऀ chứng minh rằng bi ऀ u thức sau l愃 hằng đúng
[r [(p q) r]] [( p q ) r]
b/ Dùng các luật logic, quy tắc suy diễn đ ऀ ki ऀ m tra tính đúng đắn của suy luận sau:
p (q r) lOMoAR cPSD| 40425501 t r s q p t s u u hoặc
H愃̀y ki ऀ m tra xem suy luận sau có đúng không?
c/ Viết d愃⌀ng phủ định cho mệnh đề sau v愃 cho biết chân trị của mệnh đề vừa tìm được.
A x ¡ , y ¡ ,(x 0) ((y 0) (x y 0)) Câu 2:
Trường t ऀ chức cho sinh viên đăng ký hiến máu nhân đ愃⌀o. Biết có 4 nhóm máu chính:
O, A, B, AB; mỗi sinh viên chỉ được đăng kí hiến một l n v愃 các sinh viên đăng kí đều
tham gia hiến đ y đủ. Hỏi phải có ít nhất bao nhiêu sinh viên đăng ký hiến máu đ ऀ chắc
chắn rằng có nhóm máu n愃o đó có ít nhất 30 lượt hiến. Câu 3:
Xếp 54 b愃n phím máy tính đ ऀ b愃n (keyboard) cùng lo愃⌀i v愃o 4 thùng A, B, C, D.
Tất cả các thùng ban đ u đều chưa có b愃n phím n愃o. Hỏi có bao nhiêu cách xếp, sao cho:
a) Mỗi thùng đều có ít nhất l愃 9 b愃n phím.
b) Thùng A có ít nhất 12 b愃n phím v愃 thùng C có t Āi đa 5 b愃n phím. Câu 4:
Trên tập hợp X { 3, 2, 1, 0,1, 2, 3, 4, 5}, cho quan hệ 2 ngôi R như sau:
x yR x3 x y 3 y , vơꄁi x y X, . a/ Chứng
minh rằng R l愃 quan hệ tương đương trên X.
b/ Chỉ ra các lơꄁp tương đương xét theo R trên X v愃 tập hợp thương tương ứng. Từ đó
viết X dươꄁi d愃⌀ng phân ho愃⌀ch của các lơꄁp tương đương theo R trên X. lOMoAR cPSD| 40425501 Câu 5:
Trên tập hợp X { 5, 3, 2,0,1,4,5,7,8,15, 18,20}, cho quan hệ 2
ngôi R như sau: x yR x y hoặc | x y | 5 , vơꄁi x y X, .
a) Chứng minh rằng R l愃 quan hệ thứ tự.
b) Quan hệ R có to愃n ph n không? Vì sao?
c) Vẽ bi ऀ u đồ Hasse cho (X,R).
d) Tìm các ph n tư뀉 t Āi đ愃⌀i, t Āi ti ऀ u, lơꄁn nhất, nhỏ nhất (nếu có) của X xét theo quan hệ thứ tự R. -----HẾT-----