Logic Toán - Trần Thọ Châu

Chia sẻ: Nguyễn Duy | Ngày: | Loại File: PDF | Số trang:205

Thêm vào BST

Báo xấu

129
lượt xem 37
download

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

Nhằm giúp các bạn có thêm tài liệu phục vụ nhu cầu học tập và ôn tập môn Toán, mời các bạn cùng tham khảo nội dung tài liêu "Logic Toán". Nội dung tài liệu giới thiệu đến các bạn những nội dung về đại số mệnh đề, hệ số mệnh đề, hệ toán tân từ, logic mờ, định lý suy diễn, logic mệnh đề,...

Chủ đề:

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

Lưu

Nội dung Text: Logic Toán - Trần Thọ Châu

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ả.
Mu.c lu.c o.i mo’. dˆ L` `au . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 o´ mˆ 1 Da.i sˆ e.nh dˆ `e 7 1.1 C´ac ph´ep to´an v`a ba’ng chˆan l´ y . . . . . . . . . . . . . . . . . 8 1.1.1 Ph´ep phu’ di.nh (¬, not) . . . . . . . . . . . . . . . . . . 10 1.1.2 Ph´ep v` a (∧, and, hˆ o.i) . . . . . . . . . . . . . . . . . . . 10 1.1.3 Ph´ep hay l` a (∨, or, tuyˆe’n) . . . . . . . . . . . . . . . . 10 1.1.4 Ph´ep k´eo theo (→) . . . . . . . . . . . . . . . . . . . . 11 1.1.5 Ph´ep tu.o.ng du.o.ng (↔ ↔) . . . . . . . . . . . . . . . . . 12 1.2 Cˆong th´ . u c mˆe.nh dˆ`e . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Mˆo.t sˆo´ di.nh ngh˜ıa . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3.1 H`am da.i sˆo´ logic . . . . . . . . . . . . . . . . . . . . . 16 1.3.2 Su.. dˆo`ng nhˆa´t d´ ung - dˆo`ng nhˆa´t sai . . . . . . . . . . . 18 1.4 Mˆo.t sˆo´ t´ınh chˆa´t . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.5 Da.ng chuˆa’n t˘a´c cu’a cˆong th´ u.c mˆe.nh dˆ `e . . . . . . . . . . . . 23 1.5.1 Da.ng chuˆa’n t˘a´c tuyˆe’n v`a chuˆa’n t˘a´c hˆo.i . . . . . . . . 23 1.5.2 Da.ng chuˆa’n t˘a´c ho`an to`an . . . . . . . . . . . . . . . . 24 1.6 C´ac hˆe. dˆ `ay du’ cu’a c´ac ph´ep to´an . . . . . . . . . . . . . . . . 25 1.7 B`ai tˆa.p chu.o.ng 1 . . . . . . . . . . . . . . . . . . . . . . . . . 34 2 Hˆe. to´ an mˆ e.nh dˆ `e 39 2.1 Hˆe. tiˆen dˆ`e trong hˆe. to´an mˆe.nh dˆ `e . . . . . . . . . . . . . . . . 40 2.1.1 Mˆo.t sˆo´ di.nh ngh˜ıa co. ba’n . . . . . . . . . . . . . . . . 40 2.1.2 C´ac t´ınh chˆa´t . . . . . . . . . . . . . . . . . . . . . . . 42
2 MU . C LU .C 2.1.3 L´ y thuyˆe´t tiˆen dˆ `e trong hˆe. to´an mˆe.nh dˆ`e . . . . . . . . 43 2.1.4 Di.nh l´ y suy diˆ˜en trong hˆe. to´an mˆe.nh dˆ `e . . . . . . . . 44 2.2 Nguyˆen l´ y suy diˆ˜en v`a b`ai to´an lˆa.p luˆa.n trong logic mˆe.nh dˆ `e . 52 2.2.1 Nguyˆen l´ y suy diˆ˜en . . . . . . . . . . . . . . . . . . . . 52 2.2.2 B`ai to´an lˆa.p luˆa.n trong logic mˆe.nh dˆ `e . . . . . . . . . 52 2.3 Mˆo.t sˆo´ di.nh l´ y trong hˆe. to´an mˆe.nh dˆ `e . . . . . . . . . . . . . 55 2.3.1 T´ınh dˆ `ay du’ . . . . . . . . . . . . . . . . . . . . . . . . 55 2.3.2 T´ınh phi mˆau thuˆa˜n . . . . . . . . . . . . . . . . . . . 58 2.3.3 T´ınh dˆo.c lˆa.p . . . . . . . . . . . . . . . . . . . . . . . . 59 2.4 Gi´o.i thiˆe.u v`ai n´et vˆ `e logic da tri. . . . . . . . . . . . . . . . . . 61 2.5 T´ınh quyˆe´t di.nh cu’a hˆe. to´an mˆe.nh dˆ `e . . . . . . . . . . . . . 62 2.6 `e kh´ac . . . . . . . . . . . . . . . . . . . . . Mˆo.t sˆo´ hˆe. tiˆen dˆ . 62 2.7 ´ du.ng di.nh l´ Ap y dˆ`ay du’ cho b`ai to´an suy diˆ˜en trong logic mˆe.nh dˆ `e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 2.8 B`ai tˆa.p chu.o.ng 2 . . . . . . . . . . . . . . . . . . . . . . . . . 66 3 Hˆe. to´ an tˆ an t` u. 70 3.1 C´ac lu.o..ng t`u. . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.2 C´ac kh´ai niˆe.m v`a di.nh ngh˜ıa . . . . . . . . . . . . . . . . . . . 77 3.3 Minh hoa., su.. dˆo`ng nhˆa´t d´ ung v`a mˆo h`ınh . . . . . . . . . . . 81 3.3.1 Minh hoa. . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.3.2 T´ınh thu..c hiˆe.n du.o..c . . . . . . . . . . . . . . . . . . . 83 3.3.3 Su.. dˆo`ng nhˆa´t d´ ung (h˘`a ng d´ ung) . . . . . . . . . . . . 85 3.3.4 Mˆo h`ınh . . . . . . . . . . . . . . . . . . . . . . . . . . 85 3.3.5 Mˆo.t sˆo´ hˆe. qua’ . . . . . . . . . . . . . . . . . . . . . . . 86 3.3.6 Mˆo.t sˆo´ di.nh ngh˜ıa kh´ac . . . . . . . . . . . . . . . . . 89 3.3.7 C´ac cˆong th´ u.c logic dˆo`ng nhˆa´t d´ ung trong hˆe. to´an tˆan u . . . . . . . . . . . . . . . . . . . . . . . . . . . . t`. . 92 3.3.8 Da.ng chuˆa’n t˘a´c trong logic tˆan t` u. . . . . . . . . . . . . 93 3.4 L´y thuyˆe´t tˆan t`u. cˆa´p 1K . . . . . . . . . . . . . . . . . . . . . 100 3.4.1 Di.nh ngh˜ıa . . . . . . . . . . . . . . . . . . . . . . . . 100 3.4.2 Mˆo.t v`ai th´ı du. vˆ `e L´ u. cˆa´p 1K . . . . . y thuyˆe´t tˆan t` . 103
MU . C LU .C 3 3.5 Di.nh l´ y suy diˆ˜en trong logic tˆan t` u. . . . . . . . . . . . . . . . 104 3.6 T´ınh phi mˆau thuˆa˜n v`a dˆ `ay du’ cu’a logic tˆan t` u. . . . . . . . . 110 3.6.1 C´ac kh´ai niˆe.m v`a di.nh ngh˜ıa . . . . . . . . . . . . . . . 110 3.6.2 T´ınh phi mˆau thuˆa˜n cu’a l´ y thuyˆe´t tˆan t` u. cˆa´p 1 PP . . 111 3.6.3 Mˆo.t sˆo´ di.nh l´ y trong l´ y thuyˆe´t tˆan t` u. cˆa´p 1 K . . . . . 112 3.6.4 T´ınh dˆ `ay du’ cu’a l´ u. cˆa´p 1K . . . . . . . y thuyˆe´t tˆan t` 120 3.7 ´ du.ng trong ch´ Ap u.ng minh di.nh l´ y thuyˆe´t tˆan t` y cu’a l´ u. cˆa´p 1 121 3.8 B`ai tˆa.p chu.o.ng 3 . . . . . . . . . . . . . . . . . . . . . . . . . 123 4 Ngˆon ng˜u. PROLOG 126 4.1 Mo’. dˆ `au . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 4.2 Ngˆon ng˜ u. PROLOG . . . . . . . . . . . . . . . . . . . . . . . 131 4.2.1 Qui t˘a´c c´ u ph´ap . . . . . . . . . . . . . . . . . . . . . . 131 4.2.2 C´ac kiˆe u dˆo´i tu.o..ng . . . . . . . . . . . . ’ . . . . . . . . 131 4.2.3 C´ac ph´ep to´an, quan hˆe. v`a h`am chuˆa’n . . . . . . . . . 137 4.3 Cˆa´u tr´ uc cu’a chu.o.ng tr`ınh PROLOG . . . . . . . . . . . . . . 139 4.4 Tˆan t` u. FAIL, nh´at c˘a´t (!) v`a tˆan t` u. NOT . . . . . . . . . . . 141 4.5 Phu.o.ng th´ u.c xuˆa´t nhˆa.p d˜u. liˆe.u . . . . . . . . . . . . . . . . . 143 4.5.1 Phu.o.ng th´ u.c xuˆa´t d˜u. liˆe.u . . . . . . . . . . . . . . . . 143 4.5.2 Phu.o.ng th´ u.c nhˆa.p d˜ u. liˆe.u . . . . . . . . . . . . . . . . 145 4.6 Mˆo.t sˆo´ th´ı du. minh hoa. vˆ `e lˆa.p tr`ınh PROLOG . . . . . . . . 148 4.7 B`ai tˆa.p chu.o.ng 4 . . . . . . . . . . . . . . . . . . . . . . . . . 162 5 Logic m` o. 166 5.1 Mo’. dˆ `au . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 5.2 C´ac kh´ai niˆe.m co. ba’n . . . . . . . . . . . . . . . . . . . . . . 169 5.3 Mˆo.t sˆo´ ch´ uy `e biˆe´n ngˆon ng˜ ´ vˆ u. . . . . . . . . . . . . . . . . . 172 5.4 C´ac ph´ep to´an trˆen tˆa.p m`o. . . . . . . . . . . . . . . . . . . . 176 5.5 C´ac t´ınh chˆa´t trˆen tˆa.p m`o. . . . . . . . . . . . . . . . . . . . . 177 5.6 Quan hˆe. m`o. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 5.6.1 C´ac ph´ep to´an trˆen quan hˆe. m`o. . . . . . . . . . . . . . 180 5.6.2 Mˆo.t sˆo´ t´ınh chˆa´t trˆen quan hˆe. m`o. . . . . . . . . . . . . 180
4 MU . C LU .C 5.7 Logic m`o. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 5.7.1 Mo’. dˆ `au . . . . . . . . . . . . . . . . . . . . . . . . . . 180 5.7.2 C´ac ph´ep kˆe´t nˆo´i . . . . . . . . . . . . . . . . . . . . . 181 5.7.3 Ph´ep tuyˆe’n (OR-disjunction) . . . . . . . . . . . . . . 183 5.7.4 Ph´ep k´eo theo (Implication [Zadeh 1973]) . . . . . . . 183 5.8 Su.. dˆo`ng nhˆa´t d´ung m`o. (Fuzzy Tautologies) . . . . . . . . . . 185 5.9 C´ac ph´ep to´an t − norm T v`a t − conorm S . . . . . . . . . . 185 5.10 Ph´ep ho..p th`anh (Composition) . . . . . . . . . . . . . . . . . 187 5.11 Phu.o.ng tr`ınh quan hˆe. m`o. . . . . . . . . . . . . . . . . . . . . 187 5.12 Lˆa.p luˆa.n m`o. (Fuzzy Reasoning) . . . . . . . . . . . . . . . . . 189 5.12.1 Thuˆa.t to´an m`o. . . . . . . . . . . . . . . . . . . . . . . 190 5.12.2 Lˆa.p luˆa.n m`o. . . . . . . . . . . . . . . . . . . . . . . . 192 5.12.3 Mˆo.t sˆo´ ph´ep suy diˆ˜en m`o. kh´ac . . . . . . . . . . . . . 192 5.13 C´ac luˆa.t ho..p th`anh cu’a suy diˆ˜en . . . . . . . . . . . . . . . . 194 5.14 U´ .ng du.ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 5.15 B` a.p chu.o.ng 5 . . . . . . . . . . . . . . . . . ai tˆ . . . . . . . 199 T` e.u tham kha’o . . . . . . . . . . . . . . . . . . ai liˆ . . . . . . . 203
o.i mo’. dˆ L` `au Ta biˆe´t r˘`a ng Logic To´an l`a mˆo.t ng`anh khoa ho.c l´ y thuyˆe´t g˘a´n ch˘a.t v´o.i tu. duy suy diˆ˜en cu’a con ngu.`o.i v`a du.o..c ph´at triˆe’n trˆen co. so’. tuˆan thu’ nghiˆem ng˘a.t c´ac qui luˆa.t lˆa.p luˆa.n cu’a tu. duy logic h`ınh th´ u.c. Ho.n n˜ u.a, Logic To´an nghiˆen c´ u.u phu.o.ng ph´ap suy luˆa.n trong To´an ho.c, phu.o.ng ph´ap ch´ u.ng minh v`a kha’ n˘ang suy diˆ˜en dˆa˜n dˆe´n c´ac di.nh l´ y trong mˆo.t l´ y thuyˆe´t. C´ac qui luˆa.t co. ba’n cu’a logic h`ınh th´ u.c d˜a du.o..c ph´at triˆe’n t` u. th`o.i Aristote (384-322 tru.´o.c Cˆong nguyˆen). Su.. ph´at triˆe’n cu’a c´ac ng`anh khoa ho.c l´y thuyˆe´t t` u. th`o.i v˘an minh cˆo’ Hy La.p cho t´o.i th`o.i hiˆe.n da.i ng`ay nay `eu tra’i qua nhiˆ dˆ `eu bu.´o.c th˘ang trˆ`am, v`a c´o nh˜ u.ng giai doa.n khˆong ph´at triˆe’n du.o..c, ngu.ng trˆe., ho˘a.c ph´at triˆe’n rˆa´t chˆa.m cha.p. Tuy vˆa.y, mˆo˜i mˆo.t giai doa.n `eu dˆe’ la.i nh˜ dˆ u.ng dˆa´u ˆa´n vˆo c`ung qu´ı gi´a, dˆa´y l`a nh˜ u.ng ph´at minh v˜ı da.i cu’a c´ac nh`a khoa ho.c n´oi chung v`a ng`anh To´an ho.c n´oi riˆeng, ch˘a’ng ha.n c´ac ph´at minh cu’a Newton, Leibnitz vˆ `e ph´ep t´ınh vi phˆan v`ao thˆe´ ky’ 16 – 17, y thuyˆe´t tˆa.p ho..p Cantor v`ao cuˆo´i thˆe´ ky’ 19 v`a dˆ l´ `au thˆe´ ky’ 20... Tˆa.p gi´ao tr`ınh n`ay nh˘`a m gi´o.i thiˆe.u mˆo.t sˆo´ vˆa´n dˆ `e co. ba’n nhˆa´t cu’a logic To´an v`a logic m`o. d˜a v`a dang du.o..c nhiˆ `eu nh`a khoa ho.c quan tˆam nghiˆen . u u, u c´ . ´ ng du.ng. Gi´ao tr`ınh du.o..c chia th`anh 5 chu.o.ng: Chu.o.ng 1 v`a 2 tr`ınh b`ay vˆ `e logic mˆe.nh dˆ `e v´o.i mu.c d´ıch l`a mˆo h`ınh ho´a qu´a tr`ınh suy diˆ˜en. Logic mˆe.nh dˆ `e l`a hˆe. thˆo´ng logic do.n gia’n m`a do.n vi. co. ba’n l`a c´ac mˆe.nh dˆ `e mang nˆo.i dung cu’a c´ac ph´an do´an, mˆo˜i mˆo.t ph´an do´an c´o mˆo.t gi´a tri. chˆan l´y ho˘a.c l`a d´ ung ho˘a.c l`a sai. C´ac mˆe.nh dˆ `e ph´u.c ho..p du.o..c
6 o.i mo’. dˆ L` `au lˆa.p nˆen t`u. c´ac mˆe.nh dˆ`e co. ba’n nh`o. c´ac ph´ep to´an logic nhu. “khˆ ong” , “v` a” , “hay l` a” , “nˆe´u th`ı”, “khi v` . . a chı’ khi”. Chu o ng 3 tr`ınh b`ay vˆ `e logic tˆan t` u. l`a mˆo.t da.ng tˆo’ng qu´at ho´a cu’a logic mˆe.nh dˆ `e. Logic tˆan t` . . . u c`on du o. c go.i l`a logic cˆa´p 1 (first-order logic). C´ac tˆan t` u. (predicates) l`a c´ac h`am theo khˆong ho˘a.c nhiˆ `eu biˆe´n, v`a tra’ vˆ`e gi´a tri. Boole. V`ı vˆa.y tˆan t` u. c´o l´ uc d´ung, c´o l´ uc khˆong d´ ung tu` y thuˆo.c v`ao c´ac gi´a tri. cu. thˆe’ cu’a c´ac dˆo´i cu’a n´o. Logic tˆan t` . u c˜ . . ung du o. c d` ung trong c´ac hˆe. thˆo´ng suy luˆa.n ho˘a.c c´ac hˆe. thˆo´ng chuyˆen gia, ... Chu.o.ng 4 tr`ınh b`ay nh˜ u.ng n´et co. ba’n cu’a ngˆon ng˜ u. PROLOG, viˆe´t t˘a´t cu’a “Programming in Logic”. Logic tˆan t` u. c´o du’ kha’ n˘ang diˆ˜en ta’ dˆe’ ta.o nˆen co. so’. cho ngˆon ng˜ u. lˆa.p tr`ınh Prolog cu’a chu.o.ng n`ay. Chu.o.ng 5 tr`ınh b`ay nh˜ u.ng vˆa´n dˆ `e co. ba’n cu’a logic m`o. (Fuzzy Logic) xuˆa´t ph´at t` u. l´y thuyˆe´t tˆa.p m`o. cu’a Zadeh ra d`o.i t` u. 1965 dˆe´n c´ac ph´ep ho..p th`anh c` ung v´o.i nh˜ u.ng phu.o.ng ph´ap suy diˆ˜en thˆong qua quan hˆe. m`o. thˆe’ hiˆe.n du.´o.i da.ng ph´ep k´eo theo b˘a` ng nhiˆ `eu c´ach th´ u.c kh´ac nhau du.o..c tr`ınh b`ay dˆ `ay du’ kˆe´t ho..p v´o.i c´ac th´ı du. minh hoa.. Viˆe.c vˆa.n du.ng c´ac mˆo to. suy diˆ˜en du..a trˆen c´ac to´an tu’. ho..p th`anh g˘a´n liˆ `en v´o.i tˆen tuˆo’i cu’a c´ac nh`a khoa ho.c d˜a du.o..c u ´.ng du.ng trong nhiˆ `eu l˜ınh vu..c kh´ac nhau nhu. diˆ `eu khiˆe’n m`o., hˆe. chuyˆen gia, tr´ı tuˆe. nhˆan ta.o, chˆe´ ta.o Robot, c´ac m´ay m´oc chuyˆen du.ng, di.ch thuˆa.t... Gi´ao tr`ınh c´o thˆe’ du.o..c su’. du.ng rˆo.ng r˜ai cho c´ac dˆo´i tu.o..ng sinh viˆen, ho.c viˆen cao ho.c, nghiˆen c´ u.u sinh to´an-tin v`a nh˜ u.ng ai quan tˆam dˆe´n logic to´an. Tuy d˜a cˆo´ g˘a´ng song ch˘a´c ch˘a´n gi´ao tr`ınh khˆong tr´anh kho’i nh˜ u.ng thiˆe´u s´ot. T´ac gia’ rˆa´t mong nhˆa.n du.o..c su.. g´op y ´ cu’a ba.n do.c. Xin chˆan th`anh ca’m o n! . Thu. g´op y ´ xin gu’.i vˆ `e: Khoa To´an-Co.-Tin, Tru.`o.ng Da.i ho.c Khoa ho.c Tu.. nhiˆen, Da.i ho.c Quˆo´c gia H`a Nˆo.i, 334 - Nguyˆ˜en Tr˜ai, Quˆa.n Thanh Xuˆan, H`a Nˆo.i. T´ac gia’
Chu.o.ng 1 o´ mˆ Da.i sˆ `e e.nh dˆ 1.1 C´ ac ph´ ep to´ a ba’ng chˆ an v` an l´ y . . . . . . . . . . 8 1.1.1 Ph´ep phu’ di.nh (¬, not) . . . . . . . . . . . . . . . 10 1.1.2 Ph´ep v` a (∧, and, hˆ o.i) . . . . . . . . . . . . . . . . 10 1.1.3 a (∨, or, tuyˆe’n) . . . . . . . . . . . . . . 10 Ph´ep hay l` 1.1.4 Ph´ep k´eo theo (→) . . . . . . . . . . . . . . . . . . 11 1.1.5 Ph´ep tu.o.ng du.o.ng (↔ ↔) . . . . . . . . . . . . . . . 12 1.2 Cˆ ong th´ u.c mˆe.nh dˆ`e . . . . . . . . . . . . . . . . . 12 1.3 Mˆ o´ di.nh ngh˜ıa . . . . . . . . . . . . . . . . . . o.t sˆ 16 1.3.1 H`am da.i sˆo´ logic . . . . . . . . . . . . . . . . . . . 16 1.3.2 Su.. dˆ o`ng nhˆa´t d´ o`ng nhˆ ung - dˆ a´t sai . . . . . . . . . 18 1.4 Mˆ o´ t´ınh chˆ o.t sˆ a´t . . . . . . . . . . . . . . . . . . . 22 1.5 Da.ng chuˆ a’n t˘ ´ ac cu’a cˆ ong th´ u.c mˆe.nh dˆ`e . . . . . 23 1.5.1 a’n t˘ Da.ng chuˆ a´c tuyˆe’n v` a chuˆa’n t˘ a´c hˆ o.i . . . . . . 23 1.5.2 a’n t˘ Da.ng chuˆ a´c ho` an to` an . . . . . . . . . . . . . . 24 1.6 C´ ac hˆ `ay du’ cu’a c´ e. dˆ ac ph´ ep to´ an . . . . . . . . . 25 1.7 B` a.p chu.o.ng 1 . . . . . . . . . . . . . . . . . . ai tˆ 34
8 Chu.o.ng 1. Da.i sˆo´ mˆe.nh dˆ `e Thˆong thu.`o.ng ch´ ung ta th`anh lˆa.p c´ac mˆe.nh dˆ `e ph´u.c ho..p t`u. c´ac mˆe.nh `e do.n gia’n. Trong chu.o.ng n`ay, ch´ dˆ ung ta s˜e di sˆau nghiˆen c´ u.u dˆ`ay du’ ba’n `e v`a tu. duy suy diˆ˜en cu’a n´o mˆo.t c´ach ch˘a.t ch˜e, logic chˆa´t cu’a da.i sˆo´ mˆe.nh dˆ v`a mang t´ınh thu..c tiˆ˜en. 1.1 C´ ac ph´ ep to´ a ba’ng chˆ an v` an l´ y Ch´ ung ta dˆ `eu biˆe´t con ngu.`o.i c´o kha’ n˘ang pha’n ´anh mˆo´i quan hˆe. hiˆe.n thu..c gi˜u.a c´ac su.. vˆa.t b˘`a ng nh˜ u.ng mˆe.nh dˆ `e. C´ac mˆe.nh dˆ `e d´o du.o..c du.a ra du.´o.i nhiˆ `eu h`ınh th´ u.c kh´ac nhau, ch˘a’ng ha.n nhu. mˆo.t l`o.i n´oi, mˆo.t cˆau v˘an, mˆo.t cˆong th´ u.c To´an, L´ y, Ho´a, hay su.. mˆo pho’ng cu’a mˆo.t b´ u.c tranh v.v.., nhu.ng co. ba’n trong d´o l`a c´ac mˆe.nh dˆ `e n`ay c´o mang dˆ `ay du’ y ´ ngh˜ıa nhˆa´t di.nh hay khˆong, ngh˜ıa l`a c´ac mˆe.nh dˆ `e d´o c´o mang theo t´ınh chˆa´t hiˆe.n thu..c du.´o.i mˆo.t h`ınh th´ u.c nhˆa´t di.nh, ch´ u. khˆong pha’i l`a mˆo.t mˆe.nh dˆ `e suˆong, vˆo ngh˜ıa, v`a ung khˆong pha’i l`a nh˜ c˜ u.ng l`o.i n´oi ch´ u.a du..ng mˆo.t y ´ ngh˜ı khˆong nghiˆem t´ uc. Mˆo.t mˆe.nh dˆ . `e pha’n ´anh mˆo.t su. viˆe.c n`ao d´o theo mˆo.t c´ach th´ . u c nhˆa´t di.nh v`a su.. viˆe.c d´o pha’n ´anh t´ınh chˆan thu..c theo c´ach trˆen th`ı du.o..c go.i l`a mˆo.t mˆe.nh dˆ `e d´ ung; Tr´ai la.i mˆe.nh dˆ `e d´o du.o..c go.i l`a mˆo.t mˆe.nh dˆ `e sai. . Thu. c chˆa´t vˆa´n dˆ `e ch´ ung ta quan tˆam d˘a.c biˆe.t trong To´an ho.c l`a o’. chˆo˜: “Mˆ o˜i mˆ o.t mˆe.nh dˆ `e ho˘ a.c l`a d´ ung ho˘ a.c l` a sai, v` a khˆong c´ o mˆo.t mˆe.nh dˆ`e n`ao . u a d´ v` ung la.i v` . u a sai”. Dˆay ch´ınh l`a nˆo.i dung cu’a di.nh l´ y 2 - gi´a tri.. . . Bo’ i vˆa.y, l´o p tˆa´t ca’ c´ac mˆe.nh dˆ `e du o. c chia th`anh hai l´o.p con: mˆo.t l´o.p . . gˆo`m tˆa´t ca’ c´ac mˆe.nh dˆ `e d´ung v`a mˆo.t l´o.p gˆo`m tˆa´t ca’ c´ac mˆe.nh dˆ `e sai. Mˆo˜i mˆe.nh dˆ `e thuˆo.c mˆo.t trong c´ac l´o.p d´o s˜e nhˆa.n mˆo.t gi´a tri. chˆan l´ y d´ung (True, viˆe´t t˘a´t l`a T) ho˘a.c sai (False, viˆe´t t˘a´t l`a F). Ta k´ y hiˆe.u c´ac mˆe.nh dˆ `e b˘a` ng c´ac ch˜ u. c´ai hoa A, B, C, ... c`on c´ac biˆe´n mˆe.nh dˆ `e b˘a` ng c´ac ch˜ u. c´ai A, B, C, ... v`a ch´ ung c´o kha’ n˘ang nhˆa.n c´ac gi´ a tri. chˆ an l´y {T, F } ho˘a.c {1, 0}. Th´ı du. 1.1.1
1.1. C´ac ph´ep to´an v`a ba’ng chˆan l´ y 9 1. “Trˆen m˘a.t tr˘ang khˆong c´o ngu.`o.i” (T) 2. “35 chia hˆe´t cho 6” (F) 3. “B´ac Hˆo` sinh ng`ay 19 th´ang 5 n˘am 1890” (T) Ch´ ´ r˘a` ng trong di.nh l´ u y y 2 - gi´a tri., ngu.`o.i ta chı’ ph´at biˆe’u r˘`a ng: mˆo˜i mˆo.t mˆe.nh dˆ `e ho˘a.c l`a d´ung, ho˘a.c l`a sai, nhu.ng khˆong kh˘a’ng di.nh du.o..c r˘a` ng mˆo˜i mˆo.t mˆe.nh dˆ `e ta c´o thˆe’ quyˆe´t di.nh du.o..c liˆe.u n´o d´ ung hay khˆong, ch˘a’ng ha.n di.nh l´ y cuˆo´i c` ung cu’a Fermat [1], gia’ thuyˆe´t Continuum [5]. Tˆa´t nhiˆen, mˆo˜i mˆo.t mˆe.nh dˆ `e n`ay ho˘a.c l`a d´ung, ho˘a.c l`a sai. Di.nh l´y cuˆo´i c` ung cu’a Fermat d˜a tˆo`n ta.i trˆen 350 n˘am, v`a m˜ai cho dˆe´n n˘am 1986, G. Faltings [1], mˆo.t nh`a To´an ho.c tre’ 26 tuˆo’i ngu.`o.i D´ u.c d˜a du.o..c nhˆa.n gia’i thu.o’.ng Fields vˆ `e mˆo.t cˆong tr`ınh trong h`ınh ho.c da.i sˆo´. Gia’i thu.o’.ng Fields l`a gia’i thu.o’.ng d`anh cho c´ac nh`a To´an ho.c tre’ tuˆo’i du.´o.i 40 tuˆo’i, 4 n˘am m´o.i cˆa´p mˆo.t lˆ `an v`a mˆo˜i lˆ`an khˆong qu´a 4 ngu.`o.i. Nhu. ch´ ung . . ta d˜a biˆe´t gia’i thu o’ ng Nobel khˆong gi`anh cho c´ac nh`a To´an ho.c, nˆen gia’i thu.o’.ng Fields du.o..c xem nhu. l`a gia’i “Nobel” cho To´an ho.c v`a gia’i thu.o’.ng du.o..c coi l`a mˆo.t trong nh˜ u.ng vinh du.. l´o.n nhˆa´t dˆo´i v´o.i mˆo.t ngu.`o.i l`am To´an ho.c. Ngo`ai ra G. Falting c`on du.a ra nh˜ u.ng y´ tu.o’.ng co. ba’n vˆ `e ch´ u.ng minh di.nh l´ y cuˆo´i c`ung cu’a Fermat v`ao th´ang 9 n˘am 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 v`ao n˘am 1997, nh`a To´an ho.c ngu.`o.i Anh l`a A. Weil sinh n˘am 1953 d˜a ch´ u.ng minh tro.n ve.n di.nh l´ y n`ay b˘`a ng mˆo.t phu.o.ng ph´ap kh´ac v`a ˆong du.o..c nhˆa.n gia’i thu.o’.ng rˆa´t d˘a.c biˆe.t, n˘am ˆa´y ˆong d˜a ngo`ai 40 tuˆo’i nˆen khˆong thˆe’ trao gia’i thu.o’.ng Fields. C`on gia’ thuyˆe´t Continuum d˜a du.o..c nh`a To´an ho.c M˜ y l`a P.J Cohen [5] gia’i quyˆe´t v`ao n˘am 1966 v`a ˆong d˜a du.o..c nhˆa.n gia’i thu.o’.ng Fields. `eu rˆa´t hiˆe’n nhiˆen l`a ch´ Mˆo.t diˆ ung ta c´o thˆe’ di t` u. mˆo.t sˆo´ mˆe.nh dˆ`e d˜a cho dˆe´n mˆo.t mˆe.nh dˆ `e m´o.i nh`o. mˆo.t sˆo´ t` u. nˆo´i, ch˘a’ng ha.n dˆo´i v´o.i mˆe.nh dˆ `e A, ch´ ung ta c´o thˆe’ lˆa´y phu’ di.nh cu’a n´o “khˆ ong A” (viˆe´t t˘a´t l`a ¬A), ho˘a.c dˆo´i . v´o i hai mˆe.nh dˆ `e d˜a cho A v`a B, ta c´o thˆe’ nˆo´i c´ac mˆe.nh dˆ `e d´o v´o.i nhau “A a B” (viˆe´t t˘a´t l`a A ∧ B), “A hay l` v` a B” (viˆe´t t˘a´t l`a A ∨ B), “Nˆe´u A th`ı B”
10 Chu.o.ng 1. Da.i sˆo´ mˆe.nh dˆ `e (viˆe´t t˘a´t l`a A → B), v`a “A khi v` a chı’ khi B” (viˆe´t t˘a´t l`a A ↔ B). C´ac k´ y . . hiˆe.u ¬, ∧, ∨, →, ↔ du o. c go.i l`a c´ ac ph´ep to´ . . an logic. C´ac ph´ep to´an n`ay du o. c x´ac di.nh du..a theo c´ac ba’ng chˆan l´ y du.´o.i dˆay. 1.1.1 ep phu’ di.nh (¬, not) Ph´ A ¬A T F F T Nhu. vˆa.y ngh˜ıa l`a khi A nhˆa.n gi´a tri. T th`ı ¬A nhˆa.n gi´a tri. F, v`a khi A nhˆa.n gi´a tri. F th`ı ¬A nhˆa.n gi´a tri. T. 1.1.2 Ph´ ep v` a (∧, and, hˆ o.i) A B A∧B T T T T F F F T F F F F `e A ∧ B nhˆa.n gi´a tri. T, khi v`a chı’ khi A v`a B dˆ Vˆa.y mˆe.nh dˆ `eu nhˆa.n gi´a tri. T. 1.1.3 Ph´ a (∨, or, tuyˆe’n) ep hay l` A B A∨B T T T T F T F T T F F F `e A ∨ B nhˆa.n gi´a tri. F, khi v`a chı’ khi A v`a B dˆ Vˆa.y mˆe.nh dˆ `eu nhˆa.n gi´a tri. F.
1.1. C´ac ph´ep to´an v`a ba’ng chˆan l´ y 11 1.1.4 Ph´ ep k´eo theo (→) A B (A→B) T T T T F F F T T F F T `e A → B nhˆa.n gi´a tri. F, khi v`a chı’ khi A (gia’ thiˆe´t) nhˆa.n Vˆa.y mˆe.nh dˆ gi´a tri. T v`a B (kˆe´t luˆa.n) nhˆa.n gi´a tri. F. Trong mˆo.t v`ai tru `o.ng ho..p, mˆe.nh dˆ . `e “Nˆe´u A th`ı B” du.o..c su’. du.ng nhu.ng khˆong quan tˆam dˆe´n c´ac gi´a tri. chˆan l´ `e mˆo.t c´ach dˆ y cu’a c´ac mˆe.nh dˆ `ay du’, ch˘a’ng ha.n nhu. c´ac mˆe.nh dˆ `e sau: 1. Nˆe´u 1+1=2 th`ı Paris l`a Thu’ dˆo cu’a nu.´o.c Ph´ap. 2. Nˆe´u 1+16=2 th`ı Paris l`a Thu’ dˆo cu’a nu.´o.c Ph´ap. 3. Nˆe´u 1+16=2 th`ı Rome l`a Thu’ dˆo cu’a nu.´o.c Ph´ap. Ta dˆ˜e d`ang nhˆa.n thˆa´y ca’ 3 mˆe.nh dˆ `e trˆen dˆ `eu nhˆa.n gi´a tri. chˆan l´ y l`a T, . nhu ng mˆo´i liˆen hˆe. gi˜ . . . u a gia’ thiˆe´t A v`a kˆe´t luˆa.n B khˆong ˘an kh´o p v´o i nhau. Do d´o dˆe’ da’m ba’o t´ınh logic v`a ch˘a.t ch˜e cua’ mˆo.t mˆe.ng dˆ `e, ch´ung ta pha’i su’. du.ng mˆo´i quan hˆe. d´o sao cho gi˜ u.a gia’ thiˆe´t A v`a kˆe´t luˆa.n B pha’i c´o mˆo´i quan hˆe. x´ac di.nh, thu.`o.ng l`a nguyˆen nhˆan. Ngo`ai ra, n´oi riˆeng trong thu..c tˆe´, ngu.`o.i ta hay d` ung mˆe.nh dˆ `e “Nˆe´u A th`ı . . B” du ´o i mˆo.t h`ınh th´ u c kh´ac, khˆong mˆau thuˆa˜n v`a hay du o. c su’. du.ng rˆo.ng . . . r˜ai, ch˘a’ng ha.n: “Nˆe´u ba.n c´o th`o.i gian th`ı ba.n dˆe´n th˘am tˆ oi”, c˜ung du.o..c hiˆe’u theo ngh˜ıa l`a: ong dˆe´n th˘ “Nˆe´u ba.n khˆ am tˆoi th`ı ba.n khˆ ong c´ o.i gian”. Diˆ o th` `eu n`ay luˆon luˆon d´ung v`ı theo luˆa.t logic sau dˆay: Mˆe.nh dˆ`e:“A → B” tu.o.ng du.o.ng v´o.i “¬B → ¬A”
12 Chu.o.ng 1. Da.i sˆo´ mˆe.nh dˆ `e 1.1.5 ep tu.o.ng du.o.ng (↔ Ph´ ↔) A B (A↔B) T T T T F F F T F F F T `e A ↔ B nhˆa.n gi´a tri. T, khi v`a chı’ khi A v`a B nhˆa.n c` Vˆa.y mˆe.nh dˆ ung gi´a tri.. 1.2 Cˆ u.c mˆ ong th´ `e e.nh dˆ Di.nh ngh˜ıa 1.2.1 Cˆ u.c mˆe.nh dˆ ong th´ `e du.o..c lˆa.p nˆen t` `e l`a mˆe.nh dˆ u. c´ac ch˜ u. c´ai La-tinh A, B, C, ... v`a kˆe’ ca’ c´ac ch˜u. c´ai La-tinh c´o chı’ sˆo´ A1 , B1, C1 , ... nh`o. c´ac ph´ep to´an logic. Mˆo.t c´ach ch´ınh x´ac ho.n, ch´ ung ta di.nh ngh˜ıa cˆ u.c mˆe.nh dˆ ong th´ `e b˘a` ng . c´ach dˆe. quy nhu sau: u. c´ai La-tinh , kˆe’ ca’ c´ac ch˜ (1) Tˆa´t ca’ c´ac ch˜ u. c´ai La-tinh c´o chı’ sˆo´ dˆ `eu l`a cˆong th´ uc. (2) Nˆe´u A v`a B l`a c´ac cˆong th´u.c th`ı (¬A), (A ∧ B), (A ∨ B), (A →B), (A ↔ B) c˜ ung l`a cˆong th´u.c u.c l`a mˆo.t cˆong th´ (3) Mˆo.t biˆe’u th´ u.c, nˆe´u n´o du.o..c lˆa.p nˆen t` u. co. so’. (1) v`a (2). Mˆo˜i mˆo.t phˆan bˆo´ c´ac gi´a tri. chˆan l´ y cu’a c´ac biˆe´n c´o m˘a.t trong cˆong th´ u.c cho ta mˆo.t gi´a tri. chˆan l´y cu’a cˆong th´ u.c. Do vˆa.y, mˆo˜i mˆo.t cˆong th´ u.c mˆe.nh `e x´ac di.nh mˆo.t h`am da.i sˆo´ logic n`ao d´o. H`am n`ay du.o..c x´ac di.nh du..a v`ao dˆ ba’ng chˆan l´ y cu’a cˆong th´ u.c d˜a cho.
u.c mˆe.nh dˆ 1.2. Cˆong th´ `e 13 Th´ı du. 1.2.1 Cho cˆong th´ u.c A = (((¬A) ∨ B) → C). T`ım h`am da.i sˆo´ logic tu.o.ng u´.ng cu’a cˆong th´ u.c A? Tru.´o.c hˆe´t ta lˆa.p ba’ng chˆan l´ y dˆ `ay du’ cu’a A. Mˆo˜i d`ong l`a mˆo.t bˆo. phˆan bˆo´ c´ac gi´a tri. chˆan l´ y cu’a c´ac biˆe´n A, B, C v`a . . tu o ng u . ´ ng l`a mˆo.t gi´a cu’a cˆong th´ . u c A. A B C ¬A (¬A) ∨ B A T T T F T T T T F F T F T F T F F T T F F F F T F T T T T T F T F T T F F F T T T T F F F T T F ung ta dˆ˜e d`ang x´ac di.nh du.o..c mˆo.t h`am da.i sˆo´ logic 3 biˆe´n f : Vˆa.y ch´ {T, F}3 → {T, F} du..a v`ao ba’ng chˆan l´ y 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 Ch´ u y ´ 1. Nˆe´u cˆong th´u.c mˆe.nh dˆ`e c´ u.a n biˆe´n mˆe.nh dˆ o ch´ `e th`ı ba’ng chˆ an l´y cu’a cˆ ong th´ . a cho pha’i ch´ u c d˜ . n u a 2 bˆ o. phˆ an bˆo´ c´ ac gi´ a tri. chˆ an l´y cu’a n biˆe´n d´ o. L` ao dˆe’ c´ am thˆe´ n` o thˆe’ viˆe´t dˆ `ay du’ 2n bˆo. phˆan bˆ o´ n` ay? Ch´ `an thu..c hiˆe.n “thuˆ ung ta chı’ cˆ . t chia dˆ a oi” du.o..c dˆ a˜n ra theo c´ ach quy na.p cu’a biˆe´n n: • n = 2: Khi d´ o 22 = 4 v` a chia 2 cho kˆe´t qua’ l` a 2. Ta lˆ a.p ba’ng nhu. sau:
14 Chu.o.ng 1. Da.i sˆo´ mˆe.nh dˆ `e o 23 = 8 v` • n = 3: Khi d´ a chia 2 cho kˆe´t qua’ l` a.p ba’ng nhu. a 4. Ta lˆ sau: • Mˆ o.t c´ ach tu.o.ng tu.. khi ch´ ung ta t˘ ang bˆ a.c cu’a hˆe. sˆo´ n lˆen v` a thu..c chˆ a´t khi lˆ a.p ba’ng ch´ ung ta viˆe´t cˆ `au tiˆen mˆ o.t dˆ o.t nu’.a trˆen l`a T v` a mˆo.t . nu’ a du ´ . . o i l` a F (ho˘ . . a.c ngu o. c la.i theo mˆ o.t nguyˆen t˘ ´ ac), rˆ ` o i dˆe´n c´ ac cˆ o.t tiˆe´p theo nhu ng ch´ . ung ta chı’ lˆ a.p mˆ . o.t nu’ a ba’ng trˆen theo thuˆ a.t chia dˆoi c´ o bˆa.c gia’m dˆ `an, cuˆo´i c` . . ung th`ı thu. c hiˆe.n copy nu’ a trˆen xuˆ o´ng nu’.a du.´ o.i l` a ho` an th`anh du’ 2n bˆ o. phˆan bˆo´ c´ ac gi´ a tri. chˆan l´y cu’a n biˆe´n c´ o m˘ a.t trong cˆ ong th´ . u c d˜a cho. 2. Phu.o.ng ph´ ap lˆ a.p ba’ng chˆ an l´y thu go.n Tru.´ o.c hˆe´t viˆe´t cˆong th´ u.c d˜ a cho th` anh mˆ o.t d`ong cu’a ba’ng, tiˆe´p dˆe´n l` a c´ ac d`ong du.o..c t´ınh lˆ `an lu.o..t theo gi´a tri. phˆan bˆ o´ cu’a c´ac biˆe´n c´ o m˘ a.t trong cˆong th´ . u c v` . . a tu o ng u . ´ ng l` a c´ac gi´ a tri. cu’a t` . u ng th`anh phˆ `an lˆa.p nˆen cˆ ong th´ . u c, v` a cuˆ o´i c`ung l` a tri. cu’a cˆ a gi´ ong th´ . . . u c du o. c t´ınh theo u.ng th` t` anh phˆ `an trˆen du..a theo ph´ep to´ an cuˆ o´i c`ung cu’a cˆ ong th´ u.c.
u.c mˆe.nh dˆ 1.2. Cˆong th´ `e 15 . 1.2.2 Lˆa.p ba’ng chˆan l´ Th´ı du u.c y thu go.n cu’a cˆong th´ A = (A ↔ B) → ((¬A) ∧ B) y thu go.n nhu. sau: ung ta lˆa.p ba’ng chˆan l´ Ch´ (A ↔ B) → ((¬ A) ∧ B) T T T F F F T T F F T F F F F F T T T T T F T F F T F F Phu.o.ng ph´ap lˆa.p ba’ng chˆan l´ y thu go.n du..a v`ao vi. tr´ı cu’a c´ac biˆe´n mˆe.nh dˆ `e v`a c´ac ph´ep to´an c´o m˘a.t trong cˆong th´ u.c l`am c´ac cˆo.t tu.o.ng ´.ng, nˆen vˆ u `e m˘a.t t´ınh to´an du.o..c tiˆe´t kiˆe.m th`o.i gian nhiˆ`eu ho.n v`a ba’ng lˆa.p do.n gia’n ho.n. 3. T´ınh u.u tiˆ en cu’a c´ ac ph´ ep to´ an Ta d˜ o´ ho.c dˆe’ gia’m thiˆe’u viˆe.c viˆe´t dˆ a biˆe´t trong sˆ a´u ngo˘a.c cho mˆo.t biˆe’u u.c sˆ th´ ong thu.` o´ ho.c thˆ o.ng l`a nhˆan, chia tru.´ o.c v` a cˆ u. sau, v` o.ng, tr` a c´ ac ph´ep to´an c´ o c` ung m´ . . . . . u c u u tiˆen du o. c thu. c hiˆe.n t` . u tr´ai qua pha’i. Trong c´ ac ph´ep to´ ung tu.o.ng tu.., ngu.` an logic c˜ o.i ta d˜ a du.a ra mˆ o.t quy u.´ o.c viˆe´t dˆ a´u ngo˘ a.c theo th´u. tu.. u.u tiˆen sau dˆ ay: 1 ¬; 2 ∧; 3 ∨; 4 →; 5 ↔ trong d´ o ch´u ´y hai ph´ep to´ o´i c` an cuˆ ung →, ↔ xuˆ a´t hiˆe.n nhiˆ `eu lˆ `an liˆen tiˆe´p th`ı lˆ a.p ngo˘ . a’ ng ha.n: A → B → C th`ı pha’i ai qua pha’i, ch˘ u tr´ a.c t` lˆ a.p ngo˘ a.c d´ ung l` a ((A → B) → C). Th´ı du. 1.2.3 Ch´ u.c ung ta lˆa.p ngo˘a. c cho cˆong th´
16 Chu.o.ng 1. Da.i sˆo´ mˆe.nh dˆ `e A = A ∨ ¬B → C ↔ A theo c´ac bu.´o.c sau dˆay: A ∨ (¬B) → C ↔ A (A ∨ (¬B)) → C ↔ A ((A ∨ (¬B)) → C) ↔ A (((A ∨ (¬B)) → C) ↔ A) 1.3 Mˆ o´ di.nh ngh˜ıa o.t sˆ 1.3.1 H` o´ logic am da.i sˆ Di.nh ngh˜ıa 1.3.1 o´ logic n biˆe´n l`a mˆo.t ´anh xa. cu’a tˆa.p ho..p {T, F}n v`ao am da.i sˆ • Mˆo.t h` {T, F}. • L´o.p c´ac h`am da.i sˆo´ logic nhˆa.n hai gi´a tri. {T, F } (ho˘a.c {0, 1}) c` ung v´o.i c´ac biˆe´n cu’a n´o du.o..c k´ y hiˆe.u l`a l´o.p h`am P 2 . n Ta dˆ˜e d`ang nhˆa.n thˆa´y r˘`a ng sˆo´ c´ac h`am da.i sˆo´ logic n biˆe´n l`a b˘`a ng 22 , v`ı r˘a` ng v´o.i n biˆe´n ta c´o 2n bˆo. phˆan bˆo´ c´ac gi´a tri. chˆan l´ y {T, F} v`a mˆo˜i mˆo.t bˆo. nhu. vˆa.y tu.o.ng u´.ng v´o.i mˆo.t gi´a tri. {T, F}, nˆen sˆo´ h`am tu.o.ng u ´.ng v´o.i n n biˆe´n pha’i l`a 22 . Th´ı du. 1.3.1 1. X´et l´o.p h`am P 2 mˆo.t biˆe´n gˆo`m c´o 22 = 4 h`am du.o..c cho theo ba’ng sau 1 dˆay: x\f f1 f2 f3 f4 T T T F F F T F T F trong d´o f2 (x) = x; f3(x) = ¬x
1.3. Mˆo.t sˆo´ di.nh ngh˜ıa 17 2. X´et l´o.p h`am P 2 hai biˆe´n gˆo`m c´o tˆa´t ca’ l`a: 22 = 16 h`am du.o..c cho theo 2 ba’ng sau dˆay: x1 x2 \f f1 f2 f3 f4 f5 f6 f7 f8 TT T T T T T T T T TF T T T T F F F F FT T T F F T T F F FF T F T F T F T F x1x2 \f f9 f10 f11 f12 f13 f14 f15 f16 TT F F F F F F F F TF T T T T F F F F FT T T F F T T F F FF T F T F T F T F trong d´o c´o mˆo.t sˆo´ h`am quen thuˆo.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 ; Ch´ uy ´ o’. dˆay thay ¬x b˘a` ng x. Ta biˆe´t mˆo˜i mˆo.t cˆong th´ u.c mˆe.nh dˆ `e tu.o.ng u ´.ng v´o.i mˆo.t h`am da.i sˆo´ logic, v`ı r˘`a ng th´u. nhˆa´t tˆa.p ho..p tˆa´t ca’ c´ac biˆe´n mˆe.nh dˆ `e l`a dˆe´m du.o..c, ch˘a’ng ha.n theo c´ach s˘a´p xˆe´p th´ u. tu.. sau dˆay A, B, C, ..., Z, A1, B1, C1 , ..., Z1 , ... Th´ u. hai l`a nˆe´u mˆo.t cˆong th´ u.c mˆe.nh dˆ `e n`ao d´o c´o ch´u.a c´ac biˆe´n i1 , i2, ..., in (i1 < i2 < ... < in ) trong tˆa.p kˆe’ du.o..c o’. trˆen th`ı khi d´o tu.o.ng u ´.ng ta c´o thˆe’ lˆa.p du.o..c mˆo.t h`am da.i sˆo´ logic v´o.i c´ac biˆe´n xi1 , xi2 , ..., xin . Th´ı du. 1.3.2 V´o.i cˆong th´ u.c A → B th`ı h`am da.i sˆo´ logic tu.o.ng u ´.ng l`a:
18 Chu.o.ng 1. Da.i sˆo´ mˆe.nh dˆ `e x1 x2 f (x1 , x2) T T T T F F F T T F F T c`on dˆo´i v´o.i cˆong th´ u.c B → A th`ı h`am da.i sˆo´ logic tu.o.ng u ´.ng l`a: x1 x2 g(x1 , x2) T T T T F T F T F F F T 1.3.2 Su.. dˆ o`ng nhˆ a´t d´ o`ng nhˆ ung - dˆ a´t sai Di.nh ngh˜ıa 1.3.2 Mˆo.t cˆong th´ u.c mˆe.nh dˆ `e du.o..c go.i l`a dˆ o`ng nhˆ a´t d´ ung (hay ` a ng d´ h˘ ung dˆo´i v´o.i mo.i ph´ep thˆe´ c´ac gi´a tri. chˆan ung), nˆe´u n´o nhˆa.n gi´a tri. d´ y cu’a c´ac biˆe´n c´o m˘a.t trong cˆong th´ l´ u.c. ung ta c´o thˆe’ n´oi r˘a` ng mˆo.t cˆong th´ Vˆa.y ch´ u.c mˆe.nh dˆ o`ng nhˆ `e l`a dˆ a´t d´ ung, . khi v`a chı’ khi h`am da.i sˆo´ logic tu o ng u. . ´ ng cu’a n´o nhˆa.n to`an gi´a tri. d´ ung, ho˘a.c c´o thˆe’ n´oi nˆe´u cˆo.t cuˆo´i c` ung cu’a ba’ng chˆan l´ y cu’a cˆong th´ . u c d˜a cho chı’ gˆo`m to`an gi´a tri. d´ung. Th´ı du. 1.3.3 a) Cˆong th´ u.c A = A ∨ (¬A) l`a dˆo`ng nhˆa´t d´ ung (hiˆe’n nhiˆen). b) Cˆong th´ u.c A = A ∧ B → A l`a dˆo`ng nhˆa´t d´ ung. Ta ch´ u.ng minh b˘`a ng pha’n ch´ u.ng nhu. sau: Gia’ su’. ngu.o..c la.i, A khˆong dˆo`ng nhˆa´t d´ung, ngh˜ıa l`a tˆo`n ta.i mˆo.t bˆo. phˆan bˆo´ I0 c´ac gi´a tri. chˆan l´ y cu’a c´ac biˆe´n c´o m˘a.t trong A sao cho A(I0) = False, t´ . u c l`a:  A ∧ B = T (1) A∧B →A=F ⇔ A = F (2)
1.3. Mˆo.t sˆo´ di.nh ngh˜ıa 19 Thay (2) v`ao (1) ta c´o: A ∧ B = F (3) So s´anh (1) v`a (3) suy ra mˆau thuˆa˜n. Vˆa.y A l`a dˆo`ng nhˆa´t d´ ung. Di.nh ngh˜ıa 1.3.3 Nˆe´u cˆong th´ u.c (A → B) l`a dˆo`ng nhˆa´t d´ ung th`ı khi d´o . . A du o. c go.i l`a logic k´eo theo B ho˘a.c B l`a logic k´eo theo t`. u A. Th´ı du. 1.3.4 Cˆong th´ u.c A ∧ (A → B) logic k´eo theo B. `an ch´ Thˆa.t vˆa.y, ta chı’ cˆ u.ng minh r˘`a ng cˆong th´ u.c A = (A ∧ (A → B) → B) l`a dˆo`ng nhˆa´t d´ ung. Ta lˆa.p ba’ng chˆan l´ y thu go.n sau dˆay: (A ∧ (A → B) → B) T T T T T T T T F T F F T F F F F T T T T F F F T F T F Di.nh ngh˜ıa 1.3.4 Hai cˆong th´ u.c A v`a B du.o..c go.i l`a logic tu.o.ng du.o.ng, u.c (A ↔ B) l`a dˆo`ng nhˆa´t d´ nˆe´u cˆong th´ ung. Th´ı du. 1.3.5 A → B v`a (¬A) ∨ B l`a hai cˆong th´ u.c logic tu.o.ng du.o.ng, u.c `an chı’ ra r˘`a ng cˆong th´ ngh˜ıa l`a ta chı’ cˆ A = (A → B) ↔ ((¬A) ∨ B) l`a dˆo`ng nhˆa´t d´ ung. Lˆa.p ba’ng chˆan l´ y thu go.n sau dˆay (A → B) ↔ ((¬A) ∨ B) T T T T F T T T F F T F F F F T T T T T T F T F T T T F