Bài giảng Toán rời rạc - Phần 6: Đại số Bool và hàm Bool (TS. Nguyễn Viết Đông)

ầ Ph n VI ạ ố Đ i S Bool và hàm Bool

ạ

ễ

ế

Biên so n:Nguy n Vi Đông

George Boole (1815-1864)

Tài liệu tham khảo

n [1] GS.TS. Nguyễn Hữu Anh, Toán rời rạc,

Nhà xuất bản giáo dục.

n [2] TS.Trần Ngọc Hội, Toán rời rạc

Đại Số Bool

(cid:0)

Moät ñaïi soá Bool (A,(cid:0) ,(cid:0) ) laø moät taäp hôïp A (cid:0) vôùi hai pheùp toaùn (cid:0) , (cid:0) , töùc laø hai aùnh xaï:

(cid:0) : A(cid:0) A (cid:0)

(x,y) (cid:0) x(cid:0) y vaø (cid:0) : A(cid:0) A (cid:0) A (x,y)(cid:0) x(cid:0) y thoûa 5 tính chaát sau:

Đại Số Bool

n Tính giao hoaùn: (cid:0) x,y(cid:0) A

x(cid:0) y = y(cid:0) x; x(cid:0) y = y(cid:0) x;

n Tính keát hôïp: (cid:0) x,y,z(cid:0) A (x(cid:0) y) (cid:0) z = x(cid:0) (y (cid:0) z); (x(cid:0) y) (cid:0) z = x(cid:0) (y (cid:0) z).

n Tính phaân boá: (cid:0) x,y,z(cid:0) A

x(cid:0) (y (cid:0) z) = (x(cid:0) y) (cid:0) (x(cid:0) z); x(cid:0) (y(cid:0) z) = (x(cid:0) y) (cid:0) (x(cid:0) z).

Đại Số Bool

n Coù caùc phaàn töû trung hoøa 1 vaø 0:

(cid:0) x (cid:0) A

n Moïi phaàn töû ñeàu coù phaàn töû buø:

x(cid:0) 1 = 1(cid:0) x = x; x(cid:0) 0 = 0(cid:0) x = x.

(cid:0) x (cid:0) A,

x (cid:0) A,

x x

x x (cid:0) = (cid:0) x = 0; x x (cid:0) = (cid:0) x = 1.

(cid:0)

Đại Số Bool

Ví dụ:

Xeùt F laø taäp hôïp taát caû caùc daïng meänh ñeà theo n bieán p1, p2,…,pn vôùi hai pheùp toaùn noái lieàn (cid:0) , pheùp toaùn noái rôøi (cid:0) , trong ñoù ta ñoàng nhaát caùc daïng meänh ñeà töông ñöông. Khi ñoù F laø moät ñaïi soá Bool vôùi phaàn töû 1 laø haèng ñuùng 1, phaàn töû 0 laø haèng sai 0, phaàn töû buø cuûa daïng meänh ñeà E laø daïng meänh ñeà buø

Đại Số Bool

Xeùt taäp hôïp B = {0, 1}. Treân B ta

ñònh nghóa hai

ộ ạ ố

ở

Khi đó, B tr thành m t đ i s Bool

pheùp toaùn (cid:0) ,(cid:0) nhö sau:

Đại Số Bool

Cho ñaïi soá Bool (A,(cid:0) ,(cid:0) ). Khi ñoù vôùi

1 0; 0 1.

moïi x,y(cid:0) A, ta coù: 1) x(cid:0) x = x; x(cid:0) x = x. 2) x(cid:0) 0 = 0(cid:0) x =0; x(cid:0) 1 =1(cid:0) x = 1. 3) Phaàn töû buø cuûa x laø duy

� x y;

x y

nhaát x

� x y.

x y

vaø = x; =� 4) Coâng thöùc De Morgan: =�

5) Tính haáp thuï:x(cid:0) (x(cid:0) y) = x; x(cid:0) (x(cid:0) y)

= x.

Định nghĩa hàm Bool

Haøm Bool n bieán laø aùnh xaï

f : Bn (cid:0) B , trong ñoù B = {0, 1}.

Như vậy haøm Bool n bieán laø moät haøm soá coù daïng : f = f(x1,x2,…,xn), trong ñoù moãi bieán trong x1, x2,…, xn vaø f chỉ nhaän giaù trò trong B = {0, 1}. Kyù hieäu Fn ñeå chæ taäp caùc haøm Bool n bieán. Ví duï: Daïng meänh ñeà E = E(p1,p2,…,pn) theo n bieán p1, p2,…, pn laø moät haøm Bool n bieán.

Bảng chân trị

Xeùt haøm Bool n bieán f(x1,x2,…,xn)

Vì moãi bieán xi chæ nhaän hai giaù trò 0, 1 neân chæ coù 2n tröôøng hôïp cuûa boä bieán (x1,x2,…,xn).

Do ñoù, ñeå moâ taû f, ta coù theå laäp baûng goàm 2n haøng ghi taát caû caùc giaù trò cuûa f tuøy theo 2n tröôøng hôïp cuûa bieán. Ta goïi ñaây laø baûng chaân trò cuûa f

Ví dụ

Xeùt keát quả f trong vieäc thoâng qua moät quyeát ñònh döïa vaøo 3 phieáu baàu x, y, z 1. Moãi phieáu chæ laáy moät trong hai giaù trò: 1 (taùn thaønh) hoaëc 0 (baùc boû). 2. Keát q aủ f laø 1 (thoâng qua quyeát ñònh) neáu

ñöôïc ña soá phieáu taùn thaønh, laø 0

(khoâng thoâng

qua quyeát ñònh) neáu ña soá phieáu

baùc boû.

Hàm Bool

Khi ñoù f laø haøm Bool theo 3 bieán x, y, z coù baûng chaân trò nhö sau:

Các phép toán trên hàm Bool

ượ ị ư c đ nh nghĩa nh

Các phép toán trên Fn đ sau: 1. Pheùp coäng Bool (cid:0) :

Vôùi f, g (cid:0) cuûa f vaø g:

Fn ta ñònh nghóa toång Bool f (cid:0) g = f + g – fg

(cid:0) x = (x1,x2,…,xn)(cid:0) Bn,

(f (cid:0) g)(x) = f(x) + g(x) – f(x)g(x)

Các phép toán trên hàm Bool

2. Pheùp nhaân Bool (cid:0) :

Vôùi f, g (cid:0) Fn ta ñònh nghóa tích Bool cuûa f vaø g

f (cid:0) g = fg

(cid:0) x=(x1,x2,…,xn)(cid:0) Bn,

(f (cid:0) g)(x) = f(x)g(x)

Ta thöôøng vieát fg thay cho f (cid:0) g

Các phép toán trên hàm Bool

Fn ta ñònh nghóa haøm buø cuûa f nhö

3) Pheùp laáy haøm buø: Vôùi f (cid:0) sau:

= - 1

ứ ự

(cid:0)

trên Fn Fn thì x = (x1, x2, …, xn)(cid:0) Bn , f(x) (cid:0)

4) Th t ớ V i f, g f g (cid:0) (cid:0)  g(x)

ố ờ

ạ

ắ ủ

D ng n i r i ch

ính t c c a Hàm Bool

ợ

ậ

ế

ủ

ế x1 ,x2,

ừ ơ

đ n.

c g i là t ủ

ượ ọ ứ là tích khác không c a m t s h u h n t

đ n.

ộ ố ữ ạ ừ ơ ừ ơ

ủ

đ n.

i ti u ứ

ứ

ể

ễ

Xét t p h p các hàm Bool c a n bi n Fn theo n bi n …,xn ix n Mỗi hàm bool xi hay đ n Đ n th c ơ n T t ừ ố ể là tích khác không c a đúng n t n Công th c đa th c là công th c bi u di n hàm Bool thành

ứ ơ

ứ

ễ

ứ ổ ủ t ng c a các đ n th c. n D ng n i r i chính t c ể ắ là công th c bi u di n hàm Bool ố ờ ạ ừ ố ể ủ ổ t thành t ng c a các t

i ti u.

ắ ủ

ố ề

ạ

D ng n i li n chính t c c a hàm Bool

ủ ừ ố ể i đ i ầ ố ạ là ph n bù c a các t i ti u. M i t ỗ ừ

n Từ t t

ố ạ ủ ổ ừ ơ i đ i là t ng Boole c a n t t đ n.

n Công th c bi u di n hàm Boole f thành tích c a các

ủ ứ ể

ố ề ễ ạ d ng n i li n chính t c ủ ắ c a hàm i đ i g i là

ừ ố ạ ọ t t Boole f

Công thức đa thức tối tiểu

ả

ộ

ứ ủ

ứ

ế ơ công th c G n u

→

: {1,2,..,k} ố ừ ơ ủ

ề

ọ ớ l} sao cho v i m i ơ ố ừ

đ n c a mi không nhi u h n s t

n Đ n gi n h n ơ ứ Cho hai công th c đa th c c a m t hàm Bool : f = m1(cid:0) m2 (cid:0) …. (cid:0) mk (F) f = M1 (cid:0) M2 (cid:0) … (cid:0) Ml (G) ả ơ ằ đ n gi n h n Ta nói r ng công th c F ồ ạ ơ { 1,2,…, t n t i đ n ánh i(cid:0) {1,2,..,k} thì s t ơ ủ đ n c a M

(cid:0) (i)

(cid:0)

Công thức đa thức tối tiểu

ơ ư

ơ ơ ả ế

ứ ố ể : i ti u

ượ ọ ứ iố t c g i là

ế ơ ủ ư ả

n Đ n gi n nh nhau ả ả ơ ơ N u F đ n gi n h n G và G đ n gi n h n F ả ơ thì ta nói F và G đ n gi n nh nhau ứ ** Công th c đa th c t ủ Công th c F c a hàm Bool f đ ơ ứ ớ ấ ỳ ti u ể n u v i b t k công th c G c a f mà đ n ả ơ gi n h n F thì F và G đ n gi n nh nhau

ươ

ể ồ ng pháp bi u đ Karnaugh

ế

ặ

ớ

Xét f là hàm Bool theo n bi n x1,x2,…,xn v i n = 3 ho c 4.

ườ

ợ

ng h p n = 3:

ị ủ

ả

ế ả

ẽ ộ ả ị

ủ ả

ứ

ớ

ị ủ ng ng v i 8 hàng c a b ng chân tr , đ

f là hàm Bool theo 3 bi n x, y, z. Khi đó b ng chân tr c a f ữ ồ g m 8 hàng. Thay cho b ng chân tr c a f ta v m t b ng ch ượ ươ ậ ồ c nh t g m 8 ô, t : ấ đánh d u nh sau

Vô ù i q u i ö ô ù c :

1. Khi moät oâ naèm trong daõy ñöôïc ñaùnh daáu bôûi x thì taïi ñoù x =1, bôûi thì taïi ñoù x =0, töông töï cho y, z.

2. Caùc oâ taïi ñoù f baèng 1 seõ ñöôïc ñaùnh daáu (toâ ñaäm hoaëc gaïch cheùo). Taäp caùc oâ ñöôïc ñaùnh daáu ñöôïc goïi laø bieåu ñoà Karnaugh cuûa f, kyù hieäu laø kar(f).

f laø haøm Bool theo 4 bieán x, y, z, t. Khi ñoù baûng chaân trò cuûa f goàm 16 haøng. Thay cho baûng chaân trò cuûa f ta veõ moät baûng chöõ nhaät goàm 16 oâ, töông öùng vôùi 16 haøng cuûa baûng chaân trò, ñöôïc ñaùnh daáu nhö sau:

Tröôøng hôïp n = 4:

Vôùi qui öôùc:

1. Khi moät oâ naèm trong daõy ñöôïc ñaùnh daáu bôûi x thì taïi ñoù x =1, bôûi thì taïi ñoù x =0, töông töï cho y, z, t.

2. Caùc oâ taïi ñoù f baèng 1 seõ ñöôïc ñaùnh daáu (toâ ñaäm hoaëc gaïch cheùo). Taäp caùc oâ ñöôïc ñaùnh daáu ñöôïc goïi laø bieåu ñoà karnaugh cuûa f, kyù hieäu laø kar(f).

Ñònh lyù

ế

Cho f, g là các hàm Bool theo n bi n x1,x2, …,xn. Khi đoù: a) kar(fg) = kar(f)(cid:0) kar(g).

c) kar(f) goàm ñuùng moät oâ khi vaø chæ khi f laø moät từ toái tieåu f g

d) kar(f) (cid:0)

kar(g) (cid:0)

b) kar(f(cid:0) g) = kar(f)(cid:0) kar(g).

Teá baøo

Hai oâ ñöôïc goïi laø keà nhau (theo nghóa roäng), neáu chuùng laø hai oâ lieàn nhau hoaëc chuùng laø oâ ñaàu, oâ cuoái cuûa cuøng moät haøng (coät) naøo ñoù. Nhaän xeùt raèng, do caùch ñaùnh daáu nhö treân, hai oâ keà nhau chæ leäch nhau ôû moät bieán duy nhaát.

Tế bào là hình chữ nhật (theo nghĩa rộng) gồm

Neáu T laø moät teá baøo thì T laø bieåu ñoà karnaugh cuûa moät ñôn thöùc duy nhaát m, caùch xaùc ñònh m nhö sau: laàn löôït chieáu T leân caùc caïnh, neáu toaøn boä hình chieáu naèm troïn trong moät töø ñôn naøo thì töø ñôn ñoù môùi xuaát hieän trong m.

2k ô (k = 0,1,…,n – 1)

Ví du 1ï: