Boolean Algebra
Boolean algebra' is the branch of algebra in which the values of the variables and constants have exactly two values: "true" and "false", usually denoted 1 and 0 respectively. This overview is loosely based on the Wikipedia article on [[1]]Algebra.
The basic operators in Boolean algebra are "and", "or", and "not". The "and" of two variable results in true only whenever both variables are true. The "or" of two variables is true whenever either or both variables are true. The "not" of a variable changes a true to false and a false to true. Just as algebra has basic rules for simplifying and evaluating expression, so does Boolean algebra.
Why is Boolean Algebra Important?
Boolean algebra is important to programmers, computer scientists, and the general population.
- For programmers, Boolean expressions are used for conditionals and loops. For example, the following snippet of code sums the even numbers that are not also multiples of 3, stopping when the sum hits 100:
-
s = 0 x = 1 while (s < 100): if (x % 2 == 0) and (x % 3 != 0): s = s + x x = x + 1
Both
s < 100and(x % 2 == 0) and (x % 3 != 0)are Boolean expressions.
- For computer scientists, Boolean algebra is the basis for digital circuits that make up a computer's hardware. The Digital Electronics category concerns a graphical representation of a circuit. That circuit is typically easiest to understand and evaluate by converting it to its Boolean algebra representation.
- The general population uses Boolean algebra, probably without knowing that they are doing so, when they enter search terms in Internet search engines. For example, the search expression "red sox -yankees" is the Boolean expression that will returns web pages that contain the words "red" and "sox", as long as it does not contain the word "yankees". The search expression "jaguar speed -car" returns pages about the speed of the jaguar animal, not the Jaguar car.
Operations
Basic operations
The basic operations of Boolean algebra are AND, OR, and NOT:
- AND (conjunction) will be denoted as [math]x \wedge y[/math], [math]x \text{AND} y[/math], [math]x \& y[/math], [math]xy[/math], or [math]x \cdot y[/math]
- OR (disjunction) will be denoted as [math]x \vee y[/math], [math]x \text{OR} y[/math], or [math]x + y[/math]
- NOT (negation) will be in denated as [math]\neg x[/math], [math]\text{NOT} x[/math], or [math]\bar{x}[/math]
The values of AND, OR, and NOT for all possible inputs is show in the following truth table:
-
[math]x[/math] [math]y[/math] [math]x y[/math] [math]x + y[/math] [math]\bar{x}[/math] 0 0 0 0 1 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0
Secondary operations
The three Boolean operations described above are referred to 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. Operations composed from the basic operations include the following examples:
- [math]x \oplus y = (x \vee y) \wedge \neg{(x \wedge y)}[/math]
- [math]x \equiv y = \neg{(x \oplus y)}[/math]
These definitions give rise to the following truth tables giving the values of these operations for all four possible inputs.
[math]x[/math] [math]y[/math] [math]x \oplus y[/math] [math]x \equiv y[/math] 0 0 0 1 1 0 1 0 0 1 1 0 1 1 0 1
The first operation, x ⊕ y, or Jxy, is called exclusive or (often abbreviated as XOR) to distinguish it from disjunction as the inclusive kind. It excludes the possibility of both x and y.
The second 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. Equivalence's counterpart in arithmetic mod 2 is x + y + 1.
Laws
A law of Boolean algebra is an identity such as x∨(y∨z) = (x∨y)∨z between two Boolean terms, where a Boolean term is defined as an expression built up from variables and the constants 0 and 1 using the operations ∧, ∨, and ¬. The concept can be extended to terms involving other Boolean operations such as ⊕, →, and ≡, but such extensions are unnecessary for the purposes to which the laws are put. Such purposes include the definition of a Boolean algebra as any model of the Boolean laws, and as a means for deriving new laws from old as in the derivation of x∨(y∧z) = x∨(z∧y) from y∧z = z∧y as treated in the section on axiomatization.
Monotone laws
Boolean algebra satisfies many of the same laws as ordinary algebra when one matches up ∨ with addition and ∧ with multiplication. In particular the following laws are common to both kinds of algebra:<ref name="O'Regan_p33">Template:Cite book</ref>
Associativity of [math]\vee[/math]: [math]x \vee (y \vee z)[/math] [math]= (x \vee y) \vee z[/math] Associativity of [math]\wedge[/math]: [math]x \wedge (y \wedge z)[/math] [math]= (x \wedge y) \wedge z[/math] Commutativity of [math]\vee[/math]: [math]x \vee y[/math] [math]= y \vee x[/math] Commutativity of [math]\wedge[/math]: [math]x \wedge y[/math] [math]= y \wedge x[/math] Distributivity of [math]\wedge[/math] over [math]\vee[/math]: [math]x \wedge (y \vee z)[/math] [math]= (x \wedge y) \vee (x \wedge z)[/math] Identity for [math]\vee[/math]: [math]x \vee 0[/math] [math]= x[/math] Identity for [math]\wedge[/math]: [math]x \wedge 1[/math] [math]= x[/math] Annihilator for [math]\wedge[/math]: [math]x \wedge 0[/math] [math]= 0[/math]
The following laws hold in Boolean Algebra, but not in ordinary algebra:
Annihilator for [math]\vee[/math]: [math]x \vee 1[/math] [math]= 1[/math] Idempotence of [math]\vee[/math]: [math]x \vee x[/math] [math]= x[/math] Idempotence of [math]\wedge[/math]: [math]x \wedge x[/math] [math]= x[/math] Absorption 1: [math]x \wedge (x \vee y)[/math] [math]= x[/math] Absorption 2: [math]x \vee (x \wedge y)[/math] [math]= x[/math] Distributivity of [math]\vee[/math] over [math]\wedge[/math]: [math]x \vee (y \wedge z)[/math] [math]=(x \vee y) \wedge (x \vee z)[/math]
Taking x = 2 in the third law above shows that it is not an ordinary algebra law, since 2×2 = 4. The remaining five laws can be falsified in ordinary algebra by taking all variables to be 1, for example in Absorption Law 1 the left hand side would be 1(1+1) = 2 while the right hand side would be 1, and so on.
All of the laws treated so far have been for conjunction and disjunction. These operations have the property that changing either argument either leaves the output unchanged or the output changes in the same way as the input. Equivalently, changing any variable from 0 to 1 never results in the output changing from 1 to 0. Operations with this property are said to be monotone. Thus the axioms so far have all been for monotonic Boolean logic. Nonmonotonicity enters via complement ¬ as follows.<ref name="givhal"/>
Nonmonotone laws
The complement operation is defined by the following two laws.
- [math] \begin{align} &\text{Complementation 1} & x \wedge \neg x & = 0 \\ &\text{Complementation 2} & x \vee \neg x & = 1 \end{align} [/math]
All properties of negation including the laws below follow from the above two laws alone.<ref name="givhal"/>
In both ordinary and Boolean algebra, negation works by exchanging pairs of elements, whence in both algebras it satisfies the double negation law (also called involution law)
- [math] \begin{align} &\text{Double negation} & \neg{(\neg{x})} & = x \end{align} [/math]
But whereas ordinary algebra satisfies the two laws
- [math] \begin{align} (-x)(-y) & = xy \\ (-x) + (-y) & = -(x + y) \end{align} [/math]
Boolean algebra satisfies De Morgan's laws:
- [math] \begin{align} &\text{De Morgan 1} & \neg x \wedge \neg y & = \neg{(x \vee y)} \\ &\text{De Morgan 2} & \neg x \vee \neg y & = \neg{(x \wedge y)} \end{align} [/math]