Logic Gates and Boolean Algebra
COS2621 - Computer Organisation · Digital Logic Design
Logic Gates and Boolean Algebra
Logic gates are the basic building blocks of digital circuits. They perform logical operations on one or more binary inputs to produce a single binary output. Boolean algebra is the mathematical framework used to describe these operations.
Logic Gates
There are several types of logic gates, each corresponding to a specific logical operation. The most common gates are AND, OR, NOT, NAND, NOR, XOR, and XNOR.
AND Gate
The AND gate outputs true (1) only when all its inputs are true. The truth table for an AND gate with two inputs A and B is as follows:
| A | B | Output (A AND B) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
OR Gate
The OR gate outputs true (1) if at least one of its inputs is true. The truth table for an OR gate with two inputs A and B is:
| A | B | Output (A OR B) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
NOT Gate
The NOT gate, also known as an inverter, outputs the opposite value of its input. The truth table for a NOT gate with input A is:
| A | Output (NOT A) |
|---|---|
| 0 | 1 |
| 1 | 0 |
NAND Gate
The NAND gate is the inverse of the AND gate. It outputs false (0) only when all its inputs are true. Its truth table is:
| A | B | Output (A NAND B) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NOR Gate
The NOR gate is the inverse of the OR gate. It outputs true (1) only when all its inputs are false. Its truth table is:
| A | B | Output (A NOR B) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
XOR Gate
The XOR (exclusive OR) gate outputs true (1) if exactly one of its inputs is true. Its truth table is:
| A | B | Output (A XOR B) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
XNOR Gate
The XNOR (exclusive NOR) gate is the inverse of the XOR gate. It outputs true (1) if both inputs are the same. Its truth table is:
| A | B | Output (A XNOR B) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Boolean Algebra
Boolean algebra is a branch of algebra that deals with true and false values. It uses binary variables and logical operations. The main operations in Boolean algebra are AND, OR, and NOT.
Basic Laws of Boolean Algebra
There are several basic laws that govern Boolean algebra:
- Identity Law: A AND 1 = A and A OR 0 = A
- Null Law: A AND 0 = 0 and A OR 1 = 1
- Idempotent Law: A AND A = A and A OR A = A
- Complement Law: A AND NOT A = 0 and A OR NOT A = 1
De Morgan's Theorems
De Morgan's Theorems provide a way to express the negation of conjunctions and disjunctions. They are:
- NOT (A AND B) = NOT A OR NOT B
- NOT (A OR B) = NOT A AND NOT B
Remember: De Morgan's Theorems are essential for simplifying complex Boolean expressions.
Simplifying Boolean Expressions
To simplify Boolean expressions, you can apply the laws of Boolean algebra. Let’s simplify the expression A AND (B OR C).
Example
1. Start with the expression: A AND (B OR C)
2. Apply the Distributive Law: (A AND B) OR (A AND C)
3. The simplified expression is (A AND B) OR (A AND C).
Example 2
Let’s simplify the expression A OR (A AND B).
1. Start with the expression: A OR (A AND B)
2. Apply the Absorption Law: A
3. The simplified expression is A.
Watch out: Be careful with the Absorption Law. It can easily be confused with other laws.
Applications of Logic Gates
Logic gates are used in various applications, including:
- Arithmetic operations in calculators
- Data storage in computer memory
- Control systems in machinery
Combining Logic Gates
Logic gates can be combined to create more complex circuits. For example, you can combine AND and OR gates to create a half adder, which adds two single-bit binary numbers.
Half Adder Example
A half adder has two inputs A and B, and two outputs: sum (S) and carry (C). The equations for the outputs are:
- S = A XOR B
- C = A AND B
The truth table for a half adder is:
| A | B | Sum (S) | Carry (C) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Summary
- Logic gates perform basic logical operations.
- Common gates include AND, OR, NOT, NAND, NOR, XOR, and XNOR.
- Boolean algebra provides the rules for manipulating logical expressions.
- De Morgan's Theorems are crucial for simplifying expressions.
- Logic gates can be combined to create complex circuits, such as adders.
Check your understanding
- What is the output of an AND gate when both inputs are true?
- How does a NOR gate differ from an OR gate?
- What is the result of applying De Morgan's Theorem to the expression NOT (A AND B)?
- How would you simplify the expression A OR (A AND C)?