A digital computer works with electrical signals that are interpreted as two logical states. These states are commonly represented by 0 and 1. To describe how these binary states interact, computer systems use Boolean algebra.
Boolean algebra provides a mathematical method for representing logical conditions and combining binary variables. It is particularly important in Computer Organization and Architecture because the behavior of digital circuits can be expressed as Boolean expressions and then implemented using logic gates.
For example, a circuit may need to produce an output only when two conditions are true. Another circuit may produce an output when either of two conditions is true. Boolean operations provide a precise way to describe both situations.
In this chapter, we will study Boolean variables, the basic AND, OR and NOT operations, their truth tables, important Boolean laws, De Morgan's theorems, the principle of duality and the simplification of Boolean expressions.
Boolean algebra is a mathematical system in which variables have one of two possible values: 0 or 1. These values can represent logical states such as false and true, low and high, or OFF and ON.
Unlike ordinary arithmetic, Boolean algebra does not operate on an unlimited range of numerical values. Its operations are specifically defined for binary logic.
The three fundamental Boolean operations are:
Other logical operations, such as NAND, NOR, XOR and XNOR, can be constructed from these basic operations and are widely used in digital circuit design.
A Boolean variable can contain either 0 or 1. Boolean expressions are formed by combining variables with logical operators.
For example, consider two Boolean variables A and B.
A = 0 B = 1
Here, A and B are Boolean variables, while 0 and 1 are Boolean constants.
A Boolean expression may combine these variables. For example:
A + B A · B A'
In Boolean notation, the plus sign represents OR, the dot represents AND, and the apostrophe represents NOT or complement.
| Operation | Symbol | Meaning |
|---|---|---|
| AND | A · B | Produces 1 only when both inputs are 1. |
| OR | A + B | Produces 1 when at least one input is 1. |
| NOT | A' | Reverses the value of the input. |
The AND operation combines two or more Boolean inputs. Its output becomes 1 only when every input is 1. If any input is 0, the result is 0.
The Boolean expression for a two-input AND operation is:
Y = A · B
| A | B | A · B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Suppose a circuit has two conditions, A and B. The output should become active only when both conditions are satisfied.
A = 1 B = 1 A · B = 1
If either A or B becomes 0, the output becomes 0.
The OR operation produces an output of 1 when at least one input is 1. The output is 0 only when all inputs are 0.
For two inputs, the expression is:
Y = A + B
| A | B | A + B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
A = 0 B = 1 A + B = 1
Only one input is required to be 1 for the OR result to become 1.
The NOT operation has only one input. It produces the opposite value of that input.
If A is 0, its complement is 1. If A is 1, its complement is 0.
Y = A'
| A | A' |
|---|---|
| 0 | 1 |
| 1 | 0 |
Boolean laws provide rules for transforming and simplifying Boolean expressions without changing their logical result. These rules are important when designing digital circuits because an equivalent expression may require fewer gates or connections.
A + 0 = A A · 1 = A
Adding 0 through OR or multiplying by 1 through AND does not change the value of A.
A + 1 = 1 A · 0 = 0
An OR operation with 1 always produces 1, while an AND operation with 0 always produces 0.
A + A = A A · A = A
Combining the same Boolean variable with itself does not change its value.
A + A' = 1 A · A' = 0
A Boolean variable and its complement always produce 1 through OR and 0 through AND.
(A')' = A
Taking the complement of a value twice returns the original value.
A + B = B + A A · B = B · A
The order of the operands does not affect the result.
(A + B) + C = A + (B + C) (A · B) · C = A · (B · C)
The grouping of operands can be changed without changing the result.
A · (B + C) = A·B + A·C A + (B·C) = (A+B)·(A+C)
The distributive laws allow Boolean expressions to be expanded or factored during simplification.
De Morgan's theorems provide two important rules for transforming complemented Boolean expressions. They are frequently used when simplifying logic expressions and when converting between different logic-gate implementations.
(A · B)' = A' + B'
The complement of an AND expression is equal to the OR of the individual complements.
(A + B)' = A' · B'
The complement of an OR expression is equal to the AND of the individual complements.
When a complement is applied to a group of Boolean variables:
For example:
(A + B + C)' = A' · B' · C'
Similarly:
(A · B · C)' = A' + B' + C'
The principle of duality is an important property of Boolean algebra. It states that a valid Boolean identity has a corresponding dual identity obtained by exchanging OR with AND and 0 with 1.
For example:
A + 0 = A
Its dual form is:
A · 1 = A
Both expressions are valid Boolean identities.
Boolean simplification means transforming an expression into an equivalent form that contains fewer terms or operations. In digital systems, simplification can help reduce circuit complexity.
Consider:
A · B + A · B'
Take A as the common factor:
A(B + B')
Using the complement law:
B + B' = 1
Therefore:
A · 1 = A
Final result:
A
The original expression contained two product terms, but the simplified expression requires only A.
Consider the expression:
A + A · B
Using the absorption law:
A + A·B = A
Therefore:
A + A·B = A
This is an example of how Boolean laws can eliminate unnecessary terms from an expression.
Absorption laws are particularly useful for reducing Boolean expressions.
A + A·B = A A·(A+B) = A
For example:
A + A·B = A(1+B) = A·1 = A
These identities are useful during manual simplification and digital circuit optimization.
A truth table can be used to verify whether two Boolean expressions are equivalent. For two variables, there are four possible combinations of input values.
Consider:
A + A·B
and its simplified form:
A
| A | B | A·B | A + A·B | A |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
The final two columns are identical for every input combination. Therefore, the two expressions produce the same output.
Boolean expressions have a direct relationship with digital logic gates. A Boolean operator can be represented physically by a gate in a digital circuit.
| Boolean Operation | Typical Logic Gate | Boolean Expression |
|---|---|---|
| AND | AND Gate | Y = A · B |
| OR | OR Gate | Y = A + B |
| NOT | NOT Gate | Y = A' |
| NOT AND | NAND Gate | Y = (A · B)' |
| NOT OR | NOR Gate | Y = (A + B)' |
This connection between algebraic expressions and physical gates is one of the main reasons Boolean algebra is studied before logic gates in Computer Organization and Digital Electronics.
A digital circuit can often be represented by more than one Boolean expression. Although two expressions may produce exactly the same output, one may require significantly fewer gates than the other.
For example, if a circuit implements:
A·B + A·B'
Boolean simplification gives:
A
The simplified form eliminates the need to separately implement the two product terms and their combination. In practical circuit design, such reductions can help decrease hardware complexity, power consumption, propagation delay and physical area.
Boolean algebra is not limited to textbook simplification exercises. It forms part of the mathematical foundation used to describe many components of a computer system.
| Law | Identity |
|---|---|
| Identity | A + 0 = A ; A · 1 = A |
| Null | A + 1 = 1 ; A · 0 = 0 |
| Idempotent | A + A = A ; A · A = A |
| Complement | A + A' = 1 ; A · A' = 0 |
| Involution | (A')' = A |
| Commutative | A + B = B + A ; A · B = B · A |
| Associative | (A+B)+C = A+(B+C) |
| Distributive | A(B+C) = AB+AC |
| Absorption | A + AB = A |
| Boolean Algebra | Ordinary Algebra |
|---|---|
| Variables normally have values 0 or 1. | Variables may have many numerical values. |
| Uses logical operations such as AND, OR and NOT. | Uses arithmetic operations such as addition and multiplication. |
| Used to represent digital logic. | Used for general mathematical relationships. |
| Boolean laws define its operations. | Arithmetic laws define its operations. |
Boolean simplification becomes easier when each transformation is based on a valid identity. Some mistakes occur because Boolean symbols look similar to ordinary arithmetic notation.
| Incorrect Approach | Better Approach |
|---|---|
| Treating Boolean addition exactly like ordinary numerical addition. | Apply the Boolean OR laws rather than ordinary arithmetic rules. |
| Applying De Morgan's theorem without complementing every variable. | Change the operator and complement each variable inside the expression. |
| Changing only part of a grouped expression. | Identify the complete complemented group before applying a theorem. |
| Stopping before checking for absorption or other applicable laws. | Review the resulting expression for additional simplification. |
Boolean algebra is a mathematical system used to represent and manipulate logical values, generally 0 and 1.
The three fundamental operations are AND, OR and NOT.
AND produces 1 only when all inputs are 1. OR produces 1 when at least one input is 1.
De Morgan's theorems provide rules for complementing AND and OR expressions:
(A·B)' = A' + B' (A+B)' = A'·B'
It provides the mathematical foundation for describing digital logic and helps designers analyze and simplify the circuits used in computer hardware.
It is the process of converting a Boolean expression into an equivalent but simpler form by applying valid Boolean laws and identities.
Boolean algebra provides the mathematical language used to describe binary logic in digital computer systems. By working with only two logical values and a defined collection of operations, it allows complex logical relationships to be represented in a precise form.
The AND, OR and NOT operations form the foundation of Boolean logic, while laws such as identity, complement, distributive and absorption provide techniques for transforming expressions. De Morgan's theorems extend these techniques to complemented expressions, and truth tables provide a practical way to verify the resulting logic.
For Computer Organization and Architecture, the importance of Boolean algebra becomes especially clear when these expressions are converted into physical logic gates and digital circuits. A good understanding of Boolean expressions therefore provides a strong foundation for studying logic gates, combinational circuits, arithmetic circuits and processor hardware.