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

Hàm Bool n biến là một ánh xạ f : Bn → B, trong đó B = {0, 1}. Như vậy hàm Bool n biến là một hàm số có dạng: f = f(x1, x2, ..., xn), trong đó mỗi biến trong x1, x2, ..., xn chỉ nhận 2 giá trị 0, 1 và f nhận giá trị trong B = {0, 1}.
Nội dung trích xuất từ tài liệu:
Phần VI: Đại Số Bool và hàm Bool Phần VI Đại Số Bool và hàm Bool Biên soạn:Nguyễn Viết Đông George Boole (1815-1864) 1 2 Tài liệu tham khảo Đại Số Bool Moät ñaïi soá Bool (A,,) laø moät taäp hôïp A   vôùi hai pheùp toaùn , , töùc laø hai aùnh xaï: [1] GS.TS. Nguyễn Hữu Anh, Toán rời rạc,  : AA  A Nhà xuất bản giáo dục. (x,y) xy  [2] TS.Trần Ngọc Hội, Toán rời rạc vaø : AA  A (x,y)xy thoûa 5 tính chaát sau: 3 4 1 Đại Số Bool Đại Số Bool Tính giao hoaùn: x,yA Coù caùc phaàn töû trung hoøa 1 vaø 0: x A   xy = yx; x1 = 1x = x; xy = yx; x0 = 0x = x. Tính keát hôïp: x,y,zA  (xy) z = x(y z); Moïi phaàn töû ñeàu coù phaàn töû buø: x A,  (xy) z = x (y z).  x A, Tính phaân boá: x,y,zA  x  x= x  x = 0; x(y z) = (xy) (xz); x x = x  x = 1. x (y z) = (xy)  (xz). 5 6 Đại Số Bool Đại Số Bool Ví dụ: Xeùt taäp hôïp B = {0, 1}. Treân B ta ñònh nghóa hai Xeùt F laø taäp hôïp taát caû caùc daïng meänh ñeà theo n pheùp toaùn , nhö sau: bieán p1, p2,…,pn vôùi hai pheùp toaùn noái lieàn , pheùp toaùn noái rôøi , 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ø Khi đó, B trở thành một đại số Bool daïng meänh ñeà buø E 7 8 2 Đại Số Bool Định nghĩa hàm Bool Cho ñaïi soá Bool (A,,). Khi ñoù vôùi moïi x,yA, ta coù: Haøm Bool n bieán laø aùnh xaï 1) xx = x; xx = x. f : Bn  B , trong ñoù B = {0, 1}. 2) x0 = 0x =0; x1 =1x = 1. Như vậy haøm Bool n bieán laø moät haøm soá coù daïng : 3) Phaàn töû buø cuûa x laø duy nhaát vaøx = x; 1  0; 0  1. 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}. 4) Coâng thöùc De Morgan: x  y  x  y; Kyù hieäu Fn ñeå chæ taäp caùc haøm Bool n bieán. x  y  x  y. 5) Tính haáp thuï:x(xy) = x; x (xy) = x. Ví duï: Daïng meänh ñeà E = E(p 1,p2,…,pn) theo n bieán p1, p2,…, pn laø moät h ...