Bài giảng Logic mệnh đề

Chia sẻ: Bùi Ngọc Thành | Ngày: | Loại File: PDF | Số trang:49

Thêm vào BST

Báo xấu

202
lượt xem 28
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu giảng dạy về toán đã được giảng dạy với mục đích cung cấp cho học sinh những kiến thức cơ bản nhất, có tính hệ thống liên quan tới toán học. Thông qua tài liệu này giúp các bạn hệ thống lại kiến thức. Chúc các bạn thành công.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Logic mệnh đề

CHƯƠNG 1. CÁC KIẾN THỨC CƠ SỞ 1.1. Các khái niệm cơ bản 1.2. Lý thuyết tổ hợp 1.3. Hai nguyên lý cơ bản 1.4. Lý thuyết số và các hệ đếm 1.5. Bài tập
1.1. CÁC KHÁI NIỆM CƠ BẢN Logic mệnh đề. 1. Logic vị từ. 2. Các phương pháp chứng minh. 3. Tập hợp và hàm. 4. Ma trận và giải thuật. 5.
LOGIC MỆNH ĐỀ Mệnh đề, mệnh đề có điều kiện và sự tương đương logic. a) Dạng chuẩn tắc hội và chuẩn tắc tuyển của công thức. b) Các phương pháp kiểm tra tính hằng đúng, hằng sai của công thức. c)
MỆNH ĐỀ (1/3) Mệnh đề là câu có giá trị hoặc đúng hoặc sai; nhưng không thể vừa đúng vừa sai hoặc không thể khẳng định tính đúng, sai của nó. Ví dụ 1: "6 là một số chẵn”  “Hà Nội là thủ đô của Việt Nam”  “3+2 = 6”  Ví dụ 2: Những câu không là mệnh đề “x là một số chẵn”  “Kinh tế Mỹ khi nào phục hồi”  “Trật tự” 
MỆNH ĐỀ (2/3) Mệnh đề không chứa các liên từ "và", "hoặc", "không", "nếu... thì..." được gọi là mệnh đề nguyên thủy hay mệnh đề sơ cấp. Mệnh đề không phải là mệnh đề sơ cấp được gọi là mệnh đề phức hợp. Ví dụ 3: "6 là một số chẵn” 1) “Tôi là tổng thống Mỹ” 2) “Nếu trời nắng thì tôi đi chơi” 3) “Hà Nội là thủ đô của Việt Nam và Thành phố HCM là trung tâm 4) kinh tế lớn nhất Việt Nam” “Người đi xe máy không vượt đèn đỏ nếu anh ta thấy công an trừ 5) khi anh ta quá liều” 1), 2) là mệnh đề sơ cấp. 3), 4), 5), 6) là các mệnh đề phức hợp
MỆNH ĐỀ (3/3) Các mệnh đề sơ cấp được ký hiệu là X, Y, Z...; có thể chứa chỉ số, được gọi là biến mệnh đề. Trong logic mệnh đề, giá trị chân lý đúng ký hiệu là 1, giá trị chân lý sai ký hiệu là 0. Bảng chân lý biểu diễn mối quan hệ giữa những giá trị chân lý của các biến mệnh đề
CÁC PHÉP TOÁN TRÊN MỆNH ĐỀ Phép phủ định 1. Phép hoặc (tuyển, cộng logic) 2. Phép và (hội, nhân logic) 3. Phép xor (tuyển loại) 4. Phép kéo theo 5. Phép tương đương 6.
1. PHÉP PHỦ ĐỊNH Phủ định của một mệnh đề là một mệnh đề nhận giá trị đúng nếu X sai, và sai nếu X đúng. Ký hiệu X hoặc ¬X. X X 0 1 1 0 Ví dụ 4: X = “Hôm nay là chủ nhật” Phủ định X = “Hôm nay không là chủ nhật”
2. PHÉP HOẶC (TUYỂN, CỘNG LOGIC) Cho X và Y là hai mệnh đề, khi đó “X hoặc Y” là một mệnh đề chỉ nhận giá trị sai khi cả X và Y đều sai. Ký hiệu XY XY X Y 0 0 0 1 0 1 0 1 1 1 1 1 Ví dụ 5: X = “n là một số chẵn“ ; Y = “n là một số chia hết cho 3" X  Y = “7 là một số chẵn hoặc chia hết cho 3”
3. PHÉP VÀ (HỘI, NHÂN LOGIC) Cho X và Y là hai mệnh đề, khi đó “X và Y” là một mệnh đề chỉ nhận giá trị đúng nếu cả X và Y đều đúng. Kí hiệu X  Y XY X Y 0 0 0 1 0 0 0 1 0 1 1 1 Ví dụ 6: X = “n là một số chẵn“ ; Y = “n là một số chia hết cho 3" X  Y = “n là một số chẵn và chia hết cho 3”
4. PHÉP XOR (TUYỂN LOẠI) Cho X và Y là hai mệnh đề, “X XOR Y” là một mệnh đề chỉ nhận giá trị đúng nếu chỉ một trong hai mệnh đề đã cho đúng. Kí hiệu XY XY X Y 0 0 0 1 0 1 0 1 1 1 1 0 Ví dụ 7: X=“ n là một số chẵn”, Y=“m là một số lẻ” Trong trường hợp này ta có thể định nghĩa XY = “n+m là một số chẵn”.
5. PHÉP KÉO THEO: Cho X và Y là hai mệnh đề, “X kéo theo Y” ( “nếu X thì Y” ) là một mệnh đề chỉ nhận giá trị sai nếu X đúng, Y sai. Kí hiệu X  Y. XY X Y 0 0 1 1 0 0 0 1 1 1 1 1 Ví dụ 8: X=“n là một số chẵn”, Y=“n là một số chia hết cho 2”, X  Y = “n là một số chẵn ” suy ra “n chia hết cho 2”.
6. PHÉP TƯƠNG ĐƯƠNG Cho X và Y là hai mệnh đề, “X tương đương Y” là một mệnh đề nhận giá trị đúng nếu cả hai mệnh đề đã cho cùng đúng, hoặc cùng sai. Kí hiệu X  Y. XY X Y 0 0 1 1 0 0 0 1 0 1 1 1 Ví dụ 9: X=“n là một số chẵn”, Y=“n là một số chia hết cho 2”, X  Y = ” n là một số chẵn” khi và chỉ khi ” n là một số chia hết cho 2”
CÔNG THỨC LOGIC TRONG MỆNH ĐỀ Mỗi biến mệnh đề X, Y, Z… (có thể có chỉ số) là một công thức. A, B là hai công thức, khi đó dãy ký hiệu (A  B)  (A  B)  (A  B)  (A)  cũng là một công thức. Ví dụ 10: X, Y, X  Y, X  (X  Y) là một công thức.
CÔNG THỨC ĐỒNG NHẤT ĐÚNG Công thức A được gọi là công thức đồng nhất đúng khi và chỉ khi A luôn luôn nhận giá trị đúng với mọi bộ giá trị đúng, sai của các biến mệnh đề có mặt trong A. Ký hiệu A≡1 Công thức A≡1 còn được gọi là hằng đúng. Ví dụ 11: X  Y → Y ≡ 1 XY→Y X Y X Y 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1
CÔNG THỨC ĐỒNG NHẤT SAI Công thức A được gọi là công thức đồng nhất sai khi và chỉ khi A luôn luôn nhận giá trị sai với mọi bộ giá trị đúng, sai của các biến mệnh đề có mặt trong A. Ký hiệu A≡0 Nếu A là hằng đúng thì ¬A là công thức đồng nhất sai Ví dụ 12: X  ¬X ≡ 0 X  ¬X ¬X X 1 0 0 0 1 0
CÔNG THỨC THỰC HIỆN ĐƯỢC Công thức A được gọi là công thức thực hiện được khi và chỉ khi có tồn tại một bộ giá trị đúng, sai của các biến mệnh có mặt trong A để A nhận giá trị đúng. Ví dụ 13: Các công thức tuyển, hội của hai mệnh đề; công thức hằng đúng  là các công thức thực hiện được. Công thức hằng sai là công thức không thực hiện được. 
CÔNG THỨC ĐỒNG NHẤT BẰNG NHAU Hai công thức A và B được gọi là công thức đồng nhất bằng nhau khi và chỉ khi A và B cùng nhận giá trị đúng, sai như nhau đối với mọi bộ giá trị đúng, sai của các biến mệnh đề có mặt trong A và B. Ta nói, A và B là tương đương. Ký hiệu A≡B hoặc A  B Ví dụ 14: p và ¬ (¬p) là hai công thức tương đương 
MỘT SỐ LUẬT ĐỒNG NHẤT ĐÚNG 1. A  (B  A)  1. Đây là hệ 2. (A  (B  C))  ((A  B)  (A  C))  1. tiên đề 3. (A  B)  A  1. được sử 4. (A  B)  B  1. 5. (A  B)  ((A  C)  (A  (B  C)))  1. dụng để 6. A  (A  B)  1. nghiên 7. B  (A  B)  1. cứu các 8. (A  C)  ((B  C)  ((A  B)  C))  1. tính chất   9. (A  B)  B  A  1. tổng quát 10. A  A  1. của logic 11. A  A  1. mệnh đề.
LUẬT ĐỐI NGẪU Giả sử A là một công thức chỉ chứa các phép toán ,  , ¬ mà không chứa phép →. Trong A đổi chỗ  và  cho nhau ta được công thức mới A*. A* gọi là công thức đối ngẫu của A. Định lý 1: Luật đối ngẫu của công thức: Giả sử A(X1, X2,…, Xn) là công thức không có phép →. Khi đó ta có:   A*  X 1 , X 2 ,..., X n   A X 1 , X 2 ,..., X n Ví dụ 15: A(X,Y) = XY; A*(X,Y) = XY → XY ≡ ¬(¬X¬Y)