11.1 Boolean Algebra
COS2621 - Computer Organisation · 11. Digital Logic
Boolean Algebra
Introduction to Boolean Algebra
Boolean algebra is a mathematical structure that deals with binary variables (0 and 1) and logical operations. It is essential in digital logic design and computer architecture. The primary operations in Boolean algebra are AND, OR, and NOT.
Basic Operations
AND Operation
The AND operation results in true (1) if both operands are true (1). The truth table for the AND operation is as follows:
| A | B | A AND B |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
OR Operation
The OR operation results in true (1) if at least one operand is true (1). The truth table is:
| A | B | A OR B |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
NOT Operation
The NOT operation inverts the value of the operand. The truth table is as follows:
| A | NOT A |
|---|---|
| 1 | 0 |
| 0 | 1 |
Boolean Identities
Boolean algebra has several identities that simplify expressions:
- Identity Law: A AND 1 = A, A OR 0 = A
- Null Law: A AND 0 = 0, A OR 1 = 1
- Idempotent Law: A AND A = A, A OR A = A
- Complement Law: A AND NOT A = 0, A OR NOT A = 1
Example of Simplifying a Boolean Expression
Consider the expression: [(AB)' + C]'. We will simplify it step by step:
- Apply De Morgan's Theorem: (AB)' = A' + B'
- Substitute into the expression: [(A' + B') + C]' = (A' + B' + C)'
- Apply De Morgan's Theorem again: A''B''C' = A'B'C'
The final result is A'B'C'.
Watch out: Do not confuse the AND and OR operations. Remember their truth tables.
Postfix Notation
Postfix notation, also known as Reverse Polish Notation (RPN), is a way to write expressions without parentheses. For example, the infix expression (A * B + C) / (E - F) can be converted to postfix as follows:
- Convert A * B to AB*
- Add C: AB*C+
- Convert E - F to EF-
- Combine: AB*C+EF-/
Applications of Boolean Algebra
Boolean algebra is crucial for designing digital circuits. For instance, to design a binary gate that outputs 1 when both inputs are equal (either both 0 or both 1), the Boolean function would be x'y' + xy.
Check your understanding
- What is the result of A AND 1 if A = 0?
- How does the NOT operation affect the value of a variable?
- Simplify the expression A AND (B OR C).
- State the Complement Law in Boolean algebra.
Test yourself
5 quick questions on this lesson. Pick an answer to see if you're right.
1. Given A and B as input and F as out function, the algebraic expression for XOR is
2. Give the postfix representation of the following expression where infix notation is used. (A + B * C) - (E / F)
3. Which law states that A AND NOT A = 0?
4. Give the result of the following binary operation: A AND B, where A = 1010 1101 and B = 0011 1001
5. What is the function of the REP instruction?