|
Đạ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ện]] và [[khoa học máy tính]], cũng như trong [[logic toán học]].
{{Sơ khai}}
{{Đang dịch 2 (nguồn)
|ngày = 11
|tháng = 01
|năm = 2007
|1 = {{{1|{{{ngôn ngữ|}}}}}}
}}
A Boolean algebra is also called a '''Boolean lattice'''. The connection to [[lattice (order)|lattice]]s (special [[partially ordered set]]s) is suggested by the parallel between set [[subset|inclusion]], ''A'' ⊆ ''B'', and [[order theory|ordering]], ''a'' ≤ ''b''. Consider the lattice of all subsets of {''x'',''y'',''z''}, ordered by set inclusion. This Boolean lattice is a partially ordered set in which, say, {''x''} ≤ {''x'',''y''}. Any two lattice elements, say ''p'' = {''x'',''y''} and ''q'' = {''y'',''z''}, have a least upper bound, here {''x'',''y'',''z''}, and a greatest lower bound, here {''y''}. Suggestively, the least upper bound (or join or supremum) is denoted by the same symbol as logical OR, ''p''∨''q''; and the greatest lower bound (or meet or infimum) is denoted by same symbol as logical AND, ''p''{{unicode|∧}}''q''.
The lattice interpretation helps in generalizing to [[Heyting algebra]]s, which are Boolean algebras freed from the restriction that either a statement or its negation must be true. Heyting algebras correspond to [[intuitionistic logic|intuitionist (constructivist) logic]] just as Boolean algebras correspond to [[classical logic]].
__TOC__
== Formal definition ==
A '''Boolean algebra''' is a [[set]] ''A'', supplied with two [[binary operation]]s <math>\land</math> (called AND), <math>\lor</math> (called OR), a [[unary operation]] <math>\lnot</math> (called NOT) and two distinct elements 0 (called zero) and 1 (called one), such that, for all elements ''a'', ''b'' and ''c'' of set ''A'', the following [[axioms]] hold:
:{| cellpadding=5
|<math> a \lor (b \lor c) = (a \lor b) \lor c </math>
|<math> a \land (b \land c) = (a \land b) \land c </math>
| [[associativity]]
|-
|<math> a \lor b = b \lor a </math>
|<math> a \land b = b \land a </math>
| [[commutativity]]
|-
|<math> a \lor (a \land b) = a </math>
|<math> a \land (a \lor b) = a </math>
| [[absorption law|absorption]]
|-
|<math> a \lor (b \land c) = (a \lor b) \land (a \lor c) </math>
|<math> a \land (b \lor c) = (a \land b) \lor (a \land c) </math>
| [[distributivity]]
|-
|<math> a \lor \lnot a = 1 </math>
|<math> a \land \lnot a = 0 </math>
| [[complemented lattice|complements]]
|}
The first three pairs of axioms above: associativity, commutativity and absorption, mean that (''A'', <math>\land</math>, <math>\lor</math>) is a [[lattice (order)|lattice]]. If ''A'' is a lattice and one of the above distributivity laws holds, then the second distributivity law can be proven. Thus, a Boolean algebra can also be equivalently defined as a [[distributive lattice|distributive]] [[complemented lattice]].
From these [[axioms]], one can show that the smallest element 0, the largest element 1, and the complement ''a'' of any element ''a'' are uniquely determined. For all ''a'' and ''b'' in ''A'', the following [[identity (mathematics)|identities]] also follow:
:{| cellpadding=5
| <math> a \lor a = a</math>
|<math> a \land a = a </math>
| [[Idempotent|idempotence]]
|-
|<math> a \lor 0 = a </math>
|<math> a \land 1 = a </math>
| rowspan=2 | [[bounded poset|boundedness]]
|-
|<math> a \lor 1 = 1 </math>
|<math> a \land 0 = 0 </math>
|-
|<math> \lnot 0 = 1 </math>
|<math> \lnot 1 = 0 </math>
| 0 and 1 are complements
|-
|<math> \lnot (a \lor b) = \lnot a \land \lnot b</math>
|<math> \lnot (a \land b) = \lnot a \lor \lnot b</math>
| [[De Morgan's laws]]
|-
| <math> \lnot \lnot a = a </math>
|
| [[involution]]
|}
== Examples ==
* The simplest Boolean algebra has only two elements, 0 and 1, and is defined by the rules:
{|
|-
| width="70" |
|
{| border="1" cellpadding="4" cellspacing="0"
|-
! {{unicode|∧}} || 0 || 1
|-
! 0
| 0 || 0
|-
! 1
| 0 || 1
|}
|
| width="30" |
|
{| border="1" cellpadding="4" cellspacing="0"
|-
! {{unicode|∨}} || 0 || 1
|-
! 0
| 0 || 1
|-
! 1
| 1 || 1
|}
|
| width="40" |
|
{| border="1" cellpadding="4" cellspacing="0"
|-
! a || 0 || 1
|-
! ¬a
| 1 || 0
|}
|}
:* It has applications in [[logic]], interpreting 0 as ''false'', 1 as ''true'', ∧ as ''and'', ∨ as ''or'', and ¬ as ''not''. Expressions involving variables and the Boolean operations represent statement forms, and two such expressions can be shown to be equal using the above axioms if and only if the corresponding statement forms are [[logical equivalence|logically equivalent]].
:* 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 always be checked by a trivial [[brute force search|brute force]] algorithm). This can for example be used to show that the following laws (''Consensus theorems'') are generally valid in all Boolean algebras:
:** (''a'' ∨ ''b'') ∧ (¬''a'' ∨ ''c'') ∧ (''b'' ∨ ''c'') ≡ (''a'' ∨ ''b'') ∧ (¬''a'' ∨ ''c'')
:** (''a'' ∧ ''b'') ∨ (¬''a'' ∧ ''c'') ∨ (''b'' ∧ ''c'') ≡ (''a'' ∧ ''b'') ∨ (¬''a'' ∧ ''c'')
* Starting with the [[propositional calculus]] with κ sentence symbols, form the [[Lindenbaum-Tarski algebra|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 {0,1}.
* The [[power set]] (set of all subsets) of any given nonempty set ''S'' forms a Boolean algebra 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.
* The set of all subsets of ''S'' that are either finite or [[cofinite]] is a Boolean algebra.
* For any [[natural number]] ''n'', the set of all positive [[divisor]]s of ''n'' forms a [[distributive lattice]] if we write ''a'' ≤ ''b'' for ''a'' | ''b''. This lattice is a Boolean algebra if and only if ''n'' is [[square-free integer|square-free]]. The smallest element 0 of this Boolean algebra is the natural number 1; the largest element 1 of this Boolean algebra is the natural number ''n''.
* Other examples of Boolean algebras arise from [[tô pô|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 [[mathematical ring|ring]] and we define the set of ''central idempotents'' by <br> ''A'' = { ''e'' ∈ ''R'' : ''e''<sup>2</sup> = ''e'', ''ex'' = ''xe'', ∀''x'' ∈ ''R'' } <br> then the set ''A'' becomes a Boolean algebra with the operations ''e'' ∨ ''f'' := ''e'' + ''f'' − ''ef'' and ''e'' ∧ ''f'' := ''ef''.
* Certain [[Lindenbaum–Tarski algebra]]s.
== Order theoretic properties ==
[[Image:Hasse diagram of powerset of 3.png|right|thumb|250px|Boolean lattice of subsets]]
Like any lattice, a Boolean algebra (''A'', <math>\land</math>, <math>\lor</math>) gives rise to a [[partially ordered set]] (''A'', ≤) by defining
: ''a'' ≤ ''b'' precisely when ''a'' = ''a'' <math>\land</math> ''b''
(which is also equivalent to ''b'' = ''a'' <math>\lor</math> ''b'').
In fact one can also define a Boolean algebra to be a distributive lattice (''A'', ≤) (considered as a partially ordered set) with least element 0 and greatest element 1, within which every element ''x'' has a complement ''x'' such that
: ''x'' <math>\land</math> ''x'' = 0 and ''x'' <math>\lor</math> ''x'' = 1
Here <math>\land</math> and <math>\lor</math> are used to denote the [[infimum]] (meet) and [[supremum]] (join) of two elements. Again, if complements in the above sense exist, then they are uniquely determined.
The algebraic and the order theoretic perspective can usually be used interchangeably and both are of great use to import results and concepts from both [[universal algebra]] and [[order theory]]. In many practical examples an ordering relation, conjunction, disjunction, and negation are all naturally available, so that it is straightforward to exploit this relationship.
== Principle of duality ==
One can also apply general insights from [[duality (order theory)|duality in order theory]] to Boolean algebras. Especially, the order dual of every Boolean algebra, or, equivalently, the algebra obtained by exchanging <math>\land</math> and <math>\lor</math>, is also a Boolean algebra. In general, any law valid for Boolean algebras can be transformed into another valid, dual law by exchanging 0 with 1, <math>\land</math> with <math>\lor</math>, and ≤ with ≥.
== Other notation ==
The operators of Boolean algebra may be represented in various ways. Often they
are simply written as AND, OR and NOT. In describing circuits, NAND (Not AND),
NOR (Not OR) and XOR (eXclusive OR) may also be used. [[Mathematician]]s, [[engineer]]s, and [[programmer]]s often use + for OR and · for AND (since in some ways those operations are analogous to addition and multiplication in other [[algebraic structure]]s and this notation makes it very easy to get [[canonical form (Boolean algebra)|sum of products form]] for people who are familiar with normal algebra) and represent NOT by a line drawn above the expression being negated. Sometimes, the symbol ~ or ! is used for NOT.
Here we use another common notation with "meet" <math>\land</math> for AND, "join" <math>\lor</math> for OR, and ¬ for NOT.
== Homomorphisms and isomorphisms ==
A ''[[homomorphism]]'' between the Boolean algebras ''A'' and ''B'' is a [[function (mathematics)|function]] ''f'' : ''A'' → ''B'' such that for all ''a'', ''b'' in ''A'':
: ''f''(''a'' <math>\lor</math> ''b'') = ''f''(''a'') <math>\lor</math> ''f''(''b'')
: ''f''(''a'' <math>\land</math> ''b'') = ''f''(''a'') <math>\land</math> ''f''(''b'')
: ''f''(0) = 0
: ''f''(1) = 1
It then follows that ''f''(''a'') = ''f''(''a'') for all ''a'' in ''A'' as well. The [[class (set theory)|class]] of all Boolean algebras, together with this notion of morphism, forms a [[category theory|category]]. An ''isomorphism'' from ''A'' to ''B'' is a homomorphism from ''A'' to ''B'' which is [[bijective]]. The inverse of an isomorphism is also an isomorphism, and we call the two Boolean algebras ''A'' and ''B'' ''isomorphic''. From the standpoint of Boolean algebra theory, they cannot be distinguished; they differ only in the notation of their elements.
== Boolean rings, ideals and filters ==
Every Boolean algebra (''A'', <math>\land</math>, <math>\lor</math>) gives rise to a [[ring (algebra)|ring]] (''A'', +, *) by defining ''a'' + ''b'' = (''a'' <math>\land</math> ''b'') <math>\lor</math> (''b'' <math>\land</math> ''a'') (this operation is called "symmetric difference" in the case of sets and [[Truth table|XOR]] in the case of logic) and ''a'' * ''b'' = ''a'' <math>\land</math> ''b''. The zero element of this ring coincides with the 0 of the Boolean algebra; the multiplicative identity element of the ring is the 1 of the Boolean algebra. This ring has the property that ''a'' * ''a'' = ''a'' for all ''a'' in ''A''; rings with this property are called [[Boolean ring]]s.
Conversely, if a Boolean ring ''A'' is given, we can turn it into a Boolean algebra by defining ''x'' <math>\lor</math> ''y'' = ''x'' + ''y'' + ''xy'' and ''x'' <math>\land</math> ''y'' = ''xy''. Since these two operations are inverses of each other, we can say that every Boolean ring arises from a Boolean algebra, and vice versa. Furthermore, a map ''f'' : ''A'' → ''B'' is a homomorphism of Boolean algebras if and only if it is a homomorphism of Boolean rings. The [[category theory|categories]] of Boolean rings and Boolean algebras are equivalent.
An ''ideal'' of the Boolean algebra ''A'' is a subset ''I'' such that for all ''x'', ''y'' in ''I'' we have ''x'' <math>\lor</math> ''y'' in ''I'' and for all ''a'' in ''A'' we have ''a'' <math>\land</math> ''x'' in ''I''. This notion of ideal coincides with the notion of [[ring ideal]] in the Boolean ring ''A''. An ideal ''I'' of ''A'' is called ''prime'' if ''I'' ≠ ''A'' and if ''a'' <math>\land</math> ''b'' in ''I'' always implies ''a'' in ''I'' or ''b'' in ''I''. An ideal ''I'' of ''A'' is called ''maximal'' if ''I'' ≠ ''A'' and if the only ideal properly containing ''I'' is ''A'' itself. These notions coincide with ring theoretic ones of [[prime ideal]] and [[maximal ideal]] in the Boolean ring ''A''.
The dual of an ''ideal'' is a ''filter''. A ''filter'' of the Boolean algebra ''A'' is a subset ''p'' such that for all ''x'', ''y'' in ''p'' we have ''x'' <math>\land</math> ''y'' in ''p'' and for all ''a'' in ''A'' if ''a'' <math>\lor</math> ''x'' = ''a'' then ''a'' in ''p''.
== Representing Boolean algebras ==
It can be shown that every ''finite'' Boolean algebra is isomorphic to the Boolean algebra of all subsets of a finite set. Therefore, the number of elements of every finite Boolean algebra is a [[power of two]].
[[Marshall H. Stone|Stone's]] celebrated ''[[Stone's representation theorem for Boolean algebras|representation theorem for Boolean algebras]]'' states that ''every'' Boolean algebra ''A'' is isomorphic to the Boolean algebra of all [[closed-open]] sets in some ([[compact space|compact]] [[totally disconnected]] [[Hausdorff space|Hausdorff]]) topological space.
== Axiomatics for Boolean algebras ==
Let the [[unary functional symbol]] ''n'' be read as 'complement'. In 1933, the American mathematician [[Edward Vermilye Huntington]] (1874–1952) set out the following elegant axiomatization for Boolean algebra:
# ''Commutativity'': ''x'' + ''y'' = ''y'' + ''x''.
# ''Associativity'': (''x'' + ''y'') + ''z'' = ''x'' + (''y'' + ''z'').
# ''Huntington equation'': ''n''(''n''(''x'') + ''y'') + ''n''(''n''(''x'') + ''n''(''y'')) = ''x''.
[[Herbert Robbins]] immediately asked: If the Huntington equation is replaced with its dual, to wit:
:4. ''Robbins Equation'': ''n''(''n''(''x'' + ''y'') + ''n''(''x'' + ''n''(''y''))) = ''x'',
do (1), (2), and (4) form a basis for Boolean algebra? Calling (1), (2), and (4) a ''Robbins algebra'', the question then becomes: Is every Robbins algebra a Boolean algebra? This question remained open for decades, and became a favorite question of [[Alfred Tarski]] and his students.
In 1996, [[William McCune]] at [[Argonne National Laboratory]], building on earlier work by Larry Wos, Steve Winker, and Bob Veroff, answered Robbins's question in the affirmative: Every Robbins algebra is a Boolean algebra. Crucial to McCune's proof was the [[automated reasoning program]] [[EQP]] he designed. For a simplification of McCune's proof, see Dahn (1998).
==History==
The term "Boolean algebra" honors [[George Boole]] (1815–1864), a self-educated English mathematician. The algebraic system of logic he formulated in his 1854 monograph ''The Laws of Thought'' differs from that described above in some important respects. For example, conjunction and disjunction in Boole were not a dual pair of operations. Boolean algebra emerged in the 1860s, in papers written by [[William Jevons]] and [[Charles Peirce]]. To the 1890 ''Vorlesungen'' of [[Ernst Schröder]] we owe the first systematic presentation of Boolean algebra and [[distributive lattice]]s. The first extensive treatment of Boolean algebra in English is [[A. N. Whitehead]]'s 1898 ''Universal Algebra''. Boolean algebra as an axiomatic algebraic structure in the modern axiomatic sense begins with a 1904 paper by [[Edward Vermilye Huntington]]. Boolean algebra came of age as serious mathematics with the work of [[Marshall Stone]] in the 1930s, and with [[Garrett Birkhoff]]'s 1940 ''Lattice Theory''. In the 1960s, [[Paul Cohen (mathematician)|Paul Cohen]], [[Dana Scott]], and others found deep new results in [[mathematical logic]] and [[axiomatic set theory]] using offshoots of Boolean algebra, namely [[forcing (mathematics)|forcing]] and Boolean-valued models.
==See also==
{{col-begin}}
{{col-break}}
* [[List of Boolean algebra topics|Boolean algebra topics]]
* [[Boolean domain]]
* [[Boolean function]]
* [[Boolean logic]]
* [[Boolean ring]]
* [[Boolean-valued function]]
* [[Canonical form (Boolean algebra)|Canonical form]]
* [[Complete Boolean algebra]]
{{col-break}}
* [[Finitary boolean function]]
* [[Forcing (mathematics)]]
* [[Free Boolean algebra]]
* [[Heyting algebra]]
* [[Karnaugh map]]
* [[Laws of Form]]
{{col-break}}
* [[Logic gate]]
* [[Logical graph]]
* [[Logical matrix]]
* [[Two-element Boolean algebra]]
* [[Venn diagram]]
* [[Zeroth order logic]]
{{col-end}}
==References==
* Cori, Rene, and Lascar, Daniel, 2000. ''Mathematical Logic: A Course with Exercises''. Oxford Univ. Press. See Chapter 2.
* Dahn, B.I. (1998), "Robbins Algebras are Boolean: A Revision of McCune's Computer-Generated Solution of the Robbins Problem," ''Journal of Algebra 208'': 526–532.
* [[Paul Halmos|Halmos, Paul]], 1963. ''Lectures on Boolean Algebras'', Van Nostrand.
* [[Paul Halmos|Halmos, Paul]] and Steven Givant, 1998. ''Logic as Algebra'', Dolciani Mathematical Expositions No. 21, [[Mathematical Association of America]].
* Mendelson, Elliott, 1970. ''Boolean Algebra and Switching Circuits'', Schaum's Outline Series in Mathematics. McGraw–Hill.
*Monk, J. Donald, and R. Bonnet, eds., 1989. ''Handbook of Boolean Algebras'', 3 vols. North-Holland.
* Stoll, R.R., 1979 (1963). ''Set Theory and Logic''. Dover Publications.
* [[Edward Vermilye Huntington|Huntington, E. V.]], 1933, "New sets of independent postulates for the algebra of logic," ''Trans. AMS 35'': 274--304.
* [[Edward Vermilye Huntington|Huntington, E. V.]], 1933, "Boolean algebra: A correction," ''Trans. AMS 35'': 557--558.
* Brown, Stephen and Vranesic, Zvonko, 2002. ''Fundamentals of Digital Logic with VHDL Design, Second Edition''. McGraw-Hill. See Section 2.5.
==External links==
* [http://www.allaboutcircuits.com/vol_4/chpt_7/1.html Boolean Algebra] from AllAboutCircuits
* [[:simple:Boolean algebra|Boolean algebra]], ''Simple English Wikipedia''.
* [[Stanford Encyclopedia of Philosophy]]: "[http://plato.stanford.edu/entries/boolalg-math/ The Mathematics of Boolean Algebra,]" by J. Donald Monk.
* McCune W., 1997. ''[http://www.cs.unm.edu/~mccune/papers/robbins/ Robbins Algebras Are Boolean]'' JAR 19(3), 263--276
A monograph available free online:
* Burris, Stanley N.; Sankappanavar, H. P., 1981. ''[http://www.thoralf.uwaterloo.ca/htdocs/ualg.html A Course in Universal Algebra.]'' Springer-Verlag. ISBN 3-540-90578-2.
[[Thể loại:Đại số Boole|*]]
| 