tailieunhanh - 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}. | Phần VI Đại Số Bool và hàm Bool Biên soạn Nguyễn Viết Đông George Boole 1815-1864 Tài liệu tham khảo Đại Số Bool 1 . Nguyễn Hữu Anh Toán rời rạc Nhà xuất bản giáo dục. 2 Ngọc Hội Toán rời rạc Một đại số Bool A a v là một tập hợp A 0 với hai phép toan a v tức là hai ành xạ a AxA a x y xaỵ và v AxA a thốà 5 tính chất sau 4 1 Đại Số Bool Có các phan tử trung hoa 1 va 0 Vx e A XA1 1ax x xv0 0vx X. Mói phán tử đều có phán tử bu Vx eA 3XeA x A x x A x 0 x vx x V x 1. 6 Đại Số Bool Đại Số Bool Ví dụ Xềt F lá táp hợp tát cá các dang mềnh đề thềó n biền p1 p2 . pn vôi hai phềp tóán nốì liền A phềp tóán nói rôi V tróng đó tá đóng nhái các dang mềnh đề tửông đửông. Khi đó F lá mót đái số Bóól vôi phán tử 1 lá háng đung 1 phán tử 0 lá háng sai 0 phántử bu cua dang mềnh đề E lá dang mềnh đề bu E 7 Xềt táp hợp B 0 1 . Trền B tá định nghĩa hái phềp tóán A v nhử sau Khi đó B trở thành một đại số Bool 2 Đại Số Bool Cho đại số Bool A a v . Khi đó vđi mọi x yeA ta có 1 xax x xvx x. 2 xaũ ũax 0 xvl 1vx 1. 3 Phan tử bù cua x la duy nhát vax x 1 0 0 1. 4 Cóng thức De Morgan x a y x v y x v y x a y. 5 Tính hap thu xA xvy x xv xAy x. 9 Định nghĩa hàm Bool Ham Bool n biến la anh xa f Bn B trong đo B 0 1 . Như vậy ham Bool n biên la một ham sô co dang f f x1 x2 xn trong đo moi biên trong x1 x2 . xn va f chỉ nhận gia trị trong B 0 1 . Ky hiệu Fn đê chỉ tap cac ham Bool n biên. Ví du Dang mênh đê E E p1 p2 . pn theo n biên p1 p2 . pn la mọt ham Bool n biên. 10 Bảng chân trị Xêt ham Bool n biến f x1 x2 . xn Vì moi biến xj chỉ nhặn hai gia trị 0 1 nên chỉ co 2ntrứờnghỢp cua bo biên x1 x2 . xn . Do đo đê mo ta f ta co thê lap bang gom 2n hang ghi tat ca cac gia trị cua f tuy thêo 2ntrứỢng hỢp cua biên. Ta goi đây la bang chan tri cua f 11 Ví dụ Xêt kết quả f trong việc thong qua mot quyết định dứa vao 3 phiếu bau x y z 1. Moi phiếu chỉ lây mot trong hai gia trị 1 tan thanh hoác 0 bac bo . 2. Kết qủa f la 1 thong qua quyết định nếu đứỢc đa so phiếu tan thanh la 0 khong thong