Digital computers work with binary information, where data and control signals are represented using two logical states, commonly written as 0 and 1. At the hardware level, these binary values are processed by electronic circuits. Logic gates are the fundamental elements used to perform these operations.
A logic gate receives one or more binary inputs and generates a binary output according to a defined logical relationship. By connecting gates together, designers can create larger digital circuits such as adders, multiplexers, comparators, decoders, registers, memory circuits, and processor components.
The behavior of a logic gate can be described using a Boolean expression and a truth table. The Boolean expression gives the mathematical representation of the operation, while the truth table lists the output for every possible combination of inputs.
A logic gate is a digital electronic circuit that performs a logical operation on binary input signals and produces a binary output. In a simplified digital model, the two states are represented by 0 and 1.
For example, an AND gate produces 1 only when all of its inputs are 1. An OR gate produces 1 when at least one input is 1. A NOT gate reverses the input value.
The actual hardware implementation of a gate depends on the electronic technology being used. Modern digital systems commonly implement logic using transistor-based circuits. At the logical level, however, engineers can reason about the circuit using Boolean operations without dealing with every transistor individually.
A single logic gate performs a very small operation, but millions or billions of such operations can be combined to implement complex digital hardware. The important idea is that higher-level computer hardware is constructed from simpler logical operations.
For example, a processor needs circuits for arithmetic, data selection, comparison, storage, and control. These circuits are themselves constructed from combinations of basic logical elements.
Some common hardware applications include:
An AND gate implements the Boolean AND operation. Its output becomes 1 only when every input connected to the gate is 1. If even one input is 0, the output becomes 0.
For two inputs A and B, the Boolean expression is:
Y = A · B
The dot represents the logical AND operation.
| Input A | Input B | Output Y = A · B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Think of an AND gate as a condition in which all required conditions must be satisfied. If three conditions are connected through AND logic, the final result becomes 1 only when all three conditions are 1.
AND gates are therefore useful in control circuits where several conditions must be satisfied before an operation is allowed.
An OR gate performs the Boolean OR operation. Its output is 1 when at least one input is 1. The output is 0 only when all inputs are 0.
For two inputs A and B:
Y = A + B
Here, the plus sign represents logical OR rather than ordinary arithmetic addition.
| Input A | Input B | Output Y = A + B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Logical OR should not be confused with ordinary arithmetic addition. When A = 1 and B = 1, the OR operation produces 1, whereas arithmetic addition gives 2.
A NOT gate performs inversion. Unlike AND and OR gates, which normally receive two or more inputs, a basic NOT gate has a single input and a single output.
If the input is A, the output is:
Y = A̅
The bar over A means NOT A.
| Input A | Output Y = A̅ |
|---|---|
| 0 | 1 |
| 1 | 0 |
The NOT operation is fundamental because digital circuits frequently need both a signal and its complement. In circuit diagrams, an inverter is commonly represented by a triangular symbol followed by a small circle at the output.
A NAND gate is obtained by applying NOT to the result of an AND operation. Therefore, its output is the complement of AND.
For two inputs:
Y = (A · B)̅
The output is 0 only when both inputs are 1. For all other input combinations, the output is 1.
| Input A | Input B | Output Y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
The small inversion circle commonly shown at the output of a NAND gate indicates that the AND result is complemented.
A NOR gate is the inverted form of an OR gate. It first performs the OR operation and then complements the result.
For two inputs:
Y = (A + B)̅
A NOR gate produces 1 only when both inputs are 0.
| Input A | Input B | Output Y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
NAND and NOR are particularly important in digital electronics because both are universal gates.
XOR stands for Exclusive OR. Unlike a normal OR gate, XOR produces 1 only when the inputs are different.
For two inputs A and B:
Y = A ⊕ B
The same operation can also be expressed using AND, OR and NOT operations:
A ⊕ B = A̅B + AB̅
| Input A | Input B | Output Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
XOR is especially important in arithmetic circuits. When two single-bit binary numbers are added without considering the carry, the sum bit is equivalent to XOR.
For example:
A = 1 B = 0 1 XOR 0 = 1
For 1 + 1, XOR produces a sum bit of 0. The carry generated by this addition is handled separately by the carry-producing part of the adder circuit.
XNOR stands for Exclusive NOR. It is the complement of XOR. Therefore, its output is 1 when the two inputs are equal.
For two inputs:
Y = (A ⊕ B)̅
| Input A | Input B | Output Y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Because XNOR produces 1 when its inputs are equal, it is useful in digital comparison circuits. For example, an equality comparator can use XNOR operations to compare corresponding bits of two binary numbers.
| Gate | Boolean Expression | Output is 1 When |
|---|---|---|
| AND | A · B | Both inputs are 1 |
| OR | A + B | At least one input is 1 |
| NOT | A̅ | Input is 0 |
| NAND | (A · B)̅ | At least one input is 0 |
| NOR | (A + B)̅ | Both inputs are 0 |
| XOR | A ⊕ B | Inputs are different |
| XNOR | (A ⊕ B)̅ | Inputs are equal |
XOR and OR are frequently confused because their outputs are identical for three of the four possible input combinations. Their difference appears when both inputs are 1.
| A | B | OR | XOR |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 |
The easiest way to remember the distinction is: OR means at least one, while XOR means exactly one for the common two-input case.
XOR and XNOR have opposite outputs for every input combination. XOR indicates that the inputs are different, whereas XNOR indicates that the inputs are equal.
| Inputs | XOR | XNOR |
|---|---|---|
| 0, 0 | 0 | 1 |
| 0, 1 | 1 | 0 |
| 1, 0 | 1 | 0 |
| 1, 1 | 0 | 1 |
A universal gate is a logic gate that can be used by itself to construct the basic Boolean operations. NAND and NOR are universal gates because suitable combinations of either gate can implement NOT, AND and OR operations. Once these operations can be created, more complex Boolean functions can also be constructed.
Connect both inputs of a NAND gate to the same input A.
Y = A NAND A Y = (A · A)̅ Since A · A = A, Y = A̅
Therefore, a NAND gate with its two inputs connected together behaves as a NOT gate.
The output of the first NAND gate is inverted using a second NAND gate whose inputs are connected together.
X = A NAND B Y = X NAND X Therefore: Y = A · B
The first NAND performs the AND operation with inversion, and the second NAND removes that inversion.
An OR operation can also be constructed from NAND gates by first inverting both inputs and then applying NAND.
A NAND A = A̅ B NAND B = B̅ A̅ NAND B̅ = A + B
This demonstrates how NAND gates can be combined to reproduce other fundamental Boolean operations.
NOR has the same universal property. NOT, OR and AND can all be constructed using only NOR gates.
A NOR A = (A + A)̅ = A̅
The output of a NOR gate can be inverted using another NOR gate whose inputs are connected to the same intermediate signal.
X = A NOR B Y = X NOR X Therefore: Y = A + B
The ability to create fundamental Boolean operations from only one type of gate makes universal gates important in digital circuit design and logic implementation.
Logic gates are rarely used in isolation in a complete computer system. Instead, several gates are interconnected to form functional digital circuits.
A half adder adds two one-bit binary numbers. It produces two outputs: a Sum and a Carry.
This simple example shows why different gates can work together to perform an arithmetic operation.
A comparator determines whether binary values are equal or different. XNOR gates are useful for comparing corresponding bits because an XNOR output becomes 1 when the two compared bits are equal.
AND, OR and NOT operations can be combined to create conditions used by control logic. These circuits help determine whether a particular operation should be enabled based on several input signals.
Multiplexers use combinations of AND, OR and NOT logic to select one input from several available inputs and forward the selected value to an output.
Boolean algebra provides the mathematical foundation for logic gates. Each basic Boolean operation corresponds to a logical hardware operation.
| Boolean Operation | Common Gate | Meaning |
|---|---|---|
| AND | AND | All required conditions must be true |
| OR | OR | At least one condition must be true |
| NOT | NOT | Reverses the logical state |
| NOT AND | NAND | Complement of AND |
| NOT OR | NOR | Complement of OR |
| Exclusive OR | XOR | Produces 1 when inputs differ |
| Exclusive NOR | XNOR | Produces 1 when inputs are equal |
This relationship between Boolean algebra and physical digital circuits is one of the central ideas in Computer Organization. Boolean expressions can be used to describe a circuit before the circuit is implemented electronically.
When a circuit contains several interconnected gates, the output can be determined by evaluating each stage in sequence.
A useful approach is:
For example, consider a circuit in which A and B first pass through an AND gate and the result is then inverted:
First stage: X = A · B Second stage: Y = X̅ Therefore: Y = (A · B)̅
The complete circuit is therefore equivalent to a NAND operation.
A logic gate is a digital circuit that accepts one or more binary inputs and produces a binary output according to a defined logical operation.
AND, OR and NOT are commonly considered the fundamental basic logic gates. NAND, NOR, XOR and XNOR are additional important gates used in digital circuit design.
A universal gate is a gate from which other fundamental Boolean operations can be constructed. NAND and NOR are universal gates.
NAND is called universal because NOT, AND and OR operations can be implemented using only NAND gates. More complex Boolean circuits can then be constructed from these operations.
OR produces 1 when at least one input is 1, including the case where both inputs are 1. XOR produces 1 only when the two inputs are different.
XNOR produces 1 when its inputs are equal. This makes it useful in digital equality comparison circuits.
Logic gates are used as building blocks for arithmetic circuits, control units, multiplexers, comparators, registers, memory circuits and many other digital components.
For two one-bit inputs, XOR produces the correct sum bit without considering the carry. An additional circuit is used to generate the carry.
Logic gates provide the basic logical building blocks from which digital computer hardware is constructed. Each gate follows a specific rule for converting binary inputs into an output, and its behavior can be represented using Boolean expressions and truth tables.
AND, OR and NOT form the fundamental Boolean operations, while NAND and NOR provide inverted versions of AND and OR. XOR and XNOR are particularly useful when a circuit needs to detect differences or equality between binary values.
The real importance of logic gates becomes clear when they are combined. Groups of gates can implement adders, comparators, multiplexers, control circuits and other digital components that eventually form larger parts of a computer such as the ALU, processor datapath and control logic.
After understanding logic gates, the next step is to study registers, where digital circuits are used to store binary information temporarily inside the processor.