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) cung cấp cho học viên những kiến thức về tính giao hoán, tính kết hợp, tính phân bố của đại số Bool; hàm Bool n biến; bảng chân trị; các phép toán trên hàm Bool: phép công Bool, phép nhân Bool, phép lấy hàm bù; dạng nối rời chính tắc của hàm Bool; . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | Phần VI Đại Số Bool và hàm Bool Biên soạn Nguyễn Viết Đông 1 George Boole 1815-1864 2 Tài liệu tham khảo n 1 . Nguyễn Hữu Anh Toán rời rạc Nhà xuất bản giáo dục. n 2 Ngọc Hội Toán rời rạc 3 Đạ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ï A A A x y x y vaø A A A x y x y thoûa 5 tính chaát sau 4 Đại Số Bool n Tính giao hoaùn x y A x y y x x y y x n Tính keát hôïp x y z A x y z x y z x y z x y z . n Tính phaân boá x y z A x y z x y x z x y z x y x z . 5 Đại Số Bool n Coù caùc phaàn töû trung hoøa 1 vaø 0 x A x 1 1 x x x 0 0 x x. n Moïi phaàn töû ñeàu coù phaàn töû buø x x A A x x x x x x 0 x x 1. 6 Đạ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 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öû E 1 laø haèng ñuùng 1 phaàn töû 0 laø haèng sai 0 7 phaàn töû buø cuûa daïng meänh ñeà E laø daïng Đại Số Bool Xeùt taäp hôïp B 0 1 . Treân B ta ñònh nghóa hai pheùp toaùn nhö sau Khi đó B trở thành một đại số Bool 8 Đại Số Bool Cho ñaïi soá Bool A . Khi ñoù vôùi moïi x y A ta coù 1 x x x x x x. 2 x 0 0 x 0 x 1 1 x 1. 3 Phaàn töû buø cuûa x laø duy nhaát x 1 0 0 1. vaø x x y x y 4 Coâng thöùc De Morgan x y x y. 9 5 Tính haáp thuï x x y x x x y Định nghĩa hàm Bool Haøm Bool n bieán laø aùnh xaï f Bn 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 hieäu Fn ñeå chæ taäp caùc haøm 0 1 . Kyù 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. 10 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.
