computer science

Our computers, tablets, and smartphones are made up of a collection of components. We often think about the CPU (Central Processing Unit), GPU (Graphics Processing Unit), memory, and disk storage. But what we don’t think about is what goes on within each of these components that makes them work. Distilled down to the simplest of components we would see that our larger hardware components are made up of transistors that form logical circuits. Without logical circuits there would be no flow of control inside our devices, their worth would evaporate.

Stepping back a little bit, when code is written whether it be in Java or Assembly Language programmers insert their own conditional statements to allow their applications to do smart looking procedures. While our personal computers are very complex devices we can look at some of the core logic involved in a simple way. We use logic in our day to day lives to evaluate the worth and risk to certain decisions we make. It comes down to stating preposition, evaluating what’s known as true, and then evaluating this preposition. This is where our journey begins!

When discussing formal logic we have a collection of logical operators, or gates as they’re called at the hardware level. These gates can be used to represent almost any boolean algebraic expression. The term boolean comes from the name of its inventor, George Boole, who defined boolean algebra in the 19th century. Boolean values can only have two possible values, true or false. Boolean expressions can then be thought of as typical algebraic expressions (though with different operators and laws) that evaluate to a boolean value. Here are some of the common logical gates:

• AND – Requires both operands to be true for the result to be true. If one is false then the result is also false.
• OR – One or both operands must be true for the result to be true. The result is only false if both operands are false.
• NOT – A simple inversion. Results in the opposite value.
• NAND – Not AND. An AND gate with NOT attached to it. This one is special, more on it later.
• XOR – Exclusive OR. Only operand may be true in order to get a final result of true. If both operands are true or neither operand is true then the result is false.

When looking to evaluate simple boolean expressions we can use truth tables to get a better picture of what each of the above operations means. A truth table is a table that lists the 4 possible states of two variables in question, since each variable can only have two states. This gives us the following for NOT:

OR:

Now, AND:

Finally, XOR:

Before leaving off for this month I want to talk about the special significance of NAND. NAND (NOT AND) is simply the inverse of the AND operator.

The NAND gate allows for the construction of all of the other gates mentioned previously in this article. How is this possible? It all starts with the ability to create the NOT gate. Remember that the NOT gate is a simple inversion or negation of a given value, 0 becomes 1 and 1 becomes 0. The NAND gate like others takes two inputs and has one output. This means that by joining the two inputs of a NAND gate together, you are effectively left with the expression NOT (A AND A) which when evaluated gives the same results as NOT. From here you can use this derived NOT gate to create an AND gate by just preceding the NAND gate with the derived NOT gate.

What about something more complicated such as OR? To build the OR gate out of a NAND gate we must take note of two important properties. When using an OR gate, any input that is 1 will yield a result of 1 as well. We then link this property to a similar behaviour within the NAND gate, whenever an input is 0 we have a result of 1. This means that by inverting the inputs of a NAND constructed AND gate we can create an OR gate. i.e. NOT ( NOT(A AND A) AND NOT(B AND B)).

So… that may have seemed overly complicated and you’re probably asking, why do that? It comes down to illustrating that the basic operators used in boolean logic, the core of computer programming can be defined using one construct, the NAND gate. While this may not seem important, it shows the underlying elegance of a computer system. That is, one small component can be tailored and retailored to something larger and more useful.

While a section of boolean algebra has been demonstrated this is only the very beginning on the topic. Boolean algebra and its laws can be combined with other prepositional logic laws, then we can truly represent sentence like constructs with symbols and truth tables. While interesting, this is beyond the scope of this article and is a fundamental pillar of computer science. If this introduction was interesting I suggest reading up on topics including: boolean algebra, De Morgan’s laws, and prepositional logic.