Chương 2: Hệ toán mệnh đề

Chia sẻ: Hoàng Minh Quân | Ngày: | Loại File: PDF | Số trang:32

Thêm vào BST

Báo xấu

79
lượt xem 8
download

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

Để nghiên cứu một cách toàn diện và hệ thống theo mạch tư duy suy diễn của con người, ta chuyển qua việc khảo sát nó một cách " hình thức" , " trừu tượng" nhưng lại làm cho quá trình tư duy, suy luận một cách chính xác, đầy đủ và mang tính chất logic toán học hơn. Mặc dù các hệ hình thức này được trình bày một cách trừu tượng nhưng thực chất nó nhằm phục vụ cho việc nghiên cứu đại số mệnh đề....

Chủ đề:

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

Lưu

Nội dung Text: Chương 2: Hệ toán mệnh đề

Chương 2. Hệ toán mệnh đề Trần Thọ Châu Logic Toán. NXB Đại học quốc gia Hà Nội 2007. Tr 39-69. Từ khoá: Logic toán, Đại số mệnh đề, Hệ toán mệnh đề, Định lý suy diễn, Logic mệnh đề, Tính đầy đủ, Tính phi mâu thuẫn, Tính độc lập. Tài liệu trong Thư viện điện tử ĐH Khoa học Tự nhiên có thể sử dụng cho mục đích học tập và nghiên cứu cá nhân. Nghiêm cấm mọi hình thức sao chép, in ấn phục vụ các mục đích khác nếu không được sự chấp thuận của nhà xuất bản và tác giả.
Chu.o.ng 2 ` Hˆ to´n mˆnh dˆ ea e e . . ee` ` 2.1 Hˆ tiˆn dˆ trong hˆ to´n mˆnh dˆ . . . . . . . . e ea e e 40 . . . 2.1.1 Mˆt sˆ dinh ngh˜ co. ban . . . . . . . . . . . . . 40 .´ ’ oo. ıa ´ 2.1.2 C´c t´ chˆ t a ınh a . . . . . . . . . . . . . . . . . . . . 42 ee` ´ ` 2.1.3 L´ thuyˆt tiˆn dˆ trong hˆ to´n mˆnh dˆ . . . . . 43 y e ea e e . . ˜ ` 2.1.4 Dinh l´ suy diˆn trong hˆ to´n mˆnh dˆ . . . . . . 44 y e ea e e . . . ˜ 2.2 Nguyˆn l´ suy diˆn v` b`i to´n lˆp luˆn trong ey e aa aa a . . ` logic mˆnh dˆ . . . . . . . . . . . . . . . . . . . . . e e 52 . ˜ 2.2.1 Nguyˆn l´ suy diˆn . . . . . . . . . . . . . . . . . . 52 ey e ` 2.2.2 B`i to´n lˆp luˆn trong logic mˆnh dˆ . . . . . . . 52 a aa a e e . . . ´ ` 2.3 Mˆt sˆ dinh l´ trong hˆ to´n mˆnh dˆ oo. y ea e e ..... 55 . . . ınh ` ’ 2.3.1 T´ dˆy du a . . . . . . . . . . . . . . . . . . . . . 55 ˜ 2.3.2 T´ phi mˆu thuˆn . . . . . . . . . . . . . . . . . 58 ınh a a 2.3.3 T´ dˆc lˆp . . . . . . . . . . . . . . . . . . . . . 59 ınh o a .. Gi´.i thiˆu v`i n´t vˆ logic da tri . . . . . . . . . ae` 2.4 o e e 61 . . ´ ` ’ 2.5 T´ ınh quyˆt dinh cua hˆ to´n mˆnh dˆ . . . . . . e. ea e e 62 . . ooee ` ´. 2.6 Mˆt sˆ hˆ tiˆn dˆ kh´c . . . . . . . . . . . . . . . e a 62 .
Chu.o.ng 2. Hˆ to´n mˆnh dˆ ` 40 ea e e . . ´ ˜ y` ’ 2.7 Ap dung dinh l´ dˆy du cho b`i to´n suy diˆn a a a e . . ` trong logic mˆnh dˆ . . . . . . . . . . . . . . . . . e e 64 . B`i tˆp chu.o.ng 2 . . . . . . . . . . . . . . . . . . 2.8 aa 66 . Trong chu.o.ng 1, ta d˜ bu.´.c dˆu nghiˆn c´.u nˆi dung dai sˆ mˆnh dˆ. o` ´. ` a a eu o .oe e . .u mˆt c´ch to`n diˆn v` hˆ thˆng theo mach tu. duy suy diˆn ’ ˜ .´ Dˆ nghiˆn c´ e eu oa a e ae o e . . . cua con ngu.`.i, ta chuyˆ n qua viˆc khao s´t n´ mˆt c´ch “h` th´.c”, “tr`.u ’ ’ ’aooa o e e ınh u u . . .o.ng”, nhu.ng lai l`m cho qu´ tr`nh tu. duy, suy luˆn mˆt c´ch ch´ x´c, tu . .a aı a oa ınh a . . .n. M˘c d` c´c hˆ h`nh th´.c n`y ` ´ ’a dˆy du v` mang t´ chˆ t logic To´n hoc ho a ınh a a. a ua eı ua . . du.o.c tr` b`y mˆt c´ch tr`.u tu.o.ng, nhu.ng thu.c chˆ t n´ nh˘ m phuc vu cho ao` ´ ınh a oa u a . . . . .. .u dai sˆ mˆnh dˆ sˆu s˘c, c´ t´nh hˆ thˆng v` c´ nh˜.ng u.ng ´ ´. `a a .´ viˆc nghiˆn c´ e eu .oe e oı eo ao u ´ . .c kh´c liˆn quan dˆn ban chˆ t cua dai sˆ mˆnh dˆ. ` ınh . ´’ ´ ´. ` a’ dung trong nhiˆu l˜ vu e ae e .oe e . ee` ` 2.1 Hˆ tiˆn dˆ trong hˆ to´n mˆnh dˆ e ea e e . . . Mˆt sˆ dinh ngh˜ co. ban ´ ’ 2.1.1 oo. ıa . Dinh ngh˜ 2.1.1 S du.o.c goi l` l´ thuyˆt h` th´.c (hay l´ thuyˆt tiˆn dˆ), ´ ee` ´ ıa . . ay e ınh u y e . ´ ’aa` nˆu n´ thoa m˜n c´c diˆu kiˆn sau dˆy: eo e e a . (1) Mˆt tˆp dˆm du.o.c c´c k´ hiˆu goi l` k´ hiˆu cua S . Mˆt d˜y h˜.u han ´ . a y e .ay e ’ oae oau .. . . . . .o.c goi l` mˆt biˆ u th´.c cua l´ thuyˆt S . ’ ´ aye’ ’y c´c k´ hiˆu cua S du . . a o e u e . . (2) Mˆt thu tuc cho ph´p x´c dinh mˆt biˆ u th´.c d˜ cho c´ phai l` mˆt ’ ’. ’ao o ea. o e ua o . . . .c hay khˆng. cˆng th´ o u o (3) Mˆt tˆp h˜.u han c´c cˆng th´.c du.o.c goi l` c´c tiˆn dˆ cua l´ thuyˆt .aa e ` ’ y ´ oau .ao u e e .. . S. (4) Mˆt tˆp h˜.u han R1 , R2 , ..., Rk c´c quy t˘c dˆn xuˆ t cho ph´p ta dˆn ´˜ ˜ ´ oau a aa a e a .. . .o.c t`. mˆt tˆp h˜.u han c´c cˆng th´.c dˆn mˆt tˆp c´c cˆng th´.c m´.i. ´ du . u o a u .ao ue oaao u o .. .. Dinh ngh˜ 2.1.2 Mˆt d˜y c´c cˆng th´.c A1, A2, ...An du.o.c goi l` dˆn ˜ ıa oaao u .aa . . . .c A ho˘c l` tiˆn dˆ ho˘c l` dˆn du.o.c ˜ ´ ´´ aae ` aaa xuˆ t trong S nˆu bˆ t k` mˆt cˆng th´ a eayoo u e. . . . i .c tiˆp t`. c´c cˆng th´.c d´.ng tru.´.c n´ nh`. qui t˘c dˆn xuˆ t. ´a ˜ ´ ´ tru e u a o uu ooo a a .
ee` ` 2.1. Hˆ tiˆn dˆ trong hˆ to´n mˆnh dˆ e ea e e 41 . . . Dinh ngh˜ 2.1.3 Mˆt cˆng th´.c A cua l´ thuyˆt S du.o.c goi l` dinh l´ ´ ’y ıa oo u e .a. y . . . ´` .˜ ´ ´ ’y cua l´ thuyˆt S nˆu tˆ n tai mˆt dˆn xuˆ t trong S : A1 , A2, ..., Ak sao cho e eo. oa a Ak = A, v` dˆn xuˆ t n`y du.o.c goi l` dˆn xuˆ t cua cˆng th´.c A. ˜ ˜ ´ ´ a’o aa aa . .aa u ` ´ Dinh ngh˜ 2.1.4 L´ thuyˆt m` trong d´ c´ tˆ n tai mˆt thuˆt to´n cho ıa y e a ooo . o a a . . . .c d˜ cho c´ dˆn du.o.c hay khˆng du.o.c goi l` l´ ˜ ph´p x´c dinh mˆt cˆng th´ a ea. oo u oa o . . ay . . thuyˆt giai du.o.c; Tr´i lai, n´ du.o.c goi l` l´ thuyˆt khˆng giai du.o.c. ´’ ´ ’ e a. o . . ay e o . . Dinh ngh˜ 2.1.5 Mˆt cˆng th´.c A du.o.c goi l` dˆn du.o.c trong S t`. tˆp ˜ ıa oo u .aa ua . . . . . .p Γ c´c cˆng th´.c, khi v` chı khi tˆ n tai d˜y c´c cˆng th´.c A , A , ...A ` a’ ho ao u o.aao u . 1 2 n ` , ho˘c l` phˆn tu. cua ` ’’ sao cho An = A v` ∀i (i = 1...n) Ai ho˘c l` tiˆn dˆ a aae e aa a . . ˜n du.o.c tru.c tiˆp t`. c´c cˆng th´.c d´.ng tru.´.c n´ nh`. quy t˘c ´ ´ Γ, ho˘c l` dˆ aaa e ua o uu ooo a . . . ˜ ´ dˆn xuˆ t. a a D˜y cˆng th´.c n`y du.o.c goi l` dˆn xuˆ t cua A t`. Γ. C´c phˆn tu. cua ˜ ´ ` a’ a’’ ao ua .aa u a . Γ du.o.c goi l` gia thiˆt, v` ta k´ hiˆu nhu. sau: ´a . .a’ e ye . Γ A ho˘c Γ a A . S v` du.o.c doc l` “A dˆn du.o.c t`. Γ” ho˘c “A dˆn du.o.c t`. Γ trong S ”. ˜ ˜ a .a a .u a a .u . . Ch´ y 1 u´ 1a) Tru.`.ng ho.p Γ l` h˜.u han: Γ := {B1, B2, ..., Bm} th` ta k´ hiˆu: o au ı ye . . . B1, B2, ..., Bm A. 1b) Tru.`.ng ho.p nˆu Γ = ∅ th` Γ ´ a’ o e ı A, khi v` chı khi A l` dinh l´, v` ta k´ a. ya y . hiˆu: A. e . Ch´ y 2 u´ 2a) Mˆi mˆt tiˆn dˆ l` dˆn du.o.c t`. tˆp bˆ t k` Γ c´c cˆng th´.c ˜. ˜ o o e `aa ´ e . ua a y ao u . 2b) Mˆi mˆt dinh l´ l` dˆn du.o.c t`. tˆp bˆ t k` Γ c´c cˆng th´.c ˜. ˜ ´ o o. ya a . ua a y ao u . 2c) Mˆi mˆt phˆn tu. cua Γ dˆu dˆn du.o.c t`. Γ. ˜. ˜ ` ` a’’ oo ea .u
Chu.o.ng 2. Hˆ to´n mˆnh dˆ ` 42 ea e e . . ´ 2.1.2 C´c t´ chˆ t a ınh a ´ (1) Nˆu Γ ⊆ ∆ v` Γ e a A th` ∆ ı A ` a’ (2) Γ A, khi v` chı khi tˆ n tai mˆt tˆp ∆ ⊆ Γ sao cho ∆ o. oa A .. ´ (3) Nˆu ∆ e A v` ∀B ∈ ∆ : Γ a B th` Γ ı A. ’. a O dˆy ta thˆ y t´ chˆ t (1) chı ra r˘ ng mˆt cˆng th´.c d˜ dˆn du.o.c t`. ` ˜ ´ ´ ’ a ınh a a oo u aa .u . .c th` n´ c˜ng dˆn du.o.c t`. tˆp l´.n ho.n, ngh˜a l` nˆu ˜ ´ mˆt tˆp c´c cˆng th´ oaao u ıou a . ua o ıae .. . ta c´ thˆm mˆt sˆ gia thiˆt v`o tˆp d˜ dˆn du.o.c th` t´ chˆ t dˆn du.o.c cua ˜ ´˜ .´ ´ oo’ .’ oe e a a aa ı ınh a a . . .c vˆn khˆng thay dˆ i. ’ u˜ cˆng th´ a o o o T`. t´nh chˆ t (1) buˆc ta phai suy ngh˜ l`m thˆ n`o dˆ chon du.o.c mˆt ’ ´ ´ ’ uı a o ıa ea e . o . . . .a du, khˆng th`.a v` c˜ng khˆng thiˆu. Nˆu gia ´ ´ ´ ’ ’ ’ tˆp gia thiˆt sao cho n´ v` a e ou o u au o e e . thiˆt th`.a th` t´nh chˆ t dˆn du.o.c s˜ ´t du.o.c thuyˆt phuc ho.n, c`n nˆu gia ´˜ ´ ´ ´ ’ e u ıı aa . eı e oe . . .o.c dˆn diˆu phai ch´.ng minh. Dˆy ch´nh ’˜ ´ ´ ´` ’ thiˆt thiˆu th` ta khˆng thˆ dˆn du . e e e ı o ea e u a ı a` ´a ´ a’ ’’ı l` ban chˆ t dˆy du cua t´nh chˆ t (2).a T´ chˆ t (3) thˆ hiˆn “t´nh b˘c cˆu” cua ph´p dˆn du.o.c cua mˆt cˆng ’. ´a ˜ ´ a` ’ ’ ınh a ee ı ea oo . . .c. Ta c´ thˆ h` dung b˘ ng h`nh anh ph´c hoa sau dˆy: ’ ınh ` ’ th´u oe a ı a a .
ee` ` 2.1. Hˆ tiˆn dˆ trong hˆ to´n mˆnh dˆ e ea e e 43 . . . ´e` ` 2.1.3 L´ thuyˆt tiˆn dˆ trong hˆ to´n mˆnh dˆ y e e ea e e . . Hˆ to´n mˆnh dˆ l` mˆt l´ thuyˆt h` th´.c ho´ cua logic mˆnh dˆ. Viˆc `a o y ´ ` a’ ea e e e ınh u e e e . . . . . .c ho´ logic l` bu.´.c co. ban dˆu tiˆn cho viˆc h`nh th´.c ho´ c´c l´ ` ’ h`nh th´ ı u a a o a e eı u aa y . .c ho´ mˆt l´ thuyˆt l` ´a ´’ ´ ’e thuyˆt to´n hoc. Nˆi dung chu yˆu cua viˆc h` th´ e o e ınh u aoy ea . . . . .ng mˆt ngˆn ng˜. h` th´.c dˆ diˆn ta c´c ph´n do´n, du.a ra mˆt ’e u ınh u e ˜ ’ a xˆy du a o o a a o . . . ` du.o.c xem nhu. l` nh˜.ng chˆn l´ ban dˆu, v` phai x´c dinh c´c ` ’a. hˆ tiˆn dˆ ee e au ay a a a . . .o.ng ph´p suy diˆn (hay c`n goi l` ch´.ng minh) dˆ t`m ra c´c ’ ´ ˜ quy t˘c v` phu aa a e o .au eı a .i cua l´ thuyˆt. Dˆ nghiˆn c´.u mˆt c´ch cu thˆ , ta di sˆu nghiˆn ’ ’ ´ dinh l´ m´ ’ y yo e e eu oa .e a e . . c´.u l´ thuyˆt tiˆn dˆ L du.´.i dˆy. ee` ´ uy e oa ` ee` ´ Dinh ngh˜ 2.1.6 L´ thuyˆt tiˆn dˆ L bao gˆ m : ıa y e o . aye’ (1) C´c k´ hiˆu cua L: . - ¬, → du.o.c goi l` hai ph´p to´n nguyˆn thuy ’ . .a e a e ´ - C´c dˆ u ngo˘c (,) aa a. - C´c ch˜. c´i La-tinh A, B, C, ... v` c´c ch˜. c´i La-tinh c´ chı sˆ ´ o ’o a ua aa ua . c´i La-tinh n`y du.o.c goi l` c´c biˆn mˆnh ´ A1 , B1, C1 , ... . C´c ch˜ a a u a .aa e e . . ` dˆ. e (2) Cˆng th´.c du.o.c xˆy du.ng b˘ ng dˆ quy nhu. sau: ` o u .a a e . . (a) Tˆ t ca c´c biˆn mˆnh dˆ dˆu l` cˆng th´.c ´ ´ `` ao a ’a e e ee u . (b) Nˆu A v` B l` cˆng th´.c th` (¬A), (A → B ) c˜ng l` cˆng th´.c ´ e a ao u ı u ao u (c) Mˆt biˆ u th´.c l` cˆng th´.c, nˆu n´ du.o.c lˆp nˆn t`. co. so. (a) ’ ´o ’ o e u ao u e .a eu . . v` (b). a (3) C´c tiˆn dˆ: Dˆi v´.i c´c cˆng th´.c A, B , C tu` y ae` ´ e ooao u y´ A1. (A → (B → A)) A2. (A → (B → C )) → ((A → B ) → (A → C )) A3. (¬B → ¬A) → ((¬B → A) → B ) ´˜ ´ ´. ´ (4) Quy t˘c dˆn xuˆ t Modus Ponens (Kˆt luˆn): Nˆu A v` A → B th` B . aa a ea e a ı
Chu.o.ng 2. Hˆ to´n mˆnh dˆ ` 44 ea e e . . Ch´ y 3 Dˆi v´.i c´c ph´p to´n c`n lai ∧, ∨, ↔ ta c´ thˆ biˆ u diˆn ch´ng ’’ ˜ ´ u´ ooa e ao. oee e u . c´c cˆng th´.c tu.o.ng du.o.ng sau dˆy: qua hai ph´p to´n {¬, →} nh` a o e a o u a D1. (A ∧ B ) l` tu.o.ng du.o.ng v´.i ¬(A → ¬B ) a o D2. (A ∨ B ) l` tu.o.ng du.o.ng v´.i (¬A) → B a o D3. (A ↔ B ) l` tu.o.ng du.o.ng v´.i (A → B ) ∧ (B → A) a o A → A dˆi v´.i cˆng th´.c A tu` ´ trong L ’e o` ´ Bˆ dˆ 2.1.1 ooo u yy ’. a Ch´.ng minh: O dˆy ta k´ hiˆu MP l` viˆt t˘t cua Modus Ponens. Ta xˆy ´´ aea’ u ye a . .ng dˆn xuˆ t cua cˆng th´.c A → A trong L nhu. sau: ˜ ´ a’o du a u . 1. (A → ((A → A) → A)) → ((A → (A → A)) → (A → A)) (A2) 2. A → ((A → A) → A) (A1) 3. (A → (A → A)) → (A → A) (1, 2, MP) 4. (A → (A → A)) (A1) 5. (A → A) (3, 4, MP) Vˆy theo dinh ngh˜ 2.1.2 & 2.1.3 ta c´: a ıa o . . A→A ˜ ` 2.1.4 Dinh l´ suy diˆn trong hˆ to´n mˆnh dˆ y e ea e e . . . Trong nhiˆu ch´.ng minh cua hˆ to´n mˆnh dˆ, ta thu.`.ng su. dung dinh l´ ` ` ’ea ’. e u e e o y . . . ˜ suy diˆn sau dˆy: e a Dinh l´ 2.1.1 (dinh l´ suy diˆn) Nˆu Γ l` tˆp c´c cˆng th´.c, A v` B l` ˜ ´ y y e e aa a o u a a . . . .c v` Γ, A B th` Γ A → B . c´c cˆng th´ a ao u ı Tru.`.ng ho.p d˘c biˆt, nˆu A B th` A → B (Herbrand). ´ o a e e ı . . .
ee` ` 2.1. Hˆ tiˆn dˆ trong hˆ to´n mˆnh dˆ e ea e e 45 . . . Ch´.ng minh: u Gia su. B1, B2 ...Bn l` dˆn xuˆ t t`. Γ ∪ {A}, trong d´ Bn = B . Ta ch´.ng ˜ ´ ’’ aa au o u ` minh b˘ ng qui nap theo i (i = 1...n): Γ A → Bi . a . 1) Bu.´.c kho.i dˆu i = 1: ’` o a Khi d´ B1 ho˘c l` phˆn tu. cua Γ, ho˘c l` tiˆn dˆ ho˘c l` tr`ng v´.i A. aa` aae` aau a’’ o e. o . . Theo tiˆn dˆ (A1) cˆng th´.c B1 → (A → B1 ) l` tiˆn dˆ. Do d´ trong e` ae` e o u e o .`.ng ho.p dˆu ta c´ Γ A → B nh`. quy t˘c Modus Ponens v` ´ .` 2 tru o a o o a a 1 ch´ y 2. u´ Tru.`.ng ho.p 3: B1 = A. Khi d´ theo bˆ dˆ 2.1.1: A → B1. Do d´ ’e o` o o o . theo ch´ y 2 ta c´: Γ A → B1. u´ o 2) Gia thiˆt qui nap: Gia su. cˆng th´.c Γ A → Bk d´ng v´.i moi k < i. ´ ’ ’’o e u u o . . 3) Ch´.ng minh qui nap: Ta ch´.ng minh r˘ ng cˆng th´.c c˜ng d´ng v´.i ` u u a o uu u o . k = i: Γ A → Bi . Thˆt vˆy, ta x´t 4 tru.`.ng ho.p c´ thˆ xay ra dˆi v´.i Bi nhu. sau: ’ ´ . oe’ aa e o oo .. . cua Γ, ho˘c l` tiˆn dˆ, ho˘c l` B = A, ho˘c B dˆn du.o.c ˜ aa` aae` Bi ho˘c l` phˆn tu ’ a’ e aai a ia . . . . . .c tiˆp t`. c´c cˆng th´.c B v` B sao cho ´ ua o tru e u jam . j < i, m < i v` Bm = Bj → Bi . a Trong 3 tru.`.ng ho.p dˆu ta ch´.ng minh tu.o.ng tu. nhu. i = 1. Tru.`.ng ` o a u o . . .p th´. 4, ta su. dung gia thiˆt qui nap: ´ ’. ’ ho u e . . Γ A → Bj v` Γ a A → ( B j → Bi ) . e` Theo tiˆn dˆ (A2): e (A → (Bj → Bi )) → ((A → Bj ) → (A → Bi )). ´ Do d´ theo qui t˘c Modus Ponens v` ch´ y 2: o a a u´ Γ ( A → Bj ) → ( A → Bi ) .
Chu.o.ng 2. Hˆ to´n mˆnh dˆ ` 46 ea e e . . Ta ´p dung mˆt lˆn n˜.a qui t˘c Modus Ponens: ´ o` a .au a . Γ (A → Bi ). Vˆy ta ch´.ng minh du.o.c r˘ ng: ` a u .a . ∀i (i = 1, ..., n) : Γ A → Bi . Khi d´ v´.i i = n ta c´: oo o Γ A → Bn , v` v` Bn = B , ta c´: aı o Γ A→B Hˆ qua 2.1.1 Dˆi v´.i c´c cˆng th´.c A, B , C tu` ´ ’ ´ e ooao u yy . ´a a` (i) A → B , B → C A → C (b˘c cˆu) ´ a.’ (ii) A → (B → C ), B A → C (ho´n vi gia thiˆt). e Ch´.ng minh: u (i) Ta xˆy du.ng dˆn xuˆ t sau dˆy: ˜ ´ a a a a . ´ ’ 1. A → B (gia thiˆt) e ´ ’ 2. B → C (gia thiˆt) e ´ ’ 3. A (gia thiˆt) e 4. B (1, 3, MP) 5. C (2, 4, MP) Vˆy t`. 1 - 5 ta c´: au o . A → B, B → C , A C. ˜ Theo dinh l´ suy diˆn ta c´: y e o . A → B, B → C A→C
ee` ` 2.1. Hˆ tiˆn dˆ trong hˆ to´n mˆnh dˆ e ea e e 47 . . . (ii) Ta xˆy du.ng dˆn xuˆ t nhu. sau: ˜ ´ a a a . ´ ’ 1. A → (B → C ) (gia thiˆt) e ´ ’ 2. B (gia thiˆt) e ´ ’ 3. A (gia thiˆt) e 4. B → C (1, 3, MP) 5. C (2, 4, MP) Vˆy t`. 1 – 5 ta c´: au o . A → (B → C ), B , A C. ˜ Theo dinh l´ suy diˆn: y e . A → (B → C ), B A→C Dˆ nh`n r˜ ho.n t´nh chˆ t ho´n vi gia thiˆt ta ´p dung thˆm dinh l´ ’ıo ´ ´ a.’ e ı a e a e y . . ˜ suy diˆn: e A → (B → C ) B → (A → C ) Ap dung mˆt lˆn n˜.a dinh l´ suy diˆn, ta c´: ´ ˜ o` .au . y e o . (A → (B → C )) → (B → (A → C )). Hˆ qua 2.1.2 Dˆi v´.i bˆ t k` c´c cˆng th´.c A, B c´c cˆng th´.c sau dˆy ’ ´ ´ e o o a ya o u ao u a . ` a. dˆu l` dinh l´ trong L: e y a) ¬¬B → B b) B → ¬¬B c) ¬A → (A → B ) d) (¬B → ¬A) → (A → B ) e) (A → B ) → (¬B → ¬A)
Chu.o.ng 2. Hˆ to´n mˆnh dˆ ` 48 ea e e . . f) A → (¬B → ¬(A → B )) g) (A → B ) → ((¬A → B ) → B ). Ch´.ng minh: u a) ¬¬B → B Ta xˆy du.ng dˆn xuˆ t nhu. sau: ˜ ´ a a a . 1. (¬B → ¬¬B ) → ((¬B → ¬B ) → B ) (A3) ’e o` 2. ¬B → ¬B (bˆ dˆ 2.1.1) ´ a.’ 3. (¬B → ¬¬B ) → B (1, 2, ho´n vi gia thiˆt) e 4. ¬¬B → (¬B → ¬¬B ) (A1) ´a a` 5. ¬¬B → B (3, 4, b˘c cˆu) Vˆy t`. 1 – 5 ta c´: au o . ¬¬B → B . b) B → ¬¬B 1. (¬¬¬B → ¬B ) → ((¬¬¬B → B ) → ¬¬B ) (A3) 2. ¬¬¬B → ¬B (theo a)) 3. (¬¬¬B → B ) → ¬¬B (1, 2, MP) 4. B → (¬¬¬B → B ) (A1) ´a a` 5. B → ¬¬B (3, 4, b˘c cˆu) Vˆy t`. 1 - 5 ta c´: au o . B → ¬¬B .
ee` ` 2.1. Hˆ tiˆn dˆ trong hˆ to´n mˆnh dˆ e ea e e 49 . . . c) ¬A → (A → B ) ´ ’ 1. ¬A (gia thiˆt) e ´ ’ 2. A (gia thiˆt) e 3. A → (¬B → A) (A1) 4. ¬A → (¬B → ¬A) (A1) 5. ¬B → A (2, 3, MP) 6. ¬B → ¬A (1, 4, MP) 7. (¬B → ¬A) → ((¬B → A) → B ) (A3) 8. (¬B → A) → B (6, 7, MP) 9. B (5, 8, MP) Vˆy t`. 1 - 9 ta c´: au o . ¬A, A B. ´ ˜ Ap dung dinh l´ suy diˆn ta c´: y e o . . ¬A A→B Ap dung mˆt lˆn n˜.a dinh l´ suy diˆn ta c´: ´ ˜ o` .au . y e o . ¬A → (A → B ). d) (¬B → ¬A) → (A → B ) ´ ’ 1. ¬B → ¬A (gia thiˆt) e ´ ’ 2. A (gia thiˆt) e 3. (¬B → ¬A) → ((¬B → A) → B ) (A3) 4. A → (¬B → A) (A1) 5. (¬B → A) → B (1, 3, MP)
Chu.o.ng 2. Hˆ to´n mˆnh dˆ ` 50 ea e e . . ´a a` 6. A → B (4, 5, b˘c cˆu) 7. B (2, 6, MP) Vˆy t`. 1 - 7 ta c´: au o . ¬B → ¬A, A B ´ ˜ Ap dung dinh l´ suy diˆn: y e . . ¬B → ¬A A→B Ap dung mˆt lˆn n˜.a dinh l´ suy diˆn ta c´: ´ ˜ o` .au . y e o . (¬B → ¬A) → (A → B ) e) (A → B ) → (¬B → ¬A) ´ ’ 1. A → B (gia thiˆt) e 2. ¬¬A → A (theo a)) ´a a` 3. ¬¬A → B (1, 2, b˘c cˆu) 4. B → ¬¬B (theo b)) ´a a` 5. ¬¬A → ¬¬B (3, 4, b˘c cˆu) 6. (¬¬A → ¬¬B ) → (¬B → ¬A) (theo d)) 7. ¬B → ¬A (5, 6, MP) Vˆy t`. 1 – 7 ta c´: au o . A→B ¬B → ¬A. ´ ˜ Ap dung dinh l´ suy diˆn ta c´: y e o . . (A → B ) → (¬B → ¬A.)
ee` ` 2.1. Hˆ tiˆn dˆ trong hˆ to´n mˆnh dˆ e ea e e 51 . . . f) A → (¬B → ¬(A → B )) ˜a a` ´a Dˆ d`ng thˆ y r˘ ng: A, A → B e B. ´ ˜ ` Ap dung 2 lˆn dinh l´ suy diˆn ta c´: a. y e o . A → ((A → B ) → B ) (1) M˘t kh´c theo e) ta c´: a a o . ((A → B ) → B ) → (¬B → ¬(A → B )) (2) ´ ´a ’a` Ap dung (1), (2) v` Hˆ qua b˘c cˆu ta c´: ae o . . A → (¬B → ¬(A → B )). g) (A → B ) → ((¬A → B ) → B ) ´ ’ 1. A → B (gia thiˆt) e ´ ’ 2. ¬A → B (gia thiˆt) e 3. (A → B ) → (¬B → ¬A) (theo e)) 4. ¬B → ¬A (1, 3, MP) 5. (¬A → B ) → (¬B → ¬¬A) (the e)) 6. ¬B → ¬¬A (2,5 MP) 7. (¬B → ¬¬A) → ((¬B → ¬A) → B ) (A3) 8. (¬B → ¬A) → B (6, 7, MP) 9. B (4, 8, MP) Vˆy t`. 1 - 9 ta c´: au o . A → B , ¬A → B B ´ ˜ ` Ap dung hai lˆn dinh l´ suy diˆn ta c´: a. y e o . (A → B ) → ((¬A → B ) → B ).
Chu.o.ng 2. Hˆ to´n mˆnh dˆ ` 52 ea e e . . ˜ 2.2 Nguyˆn l´ suy diˆn v` b`i to´n lˆp luˆn ey e aa aa a . . ` trong logic mˆnh dˆ e e . ˜ 2.2.1 Nguyˆn l´ suy diˆn ey e Dinh ngh˜ 2.2.1 Mˆt tˆp cˆng th´.c S = {A1, A2, ..., An} du.o.c goi l` phi ıa oao u . .a .. . mˆu thuˆn, nˆu tˆ n tai mˆt minh hoa t´.c l` mˆt bˆ phˆn bˆ c´c gi´ tri chˆn ˜ ´` ´ a a eo.o .u a o o a oa a . a . .. .i c´c biˆn c´ m˘t trong hˆ S sao cho moi A (i = 1...n) dˆu nhˆn ´ ´ ` l´ dˆi v´ a yoo eoa e e a . . . . i .o.c goi l` mˆu thuˆn, nˆu khˆng c´ mˆt minh hoa ˜ ´ gi´ tri d´ng; Tr´i lai, S du . . a a a .u a. a e o oo . . . vˆy. n`o nhu a a . Dinh ngh˜ 2.2.2 Cˆng th´.c A du.o.c goi l` logic k´o theo t`. tˆp c´c cˆng ıa o u . .a e ua a o . . .c S , nˆu trong moi minh hoa m` tai d´ c´c cˆng th´.c thuˆc S dˆu nhˆn ´ ` th´ u e . a. oa o u o e a . . . gi´ tri d´ng th` A c˜ng d´ng. Khi d´ ta k´ hiˆu: a .u ı u u o ye . S |= A. Trong tru.`.ng ho.p d˘c biˆt, nˆu S = ∅ th` khi d´ |= A ngh˜ l` cˆng th´.c A ´ o a ee ı o ıa a o u . . . l` h˘ ng d´ng. Dˆ d`ng ch´.ng minh du.o.c c´c t´ chˆ t sau. ` ˜a ´ aa u e u . a ınh a ˜ Dinh l´ 2.2.1 (nguyˆn l´ suy diˆn) y ey e . V´.i moi cˆng th´.c A, B , H1, H2, ..., Hn ta c´: o .o u o 1. A |= B ⇔|= (A → B ) 2. {H1 , H2 , ..., Hn } |= A ⇔|= H1 ∧ H2 ∧ ... ∧ Hn → A 3. {H1 , H2 , ..., Hn } |= A ⇔ {H1 , H2 , ..., Hn, ¬A} |= F ` 2.2.2 B`i to´n lˆp luˆn trong logic mˆnh dˆ a aa a e e . . . Trong nh˜.ng u.ng dung cua logic mˆnh dˆ v`o c´c hˆ tr´ tuˆ nhˆn tao, ta `aa eıe a . ’ u´ e e . . . . .`.ng g˘p b`i to´n lˆp luˆn (reasoning) sau dˆy: thu o aaaa a a . . .
˜ aa a a ` 2.2. Nguyˆn l´ suy diˆn v` b`i to´n lˆp luˆn trong logic mˆnh dˆ ey e a e e 53 . . . Cho mˆt co. so. tri th´.c S gˆ m c´c cˆng th´.c H1 , H2 , ..., Hn v` mˆt cˆng `ao ’ o u o u aoo . . .c d´ (Goal) l` A. Hoi r˘ ng A c´ phai l` logic k´o theo t`. hˆ S hay ’` ’a th´ ıch u a a o e ue . khˆng? o T´.c l` ua S = {H1 , H2 , ..., Hn} |= A? Theo nguyˆn l´ suy diˆn, ta lˆp hˆ m´.i S = {H1 , H2 , ..., Hn , ¬A} c´ l` ˜ ey e a eo oa . . ˜ mˆu thuˆn hay khˆng? a a o M˘t kh´c, ta d˜ biˆt mˆi mˆt cˆng th´.c mˆnh dˆ dˆu tu.o.ng du.o.ng v´.i ˜ ´ooo `` a a ae u e ee o . . . ˜ ’ .´ o’ ’ hˆi cua mˆt tˆp c´c Clause, trong d´ mˆi Clause l` tuyˆ n cua mˆt sˆ c´c oaa oo a e o oa . .. . dˆy literal l` mˆt k´ hiˆu mˆnh dˆ ho˘c phu dinh cua k´ hiˆu mˆnh `a ’ ’. ’ye literal (o a aoye e e. e . . . . . ` ). Do d´ nˆu ta thay trong hˆ S mˆi cˆng th´.c bo.i hˆi c´c Clause tu.o.ng ˜o ´ ’oa dˆ e oe e o u . . .ng, th` ta du.o.c S tu.o.ng u.ng v´.i hˆi c´c Clause v` b`i to´n S |= A du.o.c u ´ ı ´ ooa aa a . . . .o.ng du.o.ng v´.i tˆp S ) c´ l` `a a qui vˆ b`i to´n: mˆt tˆp c´c Clause (m` hˆi tu e oaa ao oa oa .. . . ˜n hay khˆng? mˆu thuˆ a a o .o.ng ph´p thu.`.ng du.o.c d`ng l` phu.o.ng ph´p phˆn giai (resolution) ’ Phu a o .u a a a . lu.o.c nhu. sau: ’ ` ´ ao ’ cua Robinson dˆ xuˆ t m` nˆi dung c´ thˆ tr` b`y so . ea o e ınh a . Gia su. S c´ hai Clause: ’’ o ` C1 = D1 ∨ Q v` C2 = D2 ∨ ¬Q, trong d´ Q l` k´ hiˆu mˆnh dˆ. Khi d´ a o ay e e e o . . ta lˆp Clause m´.i C = D1 ∨ D2 b˘ ng c´ch khu. k´ hiˆu mˆnh dˆ Q v` ¬Q ` ` ’ye a o a a e e a . . . .o.ng u.ng trong C v` C rˆ i lˆp tuyˆ n m´.i C . Khi d´ C du.o.c goi l` giai ’ `. .a’ tu ´ 1a 2oa e o o . .c t`. c´c Clause C v` C . Dˆ d`ng thˆ y r˘ ng {C , C } |= C , v` do d´ ˜a a` ´a th´ u a u 1a e a o 2 1 2 hai tˆp S v` S = S ∪ {C } tu.o.ng u.ng v´.i nhau. a a ´ o . .o.ng ph´p giai du.o.c thu.c hiˆn trˆn nguyˆn l´ giai sau dˆy: ’ ey’ Phu a e e a . . . Cho S l` mˆt tˆp c´c Clause. Xuˆ t ph´t t`. S ta thu.c hiˆn liˆn tiˆp c´c ´ ´ aoaa a au ee ea .. . . ph´p giai th´.c, t´.c l` thˆm v`o S c´c giai th´.c cua bˆ t k` 2 Clause c´ tru.´.c ´ ’ ’ u’ay e u uae a a o o .o.c giai th´.c rˆng ho˘c ˜ ´ ’ (hai Clause c´ dang Q v` ¬Q) cho dˆn khi thu du . o. a e uo a . .c n`o n˜.a th` kˆt th´c. Khi d´ tˆp S l` mˆu ´ ’ i th´ a u khˆng c´ thˆm mˆt gia o oe o u ıe u oa aa . . .o.c giai th´.c rˆng . ˜ ˜ a’ ’ thuˆn, khi v` chı khi ta thu du . a uo . nguyˆn l´ phˆn giai ta c´ thˆ ´p dung cho nhiˆu c´ch th´.c kh´c nhau ’ `a ’ T` u eya o ea e u a . dˆ thu.c hiˆn phu.o.ng ph´p giai nh˘ m u.ng dung trong hˆ tri th´.c ch´.ng minh ’ ` ’ e. e a a´ e u u . . .
Chu.o.ng 2. Hˆ to´n mˆnh dˆ ` 54 ea e e . . t´ mˆu thuˆn cua mˆt tˆp c´c cˆng th´.c logic mˆnh dˆ ho˘c logic tˆn t`. ˜’ `a ınh a a oaao u e e. au .. . .c l` hˆi cua cˆng th´.c d´ cho ta kˆt qua l` mˆt cˆng th´.c ´ (predicate), t´ a o ’ o ’a o o u uo e u . . ` ´ dˆ ng nhˆ t sai. o a Th´ du 2.2.1 ı.  C1 . P ∨Q  (S ) C2 . Q   C3 . P (1, 2, giai th´.c) ’ C4 P u (3, 4, giai th´.c) ’ C5 u ˜ a’ o ’ oa Vˆy ta c´: S = {P ∨ Q, Q, P } l` mˆu thuˆn, khi v` chı khi hˆi cua n´ l` a o aa a . . .c A = (P ∨ Q) ∧ Q ∧ P l` dˆ ng nhˆ t sai. ` ´ cˆng th´ o u ao a Thˆt vˆy, ta chı cˆn biˆn dˆ i nhu. sau: ’ ’` ´ aa a eo .. A = (P ∨ Q) ∧ Q ∧ P ≡ (P ∨ Q) ∧ (Q ∨ P ) ≡ (P ∨ Q) ∧ (P ∨ Q) = F alse X X nhu. sau: ˜ ˜ ´ a’o Ta c´ cˆy dˆn xuˆ t cua rˆng oa a
.´ ` 2.3. Mˆt sˆ dinh l´ trong hˆ to´n mˆnh dˆ oo. y ea e e 55 . . ´ ` 2.3 Mˆt sˆ dinh l´ trong hˆ to´n mˆnh dˆ oo. y ea e e . . . ınh ` ’ 2.3.1 T´ dˆy du a ˜ ` ee` ´ ` ao ´ y’y Dinh l´ 2.3.1 Mˆi mˆt dinh l´ cua l´ thuyˆt tiˆn dˆ L dˆu l` dˆ ng nhˆ t y o o. e e a . . d´ng. u Ch´.ng minh: Ta dˆ d`ng kiˆ m tra du.o.c r˘ ng mˆi mˆt tiˆn dˆ t`. (A1) dˆn ’ ˜ ˜a ` o o e `u ´ u e e .a e e . ` ` ao ´ (A3) dˆu l` dˆ ng nhˆ t d´ng. e au M˘t kh´c theo dinh l´ 1.4.1 (chu.o.ng 1) qui t˘c Modus Ponens chuyˆ n ’ ´ a a y a e . . .c dˆ ng nhˆ t d´ng th`nh cˆng th´.c dˆ ng nhˆ t d´ng. Diˆu d´ ` ` ´ ´ ` c´c cˆng th´ o ao u au a o uo au eo ch´.ng to r˘ ng mˆi mˆt dinh l´ cua l´ thuyˆt tiˆn dˆ L dˆu l` dˆ ng nhˆ t ˜ ` ` ee` ´ ` ao ´ ’a y’y u o o. e e a . d´ng. u Bˆ dˆ 2.3.1 Gia su. A l` mˆt cˆng th´.c mˆnh dˆ v` B1 , B2 , ..., Bk l` c´c ’e o` `a ’’ aoo u e e aa . . .i bˆ phˆn bˆ I c´c gi´ tri chˆn l´ cua c´c biˆn ´ ´ ´ ´ a. ay’ a biˆn c´ m˘t trong A. Dˆi v´ o a o 0 a eoa oo. e . . sau: B1 , B2 , ..., Bk nhu ´ Bi , nˆu Bi = T e Bi = ´ ¬Bi , nˆu Bi = F e v` mˆt cˆng th´.c m´.i A . aoo u o . A, nˆu A nhˆn gi´ tri T dˆi v´.i bˆ phˆn bˆ I0 n´i trˆn ´ ´ ´ e a a. oooao oe . . A= .i bˆ phˆn bˆ I n´i trˆn ´ ´ ´ ¬A, nˆu A nhˆn gi´ tri F dˆi v´ o a o 0 o e e a a. oo. . Khi d´ ta c´: o o B1, B2 , ...., Bk A. ’ a. ay’ o Th´ du 2.3.1 Cho A = ¬(¬A → B ). Ta lˆp bang gi´ tri chˆn l´ cua cˆng ı. a . th´.c A nhu. sau: u
Chu.o.ng 2. Hˆ to´n mˆnh dˆ ` 56 ea e e . . A B ¬(¬A → B ) T T F T F F F T F F F T Gia su. ta lˆ y bˆ phˆn bˆ o. d`ng th´. 3: (F, T ) → F th` khi d´ ta c´ ´o ´ ’’ a o’ o a u ı o o . ’e o` ’ (theo A cua Bˆ dˆ 2.3.1): ¬A, B ¬¬(¬A → B ) hay l` a ¬A, B (¬A → B ). C`n nˆu lˆ y d`ng th´. 4: (F, F ) → T th` ta c´: ´´ oeao u ı o ¬A, ¬B ¬ (¬A → B ). Ch´.ng minh: Ta ch´.ng minh b˘ ng qui nap theo n l` sˆ c´c ph´p to´n c´ ` ´ u u a aoa e ao . m˘t trong cˆng th´.c A. a o u . 1. n = 0: Khi d´ A chı ch´.a d´ng mˆt biˆn B1 v` ta dˆ d`ng c´ du.o.c: ˜a ´ ’uu o o e a e o . . B1 B1 v` ¬B1 ¬B1 luˆn luˆn d´ng. a o ou 2. Gia su. bˆ dˆ d´ng v´.i moi j < n. ’e ’’ o` u o . 3. Ch´.ng minh qui nap: bˆ dˆ c˜ng d´ng v´.i j = n. ’e o`u u u o . Ta x´t c´c tru.`.ng ho.p sau dˆy: ea o a . • Tru.`.ng ho.p 1: A = ¬B , trong d´ B c´ ´ ho.n n ph´p to´n. X´t o o o ıt e a e . ´ ´ a. ay’ a mˆt bˆ phˆn bˆ I0 n`o d´ c´c gi´ tri chˆn l´ cua c´c biˆn c´ m˘t ooao a oa eoa .. . trong A. (1a) Nˆu B nhˆn gi´ tri T th` B = B v` A nhˆn gi´ tri F dˆi v´.i ´ ´ e a a. ı a a a. oo . . .c: ´ bˆ phˆn bˆ I0 n`y. Khi d´ ta c´ cˆng th´ oao a o oo u . A = ¬A = ¬¬B = B = B .
.´ ` 2.3. Mˆt sˆ dinh l´ trong hˆ to´n mˆnh dˆ oo. y ea e e 57 . . ´ ’ ’ Theo gia thiˆt qui nap cua B : B1, B2, ..., Bk e B , do d´: o . B1, B2 , ..., Bk B . Vˆy B1 , B2 , ..., Bk A . a . ´ ´ (1b) Nˆu B nhˆn gi´ tri F th` B = ¬B v` A nhˆn gi´ tri T dˆi e a a. ı a a a. o . . .i bˆ phˆn bˆ I n`y. Do d´ ta c´ cˆng th´.c: ´ v´ o a o 0 a o. o oo u A = A = ¬B . ´ ’ ’ Theo gia thiˆt qui nap cua B : B1 , B2 , ..., Bk e B , nˆn ta c´: e o . B1, B2 , ..., Bk ¬B Vˆy B1, B2 , ..., Bk A . a . • Tru.`.ng ho.p 2: A = (B → C ), trong d´ B v` C c´ sˆ ph´p to´n ´t ´ o o a oo e aı . ho.n n so v´.i A. Khi d´, theo gia thiˆt qui nap: ´ ’ o o e . B1, B2 , ..., Bk B v` B1 , B2, ..., Bk a C. (2a) Nˆu B nhˆn gi´ tri F th` A nhˆn gi´ tri T . Khi d´ cˆng th´.c ´ e a a. ı a a. oo u . . B = ¬B v` A = A. Do d´ B1 , B2, ..., Bk ¬B . a o ´ ’ M˘t kh´c, theo hˆ qua 2.1.2 (c) v` qui t˘c MP: a a e a a . . B1, B2 , ..., Bk B → C , nhu.ng B → C ch´ l` A . ınh a Vˆy B1, B2 , ..., Bk a A. . ´ (2b) Nˆu C nhˆn gi´ tri T th` A c˜ng nhˆn gi´ tri T . Do d´ C = C e a a. ı u a a. o . . ´ ae` ’ v` A = A. Theo gia thiˆt qui nap: B1 , B2 , ..., Bk C v` tiˆn dˆ a e e . . qui t˘c Modus Ponens, ´ (A1) ta c´: B1 , B2 , ..., Bk B → C nh` o o a .ng B → C ch´ l` A . Vˆy B , B , ..., B nhu ınh a a A. . 1 2 k ´ (2c) Nˆu B nhˆn gi´ tri T v` C nhˆn gi´ tri F th` A nhˆn gi´ tri e a a. a a a. ı a a. . . . F . Do d´ B = B , C = ¬C v` A = ¬A. o a e’ Ta c´: B1, B2 , ..., Bk B v` B1 , B2, ..., Bk ¬C . Do d´ theo hˆ qua o a o . ´ 2.1.2 (f) v` qui t˘c Modus Ponens: B1, B2 , ..., Bk ¬(B → C ), a a nhu.ng ¬(B → C ) ch´nh l` A . ı a Vˆy B1, B2 , ..., Bk a A .