Đại số Boolean

Bách khoa toàn thư mở Wikipedia
(đổi hướng từ Đại số Boole)
Bước tới: menu, tìm kiếm
Boolean lattice of subsets

Trong đại số trừu tượng, đại số Boole 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 algebra 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).
  • The two-element Boolean algebra is also used for circuit design in electrical engineering; here 0 and 1 represent the two different states of one bit in a digital circuit, typically high and low voltage. Circuits are described by expressions containing variables, and two such expressions are equal for all values of the variables if and only if the corresponding circuits have the same input-output behavior. Furthermore, every possible input-output behavior can be modeled by a suitable Boolean expression.
  • 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