In mathematics and abstract algebra, the two-element Boolean algebra is the Boolean algebra whose underlying set (or universe or carrier) B is the Boolean domain. The elements of the Boolean domain are 1 and 0 by convention, so that B = {0, 1}. Paul Halmos's name for this algebra "2" has some following in the literature, and will be employed here.
Definition B is a partially ordered set and the elements of B are also its bounds. An operation of arity n is a mapping from Bn to B. Boolean algebra consists of two binary operations and unary complementation. The binary operations have been named and notated in various ways. Here they are called 'sum' and 'product', and notated by infix '+' and '∙', respectively. Sum and product commute and associate, as in the usual algebra of real numbers. As for the order of operations, brackets are decisive if present. Otherwise '∙' precedes '+'. Hence A ∙ B + C is parsed as (A ∙ B) + C and not as A ∙ (B + C). Complementation is denoted by writing an overbar over its argument. The numerical analog of the complement of X is 1 − X. In the language of universal algebra, a Boolean algebra is a ⟨ B , + , {\displaystyle \langle B,+,} ∙ , . . ¯ , 1 , 0 ⟩ {\displaystyle ,{\overline {..}},1,0\rangle } algebra of type ⟨ 2 , 2 , 1 , 0 , 0 ⟩ {\displaystyle \langle 2,2,1,0,0\rangle } . Either one-to-one correspondence between {0,1} and {True,False} yields classical bivalent logic in equational form, with complementation read as NOT. If 1 is read as True, '+' is read as OR, and '∙' as AND, and vice versa if 1 is read as False. These two operations define a commutative semiring, known as the Boolean semiring.
Some basic identities 2 can be seen as grounded in the following trivial "Boolean" arithmetic:
1 + 1 = 1 + 0 = 0 + 1 = 1 0 + 0 = 0 0 ⋅ 0 = 0 ⋅ 1 = 1 ⋅ 0 = 0 1 ⋅ 1 = 1 1 ¯ = 0 0 ¯ = 1 {\displaystyle {\begin{aligned}&1+1=1+0=0+1=1\\&0+0=0\\&0\cdot 0=0\cdot 1=1\cdot 0=0\\&1\cdot 1=1\\&{\overline {1}}=0\\&{\overline {0}}=1\end{aligned}}}
Note that:
'+' and '∙' work exactly as in numerical arithmetic, except that 1+1=1. '+' and '∙' are derived by analogy from numerical arithmetic; simply set any nonzero number to 1. Swapping 0 and 1, and '+' and '∙' preserves truth; this is the essence of the duality pervading all Boolean algebras. This Boolean arithmetic suffices to verify any equation of 2, including the axioms, by examining every possible assignment of 0s and 1s to each variable (see decision procedure). The following equations may now be verified:
A + A = A A ⋅ A = A A + 0 = A A + 1 = 1 A ⋅ 0 = 0 A ¯ ¯ = A {\displaystyle {\begin{aligned}&A+A=A\\&A\cdot A=A\\&A+0=A\\&A+1=1\\&A\cdot 0=0\\&{\overline {\overline {A}}}=A\end{aligned}}}
Each of '+' and '∙' distributes over the other:
A ⋅ ( B + C ) = A ⋅ B + A ⋅ C ; {\displaystyle \ A\cdot (B+C)=A\cdot B+A\cdot C;}
A + ( B ⋅ C ) = ( A + B ) ⋅ ( A + C ) . {\displaystyle \ A+(B\cdot C)=(A+B)\cdot (A+C).}
That '∙' distributes over '+' agrees with elementary algebra, but not '+' over '∙'. For this and other reasons, a sum of products (leading to a NAND synthesis) is more commonly employed than a product of sums (leading to a NOR synthesis). Each of '+' and '∙' can be defined in terms of the other and complementation:
… excerpt ends here. Continue reading the full article.
