CS 231 - Micro Electronics

Handout on Circuits and Logic

Objectives:

This lesson discusses representation of Boolean logic. Objectives important to this lesson:

  1. Digital values as logic symbols
  2. Logic gates
  3. Truth tables
Concepts:
Handout

This time we are working with a handout about digital logic. It begins with some familiar ideas. We can say that the binary values 1 and 0 represent True (1) and False (0). The author points out that this kind of system is very polarized: it can only represent two states, so it only represents things that are true or false. It cannot represent things that are partly true.

The text (the handout) uses the word gate on page two and afterward. A logic gate performs a process on data that it is given. The word feels odd without an introduction to this meaning, which is a hardware or software implementation of a function that typically takes two inputs and produces an output based on a formula.

The first example in the text is a NOT gate, which takes one input and produces an opposite output. In the text, the input is labeled A and the output is labeled Q. This allows us to create a table of values that A can have, and the corresponding value that Q would have.

NOT gate
A
Q
0
1
1
0

A NOT gate is simple. Whatever you give it as an input comes out the opposite as the output.

NOT gate schematic

In the image above, note the circle placed at the point of the triangle, which you will see in all gate schematics that include a NOT function.

The AND gate is described next. It takes two inputs, labeled A and B in the text, and it produces one output, labeled Q once again.

AND gate
A
B
Q
0
0
0
0
1
0
1
0
0
1
1
1

The output of an AND gate is only true when both inputs are true.


In the image above from Wikipedia, the two inputs are labeled A and B, and the output is labeled Q,

The third gate described is the OR gate, which is also called the inclusive OR gate. It takes two inputs, A and B, and produces one output, Q.  The rule for the inclusive OR gate is that the output is true if either one or both of the inputs are true.

OR gate
A
B
Q
0
0
0
0
1
1
1
0
1
1
1
1

OR gate schematic

In the image above from Wikipedia, the two inputs are labeled A and B, and the output is labeled Q,

The fourth gate discussed is called the NOR gate by the text. It could also be called a NOT OR gate, since it combines the NOT and OR functions. It takes two inputs, A and B, and produces one output, Q.  The rule for the NOR gate is that the output of an OR function is reversed.

NOR gate
A
B
Q
0
0
1
0
1
0
1
0
0
1
1
0

NOR gate from wikipedia

In the image above from Wikipedia, the two inputs are labeled A and B, and the output is labeled Q, Note that this schematic consists of a circle added to the schematic for an OR gate, making this a NOT OR gate.

The text also describes a NAND gate, which is a NOT AND gate. Its outputs are the reverse of the outputs of an AND gate.

NAND gate
A
B
Q
0
0
1
0
1
1
1
0
1
1
1
0

NAND gate schematic

In the image above from Wikipedia, the two inputs are labeled A and B, and the output is labeled Q, Note that this schematic consists of a circle added to the schematic for an AND gate, making this a NOT AND gate.

The text is a bit confusing in the next section, in which the author puts two gates together, and asks us to predict the output of various inputs. It is confusing only because the author switches to a different symbol system. In the new system, an OR gate is not pointed at the right end, it is curved. You can still tell it from the AND gate because an AND gate has a vertical line on its input side, while an OR gate has a concave curve on its input side.

In the first exercise on page 4, the author passes a 1 and a 0 as inputs to an OR gate, then passes that gate's output to a NOT gate. This is really the same as giving inputs to a NOR gate. If we pass a 1 and a 0 into an OR gate, we get a 1 as its output. If we pass a 1 into a NOT gate, we get a 0 for its output. For this problem, we have a 1 as the intermediary result, and a 0 as the final result. For assignment 1, do the four problems on page 5, as noted below.

The text moves on to discuss truth tables. We have been constructing truth tables in each discussion above, but we have not called them by that name. Essentially, you make a chart that shows all the different combinations of inputs a circuit can receive, and determine what the output would be for each one, just as we did for each of the logic gates. The more inputs a circuit has, the more lines you need in the truth table.

In the example on page six, you should see that the author has arranged three gates. An OR gate is receiving inputs A and B. A NOT gate is receiving input C. Each of those gates produces one output. Those two outputs are the inputs for an AND gate. The text tells us that we should prepare a table of the possible combinations for the three inputs, and calculate the outputs in each case. It helps at this stage to mention that we can predict how many lines will be in the table. Let's review what we have already seen.

In the table for a NOT gate, there is ONE input, which has TWO possible values. The number of lines in the table is given by the formula (Possible Values) ^ (Number of Inputs). In this case, that is 2 ^ 1, or 2 to the first power, which is 2.

In the table for an AND gate, there are TWO inputs, which have TWO possible values each. The number of lines in the table is given by the formula (Possible Values) ^ (Number of Inputs). In this case, that is 2 ^ 2, or 2 to the second power, which is 4.

It should be obvious now that in the case of the example on page six, we have THREE inputs, each having two possible values, which will give us 2 ^ 3 number of lines, which is 8. This is an application of the branch of math dealing with permutations and combinations. In permutations, the order of the values matters. In combinations, the order does not matter, like when they draw numbers for a lottery. This is an example of a combination.

In the example on page six, the author has made a column for each input and a row for each possible combination of values for those inputs. Let me show you another way. Use the digits 1 and 0, and just write binary numbers in each row, starting at 0 and counting up. The first row is 000, the second is 001, the third is 010, the fourth is 011, and so on. If you do it this way, you are unlikely to miss a combination. (And you thought there was no reason to learn binary.)

A B C
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

The author adds columns to the table and starts to be confusing. Let's add a column for the first gate, which we can call A OR B.

A B C A OR B  
0 0 0 0  
0 0 1 0  
0 1 0 1  
0 1 1 1  
1 0 0 1  
1 0 1 1  
1 1 0 1  
1 1 1 1  

This looks a little repetitive, since some of the rows are identical if we only consider the A and B inputs. Let's add a column for NOT C.

A B C A OR B NOT C
0 0 0 0 1
0 0 1 0 0
0 1 0 1 1
0 1 1 1 0
1 0 0 1 1
1 0 1 1 0
1 1 0 1 1
1 1 1 1 0

Now, we need a new column to hold the result of (A OR B) AND (NOT C). (The author has actually used the same names I used, but the format of the PDF file has made it very hard to read.)

Remember that an AND gate only produces a 1 if both of its inputs are 1s.

A B C A OR B NOT C (A OR B) AND (NOT C)
0 0 0 0 1 0
0 0 1 0 0 0
0 1 0 1 1 1
0 1 1 1 0 0
1 0 0 1 1 1
1 0 1 1 0 0
1 1 0 1 1 1
1 1 1 1 0 0

My table is a top to bottom reversal of the author's table, since she made it without using any stated logic for its construction, but the individual lines match. When you make truth tables for the exercises, please make them using binary logic to make sure you don't miss any combinations.

You should now be able to create truth tables for the first two problems on page nine. The third problem is a little harder to plot, even though it only has two inputs. Let's do a lab with them for a change. (This may not work in the classroom, so be ready for that.) Go to the Neuroproductions Logic Lab site and build each of the setups in the three problems on page nine, then turn in a truth table for each problem. Hint: use a slider switch for the input for each input port. Note that the switch is ON when it is red, and OFF when it is white. When you need to send the output of something more than one place, look in the Extras drawer and use a splitter. It takes one input and produces three outputs.