01: Logic Gates & Basic Notation

Last Updated on 9 July 2023

Signals & Variables

At it’s core – every electrical devices operates on signals – and those signals represent changing (or static) variables, such as heart rate, pressure, number of times a button’s been pressed. Signals can be cut into two classes Analog and Digital. The reality is that all signals are really analog – as the whole world is analog. But for our purposes we still divide them up.

An Analog signal is something that can continually vary. It might have a possible range of 0V to 5V, but it could be ANYWHERE in between, including 1.5992388349939381V. Analog signals can be added or subtracted from other analog signals which can be a good thing – and a bad thing. The most common issue with analog circuits is they can experience something called “noise” – inadvertent signals being added to our desired signal. Noise will make the signal harder to interpret.

Digital signals can only have two values – 0 or 1. Of course that value is physically represented by a voltage, 0 is 0V, and 1 is 5V. The actual voltage that represents a 1 may vary from system to system – but simply put – if a voltage is high – then the signal is a 1. Otherwise the signal is a 0

Here’s an example of both signals:

Essential Logic Gates

So – since this class is called DIGITAL Logic – you’d expect that we’d be talking much more about digital signals – so let’s do that. There are fundamental devices that we use to operate (perform calculations) on digital signals called Logic Gates. The most simple gate that exists is called a Buffer. It takes in a binary signal as an input – and outputs the same exact value. We can display the function of the Buffer (abbreviated as “BUF”) in 3 ways; Mathematically, as a Truth Table, and as a Logic Diagram.


Mathematical RepresentationTruth Table RepresentationLogic Diagram Representation

The mathematical representation isn’t that exciting – we just see that the input is equal to the output. The truth table shows all of the possible input values (Since there’s only 1 digital input value, and digital signals can only be 0 or 1), and the corresponding output of the device. The Logic symbol for gate is very useful when you’re designing schematics and want to represent things graphically. So right now – the buffer may look a little useless, because it doesn’t really do anything to the value of the signal. But later in this class I assure you the buffer will return to show it’s great quality.

Now let’s think of another single input gate. There’s only one other way we could organize the truth table: for each input, let the output be the opposite value. The gate we end up with is called an Inverter which is sometimes called a NOT Gate:

NOT Gate:

Mathematical RepresentationTruth Table RepresentationLogic Diagram Representation
A’A Output 0 1 1 0

In this class the not function will most often shown mathematically as ” ‘ “, mainly because it’s easy to type quickly. Sometimes, however, you may see it shown as a horizontal bar over what ever is being inverted: LaTeX: \bar{A}. And when we start talking about Verilog – you’ll see it as ~A. The last thing I want to point out is the symbol for the NOT – it looks like a buffer with a circle on the end. The NOT symbol can really be boiled down to just the circle – and we’ll see that later in this lecture.

So, those were all the possible gates we could have that only accept one input. Things get much more exciting when we start adding more and more inputs. The first 2-input gate we’ll look at is the AND Gate. An AND gate’s output is a 1 if and only if all of it’s inputs are 1:

AND Gate:

Mathematical RepresentationTruth Table RepresentationLogic Diagram Representation
ABA B Output 0 0 0 0 1 0 1 0 0 1 1 1

The AND gate in a lot of ways is like multiplication – just look at the truth table and you’ll see that. So because of that, the AND function is displayed mathematically using the same symbol as multiplication (namely, the variables just pushed together with no symbol). Sometimes you may see the multiplication symbol: LaTeX: A\cdot B, and in Verilog, you’ll see it is A & B. The last thing to note is the order of the inputs in the truth table: 00, 01, 10, 11. That order is significant, as it’s how we count in Binary. For now, just accept this is the order WE WILL ALWAYS USE FOR TRUTH TABLES, and it will be explored much more in depth later.

And the last “essential gate” I want to look at is the OR Gate. The OR gate’s rule is: If ANY of the inputs are 1, then the output will be 1.

OR Gate:

Mathematical RepresentationTruth Table RepresentationLogic Diagram Representation
A+BA B Output 0 0 0 0 1 1 1 0 1 1 1 1

The OR gate is MOSTLY comparable to the addition function from regular mathematics. If you look at the final row in the truth table that kind of breaks the trend, but for the most part it’s addition – so therefore we use the “+” symbol to indicate the OR function. In Verilog you’ll see it as A|B.

ALRIGHT! Let’s see how these gates can be used for a very simple design:

The Rest of the Gates

Before we talk about new gates, let’s explore what happens when these gates get bigger (more than 2 inputs):


Now. What if we connected a NOT gate to the end of an AND Gate like this:

Well – this is kind of like a “2-step” gate, first we AND A and B, then we invert that output. This is a NOT AND gate which is always abbreviated as NAND. It’s rule is it outputs the exact opposite of what an AND gate would output.

NAND Gate:

Mathematical RepresentationTruth Table RepresentationLogic Diagram Representation
(AB)’A B Output 0 0 1 0 1 1 1 0 1 1 1 0

So mathematically, we see that inside of some parentheses (indicating we do this function first) we AND A and B, and THEN we apply the inverter. Not surprisingly, the we see that the output column of the truth table is the exact opposite of the AND gate. And for the symbol, we basically compressed the previous NOT AND circuit into one symbol. Again – the bubble indicates an inverter.

At this point you’ve probably noticed that we’ve set out on a quest to find every possible (non-trivial) truth table. So let’s carry on by putting a NOT on the end of an OR to create a NOR Gate. The NOR Gate’s rule is it’s output is the exact opposite of the OR gate.

NOR Gate:

Mathematical RepresentationTruth Table RepresentationLogic Diagram Representation
(A+B)’A B Output 0 0 1 0 1 0 1 0 0 1 1 0

Hopefully you’re starting to get the flow here. Mathematically, we have A OR B, an then the result of that is inverted. The symbol is just an OR Gate with a NOT bubble on the end.

Alright – there’s only one more set of gates left. They’re like the OR gate’s eccentric cousin. They think they’re so special that they demand you call them “exclusive”. Their symbol even has a fancy crown. The gate I am alluding to is the exclusive OR gate- appreciated to XOR Gate. Their rule is they only output a 1 if ONLY 1 INPUT is a 1. If two inputs are 1 – then it’s a 0.

XOR Gate:

Mathematical RepresentationTruth Table RepresentationLogic Diagram Representation
A BA B Output 0 0 0 0 1 1 1 0 1 1 1 0

Man the XOR gate is a little pretentious. Even it’s mathematical symbol is distinguished by a special little circle around the plus sign. As an interesting side note, the XOR gate can also be described mathematically using the expression (A’B)+(AB’). The symbol looks like an OR gate with a special distinguished crown. All joking aside – the XOR gate can be very useful in some cases, especially when you want to find out if you have an odd number of “1” inputs.

ALRIGHT ALMOST DONE! The last little thing we can do is put an inverter on the XOR gate, making an XNOR gate.

XNOR Gate:

Mathematical RepresentationTruth Table RepresentationLogic Diagram Representation
(A B)’A B Output 0 0 1 0 1 0 1 0 0 1 1 1

More Complex Boolean Functions

So as we saw with the NAND function – we can start linking these smaller functions together to create more complex devices. Hook enough of them together and you get a processor. That’s right – all you need are these fundamental devices and you can make the backbone of ANY digital device. Pretty amazing huh?

Anyways – if we’re going to start linking more of these together, we’ll also want to examine them mathematically – and it’s important to establish our order of operations (What we calculate first):

  1. Parantheses
  2. Inversion
  3. AND
  4. OR

When we’re looking at a logic diagram, the order is implied based on the way the circuit is wired. For example in the diagram below – we can see that we’d have to compute X before we could compute Y. (If you’re reviewing this lecture after you’ve progressed further in the class – you’ll likely realize that this circuit could be simplified)

Let’s look at an example of finding the logic diagram given a mathematical expression


And finally – let’s find the truth table for a complex logic diagram.

Print Friendly, PDF & Email