Definition
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 2n possible values for its n arguments. For each choice of arguments the operation may return 0 or 1, whence there are 22n n-ary operations.
The prototype therefore has two operations taking no arguments, called zeroary or nullary operations, namely zero and one. It has four unary operations, two of which are constant operations, another is the identity, and the most commonly used one, called negation, returns the opposite of its argument: 1 if 0, 0 if 1. It has sixteen binary operations; again two of these are constant, another returns its first argument, yet another returns its second, one is called conjunction and returns 1 if both arguments are 1 and otherwise 0, another is called disjunction and returns 0 if both arguments are 0 and otherwise 1, and so on. The number of (n+1)-ary operations in the prototype is the square of the number of n-ary operations, so there are 162 = 256 ternary operations, 2562 = 65,536 quaternary operations, and so on.
A family is indexed by an index set. In the case of a family of operations forming an algebra, the indices are called operation symbols, constituting the language of that algebra. The operation indexed by each symbol is called the denotation or interpretation of that symbol. Each operation symbol specifies the arity of its interpretation, whence all possible interpretations of a symbol have the same arity. In general it is possible for an algebra to interpret distinct symbols with the same operation, but this is not the case for the prototype, whose symbols are in one-one correspondence with its operations. The prototype therefore has 22n n-ary operation symbols, called the Boolean operation symbols and forming the language of Boolean algebra. Only a few operations have conventional symbols, such as ¬ for negation, ∧ for conjunction, and ∨ for disjunction. It is convenient to consider the i-th n-ary symbol to be nfi as done below in the section on truth tables.
An equational theory in a given language consists of equations between terms built up from variables using symbols of that language. Typical equations in the language of Boolean algebra are x∧y = y∧x, x∧x = x, x∧¬x = y∧¬y, and x∧y = x.
An algebra satisfies an equation when the equation holds for all possible values of its variables in that algebra when the operation symbols are interpreted as specified by that algebra. The laws of Boolean algebra are the equations in the language of Boolean algebra satisfied by the prototype. The first three of the above examples are Boolean laws, but not the fourth since 1∧0 ≠ 1.
The equational theory of an algebra is the set of all equations satisfied by the algebra. The laws of Boolean algebra therefore constitute the equational theory of the Boolean prototype.
A model of a theory is an algebra interpreting the operation symbols in the language of the theory and satisfying the equations of the theory.
- A Boolean algebra is any model of the laws of Boolean algebra.
That is, a Boolean algebra is a set and a family of operations thereon interpreting the Boolean operation symbols and satisfying the same laws as the Boolean prototype.
If we define a homologue of an algebra to be a model of the equational theory of that algebra, then a Boolean algebra can be defined as any homologue of the prototype.
Example 1. The Boolean prototype is a Boolean algebra, since trivially it satisfies its own laws. It is thus the prototypical Boolean algebra. We did not call it that initially in order to avoid any appearance of circularity in the definition.
Read more about this topic: Boolean Algebras Canonically Defined
Famous quotes containing the word definition:
“Although there is no universal agreement as to a definition of life, its biological manifestations are generally considered to be organization, metabolism, growth, irritability, adaptation, and reproduction.”
—The Columbia Encyclopedia, Fifth Edition, the first sentence of the article on “life” (based on wording in the First Edition, 1935)
“It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
—François, Duc De La Rochefoucauld (1613–1680)
“The man who knows governments most completely is he who troubles himself least about a definition which shall give their essence. Enjoying an intimate acquaintance with all their particularities in turn, he would naturally regard an abstract conception in which these were unified as a thing more misleading than enlightening.”
—William James (1842–1910)