⚡ Câu 1 · 3–4 điểm
Logic — Nền tảng
của mọi suy luận
Phần chi phối điểm số cao nhất. Gồm 3 dạng: Biến đổi logic, Suy diễn, và Vị từ/Lượng từ. Mỗi dạng có template riêng để trình bày chuẩn tự luận.
11 Luật logic cơ bản
| # | Tên luật | Công thức |
|---|---|---|
| 1 | Phủ định kép | $\lnot\lnot p \Leftrightarrow p$ |
| 2 | De Morgan (∧) | $\lnot(p \land q) \Leftrightarrow \lnot p \lor \lnot q$ |
| 3 | De Morgan (∨) | $\lnot(p \lor q) \Leftrightarrow \lnot p \land \lnot q$ |
| 4 | Giao hoán | $p \land q \Leftrightarrow q \land p \quad;\quad p \lor q \Leftrightarrow q \lor p$ |
| 5 | Kết hợp | $(p \land q) \land r \Leftrightarrow p \land (q \land r)$ |
| 6 | Phân phối (∧ trên ∨) | $p \land (q \lor r) \Leftrightarrow (p \land q) \lor (p \land r)$ |
| 7 | Phân phối (∨ trên ∧) | $p \lor (q \land r) \Leftrightarrow (p \lor q) \land (p \lor r)$ |
| 8 | Lũy đẳng | $p \land p \Leftrightarrow p \quad;\quad p \lor p \Leftrightarrow p$ |
| 9 | Trung hòa | $p \land \mathbf{T} \Leftrightarrow p \quad;\quad p \lor \mathbf{F} \Leftrightarrow p$ |
| 10 | Thống trị | $p \land \mathbf{F} \Leftrightarrow \mathbf{F} \quad;\quad p \lor \mathbf{T} \Leftrightarrow \mathbf{T}$ |
| 11 | Kéo theo | $p \rightarrow q \Leftrightarrow \lnot p \lor q$ |
| 12 | Tương đương | $p \leftrightarrow q \Leftrightarrow (p \rightarrow q) \land (q \rightarrow p)$ |
| 13 | Phần tử bù | $p \land \lnot p \Leftrightarrow \mathbf{F} \quad;\quad p \lor \lnot p \Leftrightarrow \mathbf{T}$ |
| 14 | Hấp thụ | $p \land (p \lor q) \Leftrightarrow p \quad;\quad p \lor (p \land q) \Leftrightarrow p$ |
📋 Template trình bày chuẩn
Trình bày từng bước mỗi dòng một phép biến đổi, ghi tên luật ở ngoặc phải:
[Biểu thức gốc]
⟺ [Bước 1] (Tên luật 1)
⟺ [Bước 2] (Tên luật 2)
...
⟺ T (hoặc F) (Tên luật n)
→ Vậy biểu thức là HẰNG ĐÚNG ✓
⚡ Trick xử lý nhanh
Thứ tự ưu tiên khử:
1️⃣ Khử $\leftrightarrow$ trước (dùng định nghĩa tương đương)
2️⃣ Khử $\rightarrow$ (dùng luật kéo theo: $p \rightarrow q \Leftrightarrow \lnot p \lor q$)
3️⃣ Đẩy $\lnot$ vào trong (De Morgan)
4️⃣ Phân phối & Rút gọn (hấp thụ, lũy đẳng, phần tử bù)
1️⃣ Khử $\leftrightarrow$ trước (dùng định nghĩa tương đương)
2️⃣ Khử $\rightarrow$ (dùng luật kéo theo: $p \rightarrow q \Leftrightarrow \lnot p \lor q$)
3️⃣ Đẩy $\lnot$ vào trong (De Morgan)
4️⃣ Phân phối & Rút gọn (hấp thụ, lũy đẳng, phần tử bù)
✏️ Ví dụ mẫu: Chứng minh hằng đúng
Đề bài
Chứng minh biểu thức $[(p \rightarrow q) \land (q \rightarrow r)] \rightarrow (p \rightarrow r)$ là hằng đúng.
Bài giải chuẩn tự luận
$[(p \rightarrow q) \land (q \rightarrow r)] \rightarrow (p \rightarrow r)$
Biểu thức gốc
$\Leftrightarrow [(\lnot p \lor q) \land (\lnot q \lor r)] \rightarrow (\lnot p \lor r)$
Luật kéo theo ×2
$\Leftrightarrow \lnot[(\lnot p \lor q) \land (\lnot q \lor r)] \lor (\lnot p \lor r)$
Luật kéo theo
$\Leftrightarrow [(p \land \lnot q) \lor (q \land \lnot r)] \lor (\lnot p \lor r)$
De Morgan, Phủ định kép
$\Leftrightarrow (p \land \lnot q \lor \lnot p) \lor (q \land \lnot r \lor r)$
Giao hoán, Kết hợp
$\Leftrightarrow (\lnot q \lor \lnot p \lor p) \lor (q \lor \lnot r \lor r)$
Phân phối, Giao hoán
$\Leftrightarrow (\lnot q \lor \mathbf{T}) \lor (q \lor \mathbf{T})$
Phần tử bù
$\Leftrightarrow \mathbf{T} \lor \mathbf{T} \Leftrightarrow \mathbf{T}$
Thống trị ✓
→ Vậy biểu thức là HẰNG ĐÚNG ✓
📝 Dạng bài thường gặp
Biến đổi tương đương
Biến đổi từ B.T.gốc → dạng khác
Chứng minh A ⟺ B bằng cách biến đổi từ A ra B (hoặc cả hai về dạng trung gian)
Chứng minh Hằng đúng
Biến đổi → T
Chứng tỏ biểu thức luôn đúng bằng cách biến đổi về $\mathbf{T}$ hoặc dùng bảng chân trị
6 Quy tắc suy diễn cốt lõi
Khẳng định (Modus Ponens — MP)
MP
$$\frac{p \quad p \rightarrow q}{q}$$
Biết p đúng và p→q, suy ra q đúng.
Phủ định (Modus Tollens — MT)
MT
$$\frac{\lnot q \quad p \rightarrow q}{\lnot p}$$
Biết q sai và p→q, suy ra p sai.
Tam đoạn luận (Hypothetical)
HS
$$\frac{p \rightarrow q \quad q \rightarrow r}{p \rightarrow r}$$
Nối chuỗi kéo theo.
Tam đoạn luận rời (Disjunctive)
DS
$$\frac{p \lor q \quad \lnot p}{q}$$
Loại trừ phương án sai trong phép ∨.
Thêm vào (Addition)
Add
$$\frac{p}{p \lor q}$$
Từ p đúng ta có p∨q đúng (với bất kỳ q).
Đơn giản hóa (Simplification)
Simp
$$\frac{p \land q}{p}$$
Từ p∧q đúng ta lấy ra p (hoặc q).
📋 Template trình bày suy diễn
Gọi các mệnh đề:
p = "..."
q = "..."
...
Tiền đề:
(1) [Tiền đề 1]
(2) [Tiền đề 2]
...
Suy luận:
(n+1) [Mệnh đề mới] — Từ (i)(j), Quy tắc [tên]
(n+2) [Mệnh đề mới] — Từ (k)(n+1), Quy tắc [tên]
...
Kết luận: [Điều cần chứng minh] □
🔄 Phương pháp Phản chứng
Khi nào dùng phản chứng?
Khi suy diễn trực tiếp quá phức tạp
1
Giả sử kết luận SAI: Thêm tiền đề $\lnot (\text{Kết luận})$ vào hệ tiền đề.
2
Suy diễn: Dùng các quy tắc để tìm mâu thuẫn $p \land \lnot p$.
3
Kết luận: Mâu thuẫn xảy ra, vậy giả sử sai, kết luận phải ĐÚNG. □
✏️ Ví dụ mẫu: Suy diễn
Đề bài
Cho các tiền đề: (1) $p \rightarrow q$, (2) $q \rightarrow r$, (3) $p$.
Chứng minh: $r$.
Chứng minh: $r$.
Bài giải suy diễn
(1) $p \rightarrow q$Tiền đề
(2) $q \rightarrow r$Tiền đề
(3) $p$Tiền đề
(4) $p \rightarrow r$Từ (1)(2), Tam đoạn luận (HS)
(5) $r$ ✓Từ (3)(4), Modus Ponens (MP)
→ Kết luận: $r$ đúng □
⚡ Trick làm bài suy diễn
Chiến lược truy ngược: Đọc kết luận cần CM, nhìn lại tiền đề xem quy tắc nào sinh ra kết luận đó → làm ngược từ sau lên.
Hay gặp: Kết luận dạng $p \rightarrow r$ → thường dùng HS. Kết luận là mệnh đề đơn → MP hoặc DS.
Hay gặp: Kết luận dạng $p \rightarrow r$ → thường dùng HS. Kết luận là mệnh đề đơn → MP hoặc DS.
Khái niệm cơ bản
Vị từ $P(x)$
Hàm mệnh đề — cho giá trị đúng/sai phụ thuộc vào $x$. VD: $P(x) =$ "$x$ là số chẵn"
Lượng từ phổ quát $\forall$
$\forall x\, P(x)$: "Mọi $x$ đều thỏa $P(x)$" — ĐÚng khi P(x) đúng với mọi x trong miền.
Lượng từ tồn tại $\exists$
$\exists x\, P(x)$: "Tồn tại $x$ thỏa $P(x)$" — ĐÚng khi có ít nhất một x làm P(x) đúng.
Phủ định lượng từ
$\lnot\forall x\, P(x) \Leftrightarrow \exists x\, \lnot P(x)$ | $\lnot\exists x\, P(x) \Leftrightarrow \forall x\, \lnot P(x)$
Quy tắc phủ định lượng từ
Quy tắc vàng
Phủ định $\Rightarrow$ đổi $\forall \leftrightarrow \exists$ và phủ định vị từ
$\lnot\forall x\,\exists y\, P(x,y) \Leftrightarrow \exists x\,\forall y\, \lnot P(x,y)$
⚡ Trick phủ định lượng từ lồng nhau
Đẩy $\lnot$ từ ngoài vào trong, mỗi lần qua một lượng từ thì đổi chiều ($\forall \leftrightarrow \exists$), đến khi tới vị từ thì phủ định vị từ.
✏️ Ví dụ mẫu: Xác định chân trị
Đề bài
Cho miền $D = \{1,2,3,4\}$. Xác định chân trị và viết phủ định của: $\forall x\,\exists y\,(x + y = 5)$.
Bài giải vị từ & lượng từ
Miền $D = \{1,2,3,4\}$. Xét $\forall x\,\exists y\,(x+y=5)$Đề bài
- $x=1$: cần $y=4 \in D$ ✓Kiểm tra trực tiếp
- $x=2$: cần $y=3 \in D$ ✓Kiểm tra trực tiếp
- $x=3$: cần $y=2 \in D$ ✓Kiểm tra trực tiếp
- $x=4$: cần $y=1 \in D$ ✓Kiểm tra trực tiếp
→ Mệnh đề ĐÚNG ✓Mọi x đều thỏa
Phủ định:—
$\lnot[\forall x\,\exists y\,(x+y=5)]$Phủ định toàn bộ
$\Leftrightarrow \exists x\,\forall y\,(x+y \neq 5)$Đổi ∀↔∃, phủ định =→≠
Bẫy thường gặp
Phủ định $\forall x\,P(x)$ không phải là $\forall x\,\lnot P(x)$! Phải đổi thành $\exists x\,\lnot P(x)$.