In the previous chapter, we saw how computers represent numbers, negative values, and text using binary patterns of 0s and 1s. But storing data in binary is only half the picture, since a computer also needs a formal system for reasoning about and manipulating that binary data logically. This is exactly the role Boolean algebra plays in Computer Organization and Architecture.
Boolean algebra is a branch of mathematics that deals with variables having only two possible values, typically represented as 0 and 1, or equivalently as false and true. Unlike ordinary algebra, which deals with addition, subtraction, multiplication, and an unlimited range of numeric values, Boolean algebra works with a small, well-defined set of logical operations that determine how these two-valued variables combine and interact with each other.
In this tutorial, you will learn about the three fundamental Boolean operations, AND, OR, and NOT, along with truth tables that describe their exact behavior. You will also learn the important laws of Boolean algebra, explore De Morgan's theorem, and see how Boolean expressions can be simplified using these rules.
Every decision a computer makes, whether it is comparing two numbers, checking a condition inside a program, or routing a signal through a circuit, ultimately reduces to a combination of true and false, or equivalently, 1 and 0. Boolean algebra provides the mathematical foundation needed to describe, analyze, and simplify these logical decisions in a precise and consistent way.
Even more importantly for Computer Organization specifically, Boolean algebra directly maps onto the physical logic gates that make up a computer's circuits, which we will explore in detail in the next chapter. Understanding Boolean algebra first makes it much easier to understand how those physical circuits are designed and how they behave.
A Boolean variable can hold only one of two possible values at any given time, usually written as 0 and 1. These values might represent many different real-world ideas depending on context, such as off and on, false and true, or low voltage and high voltage, but in Boolean algebra itself, they are simply treated as 0 and 1.
Let A represent whether a viewer is subscribed to CS Engineering Gyan A = 1 means the viewer is subscribed A = 0 means the viewer is not subscribed
The AND operation, written using a dot symbol or simply by placing two variables next to each other, produces a result of 1 only when both of its inputs are 1. If either input is 0, the result of the AND operation is always 0.
| A | B | A AND B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Let A = viewer is subscribed to CS Engineering Gyan Let B = viewer has notifications turned on A AND B = 1 only if the viewer is BOTH subscribed AND has notifications on
The OR operation, written using a plus symbol, produces a result of 1 if at least one of its inputs is 1. The only case where the OR operation produces 0 is when both of its inputs are 0.
| A | B | A OR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Let A = viewer liked the video Let B = viewer commented on the video A OR B = 1 if the viewer did AT LEAST ONE of these two actions
The NOT operation, also called complementation and often written with a bar over the variable or an apostrophe after it, simply reverses a single input's value. If the input is 1, NOT produces 0, and if the input is 0, NOT produces 1.
| A | NOT A |
|---|---|
| 0 | 1 |
| 1 | 0 |
Let A = viewer is subscribed to CS Engineering Gyan NOT A = 1 means the viewer is NOT subscribed
Just like ordinary algebra has rules for how addition and multiplication behave, Boolean algebra has its own set of laws that describe how AND, OR, and NOT interact with each other. These laws are extremely useful for simplifying complicated Boolean expressions into simpler, equivalent forms.
| Law | AND Form | OR Form |
|---|---|---|
| Identity Law | A · 1 = A | A + 0 = A |
| Null Law | A · 0 = 0 | A + 1 = 1 |
| Idempotent Law | A · A = A | A + A = A |
| Complement Law | A · A' = 0 | A + A' = 1 |
| Commutative Law | A · B = B · A | A + B = B + A |
| Associative Law | (A · B) · C = A · (B · C) | (A + B) + C = A + (B + C) |
| Distributive Law | A · (B + C) = (A · B) + (A · C) | A + (B · C) = (A + B) · (A + C) |
These laws might look abstract at first, but each one has a very intuitive explanation. The null law, for instance, simply reflects that ANDing anything with 0 always produces 0, since both inputs must be 1 for AND to succeed, while ORing anything with 1 always produces 1, since only one input needs to be 1 for OR to succeed.
De Morgan's theorem describes an extremely important relationship between AND, OR, and NOT, and it is one of the most frequently used tools for simplifying Boolean expressions in Computer Organization. It consists of two related rules.
NOT (A AND B) = (NOT A) OR (NOT B) (A · B)' = A' + B'
NOT (A OR B) = (NOT A) AND (NOT B) (A + B)' = A' · B'
In simple terms, De Morgan's theorem states that the complement of an AND operation is equivalent to the OR of the complements, and the complement of an OR operation is equivalent to the AND of the complements. This might sound confusing in words, but it becomes much clearer with a worked example.
Let A = viewer is subscribed to CS Engineering Gyan Let B = viewer has notifications turned on NOT (A AND B) means: it is NOT true that the viewer is both subscribed AND has notifications on By De Morgan's theorem, this is the same as saying: The viewer is NOT subscribed, OR the viewer does NOT have notifications on (or possibly both)
This example shows how De Morgan's theorem lets us rewrite a single negated combined condition into two separate, individually negated conditions joined by the opposite operator, which is often much easier to reason about or implement in a digital circuit.
One of the most practical uses of Boolean algebra is simplifying complicated logical expressions into shorter, equivalent forms. A simpler Boolean expression generally translates into a simpler, cheaper, and faster digital circuit when it is eventually implemented in hardware.
Simplify: A · B + A · B' Step 1: Factor out the common term A A · (B + B') Step 2: Apply the Complement Law, since B + B' = 1 A · 1 Step 3: Apply the Identity Law, since A · 1 = A Final simplified expression: A
This example shows how an expression that originally looked like it depended on both A and B actually simplifies down to depend only on A, once the complement law and identity law are applied correctly. This kind of simplification is exactly what allows digital circuit designers to reduce the number of components required to build a particular piece of logic.
Simplify: A + A' · B Step 1: Apply the Distributive Law in reverse, treating this as (A + A') · (A + B) Step 2: Apply the Complement Law, since A + A' = 1 1 · (A + B) Step 3: Apply the Identity Law, since 1 · (A + B) = A + B Final simplified expression: A + B
Boolean algebra follows a useful pattern known as the principle of duality, which states that every valid Boolean identity remains valid if AND is replaced with OR, OR is replaced with AND, 0 is replaced with 1, and 1 is replaced with 0 throughout the entire expression.
Original identity: A + 0 = A Applying duality (swap + with ·, and 0 with 1): Dual identity: A · 1 = A
This principle is a helpful shortcut, since it means that once one Boolean law or identity has been proven true, its dual version is automatically true as well, without needing to be proven separately from scratch.
| Advantages | Limitations |
|---|---|
| Provides a precise mathematical foundation for describing and simplifying digital logic. | Boolean expressions can become long and difficult to simplify manually as complexity grows. |
| Simplified expressions directly translate into simpler, more efficient digital circuits. | Only handles two-valued logic, unlike ordinary algebra which works with a full range of numbers. |
| Laws like De Morgan's theorem allow flexible rewriting of logical conditions. | Beginners can find switching between AND, OR, and NOT forms confusing at first. |
| Mistake | Correct Practice |
|---|---|
| Confusing the AND and OR truth tables with each other. | Remember that AND requires both inputs to be 1, while OR only requires at least one input to be 1. |
| Applying De Morgan's theorem without flipping both the operator and each variable's complement. | Always flip the operator (AND to OR, or OR to AND) and complement every individual variable together. |
| Stopping a simplification too early without checking if further laws can still be applied. | Continue applying laws step by step until no further simplification is possible. |
| Assuming Boolean algebra values behave like ordinary numbers in every case. | Remember that Boolean algebra follows its own specific set of laws, distinct from ordinary arithmetic. |
Boolean algebra provides the formal mathematical language needed to describe and simplify the logical decisions that computers make constantly, using only two possible values and a small set of operations: AND, OR, and NOT. The basic laws of Boolean algebra, along with De Morgan's theorem, give us the tools needed to rewrite and simplify complicated logical expressions into cleaner, more efficient equivalent forms.
This chapter walked through truth tables for each basic operation, the core laws of Boolean algebra, De Morgan's theorem with a worked example, step-by-step expression simplification, and the useful principle of duality. Together, these concepts form the mathematical backbone that supports everything from simple conditional logic to complex digital circuit design.
With Boolean algebra covered, you are now ready to move on to logic gates, where these same AND, OR, and NOT operations are translated into actual physical circuit components, complete with symbols, truth tables, and real circuit diagrams.