Boolean algebra

Boolean algebra is a branch of algebra that deals with logical values (true and false) rather than numerical values. It uses logical operators (such as AND, OR, NOT) rather than arithmetic operators.

In boolean algebra, true and false are often represented by 1 and 0. These are the only values that exist in Boolean algebra.

Basic boolean operators

There are 3 basic boolean operators, NOT, AND, and OR.

NOT operator

NOT is a unary operator (it operates on a single value). It inverts a logical value, swapping true and false (or 1 and 0).

There are several different ways to write the NOT operator. Here are the most common forms, we will use the first one:

NOT is roughly analogous to negation in ordinary arithmetic.

We can express the result of the operator as a truth table. This is a table that shows the output value X for each input value A:

This table is quite simple, if A is 1 then X is 0, and if A is 0 then X is 1. This functionality can also be represented as a [logic gate] like this:

OR operator

OR takes 2 input values, A and B. Its output is 1 if A or B (or both) are 1. The output is 0 if both inputs are 0.

As with NOT, there are several different ways to write the OR operator. Again here are some common forms, we will use the first one:

Here is a truth table and logic gate symbol for the OR operator:

OR is roughly analogous to addition in ordinary arithmetic. The difference is that 1 OR 1 is 1 (whereas, of course, 1 + 1 is 2 in ordinary arithmetic).

OR also behaves in the same way as the max function. The result of ORing A and B is equal to the maximum value of A or B (see the truth table above to verify this).

AND operator

AND takes 2 input values, A and B. Its output is 1 if A and B are both 1. The output is 0 if either or both inputs are 0.

There are several different ways to write the AND operator, that correspond to the different ways of writing the OR operator. Again we will use the first one:

Here is a truth table and logic gate symbol for the AND operator:

AND is exactly analogous to multiplication in ordinary arithmetic. AND also behaves in the same way as the min function. The result of ANDing A and B is equal to the minimum value of A or B.

Algebra

Now let's look at the algebra of boolean values in a bit more detail. We will look at the rules of ordinary algebra and see how they apply to boolean operators. These rules can be used to manipulate and simplify logical expressions.

Commutativity

An operator is commutative if the operands can be swapped without affecting the result. In ordinary algebra, addition and multiplication are commutative:

As shown, subtraction is not commutative in general. Of course in the special case of A and B being equal, the equality holds, but to be commutative the equation must be true for every A and B.

Logical OR and AND operators are also commutative:

Associativity

An operator is associative if the parentheses in the expression below can be moved without affecting the result. In ordinary algebra, addition and multiplication are associative:

Again, addition and multiplication are associative, but subtraction is not.

Logical OR and AND operators are associative:

Distributivity

Distributivity involves 2 operands. Here are some examples:

The first example shows that multiplication distributes across addition. This simply means that when we multiply the sum of two numbers by another number, we can expand the bracket to create a sum of 2 products.

The second example shows that multiplication also distributes across subtraction.

The third is a counter-example, showing that addition does not distribute across multiplication. If we add A to B times C, we can't expand out the bracket. We can't add A to each value and then multiply the results, that is just nonsense, it doesn't work at all.

The reason for this counter-example is that, in boolean algebra, we actually can do the equivalent thing:

AND distributes over OR, but also OR distributes over AND.

Identity element

We know that adding 0 to any number leaves that number unchanged. We also know that multiplying any number by 1 leaves that number unchanged:

We say that 0 is the identity element for addition, and 1 is the identity element for multiplication.

In boolean algebra 0 is the identity element for OR, and 1 is the identity element for AND:

Annihilation

Multiplying any (finite) number A by 0 results in 0. We say, perhaps a little dramatically, that the value A has been annihilated:

There is no annihilator for addition because there is no number that you can add to A to give a result that doesn't depend on A.

The situation is slightly different for boolean algebra:

ORing anything with 1 always gives 1, while ANDing anything with 0 always gives 0 (again, see the truth tables above to verify this).

Idempotence

Idempotence, in this context, means that A operating on itself gives A:

There is no equivalent to this in normal algebra. A added to A does not generally equal A, and similar for multiplication.

Absorption

In the following cases, the value of B does not affect the result, so we say that B has been absorbed:

De Morgan's laws

In ordinary algebra, there are special rules that apply when each operand is negated. In addition, the negative sign can be taken outside the expression. For multiplication, the 2 negatives cancel:

In boolean algebra, the equivalent rules are slightly different. They are known as De Morgan's laws:

The truth of these statements can be seen from ordinary logic. Consider an outdoor leisure activity that is open every day except Sunday. But is it also closed if it is raining. We can express this in 2 different ways:

1. It is open if it is NOT Sunday AND it is NOT raining.
2. It is NOT open if it is Sunday OR it is raining.

These 2 statements are logically equivalent. They can often be used to simplify expressions, for example in computer programming. Suppose we wanted to calculate when the activity is closed (ie NOT open). The statements above become:

1. It is closed if it is NOT (NOT Sunday AND NOT raining).
2. It is closed if it is Sunday OR it is raining.

Clearly in this case the second expression is simpler.

Secondary operators

Three other logical operators are normally considered secondary to the main operators of NOT, OR and AND. These are exclusive OR, logical equivalence, and material implication.

Exclusive OR operator

Exclusive OR (usually written as XOR) is similar to the OR operator but with a slightly different definition. The value of A XORed with B is true if A or B but not both are true. Here is the truth table:

The operator is usually written like this:

There are several ways to express this in terms of the primary logical functions. Looking at the truth table, the output is 1 if either A is 1 but B is not, or B is 1 but A is not. So one way to express XOR in terms of the primary operators is this:

Logical equivalence operator

The logical equivalence operator is true if A and B are equal, and false if they are not equal. Here is the truth table:

Looking at the truth table, it is clear that this operator is the inverse of the XOR operator. It is sometimes called the XNOR operator (exclusive NOR) for that reason.

There are 2 ways to write this operator. We can either use the equivalence symbol, or we can use the XOR symbol and invert the expression:

Material implication operator

The material implication operator has the following truth table:

Looking at the truth table, it is quite easy to see that the logical function is equivalent to:

Why does this operator have such a strange name? Material implication is a rule from propositional logic. It allows us to replace a conditional statement with a logical statement.

For example, "If it is a Sunday, then it is the weekend" is a valid conditional statement. If we are told it is a Sunday, then we can deduce that it is the weekend. In addition, if we are told that it is NOT the weekend, we can deduce that it is NOT a Sunday.

The opposites are not true, of course. If we are told it is the weekend, we don't know if it is Sunday. And if we are told it is NOT Sunday we don't know if it is the weekend.

But we can create an equivalent logical statement, "It is either NOT Sunday, or it is the weekend". One or both of those conditions must be true. If they were both false that would imply that it is Sunday but NOT the weekend, which is obviously nonsense.

We can write these equivalent statements as:

All possible cases

As we have seen from the truth tables above, a binary operator has 4 possible combinations of its inputs A and B. Each binary operator has a different set of outputs, for example an OR gate (on the left) has outputs 0, 1, 1, 1, Whereas an XOR gate (on the right) has outputs 0, 1, 1, 0:

Since there are only 16 unique states of 4 binary values, that means that there are only 16 possible binary operators. Here is a list of them all:

Remember, each line in this table represents the truth table for a distinct operator (the row is equivalent to the X column of the truth table).

Some of these are obvious: AND, OR, XOR, XNOR (aka logical equivalence), A implies B, and B implies A. The others need a bit more explanation.

The first entry is False. The operator always produces 0, regardless of the values of A and B. This isn't a particularly useful operator, but it is one of the 16 possible variants. There is also a True operator that always produces 1 regardless of A and B.

The NOT operators also require an explanation. NOT A produces the inverse of A but ignores the value of B. NOT B produces the inverse of B, but ignores the value of A. There is also an A operator that just produces the non-inverted value of A, and a B operator that does the same for B. Again these last 2 operators aren't especially useful, but they exist as part of the 16 possible operators.

Finally, for each of the main operators, there is an inverting equivalent. AND has NAND (NOT AND) that produces outputs 1, 1, 1, 0 (the inverse of the AND outputs 0, 0, 0, 1). There is also a NOR operator. Inverting values of the material implication operators NOT A implies B, and NOT B implies A.

Counting up all these possibilities gives 16 possible operators.

See also

• Logic gates
• Combining logic gates
• Simple flip-flops
• Creating an adder with logic gates
• Creating a subtractor with logic gates
• D-type flip-flops