Thursday, 2 August 2018

Boolean Algebra - The Maths of Computers

I have this theory that most of the inventions that have changed the world in which we live were actually created by a bunch of bored aristocrats who had nothing better to do with their time. Well, that's probably not a bad thing because, well, engaging in scientific and mathematical research is probably much better, and much more stimulating, than going to endless parties, invading foreign countries, and crushing peasant revolts.

George BooleSo, as we looked at before, computers think entirely in terms of 0s and 1s, and this the question arose as to how to address this mathematically. Well, it turned out that some guy named George Boole had already come up with something. Well, that whole thing about mathematicians being aristocrats didn't quite fit with Mr Boole considering that he was the son of a shoe-maker and a primary school teacher, but at the opening of the 19th Century, this did tend to put him in the middle class. However, he did eventually land up with a professorship at a college.

Anyway, enough of Mr Boole, and more on what he was actually on about, and how it applies to computer science. Well, it really comes down to the concept of truth-tables and logic. The thing is that every element, or atom if you will, has a truth value, and when you combine atoms in various ways they will produce various answers. Okay, the original algebra dealt in values of T (true) and F (false), but that was easily converted over to computer science to represent 0 and 1.

So, we have three types of expressions, or as they are termed in computer science, And, Or, and Not. Now, each of these expressions can be combined to produce Nand (And and Not), Nor (Or and Not) and Xor (or exclusive or, which then goes on to produce an Xnor, or not exclusive or). Now, each of these gates has a symbol as follows (and is expressed by the table below - the original can be found here).

Now, each of these gates are represented by a symbol, with '.' being AND, '+' being OR, and the '/' as being NOT (though it can also be represented by a line over the letter). Oh, and XOR is represented with a '+' surrounded by a circle '⊕'. This brings us to an important point, and that as some of the laws that are relevant to this form of algebra, such as the commutative law, and de Morgan's law. Now, de Morgan's law is as follows:

/A+/B = /(A.B) or /(A+B) = /A./B

and then we have the associative law, such as 

(A+B)+C = A + (B + C)

The Truth Tables

The best way to proceed here is through the use of truth tables. Basically, these tables are used to work what comes out through the gates if the certain values are fed into the gates.

Now, this might look a little odd, but they come into play when a circuit, or a boolean Algebraic problem is put before us, such as having to prove deMorgan's Law, which we will proceed to do now:

Now, as you can see, when two inputs pass through the AND gate, the output is only live (or 1), when both inputs are one. With the OR gate, the output is 1 when at least one of the inputs is 1, and the XOR gate is only 1 when only one of the inputs is 1. As for the NOT gate, well, as you can see, it inverts the input, so 0 becomes 1 and 1 becomes 0.

Now, I mentioned that you don't actually need an XOR gate because it is actually just a combination of AND, OR, and NOT gates. In fact, the NAND and NOR gates are just a combination of AND and OR gates. As an interesting side note, when we use 'or' in the English language it is in the form of an exclusive or, namely either one, the other, but certainly not both. In fact, you can create the XOR gate using either only NAND and NOR gates, as you can see with the image below (which was lifted from Wikipedia).

Now, there is a nice little program called Logism which allows you to actually construct these circuits, and to also play around with them, and I have used it to create the actual circuits which we will look at. So, what I have done is created the following circuits, and what we are going to do is to turn this diagram into a Boolean construction, and then create a truth table from it.

So, let us start off with the first gate we encounter - it is a NOT gate, and it has come from input C, so we start of with /C.

Next, we have an AND gate and the NOT gate feeds into the AND gate, so we have /C.B. 

Finally, this AND gate feeds into an OR gate, so the circuit feeds into the OR gate, so the final solution will be (/C.B)+A. 

Now there is an order of operations that is implicit with Boolean algebra, however I do prefer to use brackets to separate out components that are feeding into other components.

What we now need to do is to construct the truth table so we can see how this works, and like I did above, we break it down into components as such:

You will notice that the more inputs that we have the longer the table becomes, namely because we have to cover each of the combinations of 0s and 1s. Anyhow, I have calculated the /C, and then knowing the values of /C and AND it with B, and once we have the values of /C.B we then OR it with A, so we have the outputs for (/C.B)+A

Now, let us see if we can go the other way using the formula (A+B).(A+C).

First: we identify the inputs, which in this case are A, B, and C.

Second: We draw one NOT gate for each variable that has been noted (or rather it's complement, which means opposite). In this case this doesn't seem to happen.

Third: We start with the innermost parentheses and draw the gate in that respect, which we will do here for A+B and A+C:

Finally: We combined the innermost parentheses with the next innermost until the diagram has been completed:

A Few More Laws:

No, let us go through a few more laws to help us understand these constructions. First of all we have the identity law, which states:

x1 = x   x+0 = x

Then there is the Null, or Dominance Law:

x0 = 0   x+1 = 1

However, instead of going through each of them individually, it I'll simply refer to a table that I found here.


Some Diagrams

Now, these diagrams actually represent what is going on inside of an integrated circuit, much like the CPU in your computer (though the modern CPU is so complicated that I'm not even going to try to work it out). These circuits really come down to the interaction of switches turning on and off. So, remember how we talked about adding numbers, well, here is a circuit called a Half Adder, which adds two numbers and if there is a carry, then it sends off the carry. As you can see, it involves two gates, a XOR gate and an AND gate. So, if two 1s come into the circuit, the XOR produces a 0 and the carry produces a 1, which if only a single 1 comes in then the XOR produces a 1, and the AND produces a 0. You can probably guess what happens when two 0s come in.

Now, you could then start 'daisy chaining' these half-adders, as I have done here:

But it doesn't quite work like that because we aren't actually accepting a carry in, nor are we adding two numbers together. So, instead, a full adder needs to take into account that there might be a carry in, and once we have that aspect, we can then start 'daisy chaining' the adders:

I won't go into details on how this works, but see if you can work it our yourself.

Remembering Things

Now, while computer memory doesn't come until a lot later, I want to finish off by showing you a way that a computer remembers things. The following circuit is called a 'Flip-Flop'.

Now, the way this works is that the system will remember its state if no power is sent through. Now Logism doesn't seem to work all that well with this, but it starts off with no power, but once you put power in, it will remember a state until a further instruction is put through. These circuits are still used today, particularly in a section of the CPU known as the 'Cache'. However, as memory it is very expensive, and very power hungry, so it doesn't form a part of the computer's main memory.

Creative Commons Licence

Boolean Algebra - The Maths of Computers by David Sarkies is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. This license only applies to the text and any image that is within the public domain. Any images or videos that are the subject of copyright are not covered by this license. Use of these images are for illustrative purposes only are are not intended to assert ownership. If you wish to use this work commercially please feel free to contact me

No comments:

Post a Comment