Giáo trình Logic toán

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (298.14 KB, 20 trang )

(1)Logic Toán Trần Thọ Châu NXB Đại học quốc gia Hà Nội 2007, 204 Tr.. Từ khoá: Logic toán, Đại số mệnh đề, Hàm đại số logic, logic mờ, Định lý suy diễn, Logic mệnh đề, Tính đầy đủ, Tính phi mâu thuẫn, Lượng từ, Ngôn ngữ Prolog, Tân từ Fall.. 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ả.. Lop12.net.

(2) Mu.c lu.c `u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Lò.i mo’. dâ ` 1 Da.i sô´ mê.nh dê 1.1 Các phép toán và ba’ng chân lý . . . . . . 1.1.1 Phép phu’ di.nh (¬, not) . . . . . . . 1.1.2 Phép và (∧, and, hô.i) . . . . . . . . 1.1.3 Phép hay là (∨, or, tuyê’n) . . . . . 1.1.4 Phép kéo theo (→) . . . . . . . . . ↔) . . . . . . 1.1.5 Phép tu.o.ng du.o.ng (↔ . ` . . . . . . . . . . . . . 1.2 Công thú c mê.nh dê 1.3 Mô.t sô´ di.nh nghı̃a . . . . . . . . . . . . . 1.3.1 Hàm da.i sô´ logic . . . . . . . . . . 1.3.2 Su.. dô`ng nhâ´t dúng - dô`ng nhâ´t sai 1.4 Mô.t sô´ tı́nh châ´t . . . . . . . . . . . . . . ` . 1.5 Da.ng chuâ’n tă´c cu’a công thú.c mê.nh dê 1.5.1 Da.ng chuâ’n tă´c tuyê’n và chuâ’n tă´c 1.5.2 Da.ng chuâ’n tă´c hoàn toàn . . . . . ` y du’ cu’a các phép toán . . . . . 1.6 Các hê. dâ 1.7 Bài tâ.p chu.o.ng 1 . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . hô.i . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. 5 7 8 10 10 10 11 12 12 16 16 18 22 23 23 24 25 34. ` 39 2 Hê. toán mê.nh dê ` trong hê. toán mê.nh dê ` . . . . . . . . . . . . . . . . 40 2.1 Hê. tiên dê 2.1.1 Mô.t sô´ di.nh nghı̃a co. ba’n . . . . . . . . . . . . . . . . 40 2.1.2 Các tı́nh châ´t . . . . . . . . . . . . . . . . . . . . . . . 42. Lop12.net.

(3) 2. MU . C LU .C. 2.2. 2.3. 2.4 2.5 2.6 2.7 2.8. ` trong hê. toán mê.nh dê ` . . . . . . . 2.1.3 Lý thuyê´t tiên dê ` . . . . . . . 2.1.4 Di.nh lý suy diê˜n trong hê. toán mê.nh dê ` Nguyên lý suy diê˜n và bài toán lâ.p luâ.n trong logic mê.nh dê 2.2.1 Nguyên lý suy diê˜n . . . . . . . . . . . . . . . . . . . ` . . . . . . . . 2.2.2 Bài toán lâ.p luâ.n trong logic mê.nh dê ` . . . . . . . . . . . . Mô.t sô´ di.nh lý trong hê. toán mê.nh dê ` y du’ . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Tı́nh dâ 2.3.2 Tı́nh phi mâu thuâ˜n . . . . . . . . . . . . . . . . . . 2.3.3 Tı́nh dô.c lâ.p . . . . . . . . . . . ` logic da tri. . . . . Gió.i thiê.u vài nét vê ` Tı́nh quyê´t di.nh cu’a hê. toán mê.nh dê ` khác . . . . . . . . . Mô.t sô´ hê. tiên dê ` y du’ cho bài toán Áp du.ng di.nh lý dâ ` . . . . . . . . . . . . . . . . . mê.nh dê Bài tâ.p chu.o.ng 2 . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . suy diê˜n trong . . . . . . . . . . . . . . . . . .. Lop12.net. 43 44 52 52 52 55 55 58 59 61 62 62. . . . . . . . . .. 70 71 77 81 81 83 85 85 86 89. . . . . .. 92 93 100 100 103. . . . . . . . . . . . . logic . . . . 64 . . . . 66. toán tân tù. Các lu.o..ng tù. . . . . . . . . . . . . . . . . . . . . . . . . . . Các khái niê.m và di.nh nghı̃a . . . . . . . . . . . . . . . . . . Minh hoa., su.. dô`ng nhâ´t dúng và mô hı̀nh . . . . . . . . . . 3.3.1 Minh hoa. . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Tı́nh thu..c hiê.n du.o..c . . . . . . . . . . . . . . . . . . 3.3.3 Su.. dô`ng nhâ´t dúng (hă` ng dúng) . . . . . . . . . . . 3.3.4 Mô hı̀nh . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.5 Mô.t sô´ hê. qua’ . . . . . . . . . . . . . . . . . . . . . . 3.3.6 Mô.t sô´ di.nh nghı̃a khác . . . . . . . . . . . . . . . . 3.3.7 Các công thú.c logic dô`ng nhâ´t dúng trong hê. toán tân tù. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.8 Da.ng chuâ’n tă´c trong logic tân tù. . . . . . . . . . . . 3.4 Lý thuyê´t tân tù. câ´p 1K . . . . . . . . . . . . . . . . . . . . 3.4.1 Di.nh nghı̃a . . . . . . . . . . . . . . . . . . . . . . . ` Lý thuyê´t tân tù. câ´p 1K . . . . . 3.4.2 Mô.t vài thı́ du. vê. 3 Hê. 3.1 3.2 3.3. . . . . . . . . . . . ..

(4) MU . C LU .C 3.5 3.6. 3.7 3.8. 3. Di.nh lý suy diê˜n trong logic tân tù. . . . . . . . . . . . . . . . ` y du’ cu’a logic tân tù. . . . . . . . . Tı́nh phi mâu thuâ˜n và dâ 3.6.1 Các khái niê.m và di.nh nghı̃a . . . . . . . . . . . . . . . 3.6.2 Tı́nh phi mâu thuâ˜n cu’a lý thuyê´t tân tù. câ´p 1 PP . . 3.6.3 Mô.t sô´ di.nh lý trong lý thuyê´t tân tù. câ´p 1 K . . . . . ` y du’ cu’a lý thuyê´t tân tù. câ´p 1K . . . . . . . 3.6.4 Tı́nh dâ Áp du.ng trong chú.ng minh di.nh lý cu’a lý thuyê´t tân tù. câ´p 1 Bài tâ.p chu.o.ng 3 . . . . . . . . . . . . . . . . . . . . . . . . .. 4 Ngôn ngũ. PROLOG `u . . . . . . . . . . . . . . . . . . . . . . 4.1 Mo’. dâ 4.2 Ngôn ngũ. PROLOG . . . . . . . . . . . . . . . 4.2.1 Qui tă´c cú pháp . . . . . . . . . . . . . . 4.2.2 Các kiê’u dô´i tu.o..ng . . . . . . . . . . . . 4.2.3 Các phép toán, quan hê. và hàm chuâ’n . 4.3 Câ´u trúc cu’a chu.o.ng trı̀nh PROLOG . . . . . . 4.4 Tân tù. FAIL, nhát că´t (!) và tân tù. NOT . . . 4.5 Phu.o.ng thú.c xuâ´t nhâ.p dũ. liê.u . . . . . . . . . 4.5.1 Phu.o.ng thú.c xuâ´t dũ. liê.u . . . . . . . . 4.5.2 Phu.o.ng thú.c nhâ.p dũ. liê.u . . . . . . . . ` lâ.p trı̀nh PROLOG 4.6 Mô.t sô´ thı́ du. minh hoa. vê 4.7 Bài tâ.p chu.o.ng 4 . . . . . . . . . . . . . . . . . 5 Logic mò. `u . . . . . . . . . . . . . . . . . . . 5.1 Mo’. dâ 5.2 Các khái niê.m co. ba’n . . . . . . . . . . . ` biê´n ngôn ngũ. . . . . . . 5.3 Mô.t sô´ chú ý vê 5.4 Các phép toán trên tâ.p mò. . . . . . . . . 5.5 Các tı́nh châ´t trên tâ.p mò. . . . . . . . . . 5.6 Quan hê. mò. . . . . . . . . . . . . . . . . . 5.6.1 Các phép toán trên quan hê. mò. . . 5.6.2 Mô.t sô´ tı́nh châ´t trên quan hê. mò. .. Lop12.net. . . . . . . . .. . . . . . . . .. . . . . . . . .. . . . . . . . . . . . .. . . . . . . . .. . . . . . . . . . . . .. . . . . . . . .. . . . . . . . . . . . .. . . . . . . . .. . . . . . . . . . . . .. . . . . . . . .. . . . . . . . . . . . .. . . . . . . . .. . . . . . . . . . . . .. . . . . . . . .. 104 110 110 111 112 120 121 123. . . . . . . . . . . . .. 126 . 127 . 131 . 131 . 131 . 137 . 139 . 141 . 143 . 143 . 145 . 148 . 162. . . . . . . . .. 166 . 167 . 169 . 172 . 176 . 177 . 179 . 180 . 180.

(5) 4. MU . C LU .C Logic mò. . . . . . . . . . . . . . . . . . . . . . . `u . . . . . . . . . . . . . . . . . . . 5.7.1 Mo’. dâ 5.7.2 Các phép kê´t nô´i . . . . . . . . . . . . . . 5.7.3 Phép tuyê’n (OR-disjunction) . . . . . . . 5.7.4 Phép kéo theo (Implication [Zadeh 1973]) 5.8 Su.. dô`ng nhâ´t dúng mò. (Fuzzy Tautologies) . . . 5.9 Các phép toán t − norm T và t − conorm S . . . 5.10 Phép ho..p thành (Composition) . . . . . . . . . . 5.11 Phu.o.ng trı̀nh quan hê. mò. . . . . . . . . . . . . . 5.12 Lâ.p luâ.n mò. (Fuzzy Reasoning) . . . . . . . . . . 5.12.1 Thuâ.t toán mò. . . . . . . . . . . . . . . . 5.12.2 Lâ.p luâ.n mò. . . . . . . . . . . . . . . . . 5.12.3 Mô.t sô´ phép suy diê˜n mò. khác . . . . . . 5.13 Các luâ.t ho..p thành cu’a suy diê˜n . . . . . . . . . . 5.14 Ú ng du.ng . . . . . . . . . . . . . . . . . . . . . . 5.15 Bài tâ.p chu.o.ng 5 . . . . . . . . . . . . . . . . . Tài liê.u tham kha’o . . . . . . . . . . . . . . . . . . 5.7. Lop12.net. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .. 180 180 181 183 183 185 185 187 187 189 190 192 192 194 198 199 203.

(6) `u Lò.i mo’. dâ Ta biê´t ră` ng Logic Toán là mô.t ngành khoa ho.c lý thuyê´t gă´n chă.t vó.i tu. duy suy diê˜n cu’a con ngu.ò.i và du.o..c phát triê’n trên co. so’. tuân thu’ nghiêm ngă.t các qui luâ.t lâ.p luâ.n cu’a tu. duy logic hı̀nh thú.c. Ho.n nũ.a, Logic Toán nghiên cú.u phu.o.ng pháp suy luâ.n trong Toán ho.c, phu.o.ng pháp chú.ng minh và kha’ năng suy diê˜n dâ˜n dê´n các di.nh lý trong mô.t lý thuyê´t. Các qui luâ.t co. ba’n cu’a logic hı̀nh thú.c dã du.o..c phát triê’n tù. thò.i Aristote (384-322 tru.ó.c Công nguyên). Su.. phát triê’n cu’a các ngành khoa ho.c lý thuyê´t tù. thò.i văn minh cô’ Hy La.p cho tó.i thò.i hiê.n da.i ngày nay ` u tra’i qua nhiê ` u bu.ó.c thăng trâ ` m, và có nhũ.ng giai doa.n không phát triê’n dê du.o..c, ngu.ng trê., hoă.c phát triê’n râ´t châ.m cha.p. Tuy vâ.y, mô˜i mô.t giai doa.n ` u dê’ la.i nhũ.ng dâ´u â´n vô cùng quı́ giá, dâ´y là nhũ.ng phát minh vı̃ da.i dê cu’a các nhà khoa ho.c nói chung và ngành Toán ho.c nói riêng, chă’ng ha.n các ` phép tı́nh vi phân vào thê´ ky’ 16 – 17, phát minh cu’a Newton, Leibnitz vê ` u thê´ ky’ 20... lý thuyê´t tâ.p ho..p Cantor vào cuô´i thê´ ky’ 19 và dâ ` co. ba’n nhâ´t cu’a logic Tâ.p giáo trı̀nh này nhă` m gió.i thiê.u mô.t sô´ vâ´n dê ` u nhà khoa ho.c quan tâm nghiên Toán và logic mò. dã và dang du.o..c nhiê . . cú u, ú ng du.ng. Giáo trı̀nh du.o..c chia thành 5 chu.o.ng: ` vó.i mu.c dı́ch là mô hı̀nh hoá ` logic mê.nh dê Chu.o.ng 1 và 2 trı̀nh bày vê ` là hê. thô´ng logic do.n gia’n mà do.n vi. co. quá trı̀nh suy diê˜n. Logic mê.nh dê ` mang nô.i dung cu’a các phán doán, mô˜i mô.t phán doán ba’n là các mê.nh dê ` phú.c ho..p du.o..c có mô.t giá tri. chân lý hoă.c là dúng hoă.c là sai. Các mê.nh dê. Lop12.net.

(7) `u Lò.i mo’. dâ. 6. ` co. ba’n nhò. các phép toán logic nhu. “không” , “và” lâ.p nên tù. các mê.nh dê ` logic tân tù. , “hay là” , “nê´u thı̀”, “khi và chı’ khi”. Chu.o.ng 3 trı̀nh bày vê `. là mô.t da.ng tô’ng quát hoá cu’a logic mê.nh dê . . . Logic tân tù còn du o. c go.i là logic câ´p 1 (first-order logic). Các tân tù. ` u biê´n, và tra’ vê ` giá tri. Boole. (predicates) là các hàm theo không hoă.c nhiê Vı̀ vâ.y tân tù. có lúc dúng, có lúc không dúng tuỳ thuô.c vào các giá tri. cu. thê’ cu’a các dô´i cu’a nó. Logic tân tù. cũng du.o..c dùng trong các hê. thô´ng suy luâ.n hoă.c các hê. thô´ng chuyên gia, ... Chu.o.ng 4 trı̀nh bày nhũ.ng nét co. ba’n cu’a ngôn ngũ. PROLOG, viê´t tă´t cu’a “Programming in Logic”. Logic tân tù. có du’ kha’ năng diê˜n ta’ dê’ ta.o nên co. so’. cho ngôn ngũ. lâ.p trı̀nh Prolog cu’a chu.o.ng này. ` co. ba’n cu’a logic mò. (Fuzzy Logic) Chu.o.ng 5 trı̀nh bày nhũ.ng vâ´n dê xuâ´t phát tù. lý thuyê´t tâ.p mò. cu’a Zadeh ra dò.i tù. 1965 dê´n các phép ho..p thành cùng vó.i nhũ.ng phu.o.ng pháp suy diê˜n thông qua quan hê. mò. thê’ ` u cách thú.c khác nhau du.o..c trı̀nh hiê.n du.ó.i da.ng phép kéo theo bă` ng nhiê ` y du’ kê´t ho..p vó.i các thı́ du. minh hoa.. Viê.c vâ.n du.ng các mô to. suy bày dâ ` n vó.i tên tuô’i cu’a các nhà khoa diê˜n du..a trên các toán tu’. ho..p thành gă´n liê ` u khiê’n mò., ` u lı̃nh vu..c khác nhau nhu. diê ho.c dã du.o..c ú.ng du.ng trong nhiê hê. chuyên gia, trı́ tuê. nhân ta.o, chê´ ta.o Robot, các máy móc chuyên du.ng, di.ch thuâ.t... Giáo trı̀nh có thê’ du.o..c su’. du.ng rô.ng rãi cho các dô´i tu.o..ng sinh viên, ho.c viên cao ho.c, nghiên cú.u sinh toán-tin và nhũ.ng ai quan tâm dê´n logic toán. Tuy dã cô´ gă´ng song chă´c chă´n giáo trı̀nh không tránh kho’i nhũ.ng thiê´u sót. Tác gia’ râ´t mong nhâ.n du.o..c su.. góp ý cu’a ba.n do.c. Xin chân thành ca’m o.n! ` : Khoa Toán-Co.-Tin, Tru.ò.ng Da.i ho.c Khoa ho.c Tu.. Thu. góp ý xin gu’.i vê nhiên, Da.i ho.c Quô´c gia Hà Nô.i, 334 - Nguyê˜n Trãi, Quâ.n Thanh Xuân, Hà Nô.i. Tác gia’. Lop12.net.

(8) Chu.o.ng 1 ` Da.i sô´ mê.nh dê. 1.1. Các phép toán và ba’ng chân lý . . . . . . . . . .. 8. 1.1.1. Phép phu’ di.nh (¬, not) . . . . . . . . . . . . . . . 10. 1.1.2 1.1.3. Phép và (∧, and, hô.i) . . . . . . . . . . . . . . . . 10 Phép hay là (∨, or, tuyê’n) . . . . . . . . . . . . . . 10. 1.1.4. Phép kéo theo (→) . . . . . . . . . . . . . . . . . . 11. ↔) . . . . . . . . . . . . . . . 12 Phép tu.o.ng du.o.ng (↔ ` . . . . . . . . . . . . . . . . . Công thú.c mê.nh dê 12 Mô.t sô´ di.nh nghı̃a . . . . . . . . . . . . . . . . . . 16. 1.1.5 1.2 1.3. 1.3.1 1.3.2 1.4 1.5. Mô.t sô´ tı́nh châ´t . . . . . . . . . . . . . . . . . . . ´c cu’a công thú.c mê.nh dê ` . . . . . Da.ng chuâ’n tă 1.5.1 1.5.2. 1.6 1.7. Hàm da.i sô´ logic . . . . . . . . . . . . . . . . . . . 16 Su.. dô`ng nhâ´t dúng - dô`ng nhâ´t sai . . . . . . . . . 18 22 23. Da.ng chuâ’n tă´c tuyê’n và chuâ’n tă´c hô.i . . . . . . 23 Da.ng chuâ’n tă´c hoàn toàn . . . . . . . . . . . . . . 24. ` y du’ cu’a các phép toán . . . . . . . . . Các hê. dâ Bài tâ.p chu.o.ng 1 . . . . . . . . . . . . . . . . . .. Lop12.net. 25 34.

(9) ` Chu.o.ng 1. Da.i sô´ mê.nh dê. 8. ` phú.c ho..p tù. các mê.nh Thông thu.ò.ng chúng ta thành lâ.p các mê.nh dê ` do.n gia’n. Trong chu.o.ng này, chúng ta sẽ di sâu nghiên cú.u dâ ` y du’ ba’n dê ` và tu. duy suy diê˜n cu’a nó mô.t cách chă.t chẽ, logic châ´t cu’a da.i sô´ mê.nh dê và mang tı́nh thu..c tiê˜n.. 1.1. Các phép toán và ba’ng chân lý. ` u biê´t con ngu.ò.i có kha’ năng pha’n ánh mô´i quan hê. hiê.n thu..c Chúng ta dê ` . Các mê.nh dê ` dó du.o..c du.a ra du.ó.i giũ.a các su.. vâ.t bă` ng nhũ.ng mê.nh dê ` u hı̀nh thú.c khác nhau, chă’ng ha.n nhu. mô.t lò.i nói, mô.t câu văn, mô.t nhiê công thú.c Toán, Lý, Hoá, hay su.. mô pho’ng cu’a mô.t bú.c tranh v.v.., nhu.ng ` này có mang dâ ` y du’ ý nghı̃a nhâ´t di.nh hay co. ba’n trong dó là các mê.nh dê ` dó có mang theo tı́nh châ´t hiê.n thu..c du.ó.i mô.t không, nghı̃a là các mê.nh dê ` suông, vô nghı̃a, và hı̀nh thú.c nhâ´t di.nh, chú. không pha’i là mô.t mê.nh dê cũng không pha’i là nhũ.ng lò.i nói chú.a du..ng mô.t ý nghı̃ không nghiêm túc. ` pha’n ánh mô.t su.. viê.c nào dó theo mô.t cách thú.c nhâ´t di.nh Mô.t mê.nh dê và su.. viê.c dó pha’n ánh tı́nh chân thu..c theo cách trên thı̀ du.o..c go.i là mô.t ` dúng; Trái la.i mê.nh dê ` dó du.o..c go.i là mô.t mê.nh dê ` sai. mê.nh dê . ` chúng ta quan tâm dă.c biê.t trong Toán ho.c là o’. chô˜: Thu. c châ´t vâ´n dê ` hoă.c là dúng hoă.c là sai, và không có mô.t mê.nh dê ` nào “Mô˜i mô.t mê.nh dê vù.a dúng la.i vù.a sai”. Dây chı́nh là nô.i dung cu’a di.nh lý 2 - giá tri.. ` du.o..c chia thành hai ló.p con: mô.t ló.p Bo’.i vâ.y, ló.p tâ´t ca’ các mê.nh dê ` dúng và mô.t ló.p gô`m tâ´t ca’ các mê.nh dê ` sai. Mô˜i gô`m tâ´t ca’ các mê.nh dê ` thuô.c mô.t trong các ló.p dó sẽ nhâ.n mô.t giá tri. chân lý dúng (True, mê.nh dê viê´t tă´t là T) hoă.c sai (False, viê´t tă´t là F). ` bă` ng các chũ. cái hoa A, B, C, ... còn các biê´n Ta ký hiê.u các mê.nh dê ` bă` ng các chũ. cái A, B, C, ... và chúng có kha’ năng nhâ.n các giá tri. mê.nh dê chân lý {T, F } hoă.c {1, 0}. Thı́ du. 1.1.1. Lop12.net.

(10) 1.1. Các phép toán và ba’ng chân lý. 9. 1. “Trên mă.t trăng không có ngu.ò.i” (T) 2. “35 chia hê´t cho 6” (F) 3. “Bác Hô` sinh ngày 19 tháng 5 năm 1890” (T) Chú ý ră` ng trong di.nh lý 2 - giá tri., ngu.ò.i ta chı’ phát biê’u ră` ng: mô˜i ` hoă.c là dúng, hoă.c là sai, nhu.ng không khă’ng di.nh du.o..c ră` ng mô.t mê.nh dê ` ta có thê’ quyê´t di.nh du.o..c liê.u nó dúng hay không, chă’ng mô˜i mô.t mê.nh dê ha.n di.nh lý cuô´i cùng cu’a Fermat [1], gia’ thuyê´t Continuum [5]. Tâ´t nhiên, ` này hoă.c là dúng, hoă.c là sai. mô˜i mô.t mê.nh dê Di.nh lý cuô´i cùng cu’a Fermat dã tô`n ta.i trên 350 năm, và mãi cho dê´n năm 1986, G. Faltings [1], mô.t nhà Toán ho.c tre’ 26 tuô’i ngu.ò.i Dú.c dã ` mô.t công trı̀nh trong hı̀nh ho.c da.i sô´. Gia’i du.o..c nhâ.n gia’i thu.o’.ng Fields vê thu.o’.ng Fields là gia’i thu.o’.ng dành cho các nhà Toán ho.c tre’ tuô’i du.ó.i 40 ` n và mô˜i lâ ` n không quá 4 ngu.ò.i. Nhu. chúng tuô’i, 4 năm mó.i câ´p mô.t lâ ta dã biê´t gia’i thu.o’.ng Nobel không giành cho các nhà Toán ho.c, nên gia’i thu.o’.ng Fields du.o..c xem nhu. là gia’i “Nobel” cho Toán ho.c và gia’i thu.o’.ng du.o..c coi là mô.t trong nhũ.ng vinh du.. ló.n nhâ´t dô´i vó.i mô.t ngu.ò.i làm Toán ` chú.ng minh ho.c. Ngoài ra G. Falting còn du.a ra nhũ.ng ý tu.o’.ng co. ba’n vê di.nh lý cuô´i cùng cu’a Fermat vào tháng 9 năm 1994 (xem Gerd Falting the Proof of Fermat’s Last Theorem by R. Taylor and A. Wiles Notices of the AMS, July 1995, p. 743 - 746), nhu.ng vào năm 1997, nhà Toán ho.c ngu.ò.i Anh là A. Weil sinh năm 1953 dã chú.ng minh tro.n ve.n di.nh lý này bă` ng mô.t phu.o.ng pháp khác và ông du.o..c nhâ.n gia’i thu.o’.ng râ´t dă.c biê.t, năm â´y ông dã ngoài 40 tuô’i nên không thê’ trao gia’i thu.o’.ng Fields. Còn gia’ thuyê´t Continuum dã du.o..c nhà Toán ho.c Mỹ là P.J Cohen [5] gia’i quyê´t vào năm 1966 và ông dã du.o..c nhâ.n gia’i thu.o’.ng Fields. ` u râ´t hiê’n nhiên là chúng ta có thê’ di tù. mô.t sô´ mê.nh dê ` dã cho Mô.t diê ` mó.i nhò. mô.t sô´ tù. nô´i, chă’ng ha.n dô´i vó.i mê.nh dê ` A, dê´n mô.t mê.nh dê chúng ta có thê’ lâ´y phu’ di.nh cu’a nó “không A” (viê´t tă´t là ¬A), hoă.c dô´i ` dã cho A và B, ta có thê’ nô´i các mê.nh dê ` dó vó.i nhau “A vó.i hai mê.nh dê và B” (viê´t tă´t là A ∧ B), “A hay là B” (viê´t tă´t là A ∨ B), “Nê´u A thı̀ B”. Lop12.net.

(11) ` Chu.o.ng 1. Da.i sô´ mê.nh dê. 10. (viê´t tă´t là A → B), và “A khi và chı’ khi B” (viê´t tă´t là A ↔ B). Các ký hiê.u ¬, ∧, ∨, →, ↔ du.o..c go.i là các phép toán logic. Các phép toán này du.o..c xác di.nh du..a theo các ba’ng chân lý du.ó.i dây.. 1.1.1. Phép phu’ di.nh (¬, not) A T F. ¬A F T. Nhu. vâ.y nghı̃a là khi A nhâ.n giá tri. T thı̀ ¬A nhâ.n giá tri. F, và khi A nhâ.n giá tri. F thı̀ ¬A nhâ.n giá tri. T.. 1.1.2. Phép và (∧, and, hô.i) A T T F F. B T F T F. A∧B T F F F. ` A ∧ B nhâ.n giá tri. T, khi và chı’ khi A và B dê ` u nhâ.n giá Vâ.y mê.nh dê tri. T.. 1.1.3. Phép hay là (∨, or, tuyê’n) A T T F F. B T F T F. A∨B T T T F. ` A ∨ B nhâ.n giá tri. F, khi và chı’ khi A và B dê ` u nhâ.n giá Vâ.y mê.nh dê tri. F.. Lop12.net.

(12) 1.1. Các phép toán và ba’ng chân lý. 1.1.4. 11. Phép kéo theo (→) A T T F F. B T F T F. (A→B) T F T T. ` A → B nhâ.n giá tri. F, khi và chı’ khi A (gia’ thiê´t) nhâ.n Vâ.y mê.nh dê giá tri. T và B (kê´t luâ.n) nhâ.n giá tri. F. ` “Nê´u A thı̀ B” du.o..c su’. du.ng nhu.ng Trong mô.t vài tru.ò.ng ho..p, mê.nh dê ` mô.t cách dâ ` y du’, không quan tâm dê´n các giá tri. chân lý cu’a các mê.nh dê ` sau: chă’ng ha.n nhu. các mê.nh dê 1. Nê´u 1+1=2 thı̀ Paris là Thu’ dô cu’a nu.ó.c Pháp. 2. Nê´u 1+16=2 thı̀ Paris là Thu’ dô cu’a nu.ó.c Pháp. 3. Nê´u 1+16=2 thı̀ Rome là Thu’ dô cu’a nu.ó.c Pháp. ` trên dê ` u nhâ.n giá tri. chân lý là T, Ta dê˜ dàng nhâ.n thâ´y ca’ 3 mê.nh dê . . nhu ng mô´i liên hê. giũ a gia’ thiê´t A và kê´t luâ.n B không ăn khó.p vó.i nhau. ` , chúng ta pha’i Do dó dê’ da’m ba’o tı́nh logic và chă.t chẽ cua’ mô.t mê.ng dê su’. du.ng mô´i quan hê. dó sao cho giũ.a gia’ thiê´t A và kê´t luâ.n B pha’i có mô´i quan hê. xác di.nh, thu.ò.ng là nguyên nhân. ` “Nê´u A thı̀ Ngoài ra, nói riêng trong thu..c tê´, ngu.ò.i ta hay dùng mê.nh dê . . . . . B” du ó i mô.t hı̀nh thú c khác, không mâu thuâ˜n và hay du o. c su’. du.ng rô.ng rãi, chă’ng ha.n: “Nê´u ba.n có thò.i gian thı̀ ba.n dê´n thăm tôi”, cũng du.o..c hiê’u theo nghı̃a là: ` u này luôn “Nê´u ba.n không dê´n thăm tôi thı̀ ba.n không có thò.i gian”. Diê luôn dúng vı̀ theo luâ.t logic sau dây: ` :“A → B” tu.o.ng du.o.ng vó.i “¬B → ¬A” Mê.nh dê. Lop12.net.

(13) ` Chu.o.ng 1. Da.i sô´ mê.nh dê. 12. 1.1.5. ↔) Phép tu.o.ng du.o.ng (↔ A T T F F. B T F T F. (A↔B) T F F T. ` A ↔ B nhâ.n giá tri. T, khi và chı’ khi A và B nhâ.n cùng Vâ.y mê.nh dê giá tri... 1.2. ` Công thú.c mê.nh dê. ` là mê.nh dê ` du.o..c lâ.p nên tù. các chũ. Di.nh nghı̃a 1.2.1 Công thú.c mê.nh dê cái La-tinh A, B, C, ... và kê’ ca’ các chũ. cái La-tinh có chı’ sô´ A1 , B1, C1 , ... nhò. các phép toán logic. ` bă` ng Mô.t cách chı́nh xác ho.n, chúng ta di.nh nghı̃a công thú.c mê.nh dê . cách dê. quy nhu sau: ` u là (1) Tâ´t ca’ các chũ. cái La-tinh , kê’ ca’ các chũ. cái La-tinh có chı’ sô´ dê . công thú c (2) Nê´u A và B là các công thú.c thı̀ (¬A), (A ∧ B), (A ∨ B), (A →B), (A ↔ B) cũng là công thú.c (3) Mô.t biê’u thú.c là mô.t công thú.c, nê´u nó du.o..c lâ.p nên tù. co. so’. (1) và (2). Mô˜i mô.t phân bô´ các giá tri. chân lý cu’a các biê´n có mă.t trong công thú.c cho ta mô.t giá tri. chân lý cu’a công thú.c. Do vâ.y, mô˜i mô.t công thú.c mê.nh ` xác di.nh mô.t hàm da.i sô´ logic nào dó. Hàm này du.o..c xác di.nh du..a vào dê ba’ng chân lý cu’a công thú.c dã cho.. Lop12.net.

(14) ` 1.2. Công thú.c mê.nh dê. 13. Thı́ du. 1.2.1 Cho công thú.c A = (((¬A) ∨ B) → C). Tı̀m hàm da.i sô´ logic tu.o.ng ú.ng cu’a công thú.c A? ` y du’ cu’a A. Tru.ó.c hê´t ta lâ.p ba’ng chân lý dâ Mô˜i dòng là mô.t bô. phân bô´ các giá tri. chân lý cu’a các biê´n A, B, C và . . tu o ng ú.ng là mô.t giá cu’a công thú.c A. A B T T T T T F T F F T F T F F F F. C T F T F T F T F. ¬A F F F F T T T T. (¬A) ∨ B T T F F T T T T. A T F T T T F T F. Vâ.y chúng ta dê˜ dàng xác di.nh du.o..c mô.t hàm da.i sô´ logic 3 biê´n f : {T, F}3 → {T, F} du..a vào ba’ng chân lý cu’a A nhu. sau: f (T,T,T) =T f (F, T,T) =T f (T,T,F) =F f (F, T,F) =F f (T,F,T) =T f (F,F,T) =T f (T,F,F) =T f (F, F,F) =F Chú ý ` có chú.a n biê´n mê.nh dê ` thı̀ ba’ng chân lý cu’a 1. Nê´u công thú.c mê.nh dê . . n công thú c dã cho pha’i chú a 2 bô. phân bô´ các giá tri. chân lý cu’a n ` y du’ 2n bô. phân bô´ này? biê´n dó. Làm thê´ nào dê’ có thê’ viê´t dâ .. ` n thu..c hiê.n “thuâ Chúng ta chı’ câ . t chia dôi” du o. c dâ˜n ra theo cách quy na.p cu’a biê´n n: • n = 2: Khi dó 22 = 4 và chia 2 cho kê´t qua’ là 2. Ta lâ.p ba’ng nhu. sau:. Lop12.net.

(15) ` Chu.o.ng 1. Da.i sô´ mê.nh dê. 14. • n = 3: Khi dó 23 = 8 và chia 2 cho kê´t qua’ là 4. Ta lâ.p ba’ng nhu. sau:. • Mô.t cách tu.o.ng tu.. khi chúng ta tăng bâ.c cu’a hê. sô´ n lên và thu..c ` u tiên mô.t nu’.a trên là T và mô.t châ´t khi lâ.p ba’ng chúng ta viê´t cô.t dâ nu’.a du.ó.i là F (hoă.c ngu.o..c la.i theo mô.t nguyên tă´c), rô`i dê´n các cô.t tiê´p theo nhu.ng chúng ta chı’ lâ.p mô.t nu’.a ba’ng trên theo thuâ.t chia ` n, cuô´i cùng thı̀ thu..c hiê.n copy nu’.a trên xuô´ng nu’.a dôi có bâ.c gia’m dâ du.ó.i là hoàn thành du’ 2n bô. phân bô´ các giá tri. chân lý cu’a n biê´n có mă.t trong công thú.c dã cho. 2. Phu.o.ng pháp lâ.p ba’ng chân lý thu go.n Tru.ó.c hê´t viê´t công thú.c dã cho thành mô.t dòng cu’a ba’ng, tiê´p dê´n là ` n lu.o..t theo giá tri. phân bô´ cu’a các biê´n có mă.t các dòng du.o..c tı́nh lâ ` n lâ.p trong công thú.c và tu.o.ng ú.ng là các giá tri. cu’a tù.ng thành phâ . . . . nên công thú c, và cuô´i cùng là giá tri. cu’a công thú c du o. c tı́nh theo ` n trên du..a theo phép toán cuô´i cùng cu’a công thú.c. tù.ng thành phâ. Lop12.net.

(16) ` 1.2. Công thú.c mê.nh dê. 15. . Thı́ du . 1.2.2 Lâ.p ba’ng chân lý thu go.n cu’a công thú c A = (A ↔ B) → ((¬A) ∧ B) Chúng ta lâ.p ba’ng chân lý thu go.n nhu. sau: (A T T F F. ↔ T F F T. B) T F T F. → F T T F. ((¬ A) F F T T. ∧ F F T F. B) T F T F. Phu.o.ng pháp lâ.p ba’ng chân lý thu go.n du..a vào vi. trı́ cu’a các biê´n ` và các phép toán có mă.t trong công thú.c làm các cô.t tu.o.ng mê.nh dê ` mă.t tı́nh toán du.o..c tiê´t kiê.m thò.i gian nhiê ` u ho.n và ba’ng ú.ng, nên vê lâ.p do.n gia’n ho.n. 3. Tı́nh u.u tiên cu’a các phép toán Ta dã biê´t trong sô´ ho.c dê’ gia’m thiê’u viê.c viê´t dâ´u ngoă.c cho mô.t biê’u thú.c sô´ ho.c thông thu.ò.ng là nhân, chia tru.ó.c và cô.ng, trù. sau, và các phép toán có cùng mú.c u.u tiên du.o..c thu..c hiê.n tù. trái qua pha’i. Trong các phép toán logic cũng tu.o.ng tu.., ngu.ò.i ta dã du.a ra mô.t quy u.ó.c viê´t dâ´u ngoă.c theo thú. tu.. u.u tiên sau dây:. 1. ¬;. 2. ∧;. 3. ∨;. 4. →;. 5. ↔. ` u lâ ` n liên trong dó chú ý hai phép toán cuô´i cùng →, ↔ xuâ´t hiê.n nhiê . tiê´p thı̀ lâ.p ngoă.c tù trái qua pha’i, chă’ ng ha.n: A → B → C thı̀ pha’i lâ.p ngoă.c dúng là ((A → B) → C). Thı́ du. 1.2.3 Chúng ta lâ.p ngoă. c cho công thú.c. Lop12.net.

(17) ` Chu.o.ng 1. Da.i sô´ mê.nh dê. 16. A = A ∨ ¬B → C ↔ A theo các bu.ó.c sau dây: A ∨ (¬B) → C ↔ A (A ∨ (¬B)) → C ↔ A ((A ∨ (¬B)) → C) ↔ A (((A ∨ (¬B)) → C) ↔ A). 1.3 1.3.1. Mô.t sô´ di.nh nghı̃a Hàm da.i sô´ logic. Di.nh nghı̃a 1.3.1 • Mô.t hàm da.i sô´ logic n biê´n là mô.t ánh xa. cu’a tâ.p ho..p {T, F}n vào {T, F}. • Ló.p các hàm da.i sô´ logic nhâ.n hai giá tri. {T, F } (hoă.c {0, 1}) cùng vó.i các biê´n cu’a nó du.o..c ký hiê.u là ló.p hàm P 2 . n Ta dê˜ dàng nhâ.n thâ´y ră` ng sô´ các hàm da.i sô´ logic n biê´n là bă` ng 22 , vı̀ ră` ng vó.i n biê´n ta có 2n bô. phân bô´ các giá tri. chân lý {T, F} và mô˜i mô.t bô. nhu. vâ.y tu.o.ng ú.ng vó.i mô.t giá tri. {T, F}, nên sô´ hàm tu.o.ng ú.ng vó.i n n biê´n pha’i là 22 .. Thı́ du. 1.3.1 1 1. Xét ló.p hàm P 2 mô.t biê´n gô`m có 22 = 4 hàm du.o..c cho theo ba’ng sau dây: x\f T F. f1 T T. trong dó f2 (x) = x; f3(x) = ¬x. Lop12.net. f2 T F. f3 F T. f4 F F.

(18) 1.3. Mô.t sô´ di.nh nghı̃a. 17. 2 2. Xét ló.p hàm P 2 hai biê´n gô`m có tâ´t ca’ là: 22 = 16 hàm du.o..c cho theo ba’ng sau dây:. x1 x2 \f TT TF FT FF. f1 T T T T. f2 T T T F. f3 T T F T. f4 T T F F. f5 T F T T. f6 T F T F. f7 T F F T. f8 T F F F. x1x2 \f TT TF FT FF. f9 F T T T. f10 F T T F. f11 F T F T. f12 F T F F. f13 F F T T. f14 F F T F. f15 F F F T. f16 F F F F. trong dó có mô.t sô´ hàm quen thuô.c nhu. sau: f4 (x1 , x2) = x1; f11(x1 , x2) = x2 ; f13(x1, x2 ) = x1 f5 (x1 , x2) = x1 → x2; f7 (x1, x2 ) = x1 ↔ x2 f8 (x1 , x2) = x1 and x2 ; f2 (x1 , x2) = x1 or x2; f10 (x1, x2 ) = x1 xor x2 ; Chú ý o’. dây thay ¬x bă` ng x. ` tu.o.ng ú.ng vó.i mô.t hàm da.i sô´ logic, Ta biê´t mô˜i mô.t công thú.c mê.nh dê ` là dê´m du.o..c, chă’ng ha.n vı̀ ră` ng thú. nhâ´t tâ.p ho..p tâ´t ca’ các biê´n mê.nh dê theo cách să´p xê´p thú. tu.. sau dây A, B, C, ..., Z, A1, B1, C1 , ..., Z1 , ... ` nào dó có chú.a các biê´n i1 , i2, ..., in Thú. hai là nê´u mô.t công thú.c mê.nh dê (i1 < i2 < ... < in ) trong tâ.p kê’ du.o..c o’. trên thı̀ khi dó tu.o.ng ú.ng ta có thê’ lâ.p du.o..c mô.t hàm da.i sô´ logic vó.i các biê´n xi1 , xi2 , ..., xin .. Thı́ du. 1.3.2 Vó.i công thú.c A → B thı̀ hàm da.i sô´ logic tu.o.ng ú.ng là:. Lop12.net.

(19) ` Chu.o.ng 1. Da.i sô´ mê.nh dê. 18 x1 T T F F. x2 T F T F. f (x1 , x2) T F T T. còn dô´i vó.i công thú.c B → A thı̀ hàm da.i sô´ logic tu.o.ng ú.ng là: x1 T T F F. 1.3.2. x2 T F T F. g(x1 , x2) T T F T. Su.. dô`ng nhâ´t dúng - dô`ng nhâ´t sai. ` du.o..c go.i là dô`ng nhâ´t dúng (hay Di.nh nghı̃a 1.3.2 Mô.t công thú.c mê.nh dê ` ng dúng), nê´u nó nhâ.n giá tri. dúng dô´i vó.i mo.i phép thê´ các giá tri. chân hă lý cu’a các biê´n có mă.t trong công thú.c. ` là dô`ng nhâ´t dúng, Vâ.y chúng ta có thê’ nói ră` ng mô.t công thú.c mê.nh dê khi và chı’ khi hàm da.i sô´ logic tu.o.ng ú.ng cu’a nó nhâ.n toàn giá tri. dúng, hoă.c có thê’ nói nê´u cô.t cuô´i cùng cu’a ba’ng chân lý cu’a công thú.c dã cho chı’ gô`m toàn giá tri. dúng. Thı́ du. 1.3.3 a) Công thú.c A = A ∨ (¬A) là dô`ng nhâ´t dúng (hiê’n nhiên). b) Công thú.c A = A ∧ B → A là dô`ng nhâ´t dúng. Ta chú.ng minh bă` ng pha’n chú.ng nhu. sau: Gia’ su’. ngu.o..c la.i, A không dô`ng nhâ´t dúng, nghı̃a là tô`n ta.i mô.t bô. phân bô´ I0 các giá tri. chân lý cu’a các biê´n có mă.t trong A sao cho A(I0) = False, tú.c là:  A ∧ B = T (1) A∧B →A=F ⇔ A = F (2). Lop12.net.

(20) 1.3. Mô.t sô´ di.nh nghı̃a. 19. Thay (2) vào (1) ta có: A ∧ B = F (3) So sánh (1) và (3) suy ra mâu thuâ˜n. Vâ.y A là dô`ng nhâ´t dúng. Di.nh nghı̃a 1.3.3 Nê´u công thú.c (A → B) là dô`ng nhâ´t dúng thı̀ khi dó A du.o..c go.i là logic kéo theo B hoă.c B là logic kéo theo tù. A. Thı́ du. 1.3.4 Công thú.c A ∧ (A → B) logic kéo theo B. ` n chú.ng minh ră` ng công thú.c Thâ.t vâ.y, ta chı’ câ A = (A ∧ (A → B) → B) là dô`ng nhâ´t dúng. Ta lâ.p ba’ng chân lý thu go.n sau dây: (A ∧ T T T F F F F F. (A T T F F. → B) T T F F T T T F. → T T T T. B) T F T F. Di.nh nghı̃a 1.3.4 Hai công thú.c A và B du.o..c go.i là logic tu.o.ng du.o.ng, nê´u công thú.c (A ↔ B) là dô`ng nhâ´t dúng. Thı́ du. 1.3.5 A → B và (¬A) ∨ B là hai công thú.c logic tu.o.ng du.o.ng, ` n chı’ ra ră` ng công thú.c nghı̃a là ta chı’ câ A = (A → B) ↔ ((¬A) ∨ B) là dô`ng nhâ´t dúng. Lâ.p ba’ng chân lý thu go.n sau dây (A T T F F. → B) T T F F T T T F. ↔ ((¬A) T F T F T T T T. Lop12.net. ∨ T F T T. B) T F T F.

(21)

Giáo trình Logic toán

Tài liệu liên quan

Tài liệu bạn tìm kiếm đã sẵn sàng tải về