Boolean algebra

By Martin McBride, 2024-01-11
Tags: boolean algebra demorgans law and gate or gate xor gate not gate
Categories: logic computer science


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 formula

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:

NOT truth table

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:

NOT logic gate

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:

OR formula

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

OR truth table

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:

AND formula

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

AND truth table

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:

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:

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:

Associative

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

Logical OR and AND operators are associative:

Associative

Distributivity

Distributivity involves 2 operands. Here are some examples:

Distributivity

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:

Distributivity

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:

Identity

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:

Identity

Annihilation

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

Annihilation

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:

Annihilation

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:

Idempotence

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:

Absorption

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:

Negation

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

Negation

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:

XOR

The operator is usually written like this:

XOR

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:

XOR

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:

XNOR

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:

XOR

Material implication operator

The material implication operator has the following truth table:

Material implication

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

Material implication

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:

Material implication

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:

OR/XOR truth table

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:

All possible cases

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



Join the GraphicMaths Newletter

Sign up using this form to receive an email when new content is added:

Popular tags

adder adjacency matrix alu and gate angle area argand diagram binary maths cartesian equation chain rule chord circle cofactor combinations complex modulus complex polygon complex power complex root cosh cosine cosine rule cpu cube decagon demorgans law derivative determinant diagonal directrix dodecagon eigenvalue eigenvector ellipse equilateral triangle eulers formula exponent exponential exterior angle first principles flip-flop focus gabriels horn gradient graph hendecagon heptagon hexagon horizontal hyperbola hyperbolic function hyperbolic functions infinity integration by parts integration by substitution interior angle inverse hyperbolic function inverse matrix irregular polygon isosceles trapezium isosceles triangle kite koch curve l system line integral locus maclaurin series major axis matrix matrix algebra mean minor axis nand gate newton raphson method nonagon nor gate normal normal distribution not gate octagon or gate parabola parallelogram parametric equation pentagon perimeter permutations polar coordinates polynomial power probability probability distribution product rule pythagoras proof quadrilateral radians radius rectangle regular polygon rhombus root set set-reset flip-flop sine sine rule sinh sloping lines solving equations solving triangles square standard curves standard deviation star polygon statistics straight line graphs surface of revolution symmetry tangent tanh transformation transformations trapezium triangle turtle graphics variance vertical volume of revolution xnor gate xor gate