# GetWiki

*two-element Boolean algebra*

ARTICLE SUBJECTS

being →

database →

ethics →

fiction →

history →

internet →

language →

linux →

logic →

method →

news →

policy →

purpose →

religion →

science →

software →

truth →

unix →

wiki →

ARTICLE TYPES

essay →

feed →

help →

system →

wiki →

ARTICLE ORIGINS

critical →

forked →

imported →

original →

two-element Boolean algebra

[ temporary import ]

**please note:**

- the content below is remote from Wikipedia

- it has been imported raw for GetWiki

**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

*B*n 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 langle B,+,.,overline{..},1,0rangle algebra of type langle 2,2,1,0,0rangle.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:

- '+' 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.

**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 cdot (B+C) = A cdot B + A cdot C;
- A+(B cdot C) = (A+B) cdot (A+C).

- A cdot B=overline{overline{A}+overline{B}}
- A+B=overline{overline{A} cdot overline{B}}.

**2**. This notation is also that of Quine's Boolean term schemata. Letting (

*X*) denote the complement of

*X*and "()" denote either 0 or 1 yields the syntax of the primary algebra.A

*basis*for

**2**is a set of equations, called axioms, from which all of the above equations (and more) can be derived. There are many known bases for all Boolean algebras and hence for

**2**. An elegant basis notated using only concatenation and overbar is:

- ABC = BCA (Concatenation commutes, associates)
- overline{A}A = 1 (
**2**is a complemented lattice, with an upper bound of 1) - A0 = A (0 is the lower bound).
- Aoverline{AB} = Aoverline{B} (
**2**is a distributive lattice)

## Metatheory

De Morgan's theorem states that if one does the following, in the given order, to any Boolean function:- Complement every variable;
- Swap '+' and 'âˆ™' operators (taking care to add brackets to ensure the order of operations remains the same);
- Complement the result,

**2**holds for all Boolean algebras.Givant, S., and Halmos, P. (2009)

*Introduction to Boolean Algebras*, Springer Verlag. Theorem 9. Conversely, an identity that holds for an arbitrary nontrivial Boolean algebra also holds in

**2**. Hence all the mathematical content of Boolean algebra is captured by

**2**. This theorem is useful because any equation in

**2**can be verified by a decision procedure. Logicians refer to this fact as "

**2**is decidable". All known decision procedures require a number of steps that is an exponential function of the number of variables

*N*appearing in the equation to be verified. Whether there exists a decision procedure whose steps are a polynomial function of

*N*falls under the P = NP conjecture.

## See also

## References

{{Reflist}}## Further reading

Many elementary texts on Boolean algebra were published in the early years of the computer era. Perhaps the best of the lot, and one still in print, is:- Mendelson, Elliot, 1970.
*Schaum's Outline of Boolean Algebra*. McGraw–Hill.

- Stanford Encyclopedia of Philosophy: "The Mathematics of Boolean Algebra," by J. Donald Monk.
- Burris, Stanley N., and H.P. Sankappanavar, H. P., 1981.
*A Course in Universal Algebra.*Springer-Verlag. {{isbn|3-540-90578-2}}.

**- content above as imported from Wikipedia**

- "

- time: 3:26pm EST - Mon, Feb 18 2019

- "

__two-element Boolean algebra__" does not exist on GetWiki (yet)- time: 3:26pm EST - Mon, Feb 18 2019

[ this remote article is provided by Wikipedia ]

LATEST EDITS [ see all ]

GETWIKI 09 MAY 2016

GETWIKI 18 OCT 2015

GETWIKI 20 AUG 2014

GETWIKI 19 AUG 2014

GETWIKI 18 AUG 2014

© 2019 M.R.M. PARROTT | ALL RIGHTS RESERVED