tailieunhanh - ĐẠI SỐ BOOLE – PHẦN

Định nghĩa: Ký hiệu B = {0, 1} và Bn = {(x1, x2, , xn) | xi B, 1≤ i ≤ n}, ở đây B và Bn là các đại số Boole (xem 2) và 3) của Thí dụ 1). Biến x được gọi là một biến Boole nếu nó nhận các giá trị chỉ từ B. Một hàm từ Bn vào B được gọi là một hàm Boole (hay hàm đại số lôgic) bậc n. Các hàm Boole cũng có thể được biểu diễn bằng cách dùng các biểu thức được tạo bởi các biến và các phép toán Boole. | ĐẠI SỐ BOOLE-PHẦN 2 HÀM BOOLE . Định nghĩa Ký hiệu B 0 1 và Bn x1 x2 . xn x eB 1 i n ở đây B và Bn là các đại số Boole xem 2 và 3 của Thí dụ 1 . Biến x được gọi là một biến Boole nếu nó nhận các giá trị chỉ từ B. Một hàm từ Bn vào B được gọi là một hàm Boole hay hàm đại số lôgic bậc n. Các hàm Boole cũng có thể được biểu diễn bằng cách dùng các biểu thức được tạo bởi các biến và các phép toán Boole xem Bảng 1 trong Thí dụ 1 . Các biểu thức Boole với các biến x1 x2 . xn được định nghĩa bằng đệ quy như sau - 0 1 x1 x2 . xn là các biểu thức Boole. - Nếu P và Q là các biểu thức Boole thì P PQ và P Q cũng là các biểu thức Boole. Mỗi một biểu thức Boole biểu diễn một hàm Boole. Các giá trị của hàm này nhận được bằng cách thay 0 và 1 cho các biến trong biểu thức đó. Hai hàm n biến F và G được gọi là bằng nhau nếu F ab a2 . an G a1 a2 . an với mọi ab a2 . aneB. Hai biểu thức Boole khác nhau biểu diễn cùng một hàm Boole được gọi là tương đương. Phần bù của hàm Boole F là hàm F với F x1 X2 . xn F X1 X2 . xn . Giả sử F và G là các hàm Boole bậc n. Tổng Boole F G và tích Boole FG được định nghĩa bởi F G X1 X2 . . Xn F X1 X2 . . Xn G xi X2 . . xn FG X1 X2 . . Xn F X1 X2 . . Xn G X1 X2 . . Xn . Thí dụ 2 Theo quy tắc nhân của phép đếm ta suy ra rằng có 2n bộ n phần tử khác nhau gồm các số 0 và 1. Vì hàm Boole là việc gán 0 hoặc 1 cho mỗi bộ trong số 2n bộ n phần tử đó nên lại theo quy tắc nhân sẽ có 2 n 2 các hàm Boole khác nhau. Bậc Số các hàm Boole 1 4 2 16 3 256 4 5 6 Bảng sau cho giá trị của 16 hàm Boole bậc 2 phân biệt x y F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16 0 0 0 1 0 0 0 1 1 1 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 1 0 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 1 1 1 0 1 1 0 0 1 1 0 1 1 1 0 1 1 0 0 1 1 1 0 0 0 0 trong đó có một số hàm thông dụng như sau - Hàm F1 là hàm hằng 0 - Hàm F2 là hàm hằng 1 - Hàm F3 là hàm hội F3 x y được viết là xy hay x A y - Hàm F4 là hàm tuyển F4 x y được viết là x y hay x V y - Hàm F5 là