Boolean Algebra Basics -- AND / OR / NOT / XOR
Boolean algebra is the mathematical foundation of all digital circuits; combinations of the four basic logic operations can be used to construct arbitrarily complex circuits.
Life Analogy: Automatic Doors and Access Control Systems
When entering a highly secure building, you will encounter various access control rules. These rules happen to correspond exactly to the basic operations of Boolean algebra; let’s understand them using everyday scenarios.
AND gate — two doors must be open at the same time to enter: A certain vault requires two keys to be turned simultaneously to open. Only when both keys are inserted and turned (both inputs are 1) will the door open (output is 1). If either key is missing, the door remains motionless.
OR gate——if any one door is open, you can enter: An office building has two entrances; as long as either the front door or the back door is open, you can enter. If any entrance is open (at least one input is 1), you can pass through (output is 1).
NOT gate — button flips the sign: There is a “Vacant/Occupied” toggle sign at the restroom entrance; pressing a button flips the current state. With input 0 (vacant), the output is 1 (occupied), and vice versa.
XOR gate — the two lights in a room must be one on and one off: A room has two lights, and the rule is that the two lights must be in opposite states (one on, one off); otherwise, the alarm system is triggered. Therefore, when the two inputs differ, the output is 1; when they are the same, the output is 0.
Brief History of Boolean Algebra
Boolean algebra was developed by the British mathematicianGeorge BooleIn 1854, Boolean algebra was first systematically proposed in the work An Investigation of the Laws of Thought. Boole’s goal was to mathematize human logical reasoning; he created a method of using algebraic symbols to express “true” and “false.”
In 1938,Claude ShannonIn his MIT master’s thesis, he proved that Boolean algebra could be used to describe and simplify relay switching circuits. This work, known as “the most important master’s thesis in history,” laid the theoretical foundation for the entire design of digital circuits.
It can be said that without Boolean algebra there would be no digital circuits, and without digital circuits there would be no modern computers. Inside the device on which you are reading this passage, hundreds of millions of Boolean operations are being performed every second.
Detailed Explanation of the Four Basic Logic Operations
AND Operation
The rule for the AND operation is just one sentence:The output is 1 only when all inputs are 1.; otherwise, the output is 0. You can think of it as switches connected in series — both switches must be closed for the bulb to light.
| A | B | A AND B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Logical Expression:Y = A · B(Sometimes the dot is omitted, written directly as Y = AB). Mnemonic: output is 1 only when all inputs are 1.
OR Operation
Rules of the OR Operation:As long as one input is 1, the output is 1; the output is 0 only when all inputs are 0. Analogous to switches in parallel — if any switch is closed, the bulb lights.
| A | B | A OR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Logical Expression:Y = A + B(Note that this is not arithmetic addition; in Boolean algebra, 1+1 still equals 1). Mnemonic: any 1 yields 1.
NOT Operation
NOT is the only basic operation that accepts exactly one input, and its rule is the simplest:Output is the inverse of the inputIf the input is 1, the output is 0; if the input is 0, the output is 1.
| A | NOT A |
|---|---|
| 0 | 1 |
| 1 | 0 |
Logical Expression:Y = A'orY = NOT AIn circuit diagrams, a small circle on the input line is commonly used to represent inversion. Mnemonic: 0 becomes 1, 1 becomes 0.
XOR (Exclusive OR) Operation
Rules of XOR:When the two inputs differ, output 1; when they are the same, output 0。XOR Yesby AND、OR、NOT combinationImplementation:A XOR B = (A' · B) + (A · B')。
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Logical Expression:Y = A XOR BXOR has a large number of applications in fields such as adder design, parity checking, and data encryption. Mnemonic: different inputs give 1.
Logic gate symbols
In digital circuit diagrams, each basic logic operation has a corresponding standard logic gate symbol:
AND gate: the symbol is D-shaped — a straight edge plus a semicircular arc, with two input lines on the left and one output line on the right.
OR gate: the symbol is shield-shaped — an inward-curving arc that converges to a pointed tip at the back, representing the logical meaning of “or.”
NOT gate (inverter): a triangle followed by a small circle — the triangle represents buffering/driving, and the circle represents signal inversion.
XOR gate: similar in shape to the OR gate, but with an extra arc added before the input-side arc to distinguish “exclusive OR.”
Any complex digital circuit — including the arithmetic unit and control unit inside a CPU — can ultimately be decomposed into combinations of these four basic logic gates. This is the fundamental reason why Boolean algebra is the theoretical foundation of digital circuits.
Appendix: Logic gate SVG icons and interactive truth tables (example demo)
Below are the standard symbols of the four basic logic gates, along with an interactive truth table — click the A and B buttons to toggle the inputs and observe the output changes in the corresponding rows.
Standard Symbols of the Four Logic Gates
Interactive Truth Table — Click Buttons to Toggle Inputs
Click the A and B buttons below to toggle between 0/1, and observe the corresponding input rows in the table being highlighted
| A | B | AND | OR | NOT A | NOT B | XOR |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |
Interactive demo
Click the buttons below to toggle the values of inputs A and B (0 or 1), and observe how the outputs of each logic gate change in real time:
Logic gate interactive demonstration (example demo)
Click the buttons below to toggle the values of inputs A and B
| Logic gate | Logical Expressions | Current Output | Mnemonic |
|---|---|---|---|
| AND Gate | A AND B | - | Only 1 If All 1 |
| OR Gate | A OR B | - | 1 If Any 1 |
| NOT Gate | NOT A | - | 0 becomes 1, 1 becomes 0 |
| NOT Gate | NOT B | - | 0 becomes 1, 1 becomes 0 |
| XOR Gate | A XOR B | - | Different is 1 |
Python Code Demonstration
Below, Python is used to implement functions for the four basic logic operations, automatically generating complete truth tables while also verifying De Morgan’s laws:
Example
def AND(a, b):
"""AND operation: all 1s then 1"""
return 1 if a == 1 and b == 1 else 0
def OR(a, b):
"""OR operation: if any 1, result is 1"""
return 1 if a == 1 or b == 1 else 0
def NOT(a):
"""NOT operation: invert"""
return 1 if a == 0 else 0
def XOR(a, b):
"""XOR operation: different is 1"""
return 1 if a != b else 0
def print_truth_table(title, func, inputs):
"""Generic truth table printing function"""
print(f"\n{'='*40}")
print(f" {title}")
print(f"{'='*40}")
if func.__code__.co_argcount == 1:
print(f" {'A':>4} | {'output':>4}")
print(f" {'-'*13}")
for a in inputs:
print(f" {a:>4} | {func(a):>4}")
else:
print(f{'A':>4} | {'B':>4} | {'Output':>4})
print(f" {'-'*20}")
for a in inputs:
for b in inputs:
print(f" {a:>4} | {b:>4} | {func(a, b):>4}")
# Main program: print all truth tables
inputs = [0, 1]
print("example Boolean algebra truth table complete demonstration")
print_truth_table("AND Operation", AND, inputs)
print_truth_table("OR (or operation)", OR, inputs)
print_truth_table("NOT Operation", NOT, inputs)
print_truth_table("XOR operation", XOR, inputs)
# De Morgan's Law Verification
print(f"\n{'='*40}")
print(" De Morgan's law verification")
print(f"{'='*40}")
print(Law 1: NOT(A AND B) = NOT A OR NOT B)
print(Law 2: NOT(A OR B) = NOT A AND NOT B)
for a in inputs:
for b in inputs:
left1 = NOT(AND(a, b))
right1 = OR(NOT(a), NOT(b))
left2 = NOT(OR(a, b))
right2 = AND(NOT(a), NOT(b))
print(f" A={a}, B={b}:")
print(f" decide律1: {left1} = {right1} -> {'OK' if left1 == right1 else 'FAIL'}")
print(f" decide律2: {left2} = {right2} -> {'OK' if left2 == right2 else 'FAIL'}")