Đại số Bool B gồm có một tập hợp S chứa phần tử khác biệt 0 và 1, toán tử bậc hai + và ., toán tử bậc một ' trên S thoả mãn:
1) Luật kết hợp:
(x + y) + z = x + (y + z)
(x . y) . z = x . (y . z) cho tất cả x, y, z ∈ S.
2) Luật giao hoán:
x + y = y + x
x . y = y . x cho tất cả x, y ∈ S.
3) Luật phân phối:
x . (y + z) = (x . y) + .z)
x + (y .z) = (x + y) . ( x + z) cho tất cả x, y, z ∈ S.
4) Luật Identity :
x + 0 = x
x . 1 = x cho tất cả x ∈ S.
5) Luật complement:
x + x' = 1
x . x' = 0 cho tất cả x ∈ S.
Nếu B là Đại số Bool, ta viết B = (S, +, ., ', 0, 1).
2. Định nghĩa:
Trong Đại số Bool, ta gọi phần tử x' là complement of x.
3. Định lý:
Trong Đại số Bool, phần tử x' của định nghĩa 2 là duy nhất.
Đặc biệt, nếu x + y = 1 và x.y = 0, thì y = x'.
Chứng minh:
y = y1 Định nghĩa 4
= y(x + x') Định nghĩa 5
= yx + yx' Định nghĩa 3
= xy + yx' Định nghĩa 2
= 0 + yx' Đã cho
= xx' + yx' Định nghĩa 5
= x'x + x'y Định nghĩa 2
= x'( x + y) Định nghĩa 3
= x'1 Đã cho
= x' Định nghĩa 4
4. Định lý:
Cho B = (S, +, ., ', 0, 1) là Đại số Bool. Ta có những đặc tính sau:
1) Luật Idempotent:
x + x = x
xx = x
2) Luật Bound:
3) Luật Absorption:
4) Luật Involution:
5) Luật 0 và 1:
6) Luật De Morgan:
Chứng minh:
1) x = x + 0 Định nghĩa 4
= x + (xx') Định nghĩa 5
= (x + x)(x + x') Định nghĩa 3
= (x + x)1 Định nghĩa 5
= x + x Định nghĩa 4
2)
3)
6)
5. Định nghĩa:
The dual của một mệnh đề có biểu thức Bool là khi ta thay thế 0 bởi 1, 1 bởi 0, + bởi ., và . bởi +.
6. Thí dụ:
The dual của
(x + y)' = x'y'
(xy)' = x' + y'
7. Định lý:
The dual của một định lý thuộc Đại số Bool là một định lý.
Chứng minh:
Giả sử T là một định lý về Đại số Bool, thì ta có một chứng minh P của T chỉ gồm định nghĩa của Đại số Bool (Định nghĩa 1). Cho P' là dãy những mệnh đề có đuợc bằng cách thay thế mỗi mệnh đề trong P bởi dual của nó. Thì P' là một chứng minh của the dual của T.
8. Thí dụ:
The dual của
x + x = x (1)
là
xx = x (2)
Chứng minh:
Ta đã chứng minh (1) (Xem chứng minh 1). Nếu ta viết the dual của mỗi mệnh đề của chứng minh 1, ta có được chứng minh (2) như sau :
x = x1
= x(x + x')
= xx + xx'
= xx + 0
= xx
9. Biểu thức Bool:
Biểu thức Bool với ký hiệu x1, x2, ..., xn của bất cứ Đại số Bool (S, +, ., ', 0, 1) được định nghĩa đệ quy như sau:
x | x thuộc S, x1, ..., xn là những biểu thức Bool.
Nếu X1 và X2 là những biểu thức Bool, thì
(X1), (X1)', X1 + X2, X1.X2 là những biểu thức Bool.
10. Hàm Bool:
Hàm Bool trên S là hàm từ Sn đến S có dạng sau:
f(X1, ..., Xn) = X(x1, ..., xn),
với X là một biểu thức Booltrong ký hiệu x1, ..., xn trên S.
blogID=3383421764406311713
