Boolean Algebra is a form of algebra for manipulating boolean expressions. Unlike "normal" algebra, variables in boolean algebra are either True or False. (usually represented by 1 and 0.)

The basic boolean functions are AND, OR, and NOT.
AND is like multiplication in "normal" algebra.
OR is treated as addition.
NOT is represented by an apostrophe following the variable or expression.

Some Basic Boolean Algebra:

0' = 1 (the inverse of 0 is 1)
1' = 0 (the inverse of 1 is 0)

Operations with 0 and 1:
X + 1 = 1 (X or 1/true = 1/true)
X + 0 = X
X * 0 = 0 (X and 0 = 0)
X * 1 = X

Idempotent laws:
X + X = X
X * X = X

Laws of complementarity:
X + X' = 1
X * X' = 0

Commutative Laws:
X + Y = Y + X
XY = YX (X and Y = Y and X)

Associative laws:
(X + Y) + Z = X + (Y + Z) = X + Y + Z
(XY)Z = X(YZ) = XYZ

Distributive laws:
X(Y+Z) = XY + XZ
X + YZ = (X + Y)(X + Z)

From these basics others can easily be derived.

A boolean algebra B is a complete lattice with the following properties:
For any a,b of B let a and b := inf{a,b} and a or b:=sup{a,b}.
  1. Distributivity: a and (b or c) = (a and b) or (a and c)
  2. Distributivity: a or (b and c) = (a or b) and (a or c)
  3. Existence of a negation operation not: B -> B with
    1. ((not a) and a) or b = b
    2. ((not a) or a) and b = b

From these follows:

  • all other calculation rules (some follow directly from the lattice)
  • the unique existence of a 1 and 0 (in fact 1=sup(B) and 0=inf(B)), one could also define 1 and 0 and their properties in the definition
  • boolean algebras doesn't just consist of 0 and 1, they can be rather strange in the infinite case
  • there is some connection to the algebraic definition of an algebra
  • in a finite boolean algebra every element can be constructed from minimal elements, the so called atoms. This is the basis for the representation of boolean functions by disjunctive normal forms

Examples: set of subsets of a set.
the set of functions from an arbitrary set into a boolean algebra

In my experiences with Boolean algebra in dealing with logic gates for chip designs, there are a couple theorems which are slightly less natural, but get frequently used. Using * for our logical "and", in combination with + for our logical "or":

Covering Theorem
X * (X + Y) = X

Combining Theorem
(X + Y) * (X + Y') = X

Consensus Theorems
1. (X + Y) * (X' + Z) * (Y + Z) = (X + Y) * (X' + Z)
2. X * Y + X' * Z + Y * Z = X * Y + X' * Z

As previously mentioned, these theorems are slightly less intuitive in nature, but are quite useful.

One of the most important Boolean algebras is that with the structure 〈{0,1};+,⋅,¯,0,1〉, that is, it consists of the power set {0,1}, has two natural binary operators (+ meaning "maximum" and ⋅ meaning "minimum"), a natural unary operator (¯ meaning "complement"; due to lack of HTML symbols I will use a single quote to denote complement), the number 0 denoting a null set or ∅, and 1 denoting the full power set. This is important because of its applications in computer science, electronics, and logic, among others. This Boolean algebra and its binary operators can best be described pictorially by the use of electrical circuits.

| |
| |
| |
| |

Damn my infernal ASCII picture skills. But anyway. The point is, | down the bottom stands for a battery or power source; o stands for a lightbulb; X stands for a switch. When X is closed, the light will come on, in other words, the circuit is fully closed. We'll call that "1". When X is open, the light will turn off. We'll call that "0". Now what happens if we add a second switch Y to the top?

| |
| |
| |
| |

It stands to reason that both switches must be closed for the light to come on.

switch X switch Y circuit
open open open
open closed open
closed open open
closed closed closed

This happens to agree exactly with the Boolean operator ⋅, or "minimum", as follows:

x y min{x,y}
0 0 0
0 1 0
1 0 0
1 1 1

In other words, x⋅y is the minimum value that x and y have. Say x had a value of 5, and y had a value of 7 (neither of which actually occur in Boolean algebras that I know of), then x⋅y = 5. This operation is a Boolean Multiplication. Boolean Addition, on the other hand, is finding the maximum value of x and y, as shown by two switches placed in a circuit parallel to each other.

| |
| |
| |
| |
| |

Logically, only one of these switches needs to be on for the circuit to work. Ergo, we can change our table from before slightly:

switch X switch Y circuit
open open open
open closed closed
closed open closed
closed closed closed

Boolean Addition is counterintuitive to regular addition: in Boolean land, 1+1=1.

x y max{x,y}
0 0 0
0 1 1
1 0 1
1 1 1

These tables are called input-output tables or, as I prefer to call them, truth tables. So why is it so important? Computers work in binary digits, in other words, 0s and 1s. Logic circuits work with "and", "or" and "not" gates (which parallel ⋅, + and ', respectively). Even digital watches run using Boolean algebra of sorts: each little liquid crystal "bar" runs off of a similar Boolean algebra.

Log in or register to write something here or to contact authors.