Logic Gates
Logic gates are devices that implement Boolean functions, i.e. it does a logic operation on one or more bits of input and gives a bit as an output. They are the basic building blocks of any digital system. It is an electronic circuit having one or more inputs and only one output. The relationship between the input and output is based on a certain logic. Hence logic gates are named as AND gate, OR gate, NOT gate, etc.
Boolean functions are of interest to logicians, philosophers, computer scientists, programmers, electronic engineers and linguists alike. They are the basis of today's computing technology.
Contents
Truth Tables
Truth tables are basically a way to define Boolean functions exhaustively. They consist of rows of all possible permutations of input bits along with their corresponding values of functions.
How many \(n\)-ary boolean functions exist?
The size of the domain of an \(n\)-ary Boolean function would be \(2^n\).
This means that we would have \(2^n\) rows in our truth tables.Since there are 2 ways to fill in the outputs of each of the \(2^n\) possible inputs, we have a total of \(2^{2^n}\) possible functions. \(_\square\)
Primary Logic Gates
There are three primary logic gates: AND, OR and NOT. All other logic gates could be represented as a combination of these.
\[\]
AND
Truth Table
| a | b | a AND b |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Symbol
\[\] \[\]
OR
Truth Table
| a | b | a OR b |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Symbol
\[\] \[\]
NOT
Truth Table
| a | NOT a |
| 0 | 1 |
| 1 | 0 |
Symbol
\[\]
Universal Logic Gates
Though all logic gates can be designed by primary logic gates, but NAND or NOR alone can be implemented to design all primary logic gates. Thus, these are called universal logic gates.
\[\] NAND
A NAND B = NOT (A AND B)
Truth Table
| a | b | a NAND b |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Symbol
\[\] \[\] NOR
A NOR B = NOT (A OR B)
Truth Table
| a | b | a NOR b |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
Symbol
\[\]
Derived Logic Gates
Derived logic gates are formed from the combination of two or more of the primary logic gates. We'll discuss some important derived logic gates here.
\[\] XOR
A XOR B = (A OR B) AND (NOT (A AND B))
Intutively, XOR is exclusive OR, i.e, A OR B but not both.
Truth Table
| a | b | a XOR b |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Symbol
\[\] \[\] XNOR
A XNOR B = NOT (A XOR B) = (A AND B) OR (NOT (A) AND NOT (B))
Truth Table
| a | b | a XNOR b |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Symbol
\[\]
Implementation in Digital Circuits
Logic gates are built using different combinations of transistors, which are basically electrically controlled switches. There are two types of transistors: PNP and NPN. We will be using the latter in the following examples:
An NPN transistor allows a main current to flow from its input - called 'collector' - to its output - called 'emitter' - when a small current is applied to the 'base'. This corresponds to a closed switch, and the logical state '1'. When no current is applied to the base, the transistor does not allow current to flow from the collector to the emitter anymore. This corresponds to an open switch, and the logical state '0'.
\[\]
AND
When a current is applied to the base of both transistors (i.e. when \(a = 1\) \(AND\) \(b = 1\)), the main current is free to flow from the top collector of transistor 'a' all the way to the bottom emitter of transistor 'b'. If only one of the two bases is 'on', the main current will be blocked when reaching the transistor in the 'off' state, and will not be able to flow. Obviously, if both transistors are 'off', no current will be flowing either.
\[\]
OR
When a small current is applied to either of the two transistors - or, even better, both of them - the main current is free to flow from the top to the bottom of the circuit. Only when both transistors are in the 'off' state, no current will be flowing.
\[\]
NOT
This particular gate can be done even with one single transistor. When no current is applied to the base of the transmitter (i.e. \(a = 0\)), the main current won't be able to flow through the transistor, and its only way out will be to go through the wire \( \overline{a}\); thus \( \overline{a} = 1\). On the other hand, when a small current is applied to the base of the transistor (\(a = 1)\), all the main current will flow through it, and no current will go to wire \( \overline{a}\); thus \( \overline{a} = 0\).
Note: While the AND and the OR gate shown are pretty straightforward when building an actual circuit, a NOT gate requires some additional components to ensure proper working conditions. Nonetheless, the basic concept behind it stays the same.
Additional Problems
The combination of various logic gates are really important in digital electronics as they are the basis of all arithmetic operations in digital computers.
Logic gates can be used in many fun questions on Brilliant! See one for yourself:
Which of the following functions is implemented by the above schematic?