Editing Boolean algebra (structure) (section)

== Examples ==

* The simplest non-trivial Boolean algebra, the [[two-element Boolean algebra]], has only two elements, {{math|0}} and {{math|1}}, and is defined by the rules:
{|
|-
| width="70" |
|
{| class="wikitable"
|-
! {{math|1=∧}} || {{math|0}} || {{math|1}}
|-
! {{math|0}}
| {{math|0}} || {{math|0}}
|-
! {{math|1}}
| {{math|0}} || {{math|1}}
|}
|
| width="30" |
|
{| class="wikitable"
|-
! {{math|1=∨}} || {{math|0}} || {{math|1}}
|-
! {{math|0}}
| {{math|0}} || {{math|1}}
|-
! {{math|1}}
| {{math|1}} || {{math|1}}
|}
|
| width="40" |
|
{| class="wikitable"
|-
! {{math|''a''}} || {{math|0}} || {{math|1}}
|-
! {{math|¬''a''}}
| {{math|1}} || {{math|0}}
|}
|}

:* It has applications in [[logic]], interpreting {{math|0}} as ''false'', {{math|1}} as ''true'', {{math|1=∧}} as ''and'', {{math|1=∨}} as ''or'', and {{math|¬}} 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]];{{refn|group=note|Strictly, electrical engineers tend to use additional states to represent other circuit conditions such as high impedance - see [[IEEE 1164]] or [[IEEE 1364]].}} 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 search|brute force]] algorithm for small numbers of variables). This can for example be used to show that the following laws (''[[Consensus theorem]]s'') are generally valid in all Boolean algebras:
:** {{math|1=(''a'' ∨ ''b'') ∧ (¬''a'' ∨ ''c'') ∧ (''b'' ∨ ''c'') ≡ (''a'' ∨ ''b'') ∧ (¬''a'' ∨ ''c'')}}
:** {{math|1=(''a'' ∧ ''b'') ∨ (¬''a'' ∧ ''c'') ∨ (''b'' ∧ ''c'') ≡ (''a'' ∧ ''b'') ∨ (¬''a'' ∧ ''c'')}}

* The [[power set]] (set of all subsets) of any given nonempty set {{math|''S''}} forms a Boolean algebra, an [[algebra of sets]], with the two operations {{math|1=∨ := ∪}} (union) and {{math|1=∧ := ∩}} (intersection). The smallest element 0 is the [[empty set]] and the largest element {{math|1}} is the set {{math|''S''}} itself.

:* After the two-element Boolean algebra, the simplest Boolean algebra is that defined by the [[power set]] of two atoms:
{|
|-
| width="70" |
|
{| class="wikitable"
|-
! {{math|1=∧}} || {{math|1=0}} || {{math|1=a}} || {{math|1=b}} || {{math|1=1}}
|-
! {{math|1=0}}
| {{math|1=0}} || {{math|1=0}} || {{math|1=0}} || {{math|1=0}}
|-
! {{math|1=a}}
| {{math|1=0}} || {{math|1=a}} || {{math|1=0}} || {{math|1=a}}
|-
! {{math|1=b}}
| {{math|1=0}} || {{math|1=0}} || {{math|1=b}} || {{math|1=b}}
|-
! {{math|1=1}}
| {{math|1=0}} || {{math|1=a}} || {{math|1=b}} || {{math|1=1}}
|}
|
| width="30" |
|
{| class="wikitable"
|-
! {{math|1=∨}} || {{math|1=0}} || {{math|1=a}} || {{math|1=b}} || {{math|1=1}}
|-
! {{math|1=0}}
| {{math|1=0}} || {{math|1=a}} || {{math|1=b}} || {{math|1=1}}
|-
! {{math|1=a}}
| {{math|1=a}} || {{math|1=a}} || {{math|1=1}} || {{math|1=1}}
|-
! {{math|1=b}}
| {{math|1=b}} || {{math|1=1}} || {{math|1=b}} || {{math|1=1}}
|-
! {{math|1=1}}
| {{math|1=1}} || {{math|1=1}} || {{math|1=1}} || {{math|1=1}}
|}
|
| width="40" |
|
{| class="wikitable"
|-
! {{math|1=''x''}} || {{math|1=0}} || {{math|1=a}} || {{math|1=b}} || {{math|1=1}}
|-
! {{math|1=¬''x''}}
| {{math|1=1}} || {{math|1=b}} || {{math|1=a}} || {{math|1=0}}
|}
|}

* The set {{mvar|A}} of all subsets of {{mvar|S}} that are either finite or [[cofinite]] is a Boolean algebra and an [[algebra of sets]] called the [[finite–cofinite algebra]]. If {{mvar|S}} is infinite then the set of all cofinite subsets of {{mvar|S}}, which is called the [[Fréchet filter]], is a free [[ultrafilter]] on {{mvar|A}}. However, the Fréchet filter is not an ultrafilter on the power set of {{mvar|S}}. 
* Starting with the [[propositional calculus]] with {{math|κ}} sentence symbols, form the [[Lindenbaum–Tarski algebra|Lindenbaum algebra]] (that is, the set of sentences in the propositional calculus modulo [[logical equivalence]]).  This construction yields a Boolean algebra.  It is in fact the [[free Boolean algebra]] on {{math|κ}} 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 {{math|''L''}} with a least element, the interval algebra is the smallest Boolean algebra of subsets of {{math|''L''}} containing all of the half-open intervals {{math|[''a'', ''b'')}} such that {{math|''a''}} is in {{math|''L''}} and {{math|''b''}} is either in {{math|''L''}} or equal to {{math|∞}}.  Interval algebras are useful in the study of [[Lindenbaum–Tarski algebra]]s; every [[countable]] Boolean algebra is isomorphic to an interval algebra.

[[File:Lattice T 30.svg|thumb|x150px|[[Hasse diagram]] of the Boolean algebra of divisors of 30.]]
* For any [[natural number]] {{math|''n''}}, the set of all positive [[divisor]]s of {{math|''n''}}, defining {{math|''a'' ≤ ''b''}} if {{math|''a''}} [[divides]] {{math|''b''}}, forms a [[distributive lattice]]. This lattice is a Boolean algebra if and only if {{math|''n''}} is [[square-free integer|square-free]]. The bottom and the top elements of this Boolean algebra are the natural numbers {{math|1}} and {{math|''n''}}, respectively. The complement of {{math|''a''}} is given by {{math|''n''/''a''}}. The meet and the join of {{math|''a''}} and {{math|''b''}} are given by the [[greatest common divisor]] ({{math|gcd}}) and the [[least common multiple]] ({{math|lcm}}) of {{math|''a''}} and {{math|''b''}}, respectively. The ring addition {{math|''a'' + ''b''}} is given by {{math|lcm(''a'', ''b'') / gcd(''a'', ''b'')}}. The picture shows an example for {{math|1=''n'' = 30}}. As a counter-example, considering the non-square-free {{math|1=''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 [[topology|topological spaces]]: if {{math|''X''}} is a topological space, then the collection of all subsets of {{math|''X''}} that are [[Clopen set|both open and closed]] forms a Boolean algebra with the operations {{math|1=∨ := ∪}} (union) and {{math|1=∧ := ∩}} (intersection).
* If {{mvar|R}} is an arbitrary ring then its set of ''[[central idempotent]]s'', which is the set
<math display=block>A = \left\{e \in R : e^2 = e \text{ and } ex = xe \; \text{ for all } \; x \in R\right\},</math>
becomes a Boolean algebra when its operations are defined by {{math|1=''e'' ∨ ''f'' := ''e'' + ''f'' − ''ef''}} and {{math|1=''e'' ∧ ''f'' := ''ef''}}.