LOGIC HÌNH THỨC
(Formal Logic)
• Logic mệnh đề • Logic vị từ

1

LOGIC MỆNH ĐỀ
(Propositional Logic)
• Khái niệm mệnh đề • Phép toán mệnh đề • Dạng mệnh đề • Các qui tắc suy diễn • Các phương pháp chứng minh

2

KHÁI NIỆM MỆNH ĐỀ
• Mệnh đề là một phát biểu đúng hoặc sai • Ví dụ:
Trái đất quay quanh mặt trời 1+4 = 5 10 là số nguyên tố

• Các mệnh đề thường được ký hiệu bởi P, Q, R,…,p, q… và chân trị của mệnh đề ký hiệu T (đúng) F (sai)
3

PHÉP TOÁN MỆNH ĐỀ
• Các phép toán mệnh đề còn gọi là phép nối logic (Logical connectives): ¬ (phủ định), ∧ (hội), ∨ (tuyển), → (kéo theo) • Tập các mệnh đề cùng với các phép toán logic tạo thành một đại số mệnh đề

4

PHÉP PHỦ ĐỊNH p T F ¬p F T

p =“4 là số nguyên tố” thì ¬ p =“4 không là số nguyên tố” có chân trị là T

5

PHÉP HỘI p F F T T q F T F T p ∧q F F F T

p =“12 là một số nguyên”, q =“12 chia hết cho 5” thì p ∧ q =“12 là một số nguyên chia hết cho 5”, có chân trị là F
6

PHÉP TUYỂN p F F T T q F T F T p∨q F T T T

p =“12 là một số nguyên”, q =“12 chia hết cho 5” thì p ∨ q =“12 là một số nguyên hoặc 12 chia hết cho 5”, có chân trị là T
7

PHÉP TUYỂN p F F T T q F T F T p→ q T T F T

p =“12 là một số nguyên”, q =“12 chia hết cho 5” thì p → q =“nếu 12 là một số nguyên thì chia hết cho 5”, có chân trị là F

8

LƯU Ý
• p ∨ q sai khi và chỉ khi p và q đều sai • p ∧ q đúng khi và chỉ khi p và q đều đúng • p → q sai khi và chỉ khi p đúng q sai • Còn có phép p ↔ q (kéo theo hai chiều) phép toán này đúng khi và chỉ khi cả p và q cùng đúng hoặc cùng sai

9

DẠNG MỆNH ĐỀ
• Dạng mệnh đề (Propositional form-PF), E(p, q, r,…), là một biểu thức logic chứa các hằng và các biến mệnh đề • Nếu P, Q là hai dạng mệnh đề thì ¬ P, P ∨ Q, P ∧ Q, P → Q, P ↔ Q cũng là các dạng mệnh đề • Thứ tự ưu tiên: ( ), ¬, ∧, ∨, →

10

DẠNG MỆNH ĐỀ
• Bảng chân trị của các dạng mệnh đề p → q và ¬ p ∨ q p F F T T q F T F T ¬p T T F F p →q T T F T ¬p ∨q T T F T

11

DẠNG MỆNH ĐỀ
• Hai dạng mệnh đề P và Q được gọi là tương đương logic, ký hiệu P ⇔ Q hoặc P ≡ Q, nếu chúng có cùng bảng chân trị • Một dạng mệnh đề được gọi là hằng đúng nếu nó luôn có chân trị bằng T • Một dạng mệnh đề được gọi là hằng sai hay mâu thuẫn nếu nó luôn có chân trị bằng F
12

DẠNG MỆNH ĐỀ
• Dạng mệnh đề Q được gọi là hệ quả logic của dạng mệnh đề P nếu P → Q là một hằng đúng, ký hiệu P ⇒ Q, khi đó cũng nói P có hệ quả logic là Q • Hai dạng mệnh đề P và Q tương đương logic khi và chỉ khi Q là hệ quả logic của P và P là hệ quả logic của Q

13

DẠNG MỆNH ĐỀ
• Trong dạng mệnh đề P, nếu thay thế biểu thức con E bởi một dạng mệnh đề tương đương logic thì dạng mệnh đề thu được tương đương logic với P • Giả sử E(p, q, r,…) là một hằng đúng, nếu ta thay thế những nơi p xuất hiện trong E bởi một dạng mệnh đề tuỳ ý F(p’, q’, r’,…) thì dạng mệnh đề thu được vẫn là một hằng đúng
14

CÁC TƯƠNG ĐƯƠNG CƠ BẢN
• Luật phủ định của phủ định: ¬ ¬ p ⇔ p • Luật lũy đẳng: p ∧ p ⇔ p, p ∨ p ⇔ p • Luật trung hòa: p ∧ T ⇔ p, p ∨ F ⇔ p • Luật về phần tử bù: p ∧ ¬ p ⇔ F, p ∨ ¬ p ⇔ T

15

CÁC TƯƠNG ĐƯƠNG CƠ BẢN
• Luật thống trị: p ∧ F ⇔ F, p ∨ T ⇔ T • Luật hấp thụ: p ∧ (p ∨ q) ⇔ p , p ∨ (p ∧ q) ⇔ p • Luật giao hoán: p ∧ q ⇔ q ∧p, p ∨ q ⇔ q ∨ p

16

CÁC TƯƠNG ĐƯƠNG CƠ BẢN
• Luật kết hợp: • Luật phân bố: p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ r p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r) p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r) • Luật De Morgan: ¬(p ∧ q) ⇔ ¬p ∨ ¬q ¬(p ∨ q) ⇔ ¬p ∧ ¬q

17

VÍ DỤ 1
Chứng minh rằng: p → (q → r) ⇔ q → (p → r) Ta có: p → (q → r) ⇔ p → (¬ q ∨ r) ⇔ ¬ p ∨ (¬ q ∨ r) ⇔ (¬ p ∨ ¬ q) ∨ r ⇔ (¬ q ∨ ¬p) ∨ r ⇔ ¬ q ∨ (¬p ∨ r) ⇔ q → (¬p ∨ r) ⇔ q → (p → r).
18

VÍ DỤ 2
Chứng minh rằng: (p ∧ q) → r ⇔ p → (q → r) Ta có: (p ∧ q) → r ⇔ ¬ (p ∧ q) ∨ r ⇔ ¬ p ∨¬ q ∨ r ⇔ ¬ p ∨(¬ q ∨ r) ⇔ p → (¬ q ∨ r) ⇔ p → (q → r).

19

VÍ DỤ 3
Chứng minh rằng: [(r → s) ∧ [(r →s) →(¬ t ∨ u)]] → (¬ t ∨ u) là hằng đúng Giải: thay thế r → s bởi p và ¬ t ∨ u bởi q, thì bài toán tương đương với chứng minh mệnh đề [p ∧ (p → q)] → q là hằng đúng

20

VÍ DỤ 3
Chứng minh: [p ∧ (p → q)] → q là hằng đúng Ta có: [p ∧ (p → q)] → q ⇔ [p ∧ (¬ p ∨ q)] → q ⇔ [(p ∧ ¬ p) ∨ (p ∧ q)] → q ⇔ [F ∨ (p ∧ q)] → q ⇔ (p ∧ q) → q ⇔ ¬(p ∧ q) ∨ q ⇔ ¬p ∨ ¬ q ∨ q ⇔ ¬p ∨ T ⇔ T
21

QUI TẮC SUY DIỄN
(Inference Rules)
• Một qui tắc suy diễn là một hàm: b = R(a1, a2,...,an) biến đổi các dạng mệnh đề a1, a2,...,an thành dạng mệnh đề b • Các a1, a2,...,an gọi là giả thiết, b gọi là kết luận • Để suy luận đúng, cần phải đảm bảo các giả thiết a1, a2,...,an là đúng

22

QUI TẮC SUY DIỄN
• Có thể biểu diễn một quy tắc suy luận như sau: a1, a2, ..., an (giả thiết - premises) a1, a2, ...an ⎯⎯⎯⎯⎯ hoặc ⎯⎯⎯⎯⎯ b (kết luận- conclusion) ∴b Nghĩa là, a1 ∧ a2 ∧ ... ∧ an → b • Nếu ai, i=1, 2,…, n là các hằng đúng thì b là một hằng đúng
23

QUI TẮC SUY DIỄN
• Qui tắc khẳng định (Modus Ponens - MP) a → b, a ⎯⎯⎯⎯⎯⎯ b • Qui tắc phủ định (Modus Tollens - MT) a → b, ¬b ⎯⎯⎯⎯⎯⎯ ¬a

24

QUI TẮC SUY DIỄN
• Hội (Conjunction - Conj) a, b ⎯⎯⎯⎯⎯⎯ a∧b

• Đơn giản (Simplification- Simp) a∧b ⎯⎯⎯⎯⎯⎯ a
25

QUI TẮC SUY DIỄN
• Cộng (Addition -Add) a ⎯⎯⎯⎯⎯⎯ a∨b

• Tam đoạn luận rời (Disjunctive syllogism - DS) a ∨ b, ¬a ⎯⎯⎯⎯⎯⎯ b
26

QUI TẮC SUY DIỄN
• Tam đoạn luận (Hypothetical syllogism - HS) a → b, b → γ ⎯⎯⎯⎯⎯⎯ a→γ • Theo trường hợp (Case by case - BC) a→γ,b→γ ⎯⎯⎯⎯⎯⎯ (a ∨ b) → γ

27

HỆ THỐNG SUY LUẬN HÌNH THỨC
(Formal Reasoning SystemS)
• Lý thuyết hình thức (formal theory):
Một tập các công thức Một tập các tiên đề (axiom) Một tập các qui tắc suy luận

• Chứng minh:
Là một dãy hữu hạn các PF trong đó mỗi một PF là một tiên đề hoặc có thể được suy luận từ các công thức PF trước đó

• Định lý:
Là công thức PF cuối cùng trong một chứng minh
28

CHỨNG MINH TRỰC TIẾP
(direct Proof)
• Một mệnh đề cần chứng minh có thể được phát biểu lại dưới dạng một điều kiện • Ví dụ: Chứng minh: “D được kéo theo từ A, B và C” Dạng điều kiện: A ∧ B ∧ C → D Chứng minh: 1. A (giả thiết - premise) 2. B (giả thiết) 3. C (giả thiết) ... k. D
29

CHỨNG MINH TRỰC TIẾP
• Ví dụ: Chứng minh rằng: (A ∨ B) ∧ (A ∨ C) ∧ ¬A → B ∧ C Chứng minh: 1. 2. 3. 4. 5. 6. A∨B A∨C ¬A B C B∧C P P P 1, 3, DS 2, 3, DS Conj
30

CHỨNG MINH TRỰC TIẾP
• Ví dụ: ”Đội nhà thắng hoặc Tôi buồn. Nếu đội nhà thắng thì Tôi đi xem phim. Nếu Tôi buồn thì con chó của tôi sủa. Chó của tôi yên lặng. Vì vậy, Tôi đi xem phim”. Chứng minh kết luận là đúng W: Đội nhà thắng. S: M: B: Tôi buồn. Tôi đi xem phim. Chó của Tôi sủa.

Cần chứng minh: (W ∨ S) ∧ (W → M) ∧ (S → B) ∧ ¬B → M
31

CHỨNG MINH TRỰC TIẾP
• Chứng minh: (W ∨ S) ∧ (W → M) ∧ (S → B) ∧ ¬B → M Ta có: 1. W ∨ S 2. W → M 3. S → B 4. ¬B 5. ¬S 6. W 7. M P P P P 3, 4, MT 1, 5, DS 2, 6, MP
32

CHỨNG MINH GIÁN TIẾP
(Indirect Proof)
• A → B ≡ ¬B → ¬A • Chứng minh bằng phản chứng (Proof by contradiction): A → B ≡ A ∧¬B → False

33

CHỨNG MINH GIÁN TIẾP
Chứng minh rằng: (W ∨ S) ∧ (W → M) ∧ (S → B) ∧ ¬B → M Ta có: 1. W ∨ S P 2. W → M P 3. S → B P 4. ¬B P 5. ¬M P for IP (G.thiết cho phản chứng) 6. ¬W 2, 5, MT 7. ¬S 3, 4, MT 8. ¬W ∧ ¬S 6, 7, Conj 9. ¬(W ∨ S) 8, T 10. (W ∨ S) ∧¬(W ∨ S) 1, 9 Conj 11. False 10, T
34

(Predicate Logic)
• Khái niệm vị từ (Predicate) • Lượng từ (Quantifier) • Các qui tắc suy luận với lượng từ (Inference Rules with Quantifier)

LOGIC VỊ TỪ

35

KHÁI NIỆM VỊ TỪ
• Vị từ là một khẳng định p(x, y, …) trong đó x, y,… là các biến lấy giá trị trong các tập cho trước A, B,…
Vị từ là hàm p: A×B ×...→{0, 1} Bản thân vị từ không phải là mệnh đề Nếu thay x, y,… bằng các giá trị cố định tùy ý a∈A, b ∈B,… thì ta được một mệnh đề p(a, b,…) có chân trị xác định Các biến x, y, …được gọi là biến tự do (free variable)

36

KHÁI NIỆM VỊ TỪ
• p(n) =“n là một số nguyên tố” là một vị từ một biến tự do n ∈ N: Với n = 2, 3, 11, các mệnh đề p(2), p(3), p(11) là đúng, với n = 4, 10, các mệnh đề p(4), p(10) sai • q(x, y) = “x là ước của y” là một vị từ hai biến x, y ∈ N, q(3, 9) = T, q(5, 9) = F

37

KHÁI NIỆM VỊ TỪ
• Nếu W và V là các vị từ, thì các công thức ¬W, W∧V, W∨V, W→V, (W) cũng là các vị từ • Ví dụ: p(x) → q(x, y) =“nếu x là một số nguyên tố thì x là ước của y” là một vị từ

38

LƯỢNG TỪ
• Công thức ∀x W được gọi là lượng từ phổ dụng (Universal Quantifier) • Công thức ∃x W được gọi là lượng từ tồn tại (Existential Quantifier) • Nếu có biến tự do y trong W, có thể tiếp tục lượng từ hoá các vị từ ∀x W, ∃x W theo biến y: ∃y ∀x W, ∀y ∀x W hoặc ∀x ∃y W,...
39

LƯỢNG TỪ
• Ví dụ: s(x, y) =“y là số đi liền sau x”, với x, y ∈ N
∀x ∃y s(x, y) = “ Với mọi x, tồn tại y đi liền sau x” là một công thức (mệnh đề) lượng từ có chân trị bằng T Có thể viết ∀x, ∃y s(x, y) hoặc ∀x ∈ N, ∃y ∈ N s(x, y) hay ∀x ∈ N, ∃y ∈ N, s(x, y) thay cho ∀x ∃y s(x, y)

40

LƯỢNG TỪ
• Ngữ nghĩa (chân trị) của lượng từ
Khi vị từ W chứa biến tự do x được lượng từ hoá thành ∀x W hoặc ∃x W thì ta nói x là biến buộc (không còn tự do nữa) theo các lượng từ ∀ và ∃ Giá trị của ∀x W, ∃x W lúc này là xác định hoàn toàn, nếu trong W không có biến tự do nào khác

41

LƯỢNG TỪ
• Ngữ nghĩa(chân trị) của lượng từ
∃x W(x) là T (đúng) nếu và chỉ nếu W(d) là T với ít nhất một d∈D, trong đó D là miền xác định của biến x ∀x W(x) là T nếu và chỉ nếu W(d) là T với mọi d∈D, trong đó D là miền xác định của biến x

42

LƯỢNG TỪ
• Ví dụ: p(x) = “x là số nguyên tố”
∃x p(x) là đúng, vì có x= 3 để p(3) = T (đúng) ∀x p(x) là sai, vì có x = 4 để p(4) = F

43

LƯỢNG TỪ
• Hai công thức lượng từ α và β là tương đương nếu và chỉ nếu chúng có cùng các giá trị chân lý • Ký hiệu α ⇔ β hoặc α ≡ β • Ta có α ⇔ β khi và chỉ khi (α → β)∧(β → α) là hằng đúng

44

LƯỢNG TỪ
• Ví dụ: với p(x, y) là một vị từ bất kỳ, có các tương đương sau
∀x∈A, ∀y ∈B p(x, y) ⇔ ∀y ∈B, ∀x ∈A p(x, y) ∃ x ∈A, ∃y∈B p(x, y) ⇔ ∃y∈B, ∃x ∈A p(x, y)

45

LƯỢNG TỪ
• Phủ định của một mệnh đề lượng từ hoá vị từ p(x, y,…) có được bằng cách thay thế lượng từ ∀ bởi lượng từ ∃ và lượng từ ∃ bởi lượng từ ∀, và vị từ p(x, y,…) bởi phủ định ¬ p(x, y,…) • Ví dụ: ¬(∀x∈A, ∃ y ∈B p(x, y))⇔ ∃ x ∈A, ∀y ∈B ¬ p(x, y)

46

LƯỢNG TỪ
• Cho vị từ p(x, y) = “x < y”, thì mệnh đề lượng từ hoá ∀x∈R, ∃ y ∈ R x< y là đúng, và có tương đương sau ¬(∀x∈R, ∃ y ∈R x< y)⇔ ∃ x ∈R, ∀y ∈R x ≥ y • Lưu ý: các mệnh đề: ¬(∀x∈R, ∃ y ∈R x< y)⇔ ∃ x ∈R, ∀y ∈R x ≥ y ⇔ F

47

LƯỢNG TỪ chứng minh rằng: ¬(∀x W(x)) ⇔ ∃x ¬W(x) trên D ¬(∀x W(x)) đúng nếu và chỉ nếu ∀x W(x) là sai nếu và chỉ nếu W(d) là sai với ít nhất d∈D nếu và chỉ nếu ¬W(d) là đúng với ít nhất d∈D nếu và chỉ nếu ∃x ¬W(x) là đúng với ít nhất d∈D nếu và chỉ nếu ∃x ¬W(x) là đúng Vậy: ¬(∃x W(x)) ⇔ ∀x ¬W(x)

48

QUI TẮC SUY LUẬN VỚI LƯỢNG TỪ
• Qui tắc suy luận đặc biệt hoá phổ dụng (Universal Instantiation Inference Rule-UI): Nếu một mệnh đề đúng có dạng lượng từ hoá trong đó biến x bị buộc bởi lượng từ phổ dụng ∀ thì các suy luận sau đây là đúng ∀x W(x) ⎯⎯⎯⎯ , W(x) ∀x W(x) ⎯⎯⎯⎯ c là hằng bất kỳ W(c)
49

QUI TẮC SUY LUẬN VỚI LƯỢNG TỪ
• Qui tắc suy luận tổng quát hoá phổ dụng (Universal Generalization Inference Rule-UG): nếu mệnh đề W(c) đúng với mỗi giá trị x = c cố định bất kỳ, thì mệnh đề lượng từ hoá ∀x W(x) là đúng. W(c) ⎯⎯⎯⎯ ∀x W(x)

W(c)=T với c là hằng bất kỳ

50

QUI TẮC SUY LUẬN VỚI LƯỢNG TỪ
• Qui tắc suy luận đặc biệt hoá tồn tại (Existential Instantiation Inference Rule-EI): ∃x W(x) ⎯⎯⎯⎯⎯⎯ W(c) nếu c là một hằng mới trong suy luận

• Qui tắc suy luận khái quát hoá tồn tại (Existential Generalization Inference Rule-EG): W(x) ⎯⎯⎯⎯⎯⎯ ∃x W(x)

51

QUI TẮC SUY LUẬN VỚI LƯỢNG TỪ
• Chứng minh: (∀x p(x)) ∧ (∃x q(x)) → ∃x (p(x) ∧ q(x)) Ta có: 1. 2. 3. 4. 5. ∀x p(x) ∃x q(x) q(c) p(c) p(c) ∧ q(c) p p 2, EI 1, UI 3, 4 Conj

6. ∃x (p(x) ∧ q(x)) 5, EG.
52

QUI TẮC SUY LUẬN VỚI LƯỢNG TỪ
• Chứng minh: [(∀x (p(x)→ q(x)) ∧ ∀x (q(x) → r(x))] → ∀ x (p(x) → r(x)) Ta có: 1. ∀x (p(x)→ q(x)) 2. ∀x (q(x) → r(x)) 3. P(c) → q(c) 4. q(c) → r(c) 5. P(c) → r(c) 6. ∀ x (p(x) → r(x)) p p 1, UI 2, UI 3, 4 HS 5, UG.
53

QUI TẮC SUY LUẬN VỚI LƯỢNG TỪ
• Chứng minh phát biểu sau: Mọi kỹ sư máy tính là một nhà logic. Tâm là một kỹ sư máy tính. Vì vậy, có một số nhà logic học. Mô hình hoá bài toán: c(x) =“x là một kỹ sư máy tính” l(x) =“x là một nhà logic” Thì: ∀x (c(x) → l(x))∧c(Tâm) → ∃x l(x)
54

QUI TẮC SUY LUẬN VỚI LƯỢNG TỪ
• Chứng minh: ∀x (c(x) → l(x))∧c(Tâm) → ∃x l(x) Ta có: 1. ∀x (c(x) → l(x)) 2. c(Tâm) 3. c(Tâm) → l(Tâm ) 4. l(Tâm) 6. ∃x l(x) p p UI 2, 3, MP 4, EG.
55