Bài tập Toán rời rạc - Bài 2

Toán rời rạc Bài tập 2 Bài 1 Ở một nước lạ luôn có hai loại người. Loại Dối luôn nói dối và loại Thật luôn nói thật. Một ngày, bạn đến nước lạ này và gặp hai người A và B. • A nói: B là loại Thật. • B nói: A và B không cùng loại. Hãy xác định loại của A và B. Bài 2 Bạn có 12 đồng xu, trong đó có một đồng là giả, và một quả cân. Các đồng xu thật có trọng lượng bằng nhau, nhưng đồng xu giả có trọng lượng nhỏ hơn các đồng còn lại. Hãy đưa ra chiến lược để xác định đồng xu giả mà chỉ dùng nhiều nhất 3 lần cân. (Chú ý: cân này có 2 đĩa, luôn nghiêng về bên nặng hơn). Bài 3 Hãy sử dụng các luật đại số (slide 21 và 22 trong bài giảng) để đưa công thức A⊕ B ⊕ C về cả hai dạng chuẩn tắc hội và chuẩn tắc tuyển. Bài 4 Một tập phép toán logic được gọi là đầy đủ nếu mỗi mệnh đề đều tương đương với một mệnh đề chỉ chứa các toán tử logic đó. Ví dụ: Ta đã biết trong bài giảng rằng tập {¬,→} là đầy đủ. Chứng minh rằng các tập {AND,NOT}, {OR,NOT}, {NAND} đều là đầy đủ. 1 Bài 5 Mục đích của bài tập này là kiểm tra xem những đặc tả sau đây có thỏa được không: 1. Nếu hệ thống file không bị khóa, thì (a) các thông điệp mới sẽ được đặt trong hàng đợi. (b) các thông điệp mới sẽ được gửi tới bộ đệm thông điệp. (c) hệ thống đang hoạt động bình thường, và ngược lại, nếu hệ thông đang hoạt động bình thường, thì hệ thống không bị khóa. 2. Nếu thông điệp mới không được đặt trong hàng đợi, thì chúng sẽ được gửi tới bộ đệm thông điệp. 3. Các thông điệp mới sẽ không được gửi tới bộ đệm thông điệp. (a) Dịch năm đặc tả trên thành công thức mệnh đề dùng bốn biến mệnh đề sau đây: L := hệ thống file bị khóa, Q := các thông điệp mới được đặt trong hàng đợi, B := các thông điệp mới được gửi tới bộ đệm thông điệp, N := hệ thống hoạt động bình thường. (b) Chứng minh rằng tập đặc tả là thỏa được bằng cách mô tả một cách gán giá trị chân lý cho các biến L,Q,B,N , và kiểm tra rằng với cách gán này mọi đặc tả đều đúng. (c) Chứng tỏ rằng cách gán xác định trong phần (b) là duy nhất. Bài 6 Hãy đưa ra chứng minh hình thức của các định lý sau: Với mọi công thức mệnh đề A,B,C bất kỳ, ta có: 1. ` A→ A, 2. ` (¬A→ A)→ A, 3. A→ B, B→ C ` A→ C . 4. A→ (B→ C) ` B→ (A→ C), 5. ` (¬B→¬A)→ (A→ B), 6. ` ¬ ¬A→ A, 7. ` A→¬ ¬A. 2