Đại số Boolean

Bách khoa toàn thư mở Wikipedia
Buớc tưới chuyển hướng Bước tới tìm kiếm
Boolean lattice of subsets

Trong đại số trừu tượng, đại số Boole hay đại số Boolean là một cấu trúc đại số có các tính chất cơ bản của cả các phép toán trên tập hợp và các phép toán logic. Cụ thể, các phép toán trên tập hợp được quan tâm là phép giao, phép hợp, phép bù; và các phép toán logic, Hoặc, Không.

Đại số Boole được đặt tên theo George Boole (18151864), một nhà toán học người Anh.

Đại số Boole làm việc với các đại lượng chỉ nhận giá trị Đúng hoặc Sai và có thể thể hiện hệ thống số nhị phân, hoặc các mức điện thế trong mạch điện logic. Do đó đại số Boole có nhiều ứng dụng trong kỹ thuật điệnkhoa học máy tính, cũng như trong logic toán học.

Định nghĩa[sửa | sửa mã nguồn]

Đại số Boolean gồm 6 định lý cơ bản và một tập hợp A, được trang bị hai phép toán nhị phân (được gọi là "AND" hay "phép nhân"), (gọi là "OR" hay "phép cộng"), một phép toán đơn nhất ¬ (gọi là "NOT" hay "phép phủ định") và hai giá trị 0 và 1 tương ứng với mức thấp (ký hiệu ) và mức cao (ký hiệu ), giả sử a, b, c thuộc tập hợp A, ta có các tiên đề sau:[1]

a ∨ (bc) = (ab) ∨ c a ∧ (bc) = (ab) ∧ c Phép kết hợp
ab = ba ab = ba Phép hoán vị
a ∨ (ab) = a a ∧ (ab) = a Phép hấp thụ
a ∨ 0 = a a ∧ 1 = a Phép đồng nhất
a ∨ (bc) = (ab) ∧ (ac)   a ∧ (bc) = (ab) ∨ (ac)   Phép phân phối
a ∨ ¬a = 1 a ∧ ¬a = 0 Phép bù

Lưu ý rằng, phép hấp thụ có thể được loại trừ khỏi tập các tiên đề vì nó có thể được bắt nguồn từ các tiên đề khác.

Một đại số Boolean chỉ với một phần tử được gọi là đại số bẩm sinh hoặc một đại số Boolean thoái hoá. (Một số tác giả yêu cầu 0 và 1 là các phần tử riêng biệt để loại trừ trường hợp này).

Xuất phát từ ba cặp tiên đề cuối cùng ở trên (Phép đồng nhất, phân phối và bù), hoặc từ phép hấp thụ, ta có

a = ba     khi và chỉ khi     ab = b

Ví dụ[sửa | sửa mã nguồn]

  • Phép đại số Boolean gồm hai phần tử, 0 và 1, xác định bởi các quy tắc:
0 1
0 0 0
1 0 1
0 1
0 0 1
1 1 1
a 0 1
¬a 1 0
  • Nó có nhiều úng dụng trong logic, với 0 là false, 1 là true, ∧ là and (phép nhân), ∨ là or (phép cộng), và ¬ là not (phép phủ định).
  • Đại số Boolean hai phần tử cũng được sử dụng cho thiết kế mạch trong kỹ thuật điện; ở đây 0 và 1 đại diện cho hai trạng thái khác nhau của một bit trong một mạch kỹ thuật số, điển hình là điện thế cao và thấp. Mạch được mô tả bằng các biểu thức có chứa các biến, và hai biểu thức như vậy là bằng nhau cho tất cả các giá trị của các biến nếu và chỉ khi các mạch tương ứng có cùng một hành vi đầu vào-đầu ra. Hơn nữa, mọi hành vi đầu vào-đầu ra có thể có thể được mô hình hoá bằng một biểu thức Boolean phù hợp.
  • The two-element Boolean algebra is also important in the general theory of Boolean algebras, because an equation involving several variables is generally true in all Boolean algebras if and only if it is true in the two-element Boolean algebra (which can be checked by a trivial brute force algorithm for small numbers of variables). This can for example be used to show that the following laws (Consensus theorems) are generally valid in all Boolean algebras:
    • (ab) ∧ (¬ac) ∧ (bc) ≡ (ab) ∧ (¬ac)
    • (ab) ∨ (¬ac) ∨ (bc) ≡ (ab) ∨ (¬ac)
  • The power set (set of all subsets) of any given nonempty set S forms a Boolean algebra, an algebra of sets, with the two operations ∨:= ∪ (union) and ∧:= ∩ (intersection). The smallest element 0 is the empty set and the largest element 1 is the set S itself.
  • After the two-element Boolean algebra, the simplest Boolean algebra is that defined by the power set of two atoms:
0 a b 1
0 0 0 0 0
a 0 a 0 a
b 0 0 b b
1 0 a b 1
0 a b 1
0 0 a b 1
a a a 1 1
b b 1 b 1
1 1 1 1 1
x 0 a b 1
¬x 1 b a 0
  • The set of all subsets of S that are either finite or cofinite is a Boolean algebra, an algebra of sets.
  • Starting with the propositional calculus with κ sentence symbols, form the Lindenbaum algebra (that is, the set of sentences in the propositional calculus modulo tautology). This construction yields a Boolean algebra. It is in fact the free Boolean algebra on κ generators. A truth assignment in propositional calculus is then a Boolean algebra homomorphism from this algebra to the two-element Boolean algebra.
  • Given any linearly ordered set L with a least element, the interval algebra is the smallest algebra of subsets of L containing all of the half-open intervals [a, b) such that a is in L and b is either in L or equal to ∞. Interval algebras are useful in the study of Lindenbaum-Tarski algebras; every countable Boolean algebra is isomorphic to an interval algebra.
Hasse diagram of the Boolean algebra of divisors of 30.
  • For any natural number n, the set of all positive divisors of n, defining ab if a divides b, forms a distributive lattice. This lattice is a Boolean algebra if and only if n is square-free. The bottom and the top element of this Boolean algebra is the natural number 1 and n, respectively. The complement of a is given by n/a. The meet and the join of a and b is given by the greatest common divisor (gcd) and the least common multiple (lcm) of a and b, respectively. The ring addition a+b is given by lcm(a,b)/gcd(a,b). The picture shows an example for n = 30. As a counter-example, considering the non-square-free n=60, the greatest common divisor of 30 and its complement 2 would be 2, while it should be the bottom element 1.
  • Other examples of Boolean algebras arise from topological spaces: if X is a topological space, then the collection of all subsets of X which are both open and closed forms a Boolean algebra with the operations ∨:= ∪ (union) and ∧:= ∩ (intersection).
  • If R is an arbitrary ring and we define the set of central idempotents by
    A = { eR: e2 = e, ex = xe, ∀xR }
    then the set A becomes a Boolean algebra with the operations ef:= e + f - ef and ef:= ef.

Tham khảo[sửa | sửa mã nguồn]

  1. ^ Davey, Priestley, 1990, p.109, 131, 144

Liên kết ngoài[sửa | sửa mã nguồn]