Boolean Algebra and Logic Gates

This article assumes the reader understands what all of the basic electronic logic gates do. If you need to learn about this there is an introduction to basic logic gates here.

The functions of logic gates can be represented using an algebra style notation and the following conventions are often used in electronics:

The inputs on the gates are usually labelled with letters and then:

• A dot is used to mean an AND gate.
• A plus symbol is used to mean an OR gate
• A bar or line means NOT (inverse) of anything underneath the bar.

Note that there is no universal agreement that these are the only symbols that are ever used in boolean algebra. The above convention often turns up in electronics but the following variations in the notation are common:

• A quote is sometimes used to mean the inverse of the preceding letter because it is easier to type on a computer than a bar
• In regular algebra the multiplication symbol is quite often missed out. Equally in boolean algebra the dot for an AND gate is also sometimes omitted i.e. A.B = C may be written as AB = C
• Mathematicians often use the ∨ symbol to mean AND and the ∧ symbol to mean OR. Sometimes the ¬ is used to mean NOT.
• Computer programming languages and calculators quite often support boolean algebra but rarely use plus to mean OR because the symbol is already taken to mean regular addition. They might use a | symbol (vertical bar) to mean OR instead but can use all kinds of other symbols. Similarly the dot in many programming languages has already been taken for some other purpose and an alternative is most usually used for AND such as an & (ampersand).

Given this notation we can now write down electronic circuits as algebra instead of drawing symbols. For example:

A.B+C.D = E

To understand what this means as a circuit we need to understand the order of precedence of the operations because how do we know whether to do the OR operation (plus) first or the AND (dot)? This usually follows similar conventions to regular algebra. The dot for AND is treated like multiplication and the plus or OR like addition. The order of operations in normal algebra would be that the multiplication comes first and addition is done second. This is the same in boolean algebra. So in the above example we have an AND gate between the A and B and another AND gate between C and D. The output of the two AND gates are connected together by an OR gate. We know this because the plus is considered only after the dots.

The above is a common approach to intepretting the symbols but beware there is no universal agreement that the order of precendence follows these conventions. Programming languages and calculators may do something entirely different.

So putting this together the above boolean algebra function is equivalent to the following circuit:

As in normal algebra you can also use brackets to make the order of precedence clearer. The following has exactly the same meaning but makes explicit the order in which operations are done:

(A.B)+(C.D) = E

So far we have considered the majority of basic gates but there is one commonly used gate missing: the XOR (exclusive OR) gate. The algebra for this gate ends up looking a little complicated when written with dot and plus. As this is cumbersome to write repeatedly, XOR is given its own special symbol which is a plus in a circle.

So now we understand how boolean algebra is used to represent logic gates, why would we want to do this? One use for algebra is it provides a short-form way to write down a circuit. We can also represent a circuit purely as text without needing to draw a diagram, which is helpful in programming languages which are normally text based and less usually work with diagrams.

One big advantage of algebra is that we can use it to think about logic circuits as if they were mathematical expressions. A common use for this is simplifying circuits. We want logic circuits to be as small as they can possibly be because the fewer logic gates we can use when designing electronics then the cheaper the device can be.

Say we are designing a burglar alarm. The alarm has two intruder sensors and a key switch that determines if the alarm is enabled. If either or both of the two sensors is activated we want the alarm to sound. However we only want it to go off if the activating key switch is turned. We might design a circuit as below. We connect the alarm activation key switch to A, the two sensors to B and C respectively and the alarm bell is connected to D.

This circuit does the job, but it may not be immediately obvious, just from looking at it, that it contains more gates than are needed. Let’s write down the equivalent algebra and see if anything comes to mind:

A.B+A.C = D

Principles that may be familiar from regular algebra also often work in boolean algebra. Using our algebra knowledge we may be able to see that there is a way to make the expression simpler by pulling out the common A term as below (this is the distributive law in algebra):

A.(B+C) = D

If we convert back from the algebra to a circuit, it contains one fewer gates and the circuit still does exactly the same. We can see that the two intruder sensors (B and C) are connected to an OR gate. So if either or both sensors goes off, there is a 1 output from the gate. However that then passes to an AND gate that is connected to the key switch (at A). So the key switch has to be enabled for the sensors to cause the bell (at D) to sound.

As we’ve used one fewer gate we have potentially reduced the cost of the circuit by a third by just using some mathematics.