Title GIAI DE_CTRR_DE THI GIUA KY_NH2223_HK1.pdf ✅

phoang | Cấu trúc rời rạc page 1 GIẢI ĐỀ CẤU TRÚC RỜI RẠC – GIỮA KỲ 1- 2022 - 2023 Câu 1: (3.0 điểm) a) Hãy dùng các luật logic để chứng minh biểu thức sau là hằng đúng [(p → q) ∧ (p ∧ r̅)] → (q̅ → s) ⇔ (p̅∨ q) ∧ (p ∧ r̅) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ ∨ (q ∨ s) (kéo theo) ⇔ [(p ∧ q̅) ∨ p̅] ∨ r ∨ q ∨ s (de Morgan, kết hợp) ⇔ [(p ∨ p̅) ∧ (q̅ ∨ p̅)] ∨ r ∨ q ∨ s (phân bố) ⇔ q̅ ∨ p̅∨ r ∨ q ∨ s (phần tử bù, trung hoà) ⇔ (q̅ ∨ q) ∨ p̅∨ r ∨ s (kết hợp, giao hoán) ⇔ 1 ∨ p̅∨ r ∨ s (phần tử bù) ⇔ 1 (thống trị) b) Kiểm tra tính đúng đắn của suy luận sau: p → q r → s t → p̅ (s ∧ q) → (p ∧ t) ____________________ ∴ p̅∨ r̅ Suy luận tương đương: p → q (1) r → s (2) t → p̅(3)

phoang | Cấu trúc rời rạc page 3 Câu 2: (1.0 điểm) Để đi đến 1 buổi tiệc, mỗi người phải mặc áo màu xanh hoặc màu trắng, quần đen hoặc vàng. Hỏi cần có ít nhất bao nhiêu người đến buổi tiệc đó để chắc chắn có ít nhất 10 người mặc áo màu giống nhau và quần cũng có màu giống nhau. Số cách phối trang phục khác nhau: 2 × 2 = 4. Gọi N là số người đến buổi tiệc để chắc chắn có ít nhất 10 người trùng trang phục. Ta có: ⌈ N 4 ⌉ = 10 ⇔ 9 < N 4 ≤ 10 ⇔ 36 < N ≤ 40 Vậy N = 37 thoả mãn yêu cầu bài toán. Câu 3: (2.0 điểm) Xếp 54 thanh RAM máy tính cùng loại vào 4 hộp I, II, III, IV. Biết tất cả các hộp ban đầu đều chưa có thanh RAM nào, hỏi có bao nhiêu cách xếp sao cho: Gọi xi (i = 1̅̅,̅4̅) là số thanh RAM xếp vào các hộp I, II, III và IV. x1 + x2 + x3 + x4 = 54 (∗), xi ∈ N, xi ≥ 0, i = 1̅̅,̅4̅ a. xi ≥ 10 (i = 1̅̅,̅4̅) (1) Đặt Xi = xi − 10 (i = 1̅̅,̅4̅) ⇒ (∗) + (1) ⇔ X1 + X2 + X3 + X4 = 14, Xi ∈ N, Xi ≥ 0, i = 1̅̅,̅4̅ Số cách chia thoả mãn là: K4 14 = C17 14 = 680. b. 0 ≤ x1 ≤ 11, 0 ≤ x2, 18 ≤ x3, 0 ≤ x4 (2) Xét các điều kiện sau: x1 ≥ 0, x2 ≥ 0, x3 ≥ 18, x4 ≥ 0 (3) x1 ≥ 12, x2 ≥ 0, x3 ≥ 18, x4 ≥ 0 (4)