Algebraic Tron

This article is part of a series, access the series index.

This article deals with logic gates, and in doing so also boolean algebra.  Logic gates always remind me of the original movie Tron (I have not seen the new Tron, maybe I should?) when they travel through the various gateways and he has his little bit that utters “Yes” and “No” in a robotic voice.

George Boole and His Algebra

First a little bit of background.  A long time ago this very smart guy named George Boole wrote a book titled “An Investigation of the Law of Thought”.  It was quite the investigation, but I only know by hearsay, as I have not actually read it.  In this book, written in 1854 is you can believe it, he lays out the principles of a different type of algebra.  This algebra’s variables are constrained to certain values, its operations are of a different nature, and consequently the properties or laws of those operations.  One application of boolean algebra is in the world of digital logic, and computer programming, which is why we’re talking about it today.

In boolean algebra, variables can only have two states, typically denoted as one or zero.  I bet this sounds really familiar already from the article on binary I wrote earlier.  If it doesn’t, go read that article so that it does.  We’ll deal with only operating on singular variables (only one and zero) for now and relate them to “logic gates”.

The basic operations of boolean algebra are known as “conjunction”, “disjunction” and “negation”.  These are denoted as x∧y, x∨y, and ¬x respectively.  These operations are also related to normal algebraic operations which will become clearer as the article goes on.  These operations are multiplication (xy) for conjunction, addition (x+y) for disjunction, and negation (-x) for negation.  I don’t find it terribly useful when thinking of computers to really pay attention to the relationship to normal algebra but for you math buffs I thought you’d want to know.  I’ve included a diagram to help you out:

operations

Conjunction works with binary like multiplication: if either x or y is zero the result is zero.  1*0 = 0, 0*1 = 0, but 1*1 = 1.

Disjunction works with binary like addition with one exception if both values are 1 like so:  0 + 0 = 1, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 1.

In boolean algebra, a ‘negative 1′ so to speak is zero, and a negative zero is a one.  Thus negation just flips the value:  -1 = 0, and -0 = 1.

If that confuses you in any way you can also use what are known as truth tables.  A truth table lists all the possible inputs and shows the results of the operation.

truth

Derivations of Thought

By using “composition” we can create further operations of higher complexity.  There are several that we can create however only a couple are of really any popular use as far as I see it.  As well, they’re the only ones worth mention in terms of logic gates.  The first is “exclusive or”, and the other is “equivalence”.  Their composition is as follows respectively: x⊕y = (x∨y)∧¬(x∧y), and x=y = ¬(x⊕y).

Pretty heady stuff huh?  We’re entering into territory where I start to zone out (and thus why I have problems with higher math).  I hope those didn’t go right over your head, you can try to work them out.  It’s not absolutely necessary, however.  Here are truth tables for the operations:

composition

Now, there are all sorts of laws, completeness, principles, diagrams, subsets, vectors, prototypes, abstractions, representations, axioms, and applications, but that’s all you need to know to really understand logic gates (and the movie Tron).

Gateways of Logic

Now that you know what a logical operation is, and what the basic ones are (and a few advanced ones) you’ll better understand that a logic gate is (usually) a piece of circuitry that implements a logical operation.  They physically operate on electrical charges, power being one, and very low power being zero like I mentioned in my binary article.  These gates are usually made using diodes or transistors, but anything that can perform the logic will work even mechanical devices or molecules like in nanotechnology.

Exactly how logic gates are implemented in hardware might best be saved for another article (if ever), but I think it’s important that a programmer has the background knowledge of what they look like in a diagram, how they are put together, and how they work.  There are places where knowing boolean logic is helpful, such as in “if statements”, and you can diagram it out using logic gates (which I think is the easiest).

Just so you know, with 2 variables as we’ve been working with so far there is a total of 16 possible boolean algebraic functions.  I’ll leave it as an exercise to the reader to research or figure out all the possible combinations of functions and what they mean.  I’m here to simply talk about each logic gate and its relationships.  First, there is the NAND gate.

The NAND gate is “not and” or commonly “not both”.  It is often written as a vertical bar: |.  Looks like the word “I” doesn’t it?  If you want to sound like an L33T hacker call it the “Sheffer stroke”.  Like NOR (coming up) a bunch of strung up NANDs can be used by itself to do everything.  Literally.  All three basic functions can be constructed using only NAND gates.  So it’s a very important gate.  I’ll leave it to the reader to determine why this is so.  The NAND gate is basically a negation of the AND operation… letting everything through except when both inputs are charged.

nand

Another gate with similar properties is the NOR gate.  This gate does somewhat the opposite of NAND, which is why it can also serve as the basis for constructing the equivalence of many other gates when strung together in various combinations.  In it, all charges are stopped unless there are no charges.

nor

There is the XOR gate, which duplicates the operation we discussed above:

xor

There is the equivalency gate which is just like when we test for equivalencies between two variables in programming using the usual “==” operator:

xnor

Then there’re the basic gates doing the operations we’ve covered:

and_or_not

So what can you do with all of these gates?  Well, you can string them together to perform different operations, even other operations like we’ve been discussing.  I’ll show two example diagrams of how someone might do this.

nand_makes_nor

nor_makes_nand

Well, there you have it, the fundamentals of logic gates and boolean algebra.  Like I mentioned above, there is SOOOO much more to this stuff that’s highly technical and mathematical that I just thought was out of the scope of this article.  Logic gates can be used for data storage, there are even three state logic gates used in data buses of CPU’s.  Logic gates are primarily used in microchips to construct processing units (remember how a computer works?)  Perhaps in the future I’ll cover more of these other topics but as for now, I think this article is enough to get you started.

I learned about boolean logic and how to use it in rudimentary ways by accident.  From my first “if statement” on my TRS-80 Color Computer II 16k I was practicing boolean logic and didn’t even know it.  So when I learned about logic gates they were very easy to grasp.  I hope I helped you grasp logic gates as well.

If you appreciate my tutorials please help support me through my Patreon.

photo credit: Tandy TRS 80 via photopin (license)

Liked it? Take a second to support kadar on Patreon!

kadar

I'm just a wunk, trying to enjoy life. I am a cofounder of http//originalpursuitssoc.com/ and I like computers, code, creativity, and friends.

You may also like...

1 Response

Leave a Reply

%d bloggers like this: