User:Hugo Herbelin/BA

Boolean algebra (mass noun) is about the equational properties of a large class of structures, called Boolean algebras (count noun), whose most prominent examples are the logic of truth-values 0 and 1 and the algebra of sets.

Named after George Boole who developed it in the 1840's in the context of propositional logic, it has many applications in computer science, automated theorem proving, electronics, statistics, mathematical logic and foundation of mathematics.

Boolean algebra is a domain with many ramifications and this article is restricted to the presentation of the basic contents about Boolean algebra.

Boolean algebra on the Boolean domain

Main article: Boolean algebra (logic)

The elements of the Boolean domain are 0 (false) and 1 (true). The basic operations are x∧y (and), x∨y (or), and ¬x (not) with meanings defined by truth tables as shown on Figure 1 (other notations for ∧, ∨ and ¬ are: ⋅ (the product sign), + and -; ¬x is sometimes written ${\overline {x}}$; in programming languages, especially in C, the operations are written &&, ||, and !; in electronics, they can be represented graphical by logic gates as shown in Figure 2).

Using the truth tables, one can do arbitrary computations such as 0∧¬(0∨¬0) = 0 and 1∧¬(0∨¬1) = 1, which allow for instance to show that x∧¬(0∨¬x) = x holds whatever the value of x is.

Boolean algebra axioms

The main result about Boolean algebra is that all true equations about 0, 1, ∧, ∨ and ¬, including those mentioning variables, such as x∧¬(0∨¬x) = x above, are completely characterized by the following finite collection of Boolean algebra axioms:

$a\lor (b\lor c)=(a\lor b)\lor c$	$a\land (b\land c)=(a\land b)\land c$	associativity
$a\lor b=b\lor a$	$a\land b=b\land a$	commutativity
$a\lor (a\land b)=a$	$a\land (a\lor b)=a$	absorption
$a\lor (b\land c)=(a\lor b)\land (a\lor c)$	$a\land (b\lor c)=(a\land b)\lor (a\land c)$	distributivity
$a\lor {\neg }a=1$	$a\land {\neg }a=0$	complements

Derived laws

Since the axioms are complete, a law such as x∨0 = x (right identity) has to be derivable. Indeed, here is a proof:

x∨0	= x∨(x∧¬x)	(by complements)
	= x	(by absorption)

Also, because all axioms are symmetric in 0 and 1 and in ∨ and ∧, a dual reasoning shows that x∧1 = x holds.

Among the other standard consequences of the axioms of Boolean algebra, we can find the de Morgan laws:

¬(x∨y) = (¬x)∧(¬y)

¬(x∧y) = (¬x)∨(¬y)

Of course, alternative equivalent collections of axioms exist, some of them taking the same primitive operations as above, other based on alternative basic operations. In particular, there exists some remarkable axiomatics based on Sheffer Stroke, i.e. the negated and (NAND).

Generalization of the concept

The characterization of the true equations over the Boolean domain applies to other domains. The most typical examples are the power set of a set and bit vectors, with applications to set theory, set operations such as Boolean conjunctive query in relational databases, bitwise operations in binary arithmetic.

The algebra of sets

Indeed, if X is a given set and one takes X for 1 and Ø (empty set) for 0, then, the set-theoretic operations ∩ (intersection), ∪ (union) and $\complement$ (complement) satisfy all the equations given above. Using Venn diagrams, one can see for instance on Figure 3 that A∪(B∩c) and (A∪B)∩(A∪C) denote the same set and hence that the distributivity law of Boolean algebra holds.

As a consequence, all results from Boolean algebra apply. For instance, here is a proof that intersection is idempotent on all subsets of X:

A ∩ A	= (A ∩ A) ∪ Ø	(by derived rule: right identity)
	= (A ∩ A) ∪ (A ∩ $\complement$A)	(by complement)
	= A ∩ (A ∪ $\complement$A)	(by distributivity)
	= A ∩ X	(by complement)
	= A	(by derived rule: right identity)

Bit vectors

By interpreting O and 1 as bits, the bitwise operations, commonly written AND, OR and NEG, directly derive from their equivalent on 0 and 1 and it can easily be shown that they satisfy the axioms of Boolean algebra.

As a consequence, all results from Boolean algebra apply too. For instance, on 4-bits vectors, one can show:

0101 AND (NEG (x OR 1001))	= 0101 AND ((NEG x) AND (NEG 1001))	(by derived rule: de Morgan's law)
	= 0101 AND ((NEG x) AND 0110)	(by computation of NEG)
	= 0101 AND (0110 AND (NEG x))	(by commutativity)
	= (0101 AND 0110) AND (NEG x)	(by associativity)
	= 0100 AND (NEG x)	(by computation of AND)

Other examples can be found here, here and there

Significance of Boolean algebra

The existence of Boolean algebra axioms is of great importance: it amounts to say that methods similar to the ones of elementary algebra are applicable to the logic of two values, and, more generally to any other domain satisfying the same axioms.

For instance, thanks to algorithmic techniques relevant to the Boolean satisfiability problem, equational problems over infinite structures satisfying the Boolean axioms can be addressed as if they were problems over the Boolean domain, what makes them decidable.

Applications

Following Shannon, Boolean algebra applies to circuit design in electrical engineering; 0 and 1 may 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.

In mathematical logic, Boolean structures are models of propositional logic while Boolean algebra, following the seminal work of Boole, ensures the correctness of simplifications over propositions.

In automated theorem proving, Boolean algebra ensures the correctness of various transformations of propositions, such as disjunctive normal forms or conjunctive normal forms. In cryptography, Boolean algebra justifies algebraic normal forms.

In statistics, Boolean algebras occurs as part of comparative analysis.

An extensive list of applications can be found here

External links

• The Calculus of Logic, by George Boole, Cambridge and Dublin Mathematical Journal Vol. III (1848), pp. 183–98.

Meta questions

Vaughan Pratt cited Halmos for having mentioned statistics in his Boolean algebra book but no details is given by Halmos. There is also a page Boolean analysis listed in ||List of Boolean algebra topics]], but it is not clear from the article how it really connects to Boolean algebra. Should the reference be maintained?

There is a page on functional completeness that talks about basis. This looks like contents to merge.

There are detailed examples of Boolean algebras dispatched in too many articles. I would suggest to create a dedicated page about the examples of Boolean algebras. Then, this page could be the Main page of the Section generalization.

TODO: add figures with Truth tables, Logical gates, Venn diagrams

TODO: check tags

TODO: check reference to Boole's work

TODO: avoid mixing large and small spectrum domains in the list of application domains