1 - Theory of Computer Science / Logic Gates
|
|
Logic Gates
The physical circuits within computers are built using logic gated. There are 6 fundamental gates that we will look at in this section.
NOT, AND, OR, NAND, NOR, XOR
The combination of these gates create logic circuits that will allow a specific function to be carried out.
NOT, AND, OR, NAND, NOR, XOR
The combination of these gates create logic circuits that will allow a specific function to be carried out.
Logic Gates
As mentioned at the top of the page, there are 6 different logic gates that can be combined to create circuits within a computer system. These gates are - NOT, AND, OR, NAND, NOR , XOR. Each of these gates react differently to different inputs and will produce an output based on the inputs.
Each of these gates is explained below:
Each of these gates is explained below:
AND Gate
The AND gate has 2 inputs and will produce 1 output. In the example below you will see the inputs (A &B) and the output (Y)
Operation Description
The AND gate needs BOTH of its inputs to be 1 (True) for it to output 1 (True)
If either of its inputs are 0 (False) or if they are both 0, the output will be 0 (False)
The AND gate needs BOTH of its inputs to be 1 (True) for it to output 1 (True)
If either of its inputs are 0 (False) or if they are both 0, the output will be 0 (False)
Examples
Input A = 1
Input B = 1
Input B = 1
Output Y = 1
Input A = 1
Input B = 0
Input B = 0
Output Y = 0
Input A = 0
Input B = 1
Input B = 1
Output Y = 0
Input A = 0
Input B = 0
Input B = 0
Output Y = 0
Here is a useful video that explains the AND gate in context.
OR Gate
The OR gate has 2 inputs and will produce 1 output. In the example below you will see the inputs (A &B) and the output (Y)
Operation Description
The OR gate needs At least one or both of its inputs to be 1 (True) for it to output 1 (True)
If Both of its inputs are 0 (False) the output will be 0 (False). If Either of the inputs or both of them are 1 (True), the output will be 1 (True)
The OR gate needs At least one or both of its inputs to be 1 (True) for it to output 1 (True)
If Both of its inputs are 0 (False) the output will be 0 (False). If Either of the inputs or both of them are 1 (True), the output will be 1 (True)
Examples
Input A = 1
Input B = 1
Input B = 1
Output Y = 1
Input A = 1
Input B = 0
Input B = 0
Output Y = 1
Input A = 0
Input B = 1
Input B = 1
Output Y = 1
Input A = 0
Input B = 0
Input B = 0
Output Y = 0
Here is a useful video that explains the OR gate in context.
NOT Gate
The NOT gate only has 1 input and will produce 1 output. In the example below you will see one input (A) and the output (Y)
Operation Description
The NOT gate will essentially flip the input to the opposite value and then output it.
If The input is a 1 (True) the output will be 0 (False), If the input is 0 (False), the output will be 1 (True).
The NOT gate will essentially flip the input to the opposite value and then output it.
If The input is a 1 (True) the output will be 0 (False), If the input is 0 (False), the output will be 1 (True).
Examples
Input A = 1
Output Y = 0
Input A = 0
Output Y = 1
Here is a useful video that explains the NOT gate in context.
NOR Gate
The NOR gate has 2 inputs and will produce 1 output. In the example below you will see the inputs (A &B) and the output (Y). Its appearance is very similar to the OR gate, however be careful not to miss the small circle on the output line. This circle signifies that it is a NOR gate not an OR gate.
Operation Description
The NOR gate needs Neither of its inputs to be 1(True) for it to output 1 (True)
If Both of its inputs are 0 (False) the output will be 1 (False). If Either of the inputs or both of them are 1 (True), the output will be 0 (True)
The NOR gate needs Neither of its inputs to be 1(True) for it to output 1 (True)
If Both of its inputs are 0 (False) the output will be 1 (False). If Either of the inputs or both of them are 1 (True), the output will be 0 (True)
Examples
Input A = 1
Input B = 1
Input B = 1
Output Y = 0
Input A = 1
Input B = 0
Input B = 0
Output Y = 0
Input A = 0
Input B = 1
Input B = 1
Output Y = 0
Input A = 0
Input B = 0
Input B = 0
Output Y = 1
NAND Gate
The NAND gate has 2 inputs and will produce 1 output. In the example below you will see the inputs (A &B) and the output (Y). Its appearance is very similar to the AND gate, however be careful not to miss the small circle on the output line. This circle signifies that it is a NAND gate not an AND gate.
Operation Description
The NAND gate needs BOTH inputs A and B to NOT be 1(True) for it to output 1 (True)
If Both of its inputs are 1 (True) the output will be 0 (False). If Either of the inputs or both of them are 1 (True), the output will be 1 (True)
The NAND gate needs BOTH inputs A and B to NOT be 1(True) for it to output 1 (True)
If Both of its inputs are 1 (True) the output will be 0 (False). If Either of the inputs or both of them are 1 (True), the output will be 1 (True)
Examples
Input A = 1
Input B = 1
Input B = 1
Output Y = 0
Input A = 1
Input B = 0
Input B = 0
Output Y = 1
Input A = 0
Input B = 1
Input B = 1
Output Y = 1
Input A = 0
Input B = 0
Input B = 0
Output Y = 1
XOR Gate
The XOR gate has 2 inputs and will produce 1 output. In the example below you will see the inputs (A &B) and the output (Y). Its appearance is very similar to the OR gate, however be careful not to miss the extra line that runs parallel to the gates base by the inputs. This line signifies that it is an XOR gate not an OR gate.
Operation Description
The XOR gate needs BOTH inputs A and B to be different (1 & 0 OR 0 & 1) for it to output 1 (True)
If Both of its inputs are 1 (True) OR Both of the inputs are 0 (False) the output will be 0 (False).
The XOR gate needs BOTH inputs A and B to be different (1 & 0 OR 0 & 1) for it to output 1 (True)
If Both of its inputs are 1 (True) OR Both of the inputs are 0 (False) the output will be 0 (False).
Examples
Input A = 1
Input B = 1
Input B = 1
Output Y = 0
Input A = 1
Input B = 0
Input B = 0
Output Y = 1
Input A = 0
Input B = 1
Input B = 1
Output Y = 1
Input A = 0
Input B = 0
Input B = 0
Output Y = 0
Truth Tables
When explaining each of the 6 logic gates on the logic gate tab you will have noticed that a lot of diagrams were required to explain the different possibilities for the different inputs.
This is not the most efficient way of determining all of the outputs, instead we can use something called trace tables. Trace tables are used to trace / determine the output of a logic gate or circuit based on all of the possible inputs.
Usually a logic gate or circuit will have all of its inputs and outputs labelled. These input and output labels will become the table column headings. Beneath these the different combinations of 1s and 0s will be placed into the input columns, the result will be placed into the output column.
Below you will find the example truth tables for all 6 logic gates:
This is not the most efficient way of determining all of the outputs, instead we can use something called trace tables. Trace tables are used to trace / determine the output of a logic gate or circuit based on all of the possible inputs.
Usually a logic gate or circuit will have all of its inputs and outputs labelled. These input and output labels will become the table column headings. Beneath these the different combinations of 1s and 0s will be placed into the input columns, the result will be placed into the output column.
Below you will find the example truth tables for all 6 logic gates:
The 6 tables above show all of the outputs for each combination of inputs. It is important to note that as the gates are combined to create logic circuits, the truth tables will grow. The reason that they will grow is that they will have to allow for an increased number of inputs, as the number of inputs increases, the number of possible outputs will also increase.
Below is an example of this, however do not panic if this confuses you as it will be explained in more detail on the logic circuits tab.
Below is an example of this, however do not panic if this confuses you as it will be explained in more detail on the logic circuits tab.
Logic Circuits
Logic gates are rarely used on their own, they are in fact usually combined with each other to create logic circuits. This combination allows for more inputs to contribute towards the output and for the circuit to correctly control a real world situation. To truly understand logic circuits you are going to be able to do the following:
How to do each of these things is explained below.
- Produce a truth table for an existing circuit
- Draw a circuit given a described situation
How to do each of these things is explained below.
Producing a Truth Table
Here is an example of a logic circuit:
This logic circuit could be matched with the following situation:
Security Alarm System
A = Movement Sensor (Produces a 1 if movement is detected)
B = Sound Sensor (Produces a 1 if sound is detected)
C = Light Sensor (Produces a 1 while light is detected)
Y = Alarm (Produces sound when it receives a 1)
This circuit should mean that if the lights are off and either sound or movement or both are detected, the alarm will sound.
Security Alarm System
A = Movement Sensor (Produces a 1 if movement is detected)
B = Sound Sensor (Produces a 1 if sound is detected)
C = Light Sensor (Produces a 1 while light is detected)
Y = Alarm (Produces sound when it receives a 1)
This circuit should mean that if the lights are off and either sound or movement or both are detected, the alarm will sound.
When given a logic circuit like this it is likely that you will be asked to fill in a truth table to go with it.
This circuit has 3 inputs which means there are going to be 8 different possible combinations of input. To help break down the problem it helps to add some information points to your circuit. In the below diagram you can see that I have added points D and E. These extra points should be added after each gate to help keep track of the value flowing into the next gate.
This circuit has 3 inputs which means there are going to be 8 different possible combinations of input. To help break down the problem it helps to add some information points to your circuit. In the below diagram you can see that I have added points D and E. These extra points should be added after each gate to help keep track of the value flowing into the next gate.
Now that you have added your extra points, we can begin to produce our truth table. In the below example you will see that I have added columns for D and E. In the exam you will be given one large column named "Working space" where you can manually add these. The input Values A = 1, B = 0 and C = 0 have also been added so that we can work through them as an example:
A |
B |
C |
D |
E |
Y |
1 |
O |
O |
The above values represent the following situation:
Motion detector = Has detected sound
Sound detector = Has not detected sound
Light detector = Does not detect light
In theory, the lights are off and motion is detected therefor the alarm(Y) should be sent a 1 to trigger it.
We can work this out in steps.
Step one
place or visualize the correct combinations of 1 and 0 on our diagram inputs:
Motion detector = Has detected sound
Sound detector = Has not detected sound
Light detector = Does not detect light
In theory, the lights are off and motion is detected therefor the alarm(Y) should be sent a 1 to trigger it.
We can work this out in steps.
Step one
place or visualize the correct combinations of 1 and 0 on our diagram inputs:
Step two:
The next step would be to work out the values of D:
D = 1 as the OR gate will produce a 1 if either A or B is 1
E = 1 as the NOT gate will flip the input which is a 0
You can now add these values to your diagram and truth table:
The next step would be to work out the values of D:
D = 1 as the OR gate will produce a 1 if either A or B is 1
E = 1 as the NOT gate will flip the input which is a 0
You can now add these values to your diagram and truth table:
A |
B |
C |
D |
E |
Y |
1 |
O |
O |
1 |
1 |
Step 3:
We can now work through the final section of the circuit as we now know what D and E are. D and E are the inputs for the final AND gate which will produce our output Y.
as BOTH D = 1 AND E = 1 the AND gate will produce a 1 therefor Y = 1. You can now proceed to add this to your truth table or diagram as required:
We can now work through the final section of the circuit as we now know what D and E are. D and E are the inputs for the final AND gate which will produce our output Y.
as BOTH D = 1 AND E = 1 the AND gate will produce a 1 therefor Y = 1. You can now proceed to add this to your truth table or diagram as required:
A |
B |
C |
D |
E |
Y |
1 |
O |
O |
1 |
1 |
1 |
Final Steps:
The final steps are to repeat the previous steps for every combination of inputs. As already mentioned there are 3 inputs which allows for 8 possible combinations. If followed through correctly your table should look like this:
A |
B |
C |
D |
E |
Y |
1 |
O |
O |
1 |
1 |
1 |
1 |
O |
1 |
1 |
O |
O |
O |
1 |
1 |
1 |
O |
O |
O |
O |
O |
O |
1 |
O |
O |
O |
1 |
O |
O |
O |
1 |
1 |
1 |
1 |
O |
O |
1 |
1 |
O |
1 |
1 |
1 |
O |
1 |
O |
1 |
1 |
1 |
Drawing a Logic Circuit
At first drawing logic circuits can seem like a daunting task. The questions may seem confusing, however by breaking them down and working through them logically they soon become manageable.
When posed with a logic circuit question you will be given a statement such as this one:
X = 1 if ( ( A is 1 OR B is 1 ) AND ( A is 1 AND B is 1 ) ) OR ( C is NOT 1 )
When posed with a logic circuit question you will be given a statement such as this one:
X = 1 if ( ( A is 1 OR B is 1 ) AND ( A is 1 AND B is 1 ) ) OR ( C is NOT 1 )
Breaking down the statement
Step One
Determine the inputs and outputs by pulling out all of the letters involved:
X = 1 if - The part of the statement represents the output. This means that the whole circuit should end at one output named X and X will be 1 if all of the following conditions are met.
A, B & C - Looking to the right of the = we can identify three letters named A, B and C. Each of these are the inputs that will determine the final output.
Step One
Determine the inputs and outputs by pulling out all of the letters involved:
X = 1 if - The part of the statement represents the output. This means that the whole circuit should end at one output named X and X will be 1 if all of the following conditions are met.
A, B & C - Looking to the right of the = we can identify three letters named A, B and C. Each of these are the inputs that will determine the final output.
Step Two
The next step is to break down the statements, separating the bracketed sections to determine where to begin.
The next step is to break down the statements, separating the bracketed sections to determine where to begin.
Step 3
You can now begin to draw the different sections of the broken down statement.
Lets first draw the red bracketed section:
You can now begin to draw the different sections of the broken down statement.
Lets first draw the red bracketed section:
The coloured squares have been added to help you understand the link between the diagram and the circuit drawing.
Green Square = (A is 1 OR B is 1)
Blue Square = (A is 1 AND B is 1)
Red Square = The output of the green and blue squares are connected with an AND gate
Important Note! - If inputs such as A or B are needed more than once (Like in this example) you do not need multiple wires from each input, instead you can split the wire as seen above.
Green Square = (A is 1 OR B is 1)
Blue Square = (A is 1 AND B is 1)
Red Square = The output of the green and blue squares are connected with an AND gate
Important Note! - If inputs such as A or B are needed more than once (Like in this example) you do not need multiple wires from each input, instead you can split the wire as seen above.
Next we can draw the yellow side of the statement. This is a little simpler as it only has C leading into a NOT gate.