Boolean algebras canonically defined

Boolean algebra is a mathematically rich branch of abstract algebra. Stanford Encyclopaedia of Philosophy defines Boolean algebra as 'the algebra of two-valued logic with only sentential connectives, or equivalently of algebras of sets under union and complementation.' Just as group theory deals with groups, and linear algebra with vector spaces, Boolean algebras are models of the equational theory of the two values 0 and 1 (whose interpretation need not be numerical). Common to Boolean algebras, groups, and vector spaces is the notion of an algebraic structure, a set closed under some operations satisfying certain equations.

Just as there are basic examples of groups, such as the group ${\displaystyle \mathbb {Z} }$ of integers and the symmetric group S_n of permutations of n objects, there are also basic examples of Boolean algebras such as the following.

Boolean algebra thus permits applying the methods of abstract algebra to mathematical logic and digital logic.

Unlike groups of finite order, which exhibit complexity and diversity and whose first-order theory is decidable only in special cases, all finite Boolean algebras share the same theorems and have a decidable first-order theory. Instead, the intricacies of Boolean algebra are divided between the structure of infinite algebras and the algorithmic complexity of their syntactic structure.

Boolean algebra treats the equational theory of the maximal two-element finitary algebra, called the Boolean prototype, and the models of that theory, called Boolean algebras. These terms are defined as follows.

An algebra is a family of operations on a set, called the underlying set of the algebra. We take the underlying set of the Boolean prototype to be {0,1}.

An algebra is finitary when each of its operations takes only finitely many arguments. For the prototype each argument of an operation is either 0 or 1, as is the result of the operation. The maximal such algebra consists of all finitary operations on {0,1}.

The number of arguments taken by each operation is called the arity of the operation. An operation on {0,1} of arity n, or n-ary operation, can be applied to any of 2ⁿ possible values for its n arguments. For each choice of arguments, the operation may return 0 or 1, whence there are 2²ⁿ n-ary operations.