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 description borrows from the Wikipedia article on Boolean Algebra.

The basic operators in Boolean algebra are and, or, and not. The and of two values is true only whenever both values are true. The or of two values is true whenever either or both values are true. The not of a true value is false, and the not of a false value is true. The secondary operators are exclusive or (often called xor) and equivalence . The xor of two values is true whenever the values are different; the equivalence of two values is true when both values are the same. Just as algebra has basic rules for simplifying and evaluating expressions, so does Boolean algebra.

Why is Boolean Algebra Important for ACSL Students?

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 < 100 and (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 "red" and "sox" and not "yankees" 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) is 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]. The and of two values is true only when both values are true.
• or (disjunction) is denoted as [math]x \vee y[/math], [math]x \text{ OR } y[/math], or [math]x + y[/math] . The or of two values is true whenever one or both values are true.
• not (negation) is denoted as [math]\neg x[/math], [math]\text{ NOT } x[/math], or [math]\bar{x}[/math] . The not of a value is its opposite; that is, the not of a true value is false whereas the not" of a false value is true.

The values of and, or, and not for all possible inputs is shown 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 secondary Boolean operators are exclusive or and equivalence. They are secondary in the sense that they can be composed from the basic operations.

• exclusive or or xor is denoted as [math]x \oplus y[/math] or [math]x \text{xor} y[/math]. The xor of two values is true when the values are different. It can also be represented by ands and ors:

[math]x \oplus y = (x \cdot \bar{y}) + (\bar{x} \cdot y)[/math]

• "equivalence is denoted as [math]x \equiv y[/math], [math]x \cdot y[/math], or [math]x \text{equ} y[/math] The equivalence of two values is true when the values are the same; it is the not of the xor function:

[math]x \equiv y = \bar{(x \oplus y)} = xy + \bar{x} \bar{y}[/math]

Here is the truth table of these two operators 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

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]

===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]