Ôn thi giữa kì Môn Cấu trúc rời rạc | Trường Đại học Công nghiệp Thành phố Hồ Chí Minh

CẤU TRÚC RỜI RẠC – BUỔI 8 (26/09)
Sửa bài kiểm tra thường kỳ 2.
Bài 1. Trên mặt phẳng cho 12 điểm phân biệt. Hỏi vẽ được tất cả bao nhiêu đoạn thẳng
có hai đầu mút lấy trong các điểm đã cho?
 Muốn có 1 đoạn thẳng thì cần có 1 cặp điểm, mà đoạn thẳng thì 2 đầu mút có vai
trò như nhau  chọn mà không tính thứ tự  12C2 = 66.
Bài 2. SV lớp cấu trúc rời rạc được chia thành 3 nhóm A, B, C với số lượng lần lượt là
20, 30, 40. Hỏi có bao nhiêu cách chọn ra một cặp SV đến từ hai nhóm khác nhau?
 Chia 3 trường hợp: (A,B)  20.30 = 600, (B,C)  30.40 = 1200, (C,A)  40.20
= 800. Do đó, tổng có 600+1200+800 = 2600.
Bài 3. Hỏi có bao nhiêu cách tạo thành một mật khẩu độ dài 6 mà dùng các ký tự: a, a, a, 1, 2, 3?
 Tổng cộng có 6 ký tự, nhưng có 3 chữ a giống nhau  hoán vị có lặp: 6! / 3! = 120.
 VD: a, a, b, b, 1, 2, 3  7! / (2!.2!).
Bài 4. Có bao nhiêu cách chia 20 viên kẹo giống nhau cho 4 em bé mà em nào cũng có kẹo?
 Áp dụng công thức: Ck1  19C3. n1
* chia kẹo để số kẹo của mỗi em đều là số lẻ?
Gọi 2a – 1, 2b – 1, 2c – 1, 2d – 1 là số kẹo của các em, trong đó: a, b, c, d > 0. Thay vào:
(2a – 1) + (2b – 1) + (2c – 1) + (2d – 1) = 20
 2(a+b+c+d) = 24  a + b + c + d = 12. Số cách chia là: 11C3.
Bài 5. Có 5 bạn nam và 5 bạn nữ cần xếp vào một dãy 10 cái ghế. Hỏi có bao nhiêu
cách xếp mà tất cả các bạn nữ ngồi cạnh nhau?
 Do các bạn nữ ngồi cạnh nhau  tạo thành một “người” đặc biệt, người đó cùng
với 5 bạn nam thì được tất cả 6 người  hoán đổi vị trí: 6!, nhưng trong “nội bộ”
người đặc biệt, thì lại có 5! cách xếp nên số cách: 6!5!.
Cách khác: bố trí GBBBBB, BGBBBB, ..., BBBBBG  6.(5!)^2. Bài 6.
Bài 6. SV chọn giải 1 trong 2 bài toán sau (nộp lại file ảnh):
1. Hỏi có bao nhiêu số tự nhiên có 10 chữ số không nhất thiết phân biệt từ các số
0,1,2,3,4,5,6,7 sao cho chữ số 1 có mặt đúng 1 lần, còn số 2 có mặt đúng 2 lần?
Đếm các số tùy ý sau đó trừ ra trường hợp số 0 ở đầu.
 Tùy ý: chọn vị trí cho số 1  10 cách; chọn vị trí cho 2 số 2  9C2 cách, còn 7
vị trí, mỗi vị trí chọn từ 0, 3, 4, 5, 6, 7  6^7 cách. Do đó: 10.9C2.6^7.
 Có số 0 ở đầu: chọn vị trí cho số 1  9 cách; chọn cho 2 số 2  8C2 cách, còn 6
vị trí, chọn ra từ 0, 3, 4, 5, 6, 7  6^6 cách. Do đó: 9.8C2.6^6.
Trừ ra được: 10.9C2.6^7 – 9.8C2.6^6.
2. Giảng viên cần ra một đề thi có 5 câu hỏi có đủ các mức độ: dễ - trung bình - khó. Biết
rằng ngân hàng đề của GV có 8 câu dễ, 10 câu trung bình và 4 câu khó. Tính số cách ra đề của GV.
Cách 1: chia các trường hợp: (dễ - trung bình – khó)
(1, 1, 3), (1, 2, 2), (1, 3, 1), (2, 1, 2), (2, 2, 1), (3, 1, 1).
Tính số cách chọn trong mỗi trường hợp và cộng lại.
Cách 2: tùy ý, có 22C5, trừ ra các trường hợp vi phạm: * Thiếu câu khó: 18C5.
* Thiếu câu trung bình: 12C5. * Thiếu câu dễ: 14C5.
* Thiếu cả dễ - khó: 10C5.
* Thiếu cả trung bình – khó: 8C5.
* Thiếu cả dễ - trung bình: 4C5 = 0. * Thiếu cả 3: 0 cách.
Số trường hợp vi phạm: 18C5 + 12C5 + 14C5 – (8C5 + 10C5).
Đáp số: 22C5 – [18C5 + 12C5 + 14C5 – (8C5 + 10C5)].
ấu trúc đề giữa kỳ (chiều 03/10): liên quan đến chương 1 & 2, các nội dung BT tương tự
bài thi thường kỳ lần 1, 2: + Vị từ, lượng từ.
+ Biến đổi, rút gọn biểu thức logic; bảng chân trị. + Quy tắc suy diễn. + Phép đếm.
Sửa đề giữa kỳ năm 2020.
Bài 1. a) x  y có thể viết thành: x’ v y.
Ta có: x  (y  z)  x  (y’ v z)  x’ v (y’ v z)  y’ v (x’ v z)
 y’ v (x  z)  y  (x  z).
0  1 hay 0  0 có giá trị chân trị là 1. x y z y  z (1) x  z (2) 0 0 0 1 1 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1
Kết luận: ta thấy trong 8 trường hợp thì giá trị chân trị của (1) và (2) đều giống nhau nên
hai biểu thức logic đó tương đương. b) (x  y) ^ (x  z)
 (x’ v y) ^ (x’ v z) : quy tắc kéo theo  x’ v (y ^ z) : quy tắc phân phối  x  (y ^ z). : quy tắc kéo theo.
Bài 2: P = (x  z’)  ((x  y) ^ z)’
= (x’ v z’)  ((x  y) ^ z)’
= (x’ v z’)’ v ((x’ v y) ^ z)’
= (x ^ z) v ((x’ v y)’ v z’)
= (x ^ z) v ((x ^ y’) v z’) = (x ^ z) v (x ^ y’) v z’ = (x ^ (z v y’)) v z’
= (x v z’) ^ ((z v y’) v z’) = (x v z’) ^ (1 v y’) = (x v z’) ^ 1 = x v z’.
Câu 3: phải dùng nguyên lý bù trừ và biến đổi khó. a) 12C5; b) 11C4; c) Tương tự trên: 10C3;
(hiểu câu d, e, f theo nghĩa: đã có sẵn đội tuyển 5 người rồi) d) 5!; e) 4! f) 4! 2!
SỬA BÀI THI GIỮA KỲ MÔN CẤU TRÚC RỜI RẠC 2021
Câu 1 đề 1. (1 điểm) Cho A là tập hợp các sinh viên của lớp Cấu trúc rời rạc, B là tập hợp
các bài kiểm tra thường kỳ và vị từ:
P(x, y)  “ x đạt điểm 10 ở y ”.
Sử dụng ký hiệu lượng từ ,  trên các tập hợp A, B , phát biểu lại mệnh đề sau: “Tồn tại một
bài kiểm tra thường kỳ mà mọi sinh viên của lớp Cấu trúc rời rạc đều không đạt điểm 10”.
y  B, x  A, P(x, y) .
//thứ tự ở đây phải đúng, không được viết ngược.
//chỉ được đảo thứ tự khi cả hai đều là tồn tại, hoặc cả hai đều là với mọi.
Câu 1 đề 2. (1 điểm) Cho A là tập hợp các sinh viên của lớp Cấu trúc rời rạc, B là tập hợp
các bài kiểm tra thường kỳ và vị từ: P(x, y)  “ x đạt điểm 10 ở y ”.
Sử dụng ký hiệu lượng từ ,  trên các tập hợp A, B , phát biểu lại mệnh đề sau: “Với mọi bài
kiểm tra thường kỳ thì tồn tại sinh viên của lớp Cấu trúc rời rạc đạt điểm 10”.
y  B, x  A, P(x, y) .
Câu 2. (1.5 điểm) Cho các biến logic p, q, r và mô hình suy diễn bên dưới. Hãy hoàn thành
chứng minh bằng cách điền vào chỗ trống trong các bước 2, 4, 6 (cả biểu thức lẫn diễn giải): r  q q r  p  p
 Bước 1: r  q (giả thiết)
 Bước 2: q  r (phản đảo của 1)  Bước 3: q (giả thiết)  Bước 4: r
(quy tắc khẳng định từ 2,3)
 Bước 5: r  p (giả thiết)  Bước 6: p
(quy tắc khẳng định từ 4,5)
Câu 2 đề 2. (1.5 điểm) Cho các biến logic p, q, r và mô hình suy diễn bên dưới. Hãy hoàn
thành chứng minh bằng cách điền vào chỗ trống trong các bước 2, 4, 6 (cả biểu thức lẫn diễn giải): r  p p r  q  q
 Bước 1: r  p (giả thiết)  Bước 2: . . . .  Bước 3: p (giả thiết)  Bước 4: . . . .
 Bước 5: r  q (giả thiết)  Bước 6: . . . .
Câu 3 đề 1. (3.5 điểm) Cho biểu thức logic sau đây
T  ( p  r)  ( p  q). (p’ v r)’ v (p ^ q) (p ^ r’) v (p ^ q) p ^ (r’ v q)
a) Hãy rút gọn T thành dạng chỉ chứa 1 dấu ngoặc.
b) Lập bảng chân trị cho T (sử dụng biểu thức gốc hay biểu thức đã rút gọn đều được) và
cho biết có bao nhiêu trường hợp p, q có cùng chân trị mà giá trị chân trị của T là 0?
Đến đây lập bảng chân trị có 8 dòng  sau đó nhìn trực tiếp vào bảng để đếm.
Câu 3 đề 2. (3.5 điểm) Cho biểu thức logic sau đây
T  ( p  r)  ( p  q).
a) Hãy rút gọn T thành dạng chỉ chứa 1 dấu ngoặc.
b) Lập bảng chân trị cho T (sử dụng biểu thức gốc hay biểu thức đã rút gọn đều được) và
cho biết có bao nhiêu trường hợp p, q cùng chân trị mà giá trị chân trị của T là 1?
Câu 4 đề 1. (4 điểm) An Khang là một tân sinh viên của IUH với mã số sinh viên là
21567890. Bạn ấy muốn đặt mật khẩu có độ dài đúng 7 ký tự cho trang web học tập lms
bằng cách sử dụng các chữ cái trong tên (viết in hoa) cũng như các số trong MSSV. Hãy giúp
An Khang tính xem có bao nhiêu cách đặt mật khẩu trong mỗi trường hợp sau:
a) Mật khẩu là hoán vị các chữ cái trong tên của bạn ấy? VD: KHAANNG  có 2 A và 2 N.
 hoán vị lặp: 7! /(2!2!)
b) Mật khẩu chỉ dùng các chữ số lẻ (không nhất thiết phân biệt) trong MSSV? VD: 7979797.
Do mỗi vị trí có 4 cách chọn  4^7.
c) Mật khẩu gồm 6 số phân biệt trong MSSV và một chữ bất kỳ trong tên? VD: 012A789.
 Bước 1: chọn nguyên liệu  8C6.5C1 (chọn 6 số và 1 chữ)
 Bước 2: sắp xếp  7! Từ đó có 8C6.5C1.7!
d) Mật khẩu dùng các ký tự phân biệt trong tên và MSSV của bạn ấy, đồng thời phải bắt đầu
bởi số, kết thúc bằng chữ? VD: 56789AN.
Chọn số cho vị trí đầu, có 8C1 cách.
Chọn chữ cho vị trí cuối, có 5C1 cách.
Còn lại (số)*****(chữ), ta có 8 chữ số phân biệt + 5 chữ cái phân biệt = 13, nhưng đã dùng 2
ký tự, còn lại 11 ký tự phân biệt. 8C1.5C1.(11.10.9.8.7)
Câu 4 đề 2. (4 điểm) Hạnh Phúc là một tân sinh viên của IUH với mã số sinh viên là
21045678. Bạn ấy muốn đặt mật khẩu có độ dài đúng 8 ký tự cho trang web học tập lms
bằng cách sử dụng các chữ cái trong tên (viết in hoa, không dấu) cũng như các số trong
MSSV. Hãy giúp Hạnh Phúc tính xem có bao nhiêu cách đặt mật khẩu trong mỗi trường hợp sau:
a) Mật khẩu là hoán vị các chữ cái trong tên của bạn ấy? VD: CHANHPHU. Hoán vị có lặp: 8! / 3!
b) Mật khẩu chỉ dùng các chữ số chẵn (không nhất thiết phân biệt) trong MSSV? VD: 68686868.
Mỗi vị trí có 5 cách chọn  5^8.
c) Mật khẩu gồm 7 số phân biệt trong MSSV và một chữ bất kỳ trong tên? VD: 0124A567.
 Bước 1: chọn nguyên liệu  8C7.6C1 (chọn 6 số và 1 chữ)
 Bước 2: sắp xếp  8! Đáp số: 8C7.6C1.8!.
d) Mật khẩu dùng các ký tự phân biệt trong tên và MSSV của bạn ấy, đồng thời phải bắt đầu
bởi số, kết thúc bằng chữ? VD: 012678AN.
8C1.6C1.(12.11.10.9.8.7) = 8C1 * 6C1 * 12A6.
Câu 4 đề 3. (4 điểm) Bạn A là một tân sinh viên của IUH với mã số sinh viên là X (trong đó
A là 6 ký tự cuối trong tên, VD: NGOCVU, NGUYEN; còn X là MSSV của chính SV dự thi). Bạn
ấy muốn đặt mật khẩu có độ dài đúng 6 ký tự cho trang web học tập lms bằng cách sử dụng
các chữ cái trong tên (viết in hoa) cũng như các số trong MSSV. Hãy giúp A tính xem có bao
nhiêu cách đặt mật khẩu trong mỗi trường hợp sau:
a) Mật khẩu là hoán vị các chữ cái trong tên của bạn ấy?
b) Mật khẩu chỉ dùng các chữ số lẻ (không nhất thiết phân biệt) trong MSSV?
c) Mật khẩu gồm 4 số phân biệt trong MSSV và 2 chữ phân biệt trong tên?
d) Mật khẩu dùng các ký tự phân biệt trong tên và MSSV, đồng thời có chữ và số xen kẽ? N,G,O,C,V,U,2,0,7,5,3,1 6A3 * 5A3 *2 = 14400
Cách khác: 6C3 * 5C3 * 3!3! * 2 CSCSCS hoặc SCSCSC