ALGEBRA, BOOLEAN—an algebraic structure that is especially interesting because it can constitute an algebraic counterpart to the classic propositional calculus. Studies of Boolean algebra were an important step in the rise of modern logic.

1. Boolean algebra is called an ordered system (K, 0, 1,',+,·,=), meeting the following conditions:.
K is a non-empty set, 0 and 1 are two different elements of the set, ' is a one-argument operation, + and · are two-argument operations, and = is a two-member relation.
The Set K is closed with respect to the operation ', + and ·.
The relation = is a equipollent relation (i.e., reversible, symmetrical, and transitive) such that for any two elements x, y, z, that belong to the set K, if x = y, then x + z = y + z and x · z = y · z.
For any elements x, y, z that belong to the set K, it happens that:
  1. x + 0 = x
  2. x + x' = 1
  3. x + y = y + x
  4. x + (y · z) = (x + y) · (x + z)
  5. x · 1 = x
  6. x · x' = 0
  7. x · y = y · x
  8. x · (y + z) = (x + y) + (x · z).

All the variables that occur here have a specific meaning in Boolean algebra that does not correspond to the meaning of invariables of similar appearance in arithmetic and logic. In particular the relation = must not be understood as identity. The operations ', +, and · are commonly called completion, addition, and multiplication respectively.

If we observe the above formulas 1–8, we may notice that if in any of them we replace + and 0 respectively by · and 1, or the reverse, we also obtain a formula of the set. This property is called duality. Since we can infer from the set of formulas 1–8 all true formulas in any Boolean algebra, the property of duality also applies to them.

The formulas 1–8 and all the formulas that can be inferred from them constitute the system of Boolean algebra. The following are some of the formulas that belong to the system of Boolean algebra: x''=x; x + x = x; x · x = x; x + 1 = 1; x · 0 = 0; (x + y)' = x' · y'; (x + y)' = x' + y'; 1' = 0; 0' = 1.

A special and interesting case of Boolean algebra is two-element Boolean algebra. In this case the set K contains only the elements of 0 and 1.

2. An important feature of Boolean algebra is that different interpretations of it are possible. The system of Boolean algebra has an interpretation in a system if and only if after replacing the invariables of the system of Boolean algebra with terms of the system we obtain from expressions 1–8 the propositions of the system.

For example, if we replace the sign ' with ~, the sign · with ∧, the sign + with ∨, the sign = with ≡, 1 with the proposition p ∨ ~ p, and 0 by the proposition p ∧ ~p, and if we understand the variables of the system as propositional variables, we obtain an interpretation of the system of Boolean algebra in the propositional calculus. Other well-known interpretations of Boolean algebra are interpretations in the calculus of sets, the probability calculus, and the theory of electric networks.

3. Boolean algebra may also be treated as a model for logical calculuses. Then the elements of the set K are ascribed to the formulas of the logical calculus, and the operations of Boolean algebra are ascribed to logical invariables. A formula of a logical calculus is completed in the model if element 1 of set K corresponds to it. The completion of a formula depends upon the assingnment of the corresponding elements of the set K to the variables of the logical calculus. If the formula is completed in each such assignment, then the formula is a tautology.

A simple example of such a construction is the assigment of the model in the form of the two-element Boolean algebra to the classical propositional calculus. The verification of whether the formula is a tautology is in this case a common verification by the zero-one method of truth for the formula.

The generalization of this simple case of modeling the classical propositional calculus in the two-element Boolean algebra led to the rise and development of the field known as algebraic logic. Algebraic models analogous to the above were obtained by the predicate calculus (in Boolean algebra), and by non-classical logics, and in particular by the intuitive logic and intermediate logics (in pseudo-Boolean algebras), as well as by model logics.

R. Sikorski, Boolean Algebras, B 1960, 19693; A. Mostowski, Algebry Bool’a i ich zastosowania [Boolean algebras and their applications], Wwa 1964; H. Rasiowa, R. Sikorski, The Mathematics of Metamathematics, Wwa 19703; L. Borkowski, Elementy logiki formalnej [Elements of Formal Logic], Wwa 1972, 19805.

Bożena Czernecka, Piotr Kulicki

<--Go back