Bài tập toán rời rạc chương cơ sở logic

Nội dung Text: Giáo trình Toán rời rạc - Chương 1 Cơ sở Logic

1. LOGO Lê Văn Luyện email: lvluyen@yahoo.com TOÁN RỜI RẠC www.math.hcmus.edu.vn/~lvluyen/trr
2. Cơ sở Logic Nội dung: gồm 5 phần - Cơ sở logic - Phép đếm - Quan hệ - Hàm Bool - Đồ thị
3. Cơ sở Logic Chương I: Cơ sở logic Mệnh đề - Dạng mệnh đề - Qui tắc suy diễn - Vị từ, lượng từ - Tập hợp - Ánh xạ - Qui nạp toán học -
4. I. Mệnh đề 1. Định nghĩa: Mệnh đề là một khẳng định có giá trị chân lý xác định, đúng hoặc sai. Câu hỏi, câu cảm thán, mệnh lệnh… không là mệnh đề. Ví dụ: - mặt trời quay quanh trái đất - 1+1 =2 - Hôm nay trời đẹp quá ! [ko là mệnh đề] - Học bài đi ! [ko là mệnh đề] - 3 là số chẵn phải không? [ko là mệnh đề] 4
5. I. Mệnh đề Ký hiệu: người ta dùng các ký hiệu P, Q, R… để chỉ mệnh đề. Chân trị của mệnh đề: Một mệnh đề chỉ có thể đúng hoặc sai, không thể đồng thời vừa đúng vừa sai. Khi mệnh đề P đúng ta nói P có chân trị đúng, ngược lại ta nói P có chân trị sai. Chân trị đúng và chân trị sai sẽ được ký hiệu lần lượt là 1[hay Đ,T] và 0[hay S,F] 5
6. I. Mệnh đề Kiểm tra các khẳng định sau có phải là mệnh đề không? - Paris là thành phố của Mỹ. - n là số tự nhiên. - con nhà ai mà xinh thế! - 3 là số nguyên tố. - Toán rời rạc là môn bắt buộc của ngành Tin học. - Bạn có khỏe không? x 2  1 luôn dương. - 6
7. I. Mệnh đề 2. Phân loại: gồm 2 loại a. Mệnh đề phức hợp: là mệnh đề được xây dựng từ các mệnh đề khác nhờ liên kết bằng các liên từ [và, hay, khi và chỉ khi,…] hoặc trạng từ “không”. b. Mệnh đề sơ cấp [nguyên thủy]: Là mệnh đề không thể xây dựng từ các mệnh đề khác thông qua liên từ hoặc trạng từ “không”. Ví dụ: - 2 không là số nguyên tố - 2 là số nguyên tố [sơ cấp] - Nếu 3>4 thì trời mưa - An đang xem phim hay An đang học bài - Hôm nay trời đẹp và 1 +1 =3 7
8. I. Mệnh đề 3. Các phép toán: có 5 phép toán a. Phép phủ định: phủ định của mệnh đề P được ký hiệu là P hay P [đọc là “không” P hay “phủ định của” P]. P P Bảng chân trị : 10 Ví dụ : 01 - 2 là số nguyên tố Phủ định: 2 không là số nguyên tố - 1 >2 Phủ định : 1≤ 2 8
9. I. Mệnh đề b. Phép nối liền [hội, giao]: của hai mệnh đề P, Q được kí hiệu bởi P  Q [đọc là “P và Q”], là mệnh đề được định bởi : P  Q đúng khi và chỉ khi P và Q đồng thời đúng. PQ P Q Bảng chân trị 0 0 0 0 1 0 1 0 0 Ví dụ: 1 1 1 - 3>4 và Trần Hưng Đạo là vị tướng [S] - 2 là số nguyên tố và là số chẵn [Đ] - An đang hát và uống nước [S] 9
10. I. Mệnh đề c. Phép nối rời [tuyển, hợp]: của hai mệnh đề P, Q được kí hiệu bởi P  Q [đọc là “P hay Q”], là mệnh đề được định bởi : P  Q sai khi và chỉ khi P và Q đồng thời sai. PQ P Q Bảng chân trị 0 0 0 0 1 1 1 0 1 1 1 1 Ví dụ: - p >4 hay p >5 [S] - 2 là số nguyên tố hay là số chẵn [Đ] 10
11. I. Mệnh đề Ví dụ - “Hôm nay, An giúp mẹ lau nhà và rửa chén” - “Hôm nay, cô ấy đẹp và thông minh ” - “Ba đang đọc báo hay xem phim” 11
12. I. Mệnh đề d. Phép kéo theo: Mệnh đề P kéo theo Q của hai mệnh đề P và Q, kí hiệu bởi P  Q [đọc là “P kéo theo Q” hay “Nếu P thì Q” hay “P là điều kiện đủ của Q” hay “Q là điều kiện cần của P”] là mệnh đề được định bởi: P  Q sai khi và chỉ khi P đúng mà Q sai. Q PQ P Bảng chân trị 0 01 0 11 1 00 1 11 12
13. I. Mệnh đề Ví dụ: - Nếu 1 = 2 thì Lenin là người Việt Nam [Đ] - Nếu trái đất quay quanh mặt trời thì 1 +3 =5 [S] - p >4 kéo theo 5>6 [Đ] - p < 4 thì trời mưa - Nếu 2+1=0 thì tôi là chủ tịch nước [Đ] 13
14. I. Mệnh đề e. Phép kéo theo hai chiều: Mệnh đề P kéo theo Q và ngược lại của hai mệnh đề P và Q, ký hiệu bởi P  Q [đọc là “P nếu và chỉ nếu Q” hay “P khi và chỉ khi Q” hay “P là điều kiện cần và đủ của Q”], là mệnh đề xác định bởi: P  Q đúng khi và chỉ khi P và Q có cùng chân trị Q P Q P Bảng chân trị 0 0 1 0 1 0 1 0 0 1 1 1 14
15. I. Mệnh đề Ví dụ: - 2=4 khi và chỉ khi 2+1=0 [Đ] - 6 chia hết cho 3 khi và chi khi 6 chia hết cho 2 [Đ] - London là thành phố nước Anh nếu và chỉ nếu thành phố HCM là thủ đô của VN [S] - p >4 là điều kiện cần và đủ của 5 >6 [Đ] 15
16. II. Dạng mệnh đề 1. Định nghĩa: là một biểu thức được cấu tạo từ: - Các mệnh đề [các hằng mệnh đề] - Các biến mệnh đề p, q, r, …, tức là các biến lấy giá trị là các mệnh đề nào đó - Các phép toán , , , ,  và dấu đóng mở ngoặc []. Ví dụ: E[p,q] = [p q] F[p,q,r] = [p  q]  [q r] 16
17. II. Dạng mệnh đề Bảng chân trị của dạng mệnh đề E[p,q,r]: là bảng ghi tất cả các trường hợp chân trị có thể xảy ra đối với dạng mệnh đề E theo chân trị của các biến mệnh đề p, q, r. Nếu có n biến, bảng này sẽ có 2n dòng, chưa kể dòng tiêu đề. Ví dụ: E[p,q,r] =[p q] r . Ta có bảng chân trị sau 17
18. II. Dạng mệnh đề Mệnh đề E[p,q,r] =[p q] r theo 3 biến p,q,r có bảng chân trị sau pq [p q] r p q r 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 18
19. II. Dạng mệnh đề Bài tập: Lập bảng chân trị của những dạng mệnh đề sau E[p,q,r] = p [q r]  q F[p,q] = [p q] p 19
20. II. Dạng mệnh đề 2. Tương đương logic: Hai dạng mệnh đề E và F được gọi là tương đương logic nếu chúng có cùng bảng chân trị. Ký hiệu E  F [hay E ≡ F]. Ví dụ [p  q]  p   q Dạng mệnh đề được gọi là hằng đúng nếu nó luôn lấy giá trị 1 Dạng mệnh đề gọi là hằng sai [hay mâu thuẩn nếu nó luôn lấy giá trị 0. Định lý: Hai dạng mệnh đề E và F tương đương với nhau khi và chỉ khi EF là hằng đúng. 20