Chương 1: Đại số mệnh đề

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

Thêm vào BST

Báo xấu

80
lượt xem 8
download

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

Thông thường chúng ta thành lập các mệnh đề phức hợp từ các mệnh đề đơn giản. Trong chương này, chúng ta sẽ đi sâu nghiên cứu đầy đủ bản chất của đại số mệnh đề và tư duy suy diễn của nó một cách chặt chẽ, logic và mang tính thực tiễn.

Chủ đề:

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

Lưu

Nội dung Text: Chương 1: Đại số mệnh đề

Chương 1. Đại số mệnh đề Trần Thọ Châu Logic Toán. NXB Đại học quốc gia Hà Nội 2007. Tr 7-38. Từ khoá: Logic toán, Đại số mệnh đề, Hàm đại số logic. 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 1 ´. ` Dai sˆ mˆnh dˆ .oe e a’ 1.1 C´c ph´p to´n v` bang chˆn l´ . . . . . . . . . . a e a ay 8 ’. 1.1.1 Ph´p phu dinh (¬, not) . . . . . . . . . . . . . . . 10 e 1.1.2 Ph´p v` (∧, and, hˆi) . . . . . . . . . . . . . . . . 10 ea o. ’ 1.1.3 Ph´p hay l` (∨, or, tuyˆ n) . . . . . . . . . . . . . . 10 e a e 1.1.4 Ph´p k´o theo (→) . . . . . . . . . . . . . . . . . . 11 ee Ph´p tu.o.ng du.o.ng (↔ ) . . . . . . . . . . . . . . . 12 1.1.5 e Cˆng th´.c mˆnh dˆ . . . . . . . . . . . . . . . . . ` 1.2 o u e e 12 . ´ 1.3 Mˆt sˆ dinh ngh˜ . . . . . . . . . . . . . . . . . . oo. ıa 16 . ´ 1.3.1 H`m dai sˆ logic . . . . . . . . . . . . . . . . . . . 16 a .o Su. dˆ ng nhˆ t d´ng - dˆ ng nhˆ t sai . . . . . . . . . 18 ` ` ´ ´ 1.3.2 .o au o a ´ ´ 1.4 Mˆt sˆ t´ o o ınh chˆt . . . . . . . . . . . . . . . . . . . a 22 . Dang chuˆn t˘c cua cˆng th´.c mˆnh dˆ . . . . . ’´ ` ’ 1.5 aa o u e e 23 . . ’´ ’ ’´. 1.5.1 Dang chuˆ n t˘c tuyˆ n v` chuˆ n t˘c hˆi . . . . . . 23 aa ea aao . ’´ 1.5.2 Dang chuˆ n t˘c ho`n to`n . . . . . . . . . . . . . . 24 aa a a . e` ’’ 1.6 C´c hˆ dˆy du cua c´c ph´p to´n . . . . . . . . . a .a a e a 25 B`i tˆp chu.o.ng 1 . . . . . . . . . . . . . . . . . . 1.7 aa 34 .
Chu.o.ng 1. Dai sˆ mˆnh dˆ ´. ` 8 .oe e Thˆng thu.`.ng ch´ng ta th`nh lˆp c´c mˆnh dˆ ph´.c ho.p t`. c´c mˆnh ` o o u a aa e eu . ua e . . . ` do.n gian. Trong chu.o.ng n`y, ch´ng ta s˜ di sˆu nghiˆn c´.u dˆy du ban ` ’ ’’ dˆ e a u e a eua . duy suy diˆn cua n´ mˆt c´ch ch˘t ch˜, logic ˜’ooa ´ ´. `a a’ chˆ t cua dai sˆ mˆnh dˆ v` tu .oe e e a e . . .c tiˆn. v` mang t´nh thu ˜ a ı e . a’ 1.1 C´c ph´p to´n v` bang chˆn l´ a e a ay Ch´ng ta dˆu biˆt con ngu.`.i c´ kha n˘ng phan ´nh mˆi quan hˆ hiˆn thu.c ` ´ ´ ’a ’a u e e oo o ee .. . .a c´c su. vˆt b˘ ng nh˜.ng mˆnh dˆ. C´c mˆnh dˆ d´ du.o.c du.a ra du.´.i gi˜ a . a ` ` `o u .a u e e a e e o . . . .c kh´c nhau, ch˘ng han nhu. mˆt l`.i n´i, mˆt cˆu v˘n, mˆt ’ ` nhiˆu h`nh th´ eı u a a ooo oaa o . . . . .c To´n, L´, Ho´, hay su. mˆ phong cua mˆt b´.c tranh v.v.., nhu.ng ’ ’ cˆng th´ o u a y a .o ou . . ban trong d´ l` c´c mˆnh dˆ n`y c´ mang dˆy du y ngh˜ nhˆ t dinh hay `a o ` ´ co ’ ’´ oaa e e a ıa a . . .c du.´.i mˆt `oo ´e khˆng, ngh˜ l` c´c mˆnh dˆ d´ c´ mang theo t´nh chˆ t hiˆn thu o ıa a a e e ı a oo . . . . .c nhˆ t dinh, ch´. khˆng phai l` mˆt mˆnh dˆ suˆng, vˆ ngh˜ v` ´. `o ’ao h` th´ ınh u a u o e e o ıa, a . . .ng l`.i n´i ch´.a du.ng mˆt y ngh˜ khˆng nghiˆm t´c. ’a u c˜ng khˆng phai l` nh˜ u o oo u o´ ıo e u . . . viˆc n`o d´ theo mˆt c´ch th´.c nhˆ t dinh ` ´ e ’a Mˆt mˆnh dˆ phan ´nh mˆt su e a o oe o.. oa u a. . . . . v` su. viˆc d´ phan ´nh t´nh chˆn thu.c theo c´ch trˆn th` du.o.c goi l` mˆt ’a a. e o ı a a e ı .ao . . . . .o.c goi l` mˆt mˆnh dˆ sai. `u `o ` mˆnh dˆ d´ng ; Tr´i lai mˆnh dˆ d´ du . . a o e e a. e e e e . . . . .c chˆ t vˆ n dˆ ch´ng ta quan tˆm d˘c biˆt trong To´n hoc l` o. chˆ: ˜ aa`u ´´e . a’ o Thu a a e a . . . ˜. ` `a “Mˆi mˆt mˆnh dˆ ho˘c l` d´ng ho˘c l` sai, v` khˆng c´ mˆt mˆnh dˆ n`o ooe e aau aa ao ooe e . . . . . .a d´ng lai v`.a sai”. Dˆy ch´nh l` nˆi dung cua dinh l´ 2 - gi´ tri. ’. v` u u .u a ı ao y a. . .i vˆy, l´.p tˆ t ca c´c mˆnh dˆ du.o.c chia th`nh hai l´.p con: mˆt l´.p ´ ` Bo a o a ’ a ’. e e a o oo . . . `m tˆ t ca c´c mˆnh dˆ d´ng v` mˆt l´.p gˆ m tˆ t ca c´c mˆnh dˆ sai. Mˆi ˜ ` a ’a ´ ’a `u ´ ` gˆ o a e e aoo o e e o . . . mˆnh dˆ thuˆc mˆt trong c´c l´.p d´ s˜ nhˆn mˆt gi´ tri chˆn l´ d´ng (True, ` e e o o a o oe a o a . a yu . . . . . ´´ ´´ viˆt t˘t l` T) ho˘c sai (False, viˆt t˘t l` F). eaa a eaa . Ta k´ hiˆu c´c mˆnh dˆ b˘ ng c´c ch˜. c´i hoa A, B , C , ... c`n c´c biˆn e` `a ´ yea e a ua oa e . . mˆnh dˆ b˘ ng c´c ch˜. c´i A, B, C, ... v` ch´ng c´ kha n˘ng nhˆn c´c gi´ tri e` `a o ’a e a ua au aa a. . . chˆn l´ {T, F } ho˘c {1, 0}. ay a. Th´ du 1.1.1 ı.
a a’ 1.1. C´c ph´p to´n v` bang chˆn l´ a e ay 9 1. “Trˆn m˘t tr˘ng khˆng c´ ngu.`.i” (T) e aa o o o . ´ 2. “35 chia hˆt cho 6” (F) e ` 3. “B´c Hˆ sinh ng`y 19 th´ng 5 n˘m 1890” (T) a o a a a Ch´ y r˘ ng trong dinh l´ 2 - gi´ tri, ngu.`.i ta chı ph´t biˆ u r˘ ng: mˆi ’a ˜ ` e` ’a u´ a y a. o o . .ng khˆng kh˘ng dinh du.o.c r˘ ng ’ ` ` aau mˆt mˆnh dˆ ho˘c l` d´ng, ho˘c l` sai, nhu o e e. aa o a .a . . . . mˆi mˆt mˆnh dˆ ta c´ thˆ quyˆt dinh du.o.c liˆu n´ d´ng hay khˆng, ch˘ng ˜ ’ ’ ` ´ oo e e oe e. . e ou o a . . . ´ ´ ´ ’ ’ han dinh l´ cuˆi c`ng cua Fermat [1], gia thuyˆt Continuum [5]. Tˆ t nhiˆn, you e a e . . ˜ `a mˆi mˆt mˆnh dˆ n`y ho˘c l` d´ng, ho˘c l` sai. oo e e aau aa . . . . `.e ´i c`ng cua Fermat d˜ tˆ n tai trˆn 350 n˘m, v` m˜i cho dˆn ´ ’ Dinh l´ cuˆ u yo ao a aa e . n˘m 1986, G. Faltings [1], mˆt nh` To´n hoc tre 26 tuˆ i ngu.`.i D´.c d˜ ’ ’ a o a a o o u a . . .o.c nhˆn giai thu.o.ng Fields vˆ mˆt cˆng tr` trong h` hoc dai sˆ. Giai `oo ´ ’ ’ ’ du . a e. ınh ınh . . o . thu.o.ng Fields l` giai thu.o.ng d`nh cho c´c nh` To´n hoc tre tuˆ i du.´.i 40 ’ ’ a’ ’ ’o a a a a o . .i cˆ p mˆt lˆn v` mˆi lˆn khˆng qu´ 4 ngu.`.i. Nhu. ch´ng ’ ˜a o´ o` . a a o` tuˆ i, 4 n˘m m´ a o a o a o u .o.ng Nobel khˆng gi`nh cho c´c nh` To´n hoc, nˆn giai ´ ta d˜ biˆt giai thu ’ ’ ’ ae o a a a a e . thu.o.ng Fields du.o.c xem nhu. l` giai “Nobel” cho To´n hoc v` giai thu.o.ng ’ a’ .a’ ’ a . .o.c coi l` mˆt trong nh˜.ng vinh du. l´.n nhˆ t dˆi v´.i mˆt ngu.`.i l`m To´n ´´ du . ao u .o aooo oa a . . .a ra nh˜.ng y tu.o.ng co. ban vˆ ch´.ng minh ’`u u´’ hoc. Ngo`i ra G. Falting c`n du a o e . ´ ’ dinh l´ cuˆi c`ng cua Fermat v`o th´ng 9 n˘m 1994 (xem Gerd Falting the you a a a . Proof of Fermat’s Last Theorem by R. Taylor and A. Wiles Notices of the AMS, July 1995, p. 743 - 746), nhu.ng v`o n˘m 1997, nh` To´n hoc ngu.`.i aa aa o . Anh l` A. Weil sinh n˘m 1953 d˜ ch´.ng minh tron ven dinh l´ n`y b˘ ng ya ` a a au a . . . .o.ng ph´p kh´c v` ˆng du.o.c nhˆn giai thu.o.ng rˆ t d˘c biˆt, n˘m ˆ y ´. ´ ’ ’ mˆt phu o a a ao a aa eaa . . . . .o.ng Fields. C`n gia thuyˆt ˆng d˜ ngo`i 40 tuˆ’i nˆn khˆng thˆ trao giai thu ’ ’ ´ ’ ’ o a a oe o e o e Continuum d˜ du.o.c nh` To´n hoc M˜ l` P.J Cohen [5] giai quyˆt v`o n˘m ´ ’ a aa ya eaa . . 1966 v` ˆng d˜ du.o.c nhˆn giai thu.o.ng Fields. ’ ’ ao a a . . Mˆt diˆu rˆ t hiˆ n nhiˆn l` ch´ng ta c´ thˆ di t`. mˆt sˆ mˆnh dˆ d˜ cho ’ ’ o`a e´e .´. `a eau oe uooe e . dˆn mˆt mˆnh dˆ m´.i nh`. mˆt sˆ t`. nˆi, ch˘ng han dˆi v´.i mˆnh dˆ A, ’ ´ `o .´ ´ ´ ` e o e e o o ouo a oo e e . . . . ’´ ´´ ´ ’. ’o ch´ng ta c´ thˆ lˆ y phu dinh cua n´ “khˆng A” (viˆt t˘t l` ¬A), ho˘c dˆi u o ea o eaa ao . .i hai mˆnh dˆ d˜ cho A v` B , ta c´ thˆ nˆi c´c mˆnh dˆ d´ v´.i nhau “A ’´ `a `oo v´o e e a o eoa e e . . ´´ ´´ ´ v` B ” (viˆt t˘t l` A ∧ B ), “A hay l` B ” (viˆt t˘t l` A ∨ B ), “Nˆu A th` B ” a eaa a eaa e ı
Chu.o.ng 1. Dai sˆ mˆnh dˆ ´. ` 10 .oe e ´´ ´´ a’ (viˆt t˘t l` A → B ), v` “A khi v` chı khi B ” (viˆt t˘t l` A ↔ B ). C´c k´ eaa a eaa ay .o.c goi l` c´c ph´p to´n logic. C´c ph´p to´n n`y du.o.c hiˆu ¬, ∧, ∨, →, ↔ du . . a a e e a a e aa . . .a theo c´c bang chˆn l´ du.´.i dˆy. a’ x´c dinh du a. ayoa . ’. 1.1.1 Ph´p phu dinh (¬, not) e A ¬A T F F T Nhu. vˆy ngh˜a l` khi A nhˆn gi´ tri T th` ¬A nhˆn gi´ tri F, v` khi A nhˆn a ıa a a. ı a a. a a . . . . gi´ tri F th` ¬A nhˆn gi´ tri T. a. ı a a. . 1.1.2 Ph´p v` (∧, and, hˆi) ea o . A B A∧B T T T T F F F T F F F F ` ` a’ Vˆy mˆnh dˆ A ∧ B nhˆn gi´ tri T, khi v` chı khi A v` B dˆu nhˆn gi´ a e e a a. a e a a . . . . tri T. . ’ 1.1.3 Ph´p hay l` (∨, or, tuyˆ n) e a e A B A∨B T T T T F T F T T F F F ` ` a’ Vˆy mˆnh dˆ A ∨ B nhˆn gi´ tri F, khi v` chı khi A v` B dˆu nhˆn gi´ a e e a a. a e a a . . . . tri F. .
a a’ 1.1. C´c ph´p to´n v` bang chˆn l´ a e ay 11 1.1.4 Ph´p k´o theo (→) ee A B (A→B) T T T F T F F T T F F T ` ´ a’ ’ Vˆy mˆnh dˆ A → B nhˆn gi´ tri F, khi v` chı khi A (gia thiˆt) nhˆn a e e a a. e a . . . . ´a gi´ tri T v` B (kˆt luˆn) nhˆn gi´ tri F. a. a e a a. . . .`.ng ho.p, mˆnh dˆ “Nˆu A th` B ” du.o.c su. dung nhu.ng ` ´ .’. Trong mˆt v`i tru o oa e e e ı . . . ´ `oa ` a. ay’ a ’ khˆng quan tˆm dˆn c´c gi´ tri chˆn l´ cua c´c mˆnh dˆ mˆt c´ch dˆy du, o a ea e e. a . ch˘ng han nhu. c´c mˆnh dˆ sau: ’ ` a a e e . . 1. Nˆu 1+1=2 th` Paris l` Thu dˆ cua nu.´.c Ph´p. ´ ’o’ e ı a o a 2. Nˆu 1+1=2 th` Paris l` Thu dˆ cua nu.´.c Ph´p. ´ ’o’ e ı a o a 3. Nˆu 1+1=2 th` Rome l` Thu dˆ cua nu.´.c Ph´p. ´ ’o’ e ı a o a ˜a ´ `e` a’ Ta dˆ d`ng nhˆn thˆ y ca 3 mˆnh dˆ trˆn dˆu nhˆn gi´ tri chˆn l´ l` T, e a e e e a a . a ya . . . .ng mˆi liˆn hˆ gi˜.a gia thiˆt A v` kˆt luˆn B khˆng ˘n kh´.p v´.i nhau. ´ ´ ´a ’ nhu oeeu e ae oa oo . . ’ ` oe’ ’ ınh e’o ’ Do d´ dˆ dam bao t´ logic v` ch˘t ch˜ cua mˆt mˆng dˆ, ch´ng ta phai aa e e u . . . su. dung mˆi quan hˆ d´ sao cho gi˜.a gia thiˆt A v` kˆt luˆn B phai c´ mˆi ´ ´ ´a ´ ’. ’ ’oo o eo u e ae . . .`.ng l` nguyˆn nhˆn. quan hˆ x´c dinh, thu o ea . a e a . Ngo`i ra, n´i riˆng trong thu.c tˆ, ngu.`.i ta hay d`ng mˆnh dˆ “Nˆu A th` ´ ` ´ a oe .e o u e ee ı . .´.i mˆt h` th´.c kh´c, khˆng mˆu thuˆn v` hay du.o.c su. dung rˆng ˜ .’. B ” du o o ınh u a o a aa o . . ’ ng han: r˜i, ch˘ a a . “Nˆu ban c´ th`.i gian th` ban dˆn th˘m tˆi”, c˜ng du.o.c hiˆ u theo ngh˜a ’ ´ ´ e.oo ı. e ao u e ı . l`: a “Nˆu ban khˆng dˆn th˘m tˆi th` ban khˆng c´ th`.i gian”. Diˆu n`y luˆn ´ ´ `a e. o e a o ı. o oo e o luˆn d´ng v` theo luˆt logic sau dˆy: ou ı a a . Mˆnh dˆ:“A → B ” tu.o.ng du.o.ng v´.i “¬B → ¬A” ` e e o .
Chu.o.ng 1. Dai sˆ mˆnh dˆ ´. ` 12 .oe e Ph´p tu.o.ng du.o.ng (↔ ) 1.1.5 e A B (A↔B) T T T T F F F T F T F F ` a’ Vˆy mˆnh dˆ A ↔ B nhˆn gi´ tri T, khi v` chı khi A v` B nhˆn c`ng a e e a a. a au . . . . gi´ tri. a. Cˆng th´.c mˆnh dˆ ` 1.2 o u e e . Dinh ngh˜ 1.2.1 Cˆng th´.c mˆnh dˆ l` mˆnh dˆ du.o.c lˆp nˆn t`. c´c ch˜. `a e ` ıa o u e e e . a e ua u . . . . . c´i La-tinh c´ chı sˆ A , B , C , ... ’ ´ ae’a o ’o 1 1 1 c´i La-tinh A, B , C, ... v` kˆ ca c´c ch˜ a a u nh`. c´c ph´p to´n logic. oa e a Mˆt c´ch ch´ x´c ho.n, ch´ng ta dinh ngh˜a cˆng th´.c mˆnh dˆ b˘ ng e` `a oa ınh a u ıo u e . . . . sau: c´ch dˆ quy nhu a e. (1) Tˆ t ca c´c ch˜. c´i La-tinh , kˆ ca c´c ch˜. c´i La-tinh c´ chı sˆ dˆu l` ’ ´ o ’o` a´e a ’a e’a ua ua .c cˆng th´ o u (2) Nˆu A v` B l` c´c cˆng th´.c th` (¬A), (A ∧ B ), (A ∨ B ), (A →B ), ´ e a aa o u ı .c (A ↔ B ) c˜ng l` cˆng th´ u ao u (3) Mˆt biˆ u th´.c l` mˆt cˆng th´.c, nˆu n´ du.o.c lˆp nˆn t`. co. so. (1) v` ’ ´ ’ o e uaoo u eo .aeu a . . . (2). Mˆi mˆt phˆn bˆ c´c gi´ tri chˆn l´ cua c´c biˆn c´ m˘t trong cˆng th´.c ˜. ´ ´ a oa a . a y’ a oo eoa o u . .c. Do vˆy, mˆi mˆt cˆng th´.c mˆnh ˜ o a. ay’ o cho ta mˆt gi´ tri chˆn l´ cua cˆng th´ u a ooo u e . . . . .o.c x´c dinh du.a v`o `a. ´ dˆ x´c dinh mˆt h`m dai sˆ logic n`o d´. H`m n`y du . a . e oa o aoa a a . . . bang chˆn l´ cua cˆng th´.c d˜ cho. ’ ay’ o ua
1.2. Cˆng th´.c mˆnh dˆ ` o u e e 13 . Th´ du 1.2.1 Cho cˆng th´.c A = (((¬A) ∨ B ) → C ). T` h`m dai sˆ logic ´ ı. o u ım a .o .o.ng u.ng cua cˆng th´.c A? ’o tu ´ u Tru.´.c hˆt ta lˆp bang chˆn l´ dˆy du cua A. ´ a y` ’ ’’ oe a a . ˜ ´ ´ a. ay’ a Mˆi d`ng l` mˆt bˆ phˆn bˆ c´c gi´ tri chˆn l´ cua c´c biˆn A, B , C v` oo a o o a oa e a .. .o.ng u.ng l` mˆt gi´ cua cˆng th´.c A. ao a’ o tu ´ u . AB C ¬A (¬A) ∨ B A TT T F T T TT F F T F TF T F F T TF F F F T FT T T T T FT F T T F FF T T T T FF F T T F Vˆy ch´ng ta dˆ d`ng x´c dinh du.o.c mˆt h`m dai sˆ logic 3 biˆn f : ˜a ´ ´ a u e a. oa .o e . . . {T, F}3 → {T, F} du.a v`o bang chˆn l´ cua A nhu. sau: a’ ay’ . 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´ y u´ 1. Nˆu cˆng th´.c mˆnh dˆ c´ ch´.a n biˆn mˆnh dˆ th` bang chˆn l´ cua ´ `o u ´ ` ı’ ay’ eo u e e e e e . . .c d˜ cho phai ch´.a 2n bˆ phˆn bˆ c´c gi´ tri chˆn l´ cua n ´ ’ a. ay’ cˆng th´ a o u u o a oa . ’ ’´a ’ biˆn d´. L`m thˆ n`o dˆ c´ thˆ viˆt dˆy du 2n bˆ phˆn bˆ n`y? ´ ea eo e e` ´ ´ eoa o a oa . Ch´ng ta chı cˆn thu.c hiˆn “thuˆt chia dˆi” du.o.c dˆn ra theo c´ch ˜ ’` a o u a e a a . . . . ´ ’ quy nap cua biˆn n: e . • n = 2: Khi d´ 22 = 4 v` chia 2 cho kˆt qua l` 2. Ta lˆp bang nhu. ´ ’a a’ o a e . sau:
Chu.o.ng 1. Dai sˆ mˆnh dˆ ´. ` 14 .oe e • n = 3: Khi d´ 23 = 8 v` chia 2 cho kˆt qua l` 4. Ta lˆp bang nhu. ´ ’a a’ o a e . sau: • Mˆt c´ch tu.o.ng tu. khi ch´ng ta t˘ng bˆc cua hˆ sˆ n lˆn v` thu.c .´ a’ oa u a eo ea. . . . .a trˆn l` T v` mˆt ´ eo` ´.a e a’ o’ chˆ t khi lˆp bang ch´ng ta viˆt cˆt dˆu tiˆn mˆt nu a u ea ao . . . .a du.´.i l` F (ho˘c ngu.o.c lai theo mˆt nguyˆn t˘c), rˆ i dˆn c´c cˆt ´ `e ao o´ ’ nu oa a o ea . .. . . .ng ch´ng ta chı lˆp mˆt nu.a bang trˆn theo thuˆt chia ´ ’a o’ ’ tiˆp theo nhu e u e a . . . .c hiˆn copy nu.a trˆn xuˆng nu.a ` ´ ´ ’ ’ ’ dˆi c´ bˆc giam dˆn, cuˆi c`ng th` thu o oa a ou ı. e e o . . du.´.i l` ho`n th`nh du 2n bˆ phˆn bˆ c´c gi´ tri chˆn l´ cua n biˆn c´ ´ ´ ’ a. ay’ oa a a o a oa eo . .c d˜ cho. m˘t trong cˆng th´ a a o u . 2. Phu.o.ng ph´p lˆp bang chˆn l´ thu gon ’ aa ay . . .´.c hˆt viˆt cˆng th´.c d˜ cho th`nh mˆt d`ng cua bang, tiˆp dˆn l` ´´ ´´ ’’ Tru o e e o ua a oo eea . c´c d`ng du.o.c t´nh lˆn lu.o.t theo gi´ tri phˆn bˆ cua c´c biˆn c´ m˘t ` ´ ´ a. a o’ a ao .ı a eoa . . .c v` tu.o.ng u.ng l` c´c gi´ tri cua t`.ng th`nh phˆn lˆp `a a.’u trong cˆng th´ a o u ´ aa a a. .c, v` cuˆi c`ng l` gi´ tri cua cˆng th´.c du.o.c t´nh theo ´ aa.’ o nˆn cˆng th´ eo u aou u .ı t`.ng th`nh phˆn trˆn du.a theo ph´p to´n cuˆi c`ng cua cˆng th´.c. ` ´ ’o u a a e e a ou u .
1.2. Cˆng th´.c mˆnh dˆ ` o u e e 15 . Th´ du 1.2.2 Lˆp bang chˆn l´ thu gon cua cˆng th´.c ’ ’o ı. a ay u . . A = (A ↔ B ) → ((¬A) ∧ B ) Ch´ng ta lˆp bang chˆn l´ thu gon nhu. sau: ’ u a ay . . (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´p lˆp bang chˆn l´ thu gon du.a v`o vi tr´ cua c´c biˆn ´ ’ a .ı’ a aa ay e . . . mˆnh dˆ v` c´c ph´p to´n c´ m˘t trong cˆng th´.c l`m c´c cˆt tu.o.ng `aa e e e aoa o ua ao . . . .ng, nˆn vˆ m˘t t´nh to´n du.o.c tiˆt kiˆm th`.i gian nhiˆu ho.n v` bang e`aı ´. ` a’ u ´ e. a ee o e . .n gian ho.n. ’ lˆp do a . ınh u.u tiˆn cua c´c ph´p to´n ’ 3. T´ e a e a ’ ’ ’ ´ ´ ´´ o. e ’ Ta d˜ biˆt trong sˆ hoc dˆ giam thiˆ u viˆc viˆt dˆ u ngo˘c cho mˆt biˆ u ae e e ea a oe . . . th´.c sˆ hoc thˆng thu.`.ng l` nhˆn, chia tru.´.c v` cˆng, tr`. sau, v` c´c ´ u o. o o aa o ao u aa . .c u.u tiˆn du.o.c thu.c hiˆn t`. tr´i qua phai. ’ ph´p to´n c´ c`ng m´ e a ou u e eua . . . Trong c´c ph´p to´n logic c˜ng tu.o.ng tu., ngu.`.i ta d˜ du.a ra mˆt quy a e a u o a o . . .´.c viˆt dˆ u ngo˘c theo th´. tu. u.u tiˆn sau dˆy: ´a ´ uo e a u. e a . 1 ¬; 2 ∧; 3 ∨; 4 →; 5 ↔ ´ ´e `` trong d´ ch´ ´ hai ph´p to´n cuˆi c`ng →, ↔ xuˆ t hiˆn nhiˆu lˆn liˆn o uy e a ou a eae . . tr´i qua phai, ch˘ ng han: A → B → C th` phai ’ ´ ’ ’ tiˆp th` lˆp ngo˘c t` a e ıa au a ı . . . lˆp ngo˘c d´ng l` ((A → B ) → C ). a au a . . Th´ du 1.2.3 Ch´ng ta lˆp ngo˘ c cho cˆng th´.c ı. u a a o u . .
Chu.o.ng 1. Dai sˆ mˆnh dˆ ´. ` 16 .oe e A = A ∨ ¬B → C ↔ A theo c´c bu.´.c sau dˆy: a o a A ∨ (¬B ) → C ↔ A (A ∨ (¬B )) → C ↔ A ((A ∨ (¬B )) → C ) ↔ A (((A ∨ (¬B )) → C ) ↔ A) ´ 1.3 Mˆt sˆ dinh ngh˜ oo. ıa . ´ 1.3.1 H`m dai sˆ logic a .o Dinh ngh˜ 1.3.1 ıa . • Mˆt h`m dai sˆ logic n biˆn l` mˆt ´nh xa cua tˆp ho.p {T, F}n v`o ´ ´ .’a oa .o e a oa a . . . . {T, F}. • L´.p c´c h`m dai sˆ logic nhˆn hai gi´ tri {T, F } (ho˘c {0, 1}) c`ng v´.i ´ oaa .o a a. a u o . . .o.c k´ hiˆu l` l´.p h`m P . ´’o c´c biˆn cua n´ du . y e a o a e a . 2 n Ta dˆ d`ng nhˆn thˆ y r˘ ng sˆ c´c h`m dai sˆ logic n biˆn l` b˘ ng 22 , v` ˜a a` e a` ´a ´ ´ ´ e a oa a .o a ı . .i n biˆn ta c´ 2n bˆ phˆn bˆ c´c gi´ tri chˆn l´ {T, F} v` mˆi mˆt ˜ ` ´ ´ r˘ ng v´ a o e o o a oa a.ay aoo . . . vˆy tu.o.ng u.ng v´.i mˆt gi´ tri {T, F}, nˆn sˆ h`m tu.o.ng u.ng v´.i n ´ bˆ nhu a o ´ o o a. e oa ´ o . . . 2n ´ ’a biˆn phai l` 2 . e Th´ du 1.3.1 ı. 1. X´t l´.p h`m P 2 mˆt biˆn gˆ m c´ 22 = 4 h`m du.o.c cho theo bang sau 1 ´` ’ eo a o eo o a . . dˆy: a x\f f1 f2 f3 f4 T T T F F F T F T F trong d´ f2 (x) = x; f3(x) = ¬x o
.´ 1.3. Mˆt sˆ dinh ngh˜ oo. ıa 17 2. X´t l´.p h`m P 2 hai biˆn gˆ m c´ tˆ t ca l`: 22 = 16 h`m du.o.c cho theo 2 ´` ´ oa ’a eo a eo a . ’ bang sau dˆy: a 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´ c´ mˆt sˆ h`m quen thuˆc nhu. sau: .´ oo o oa o . 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´ y o. dˆy thay ¬x b˘ ng x. ` u´’ a a Ta biˆt mˆi mˆt cˆng th´.c mˆnh dˆ tu.o.ng u.ng v´.i mˆt h`m dai sˆ logic, ˜. ´ooo ` ´ e u e e ´ ooa .o . . v` r˘ ng th´. nhˆ t tˆp ho.p tˆ t ca c´c biˆn mˆnh dˆ l` dˆm du.o.c, ch˘ng han ı` ’ ´. ´ ´ `ae ´ . a ’a a u aa e e e a . . . . tu. sau dˆy A, B, C, ..., Z, A , B , C , ..., Z , ... ´´ theo c´ch s˘p xˆp th´ . a ae u a 1 1 1 1 Th´. hai l` nˆu mˆt cˆng th´.c mˆnh dˆ n`o d´ c´ ch´.a c´c biˆn i1 , i2, ..., in ´ ` a oo u a e ´ u ae oo u e e . . .o.c o. trˆn th` khi d´ tu.o.ng u.ng ta c´ thˆ ’ ’ (i1 < i2 < ... < in ) trong tˆp kˆ du . ’ e ae ı o ´ oe . lˆp du.o.c mˆt h`m dai sˆ logic v´.i c´c biˆn xi1 , xi2 , ..., xin . ´ ´ a oa .o oa e . . . Th´ du 1.3.2 V´.i cˆng th´.c A → B th` h`m dai sˆ logic tu.o.ng u.ng l`: ´ ı. oo u ıa .o ´ a
Chu.o.ng 1. Dai sˆ mˆnh dˆ ´. ` 18 .oe e x1 x2 f (x1 , x2) T T T F T F F T T F F T c`n dˆi v´.i cˆng th´.c B → A th` h`m dai sˆ logic tu.o.ng u.ng l`: ´ ´ oooo u ıa .o ´ a x1 x2 g (x1 , x2) T T T T F T F F T F F T Su. dˆ ng nhˆ t d´ ng - dˆ ng nhˆ t sai ` ` ´ ´ 1.3.2 .o au o a Dinh ngh˜ 1.3.2 Mˆt cˆng th´.c mˆnh dˆ du.o.c goi l` dˆ ng nhˆ t d´ng (hay ` ` ´ ıa oo u e e . .ao au . . . h˘ ng d´ng), nˆu n´ nhˆn gi´ tri d´ng dˆi v´.i moi ph´p thˆ c´c gi´ tri chˆn ` ´ ´ ´ a u eoa a .u oo e ea a.a . . .c. ´ y’ a l´ cua c´c biˆn c´ m˘t trong cˆng th´ eoa o u . Vˆy ch´ng ta c´ thˆ n´i r˘ ng mˆt cˆng th´.c mˆnh dˆ l` dˆ ng nhˆ t d´ng, ’ ` ` `ao ´ a u o eoa oo u e e au . . . khi v` chı khi h`m dai sˆ logic tu.o.ng u.ng cua n´ nhˆn to`n gi´ tri d´ng, ´ a’ ’oa a .o ´ a a.u . ho˘c c´ thˆ n´i nˆu cˆt cuˆi c`ng cua bang chˆn l´ cua cˆng th´.c d˜ cho ’ ´. ´ ’ ’ ay’ o a o eoe o ou ua . ` ’o chı gˆ m to`n gi´ tri d´ng. a a .u Th´ du 1.3.3 ı. a) Cˆng th´.c A = A ∨ (¬A) l` dˆ ng nhˆ t d´ng (hiˆ n nhiˆn). ’ ` ´ o u ao au e e .c A = A ∧ B → A l` dˆ ng nhˆ t d´ng. ` ´ b) Cˆng th´ o u ao au Ta ch´.ng minh b˘ ng phan ch´.ng nhu. sau: Gia su. ngu.o.c lai, A khˆng ` ’ ’’ u a u o .. ` ` ´ ´ a. ay’ dˆ ng nhˆ t d´ng, ngh˜ l` tˆ n tai mˆt bˆ phˆn bˆ I0 c´c gi´ tri chˆn l´ cua o au ıa a o . ooao a .. .c l`: ´ c´c biˆn c´ m˘t trong A sao cho A(I0) = False, t´ a a eoa u .  A ∧ B = T (1) A∧B →A=F ⇔ A = F (2)
.´ 1.3. Mˆt sˆ dinh ngh˜ oo. ıa 19 Thay (2) v`o (1) ta c´: A ∧ B = F (3) a o ˜ ` ´ So s´nh (1) v` (3) suy ra mˆu thuˆn. Vˆy A l` dˆ ng nhˆ t d´ng. a a a a a ao au . Dinh ngh˜ 1.3.3 Nˆu cˆng th´.c (A → B ) l` dˆ ng nhˆ t d´ng th` khi d´ ` ´ ´ ıa eo u ao au ı o . .o.c goi l` logic k´o theo B ho˘c B l` logic k´o theo t`. A. A du . . a e a a e u . Th´ du 1.3.4 Cˆng th´.c A ∧ (A → B ) logic k´o theo B. ı. o u e .ng minh r˘ ng cˆng th´.c ` ’` Thˆt vˆy, ta chı cˆn ch´ aa a u a o u .. A = (A ∧ ( A → B ) → B ) ` ´ ’ l` dˆ ng nhˆ t d´ng. Ta lˆp bang chˆn l´ thu gon sau dˆy: ao au a ay a . . (A ∧ (A → B) → B) T TT T TT T T TF T FF F T FF F TT T T FF F TF F Dinh ngh˜ 1.3.4 Hai cˆng th´.c A v` B du.o.c goi l` logic tu.o.ng du.o.ng, ıa o u a .a . . .c (A ↔ B ) l` dˆ ng nhˆ t d´ng. ` ´ ´ nˆu cˆng th´ eo u ao au Th´ du 1.3.5 A → B v` (¬A) ∨ B l` hai cˆng th´.c logic tu.o.ng du.o.ng, ı. a a o u .c ` ’` ’ ngh˜ l` ta chı cˆn chı ra r˘ ng cˆng th´ ıa a a a o u A = (A → B ) ↔ ((¬A) ∨ B ) ` ´ l` dˆ ng nhˆ t d´ng. ao au ’ Lˆp bang chˆn l´ thu gon sau dˆy a ay a . . (A → B) ↔ ((¬A) ∨ B) T T TT F T T T T FF F F F T F TT T T T T F TF T T F
Chu.o.ng 1. Dai sˆ mˆnh dˆ ´. ` 20 .oe e Bang cˆng th´.c tu.o.ng du.o.ng ’ o u 1. A ∧ B ≡ B ∧ A (giao ho´n) a A∨B ≡B∨A 2. A ∧ (B ∧ C ) ≡ (A ∧ B ) ∧ C (kˆt ho.p) ´ e. A ∨ (B ∨ C ) ≡ (A ∨ B ) ∨ C ´ 3. A ∧ (B ∨ C ) ≡ (A ∧ B ) ∨ (A ∧ C ) (luˆt phˆn phˆi hai bˆn a a o e . dˆi v´.i ∧ v` ∨) ´ A ∨ (B ∧ C ) ≡ (A ∨ B ) ∧ (A ∨ C ) oo a 4. ¬(A ∧ B ) ≡ (¬A ∨ ¬B ) (luˆt de Morgan) a . ¬(A ∨ B ) ≡ (¬A ∧ ¬ B ) 5. A ∧ (¬A) ≡ False A ∨ (¬A) ≡ True 6. A ∧ True ≡ A A ∨ False ≡ A ’. 7. ¬(¬A) ≡ A (luˆt phu dinh k´p) a e . ’ 8. (A ∧ A) ≡ A (luˆt lu˜ d˘ ng) a ya . (A ∨ A) ≡ A .´ 9. A ∧ (A ∨ B ) ≡ A (luˆt hˆ p thu) aa . A ∨ (A ∧ B ) ≡ A Dinh ngh˜ 1.3.5 Mˆt cˆng th´.c du.o.c goi l` dˆ ng nhˆ t sai (hay h˘ ng sai), ` ` ´ ıa oo u . .ao a a . . .i moi ph´p thˆ c´c gi´ tri chˆn l´ cua c´c biˆn ´ ´ ´ ´ a. ay’ a nˆu n´ nhˆn gi´ tri sai dˆi v´ eoa a. oo e ea e . . c´ m˘t trong cˆng th´.c d´. oa o uo . Bo.i vˆy trong bang chˆn l´ cua cˆng th´.c n`y, cˆt cuˆi c`ng cua bang ´ ’a ’ ay’ o ’ ’ ua o ou . . ` a y ’o chˆn l´ chı gˆ m to`n gi´ tri sai. a a.
.´ 1.3. Mˆt sˆ dinh ngh˜ oo. ıa 21 Th´ du 1.3.6 ı. a) Cˆng th´.c A = A ↔ (¬A) - dˆ ng nhˆ t sai. ` ´ o u o a ’ ’ Ta lˆp bang chˆn l´ thu gon cua A: a ay . . A↔ (¬A) TF F FF T ` ´ ’ ’ b) A = A ∧ (¬A) l` dˆ ng nhˆ t sai. Ta lˆp bang chˆn l´ thu gon cua A: ao a a ay . . A ∧ (¬A) F T F F F T Vˆy ta c´ thˆ n´i r˘ ng cˆng th´.c A l` dˆ ng nhˆ t d´ng, khi v` chı khi ’ o eo` ` ´ a’ a a o u ao au . ` ´ (¬A) l` dˆ ng nhˆ t sai. ao a Dinh ngh˜ 1.3.6 Mˆt mˆnh dˆ (du.o.c cho du.´.i dang ngˆn ng˜. h`ng ng`y ` ıa o e e o. o ua a . . . . . h` th´.c) nhˆn du.o.c t`. mˆt cˆng th´.c dˆ ng nhˆ t d´ng n`o ` ´ ho˘c ngˆn ng˜ ınh u a o u a .uoo uo au a . . . .i c´c mˆnh dˆ sao cho c`ng mˆt biˆn du.o.c thˆ ` ´ ´’ ` ´ ´ d´ b˘ ng c´ch thˆ c´c biˆn bo a oa a ea e e e u o e e . . . bo.i c`ng mˆt mˆnh dˆ th` mˆnh dˆ d´ du.o.c goi l` logic d´ng. `ıe `o ’u o e e e . .a u . . . Th´ du 1.3.7 Cho cˆng th´.c dˆ ng nhˆ t d´ng A = ((A ∨ B ) ∧ (¬B ) → A). ` ´ ı. o uo au ` Ta c´ mˆnh dˆ sau dˆy l` logic d´ng: oe e aa u . .i mu.a ho˘c tuyˆt ro.i, v` tuyˆt khˆng ro.i th` tr`.i mu.a”. ´ ´ ´ “Nˆu tr` e o a e a e o ıo . Dinh ngh˜ 1.3.7 Mˆt mˆnh dˆ nhˆn du.o.c t`. mˆt cˆng th´.c dˆ ng nhˆ t ` ` ´ ıa o e ea .uoo uo a . . . . . .i c´c mˆnh dˆ sao cho c`ng mˆt biˆn du.o.c thˆ ` ´ ´’ ` ´ ´ sai b˘ ng c´ch thˆ c´c biˆn bo a a a ea e e e u oe e . . . bo.i c`ng mˆt mˆnh dˆ th` mˆnh dˆ d´ du.o.c goi l` logic sai. `ıe `o ’u o e e e . .a . . . Th´ du 1.3.8 Ta x´t cˆng th´.c dˆ ng nhˆ t sai A = A ∧ (¬A). Khi d´ nˆu ` ´ ´ ı. eo uo a oe ` ` ` ta thay A b˘ ng mˆnh dˆ “Tˆi di hoc” th` mˆnh dˆ sau dˆy l` logic sai: a e e o ıe e aa . . . “Tˆi di hoc v` tˆi khˆng di hoc”. o . ao o . Dinh ngh˜ 1.3.8 Mˆt cˆng th´.c A du.o.c goi l` thu.c hiˆn du.o.c (hay thoa ’ ıa oo u . .a. e . . . . .o.c), nˆu tˆ n tai ´t nhˆ t mˆt bˆ phˆn bˆ c´c gi´ tri chˆn l´ cua c´c biˆn ´` ´ o o a oa ´ ´ a. ay’ a du . e o .ı a e .. c´ m˘t trong cˆng th´.c A sao cho A nhˆn gi´ tri d´ng dˆi v´.i bˆ phˆn bˆ ´ ´ oa o u a a .u oooao . . . n`y. a
Chu.o.ng 1. Dai sˆ mˆnh dˆ ´. ` 22 .oe e ´ ´ 1.4 Mˆt sˆ t´ o o ınh chˆt a . Dinh l´ 1.4.1 Nˆu A v` A → B l` c´c cˆng th´.c dˆ ng nhˆ t d´ng th` B ` ´ ´ y e a aa o uo au ı . ` ´ c˜ng dˆ ng nhˆ t d´ng. u o au Ch´.ng minh: (phan ch´.ng) ’ u u . ngu.o.c lai, B khˆng dˆ ng nhˆ t d´ng. Khi d´ tˆ n tai mˆt bˆ ` `. ´ ’’ Gia su o o au oo oo .. . . ´ ´ a. ay’ a phˆn bˆ I0 c´c gi´ tri chˆn l´ cua c´c biˆn c´ m˘t trong A v` B sao cho a o a eoa a . ` ´ ´ ’ B (I0) = F (1). M˘t kh´c, theo gia thiˆt (A → B ) l` dˆ ng nhˆ t d´ng, nˆn a a e ao au e . (A → B )(I0) = A(I0) → B (I0) = T (2). T`. (1) v` (2) suy ra A(I0) = F . Diˆu n`y mˆu thuˆn v´.i gia thiˆt A l` ˜ ` ´ ’ u a ea a ao e a ` ´ dˆ ng nhˆ t d´ng. o au Dinh l´ 1.4.2 Nˆu A l` mˆt cˆng th´.c dˆ ng nhˆ t d´ng c´ ch´.a c´c biˆn ` ´ ´ ´ y e aoo uo au oua e . . A1 , A2, ..., An, v` cˆng th´.c B l` cˆng th´.c nhˆn du.o.c t`. A b˘ ng c´ch thˆ ` ´ ao u ao u a .u a a e . .c A , A , ..., A v`o c´c biˆn tu.o.ng u.ng A , A , ..., A th` cˆng ´ c´c cˆng th´ ao u na a e ´ ıo 1 2 1 2 n .c B c˜ng dˆ ng nhˆ t d´ng, ngh˜ l` ph´p thˆ trong mˆt cˆng th´.c dˆ ng ` ` ´ ´ th´ u u o au ıa a e e oo uo . nhˆ t d´ng cho ta mˆt cˆng th´.c dˆ ng nhˆ t d´ng. ` ´ ´ au oo uo au . Ch´.ng minh: (tru.c tiˆp) ´ u e . Gia su. cho mˆt bˆ phˆn bˆ I0 c´c gi´ tri chˆn l´ cua c´c biˆn c´ m˘t ´ ´ ’’ a. ay’ a ooao a eoa . . . .c B . Khi d´ c´c cˆng th´.c A (I ), A (I ), ..., A (I ) nhˆn c´c trong cˆng th´ o u oa o u aa . 10 20 n0 .o.ng u.ng l` b , b , ..., b trong d´ b ho˘c l` T ho˘c F. Nˆu ta thˆ bˆ ´ ´. gi´ tri tu a. ´ a12 oi a a a e eo . . n gi´ tri b1 , b2, ..., bn cho c´c biˆn tu.o.ng u.ng A1 , A2, ..., An trong cˆng th´.c A ´ a. a e ´ o u .c A l` dˆ ng nhˆ t d´ng v` gi´ ` ´ th` A(b1 , b2, ..., bn) nhˆn gi´ tri T, v` cˆng th´ ı a a. ıo u ao au aa . .i gi´ tri chˆn l´ cua cˆng th´.c B tai I , t´.c l` B nhˆn gi´ tri n`y tr`ng v´ a . a y ’ o .a u o u .0ua a a . tri T dˆi v´.i bˆ phˆn bˆ I0 n´i trˆn. V` I0 du.o.c chon tu` y, nˆn B l` cˆng ´ ´ oooao oe ı y´ e ao . . . . .c dˆ ng nhˆ t d´ng. ` ´ th´ o u au Dinh l´ 1.4.3 Nˆu B1 nhˆn du.o.c t`. A1 b˘ ng c´ch thˆ B v`o mˆt ho˘c ` ´ ´ y e a .u a a e a o a . . . . .c dˆ ng nhˆ t ` ` ´ e .ı’ nhiˆu vi tr´ cua A th` ((A ↔ B ) → (A1 ↔ B1)) l` cˆng th´ o ı ao u a .`.ng ho.p, nˆu A v` B l` logic tu.o.ng du.o.ng th` A v` B c˜ng ´ d´ng. Tru o u e a a ı 1a1u . logic tu.o.ng du.o.ng.
1.5. Dang chuˆ n t˘c cua cˆng th´.c mˆnh dˆ ’´ ` aa’o u e e 23 . . Ch´.ng minh: X´t mˆt bˆ phˆn bˆ I0 c´c gi´ tri chˆn l´ cua c´c biˆn. Nˆu ´ ´ ´ a. ay’ a u eooao a e e .. .i bˆ phˆn bˆ n`y th` cˆng th´.c ´. ´ ´ A v` B nhˆn gi´ tri dˆi lˆp nhau dˆi v´ o a a a.oa oo. a oa ıo u . A ↔ B nhˆn gi´ tri F, v` do d´ ((A ↔ B ) → (A1 ↔ B1)) nhˆn gi´ tri T. a a. a o a a. . . a . aı` ´ ’a Tr´i lai, nˆu A v` B nhˆn c`ng gi´ tri, v` v` r˘ ng B1 chı kh´c A1 tai a. e a au a . . .a B , trong khi d´ A ch´.a A, do vˆy trong tru.`.ng ´ mˆt sˆ vi tr´ m` B1 ch´ oo.ıa u o1u a o . . .p n`y, (A ↔ B ) nhˆn gi´ tri T, (A ↔ B ) c˜ng nhˆn gi´ tri T, v` do d´ ho a a a. u a a. a o . . . 1 1 ((A ↔ B ) → (A1 ↔ B1 )) nhˆn gi´ tri T. a a. . .o.c chon tu` y, nˆn cˆng th´.c ((A ↔ B ) → (A ↔ B )) l` dˆ ng ` V` I0 du . ı y´ e o u ao . 1 1 ´ nhˆ t d´ng. au Trˆn dˆy l` mˆt sˆ t´ chˆ t vˆ dˆ ng nhˆ t d´ng rˆ t do.n gian, dˆ h`nh ´e` ˜ı e a a o o ınh a ` o .´ ´ ´ ’ au a e dung, v` t´ bˆ t biˆn cua t´ chˆ t dˆ ng nhˆ t d´ng l` ho`n to`n ch´.ng ´` ´ ´ ’ ınh a o ´ a ınh a e au aa a u minh du.o.c.. Dang chuˆn t˘c cua cˆng th´.c mˆnh dˆ ’´ ` ’ 1.5 aa o u e e . . ’´ ’ ’´o 1.5.1 Dang chuˆ n t˘ c tuyˆ n v` chuˆ n t˘ c hˆi aa e a aa . . Dinh ngh˜ 1.5.1 Mˆt cˆng th´.c mˆnh dˆ du.o.c goi l` dang chuˆ n t˘c ’´ ` ıa oo u e e .a. aa . . . . tuyˆ n, nˆu n´ l` tuyˆ n cua mˆt ho˘c nhiˆu hang th´.c hˆi trong d´ mˆi hang ’ ’’ ˜ ´ ` e e oa e o a e. uo oo. . . . th´.c hˆi du.o.c lˆp nˆn t`. hˆi cua mˆt ho˘c nhiˆu biˆn v` phu dinh cua biˆn. ` ´ ´ .a e uo ’ ’. ’ uo o a e ea e . . . . . Th´ du 1.5.1 ı. a) A = (A ∧ B ) ∨ (A ∧ B ) ∨ (A ∧ B ∧ C ) ’´ ’ ’a. b) B = (A ∧ (B ∨ C )) ∨ (A ∧ B ) ∨ A khˆng phai l` dang chuˆ n t˘c tuyˆ n o aa e .ng ta biˆn dˆ i th`nh phˆn th´. 1: A ∧ (B ∨ C ) ≡ (A ∧ B ) ∨ (A ∧ C ) ’a ´ ` nhu eo a u ta c´ cˆng th´.c sau: B = (A ∧ B ) ∨ (A ∧ C ) ∨ (A ∧ B ) ∨ A l` chuˆ n ’ oo u a a ’ ´ t˘c tuyˆ n. a e Dinh ngh˜ 1.5.2 Mˆt cˆng th´.c mˆnh dˆ du.o.c goi l` dang chuˆ n t˘c hˆi, ’´. ` ıa oo u e e . .a. aao . . . nˆu n´ l` hˆi cua mˆt ho˘c nhiˆu hang th´.c tuyˆ n, trong d´ mˆi hang th´.c ’ ˜ ´ ` e oa o ’ o a e u e oo. u . . . . .o.c lˆp nˆn t`. tuyˆ n cua mˆt ho˘c nhiˆu biˆn v` phu dinh cua biˆn. ’ ’ ` ´ ´ e’ ’. ’ tuyˆ n du . a e u e o a e ea e . . .
Chu.o.ng 1. Dai sˆ mˆnh dˆ ´. ` 24 .oe e Th´ du 1.5.2 ı. a) A = A ∧ (A ∨ (B ∧ C )) ∧ (A ∨ B ) khˆng phai l` dang chuˆ n t˘c hˆi, nhu.ng ’´. ’a. o aao ta biˆn dˆ i th`nh phˆn th´. hai: (A ∨ (B ∧ C )) ≡ (A ∨ B ) ∧ (A ∨ C ) ’ ´ ` eo a a u .c sau l` dang chuˆ n t˘c hˆi: ’´. khi d´ ta c´ cˆng th´ o oo u a. aao A = A ∧ (A ∨ B ) ∧ (A ∨ C ) ∧ (A ∨ B ). ’´. b) B = (A ∨ B ) ∧ (A ∨ C ) ∧ (A ∨ B ∨ C ) ∧ A - dang chuˆ n t˘c hˆi. aao . ’´ 1.5.2 Dang chuˆ n t˘ c ho`n to`n aa a a . Dinh ngh˜ 1.5.3 Mˆt cˆng th´.c mˆnh dˆ du.o.c goi l` chuˆ n t˘c tuyˆ n ’´ ’ ` ıa oo u e e .a aa e . . . . ho`n to`n, nˆu n´ l` tuyˆ n cua c´c hang th´.c hˆi, trong d´ khˆng c´ mˆt ’’a. ´ a a e oa e uo oo oo . . .c hˆi n`o ch´.a biˆn v` phu dinh cua n´, v` nˆu mˆt biˆn c´ m˘t ´ ´ ´ ’. ’ o ae hang th´ o a u u ea o eoa . . . . .c hˆi th` n´ phai c´ m˘t trong moi hang th´.c hˆi kh´c. ’oa trong mˆt hang th´ o o. u. ıo uo a . . .. . Th´ du 1.5.3 ı. a) Cˆng th´.c A = (A ∧ A ∧ B ) ∨ (A ∧ B ) ∨ (A ∧ C ) khˆng phai l` dang ’a. o u o .c th´. nhˆ t c´ biˆn A v` ’´ ’ ı` ´ ´ chuˆ n t˘c tuyˆ n ho`n to`n, v` r˘ ng hang th´ aa e a a a u u aoe a . .c tuyˆ n, nhu.ng ta biˆn dˆ i ’ ’ ´ ’. ’o phu dinh cua n´ trong c`ng mˆt hang th´ u o. u e eo . th`nh phˆn th´. nhˆ t: ` ´ a a u a (A ∧ A ∧ B ) ≡ (A ∧ A) ∧ B ≡ False ∧ B ≡ False, ta c´ cˆng th´.c oo u A = False ∨ (A ∧ B ) ∨ (A ∧ C ) ≡ (A ∧ B ) ∨ (A ∧ C ) l` dang chuˆ n t˘c tuyˆ n nhu.ng khˆng phai l` dang chuˆ n t˘c tuyˆ n ’´ ’ ’´ ’ ’a. a. aa e o aa e ho`n to`n, v` r˘ ng mˆi hang th´.c hˆi o. dˆy thiˆu tˆn biˆn th´. ba, c`n ˜ ` ´ ´ u o’ a a a ıa o. ee e u o . ’´ ’ ’ ch˘ng han: (A ∧ B ∧ C ) ∨ (A ∧ B ∧ C ) l` dang chuˆ n t˘c tuyˆ n ho`n a a. aa e a . to`n. a
a e` ’’a 1.6. C´c hˆ dˆy du cua c´c ph´p to´n .a e a 25 b) Cˆng th´.c A = (A ∧ B ∧ C ) ∨ (A ∧ B ∧ C ) ∨ (A ∧ B ∧ C ) l` dang chuˆ n ’ o u a. a ’ ´ t˘c tuyˆ n ho`n to`n. a e a a Dinh ngh˜ 1.5.4 Mˆt cˆng th´.c mˆnh dˆ du.o.c goi l` chuˆ n t˘c hˆi ho`n ’´. ` ıa oo u e e . .a aao a . . . .c tuyˆ n, trong d´ khˆng c´ mˆt hang ’ ´ e oa o ’ a . to`n, nˆu n´ l` hˆi cua c´c hang th´ a u e oo oo. . . .c tuyˆ n n`o ch´.a biˆn v` phu dinh cua n´, v` nˆu mˆt biˆn c´ m˘t trong ’ ´ ´ ´ ’. ’ o ae th´ u ea u ea o eoa . . .c tuyˆ n th` n´ phai c´ m˘t trong moi hang th´.c tuyˆ n kh´c. ’ ’ ’oa mˆt hang th´ o. u e ıo u e a . . .. Th´ du 1.5.4 ı. ’´. ’. a) A = (A ∨ B ) ∧ (A ∨ B ) ∧ A - khˆng phai dang chuˆ n t˘c hˆi ho`n to`n, o aao a a .c hˆi th´. 3 chı c´ mˆt biˆn v` thiˆu biˆn B nhu.ng ı` ´ ´ ´ ’o o v` r˘ ng hang th´ o a u u eı e e . . . cˆng th´.c n`y l` dang chuˆ n t˘c hˆi. ’´. o u aa. aao ’´. b) B = (A ∨ B ∨ C ) ∧ (A ∨ B ∨ C ) ∧ (A ∨ B ∨ C ) l` dang chuˆ n t˘c hˆi a. aao ho`n to`n. a a e` ’’ 1.6 C´c hˆ dˆy du cua c´c ph´p to´n a .a a e a Ch´ng ta d˜ biˆt mˆi mˆt cˆng th´.c mˆnh dˆ n biˆn tu.o.ng u.ng v´.i mˆt ˜. ´ooo ` ´ u ae u e e e ´ oo . . ´ logic n biˆn, trong d´ c´c biˆn v` h`m dˆu nhˆn gi´ tri T ho˘c ´ ´ aa ` h`m dai sˆ a .o e oa e e a a. a . . .n n˜.a, dˆi v´.i c´c cˆng th´.c tu.o.ng du.o.ng dˆu sinh ra c`ng mˆt h`m ´ ` F. Ho u ooao u e u oa . ´ dai sˆ logic. .o Vˆ n dˆ ngu.o.c lai, liˆu c´ phai mˆi h`m dai sˆ logic c˜ng sinh ra tu.o.ng ˜ a` ´e ´ ’ eo oa .o u .. . .ng mˆt cˆng th´.c mˆnh dˆ theo mˆt c´ch n`o d´? ` u ´ oo u e e oa ao . . . .o.c tra l`.i mˆt c´ch kh˘ng dinh nh`. dinh l´ sau dˆy. ’ ` ’o Diˆu n`y du . ea oa a o. y a . . Dinh l´ 1.6.1 Mˆi mˆt h`m dai sˆ logic dˆu sinh ra tu.o.ng u.ng mˆt cˆng ˜oa ´ ` y o .o e ´ oo . . . .c mˆnh dˆ c´ ch´.a c´c ph´p to´n ¬, ∧, ∨. `o u a th´ u e e e a . Ch´.ng minh: Gia su. f (x1, x2 , ..., xn) l` mˆt h`m dai sˆ logic. R˜ r`ng h`m ´ ’’ u aoa .o oa a . ’’ ˜ n ˜ ` o’ n`y c´ thˆ biˆ u diˆn qua mˆt bang chˆn l´ gˆ m 2 d`ng, trong d´ mˆi d`ng aoee e a yo o ooo . .o.ng u.ng ´ ´ a o o a oa a . a y’ a l` mˆt bˆ phˆn bˆ c´c gi´ tri chˆn l´ cua c´c biˆn x1, x2, ..., xn v` tu e a ´ .. aa.’ a l` gi´ tri cua h`m f (x1 , x2, ..., xn).