Title GIAI DE_CTRR_DE THI GIUA KY_NH2122_HK2.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Ỳ 2 - 2021- 2022 Câu 1: (3.0 điểm) a) Hãy dùng các luật logic để chứng minh rằng: p → (q ∧ r) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ ⇔ p̅̅̅→̅̅̅̅r̅ ∨ (p ∧ q̅) VP ⇔ (p ∧ r̅) ∨ (p ∧ q̅) (kéo theo) ⇔ p ∧ (r̅∨ q̅) (phân bố) ⇔ p → (q ∧ r) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ ≡ VT (kéo theo) b) Hãy mô hình hoá suy luận dưới đây về dạng của mô hình suy diễn. Sau đó, hãy kiểm tra tính đúng đắn của mô hình đó. Vào ngày chủ nhật, An sẽ đi câu cá hoặc chơi đá banh. Nếu An đi câu cá thì về sẽ bị đau tay và nếu đi chơi đá banh thì về An sẽ bị đau chân. Biết rằng chủ nhật tuần rồi, An không bị đau chân. Suy ra An bị đau tay. p: An đi câu cá q: An chơi đá banh r: An bị đau tay s: An bị đau chân p ∨ q (1) p → r (2) q → s (3) s̅(4) _____________ ∴ r (5)
phoang | Cấu trúc rời rạc page 2 (4) ∧ (3) ⇒ q̅ (6) (phủ định) (6) ∧ (1) ⇒ p (7) (đơn giản nối liền) (7) ∧ (2) ⇒ r ≡ (5) (đơn giản nối liền) Vậy suy luận đúng. c) Hãy cho biết chân trị và viết dạng phủ đinh của mệnh đề sau: A = "∀x ∈ R, ∃y ∈ R, (x + y = 3) → (x − y ≥ 1)" A̅= ”∃x ∈ R, ∀y ∈ R, (x + y = 3) ∧ (x − y < 1)” ”∃x ∈ R, chọn y = 2 − x. Khi đó: (x + y = 3) ∧ (x − y < 1) ⇔ (2 = 3) ∧ (2x − 2 < 1) ≡ 0 ∧ (2x − 2 < 1) ≡ 0 Vậy A̅sai, A đúng. Câu 2: (1.0 điểm) Theo thống kê, có 400 sinh viên năm nhất của một trường đại học sinh vào tháng 4. Hỏi trong số đó, có ít nhất bao nhiêu sinh viên có cùng ngày sinh? Gọi N là số sinh viên năm nhất của trường sinh vào tháng 4. Gọi K là số ngày trong tháng 4 ⇒ K = 30 Có ít nhất: ⌈ N K ⌉ = ⌈ 400 30 ⌉ = 14 sinh viên có cùng ngày sinh trong tháng 4. Câu 3: (2.0 điểm) Xếp 45 cây bút bi giống nhau vào 4 hộp A, B, C, D. Tất cả các hộp ban đầu đều chưa cáo cây bút bi nào. Hỏi có bao nhiêu cách xếp sao cho: Gọi xi (i = 1̅̅,̅4̅) là số cây bút bi được xếp vào các hộp A, B, C, D thoả mãn: x1 + x2 + x3 + x4 = 45 (∗), xi ∈ N, xi ≥ 0, i = 1̅̅,̅4̅
phoang | Cấu trúc rời rạc page 3 a) xi ≥ 5 (i = 1̅̅,̅4̅) (1) Đặt Xi = xi − 5 (i = 1̅̅,̅4̅) ⇒ (∗) + (1) ⇔ X1 + X2 + X3 + X4 = 25, Xi ∈ N, Xi ≥ 0, i = 1̅̅,̅4̅ Số cách chia thoả mãn là: K4 25 = C28 25 = 3276. b) x1 ≥ 9, x2 ≥ 0, 7 ≥ x3 ≥ 0, x4 ≥ 0 (2) Xét các điều kiện sau: x1 ≥ 9, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 (3) x1 ≥ 9, x2 ≥ 0, x3 ≥ 8, x4 ≥ 0 (4) Gọi p, q, r lần lượt là số nghiệm nguyên không âm của (∗) ứng với điều kiện (2), (3), (4). ⇒ p = q − r Tương tự ý a), ta được q = K4 36 = C39 36 = 9139 Tương tự, r = K4 28 = C31 28 = 4495 ⇒ p = C39 36 − C31 28 = 4644. Câu 4: (2.0 điểm) Trên tập hợp X = {−2, −1, 0, 2, 3, 4, 5, 7, 9}, cho quan hệ tương đương R như sau: ∀x, y ∈ X, xRy ⇔ (x − y) ⋮ 3 a) Hãy chỉ ra các lớp tương đương và tập thương của X theo quan hệ R. - Lớp tương đương: [0]R = {0, 3, 9} [1]R = {−2, 4, 7} [2]R = {−1, 2 ,5}