Boolean algebra

In mathematics and mathematical logic, Boolean algebra is the subarea of algebra in which the values of the variables are the truth values true and false, usually denoted 1 and 0 respectively. Instead of elementary algebra where the values of the variables are numbers, and the main operations are addition and multiplication, the main operations of Boolean algebra are the conjunctionand, denoted ∧, the disjunction or, denoted ∨, and the negation not, denoted ¬.

Boolean algebra was introduced in 1854 by George Boole in his book An Investigation of the Laws of Thought. According to Huntington the term "Boolean algebra" was first suggested bySheffer in 1913.

Boole's first book The Mathematical Analysis of Logic published in 1847 included the original theory. This was proposed as a Mathematical language dealing with the questions of logic which is now needed in the design of modern digital equipment, and now exists as a core data type in all modern programming languages generally abbreviated to as type bool, representing true or false within assertion logic.

Boolean algebra has been fundamental in the development of computer science and digital logic. It is also used in set theory and statistics.

Whereas in elementary algebra expressions denote mainly numbers, in Boolean algebra they denote the truth values false and true. These values are represented with the bits (or binary digits) being 0 and 1. They do not behave like the integers 0 and 1, for which 1 + 1 = 2, but may be identified with the elements of the two-element field GF(2), for which 1 + 1 = 0 with + serving as the Boolean operation XOR.

Boolean algebra also deals with functions which have their values in the set {0, 1}. A sequence of bits is a commonly used such function. Another common example is the subsets of a set E: to a subset F of E is associated the indicator function that takes the value 1 on F and 0 outside F.

As with elementary algebra, the purely equational part of the theory may be developed without considering explicit values for the variables.

Basic operations

The basic operations of Boolean algebra are the following ones:

• And (conjunction), denoted x∧y (sometimes x AND y or Kxy), satisfies x∧y = 1 if x = y = 1 and x∧y = 0 otherwise.
• Or (disjunction), denoted x∨y (sometimes x OR y or Axy), satisfies x∨y = 0 if x = y = 0 and x∨y = 1 otherwise.
• Not (negation), denoted ¬x (sometimes NOT x, Nx or !x), satisfies ¬x = 0 if x = 1 and ¬x = 1 if x = 0.

If the truth values 0 and 1 are interpreted as integers, these operation may be expressed with the ordinary operations of the arithmetic:

x∧y = xy,

x∨y = x + y - xy,

¬x = 1 - x.

Alternatively the values of x∧y, x∨y, and ¬x can be expressed by tabulating their values with truth tables as follows.

Figure 1. Truth tables

x y x∧y x∨y 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1

x ¬x 0 1 1 0

NOTE:

One may consider that only the negation and one of the two other operations are basic, because of the following identities that allow to define the conjunction in terms of the negation and the disjunction, and vice versa:

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

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

Derived operations

We have so far seen three Boolean operations. We referred to these as basic, meaning that they can be taken as a basis for other Boolean operations that can be built up from them by composition, the manner in which operations are combined or compounded. Here are some examples of operations composed from the basic operations.

x → y	=	¬x ∨ y
x ⊕ y	=	(x ∨ y) ∧ ¬(x ∧ y)
x ≡ y	=	¬(x ⊕ y)

These definitions give rise to the following truth tables giving the values of these operations for all four possible inputs.

x	y		x → y	x ⊕ y	x ≡ y
0	0		1	0	1
1	0		0	1	0
0	1		1	1	0
1	1		1	0	1

The first operation, x → y, or Cxy, is called material implication. If x is true then the value of x → y is taken to be that of y. But if x is false then we ignore the value of y; however we must return some truth value and there are only two choices, so we choose the value that entails less, namely true. (Relevance logic addresses this by viewing an implication with a false premise as something other than either true or false.)

The second operation, x ⊕ y, or Jxy, is called exclusive or to distinguish it from disjunction as the inclusive kind. It excludes the possibility of both x and y. Defined in terms of arithmetic it is addition mod 2 where 1 + 1 = 0.

The third operation, the complement of exclusive or, is equivalence or Boolean equality: x ≡ y, or Exy, is true just when x and y have the same value. Hence x ⊕ y as its complement can be understood as x ≠ y, being true just when x and y are different. Its counterpart in arithmetic mod 2 is x + y + 1.

Given two operands, each with two possible values, we have 2² = 4 possible combinations of inputs. Because each output can have two possible values, we have a total of 2⁴ = 16 possible binary Boolean operations.