Logic mệnh đề & chứng minh: bài tập có lời giải từng bước

1Mệnh đề và các liên kết

Một mệnh đề là một phát biểu hoặc đúng hoặc sai, chẳng hạn “7 là số nguyên tố”. Ta viết nó bằng một chữ cái, p hoặc q, và giá trị chân trị của nó là 1 (đúng) hoặc 0 (sai).

Các liên kết xây dựng công thức lớn hơn từ các công thức nhỏ hơn:

• ¬p (không p) đảo giá trị.
• p ∧ q (và) bằng 1 chỉ khi cả hai đều bằng 1.
• p ∨ q (hoặc) bằng 0 chỉ khi cả hai đều bằng 0. Đây là “hoặc” bao hàm: cả hai có thể cùng đúng.
• p → q (nếu p thì q) bằng 0 chỉ khi p = 1 và q = 0.
• p ↔ q (khi và chỉ khi) bằng 1 khi p và q có cùng giá trị.

Phép kéo theo làm nhiều học sinh bất ngờ: khi p sai, p → q đúng bất kể q là gì. Lời hứa “nếu trời mưa, tôi mang ô” chỉ bị phá vỡ vào ngày mưa mà không mang ô.

2Bảng chân trị

Một bảng chân trị liệt kê mọi tổ hợp giá trị chân trị của các biến. Với n biến khác nhau có 2ⁿ hàng: 4 cho hai biến, 8 cho ba biến, 16 cho bốn biến. Một biến xuất hiện hai lần vẫn chỉ tính một.

Hãy làm từ trong ra ngoài. Cho mỗi công thức con một cột riêng, để mỗi cột mới chỉ cần áp dụng một liên kết lên các cột bạn đã có.

1. Liệt kê các biến và viết tất cả 2ⁿ tổ hợp, bắt đầu bằng toàn số 1.
2. Thêm một cột cho mỗi công thức con, từ trong cùng ra.
3. Điền mỗi cột theo quy tắc của liên kết chính của nó.
4. Đọc đáp án từ cột cuối: đếm các số 1, hoặc tìm hàng được hỏi.

3Một ví dụ có lời giải

Theo dõi từng bước. Hãy thử đoán bước tiếp theo trước khi mở nó.

4Tương đương và các phương pháp chứng minh

Hai công thức tương đương (≡) khi các cột bảng chân trị của chúng giống hệt nhau. Một hằng đúng bằng 1 ở mọi hàng, một mâu thuẫn bằng 0 ở mọi hàng, còn một công thức ngẫu nhiên không thuộc loại nào.

Các luật bạn dùng nhiều nhất:

Các luật này là cơ sở của các phương pháp chứng minh. Chứng minh bằng phản đảo của p → q là chứng minh ¬q → ¬p, vốn tương đương. Chứng minh bằng phản chứng giả sử p ∧ ¬q, cách duy nhất để phép kéo theo sai, rồi suy ra điều không thể xảy ra.

Lưu ý: mệnh đề đảo q → p và mệnh đề nghịch ¬p → ¬q không tương đương với p → q.

5Lượng từ và các suy luận hợp lệ

Với các biến chạy trên một miền, ∀x P(x) nói rằng “P đúng với mọi x” và ∃x P(x) nói rằng “P đúng với ít nhất một x”. Phép phủ định đổi lượng từ:

Đưa phép phủ định vào trong từng bước một; bên trong, dùng các luật của logic mệnh đề. Ví dụ ¬∀x (P(x) → Q(x)) ≡ ∃x (P(x) ∧ ¬Q(x)): “không phải mọi P đều là Q” nghĩa là “có một P không là Q”.

Một suy luận hợp lệ khi kết luận bằng 1 ở mọi hàng mà tất cả tiền đề đều bằng 1. Các dạng hợp lệ kinh điển là modus ponens (p → q, p, vậy q), modus tollens (p → q, ¬q, vậy ¬p) và tam đoạn luận giả định (p → q, q → r, vậy p → r).

Một hàng mà mọi tiền đề bằng 1 và kết luận bằng 0 là một phản ví dụ. Khẳng định hệ quả (p → q, q, vậy p) là không hợp lệ: hàng p = 0, q = 1 là một phản ví dụ.

6Lỗi thường gặp

• Coi p → q là sai khi p sai. Nó chỉ sai khi p = 1 và q = 0.
• Đếm một biến lặp lại hai lần khi tìm số hàng.
• Nhầm mệnh đề phản đảo ¬q → ¬p với mệnh đề đảo q → p hoặc mệnh đề nghịch ¬p → ¬q.
• Phủ định ∀x P(x) thành ∀x ¬P(x): lượng từ phải đổi thành ∃.
• Viết ¬(p ∧ q) thành ¬p ∧ ¬q: De Morgan còn đổi cả liên kết.

7Các câu hỏi thi trông như thế nào

• Dễ: bảng chân trị. Bạn tìm số hàng, đếm số hàng mà một công thức đúng, hoặc nhấp vào hàng duy nhất làm công thức đúng hoặc sai.
• Trung bình: tương đương và các phương pháp chứng minh. Bạn xác định một công thức là hằng đúng, mâu thuẫn hay công thức ngẫu nhiên, chọn công thức tương đương, hoặc phát biểu cần chứng minh trong chứng minh bằng phản đảo hay phản chứng.
• Khó: lượng từ và suy luận. Bạn phủ định các mệnh đề có lượng từ, chọn kết luận suy ra từ các tiền đề, nhấp vào hàng phản ví dụ của một suy luận không hợp lệ, hoặc đếm số hàng đúng trong bảng bốn biến.