Introduction to Boolean Algebra
Boolean Algebra is a branch of algebra where variables can have only two values: TRUE (1) or FALSE (0). It was developed by George Boole in the 19th century and forms the mathematical foundation of digital electronics and computer science.
Boolean Variables
A Boolean variable can take only one of two values:
- TRUE (represented as 1, T, or true)
- FALSE (represented as 0, F, or false)
Examples:
- x = 1 (x is true)
- y = 0 (y is false)
- A light switch: ON (1) or OFF (0)
- A condition: SUCCESS (1) or FAILURE (0)
Boolean Functions
Definition
A Boolean function is a function that maps Boolean variables to a Boolean value.
Notation: f: {0, 1}ⁿ → {0, 1}
where n is the number of input variables.
Example:
- f(x, y) = x AND y
- g(x, y, z) = (x OR y) AND z
- h(x) = NOT x
Number of Boolean Functions
For n Boolean variables, there are 2²ⁿ possible Boolean functions.
Examples:
- 1 variable: 2²¹ = 4 functions
- 2 variables: 2²² = 16 functions
- 3 variables: 2²³ = 256 functions
Basic Boolean Operations
1. NOT (Negation) - ¬ or ’ or ‾
Symbol: ¬x or x’ or x̅
Definition: Inverts the value
Truth Table:
| x | ¬x |
|---|---|
| 0 | 1 |
| 1 | 0 |
Examples:
- ¬1 = 0
- ¬0 = 1
- If x = “it is raining” (true), then ¬x = “it is not raining” (false)
2. AND (Conjunction) - ∧ or × or ⋅
Symbol: x ∧ y or x × y or xy
Definition: True only when both inputs are true
Truth Table:
| x | y | x ∧ y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Examples:
- 1 ∧ 1 = 1
- 1 ∧ 0 = 0
- 0 ∧ 0 = 0
3. OR (Disjunction) - ∨ or +
Symbol: x ∨ y or x + y
Definition: True when at least one input is true
Truth Table:
| x | y | x ∨ y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Examples:
- 1 ∨ 1 = 1
- 1 ∨ 0 = 1
- 0 ∨ 0 = 0
4. XOR (Exclusive OR) - ⊕
Symbol: x ⊕ y
Definition: True when inputs are different
Truth Table:
| x | y | x ⊕ y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Formula: x ⊕ y = (x ∧ ¬y) ∨ (¬x ∧ y)
Examples:
- 1 ⊕ 0 = 1
- 0 ⊕ 1 = 1
- 1 ⊕ 1 = 0 (both same)
5. NAND (NOT AND) - ↑
Symbol: x ↑ y or x | y
Definition: Opposite of AND
Truth Table:
| x | y | x NAND y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Formula: x NAND y = ¬(x ∧ y)
Special Property: NAND is functionally complete - you can build any Boolean function using only NAND gates!
6. NOR (NOT OR) - ↓
Symbol: x ↓ y
Definition: Opposite of OR
Truth Table:
| x | y | x NOR y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
Formula: x NOR y = ¬(x ∨ y)
Special Property: NOR is also functionally complete!
Boolean Identities (Laws)
Identity Laws
- x ∨ 0 = x
- x ∧ 1 = x
Domination Laws
- x ∨ 1 = 1
- x ∧ 0 = 0
Idempotent Laws
- x ∨ x = x
- x ∧ x = x
Double Complement Law
- ¬(¬x) = x
Commutative Laws
- x ∨ y = y ∨ x
- x ∧ y = y ∧ x
Associative Laws
- (x ∨ y) ∨ z = x ∨ (y ∨ z)
- (x ∧ y) ∧ z = x ∧ (y ∧ z)
Distributive Laws
- x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)
- x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)
De Morgan’s Laws (Very Important!)
- ¬(x ∧ y) = ¬x ∨ ¬y
- ¬(x ∨ y) = ¬x ∧ ¬y
Memory Aid: “Break the bar, change the operation”
Absorption Laws
- x ∨ (x ∧ y) = x
- x ∧ (x ∨ y) = x
Complement Laws
- x ∨ ¬x = 1
- x ∧ ¬x = 0
Evaluating Boolean Functions
Example 1: f(x, y) = (x ∧ y) ∨ (¬x ∧ y)
Evaluate for x = 1, y = 0:
- f(1, 0) = (1 ∧ 0) ∨ (¬1 ∧ 0)
- = 0 ∨ (0 ∧ 0)
- = 0 ∨ 0
- = 0
Complete Truth Table:
| x | y | x∧y | ¬x | ¬x∧y | f(x,y) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 |
Simplified: f(x, y) = y
Example 2: f(x, y, z) = (x ∨ y) ∧ z
Truth Table:
| x | y | z | x∨y | f(x,y,z) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Simplifying Boolean Functions
Example 1: Simplify f = x¬y + xy
Using Distributive Law:
- f = x¬y + xy
- f = (x¬ + x)y (factor out y… wait, this is wrong!)
- Actually: f = y(x¬ + x)
- Hmm, let me use proper notation: f = ¬xy + xy
- f = (¬x + x)y
- f = 1 × y
- f = y
Example 2: Simplify f = (x + y)(x + ¬y)
Using Distributive Law:
- f = (x + y)(x + ¬y)
- f = x + x¬y + xy + y¬y
- f = x + x¬y + xy + 0 (y¬y = 0)
- f = x(1 + ¬y + y)
- f = x(1) (anything OR 1 = 1)
- f = x
Example 3: Simplify using De Morgan’s Law
Simplify: ¬(x ∧ ¬y) ∨ (x ∧ y)
Step 1: Apply De Morgan
- ¬(x ∧ ¬y) = ¬x ∨ ¬(¬y) = ¬x ∨ y
Step 2: Substitute
- f = (¬x ∨ y) ∨ (x ∧ y)
Step 3: Simplify
- f = ¬x ∨ y ∨ (x ∧ y)
- f = ¬x ∨ y (absorption: y ∨ (x ∧ y) = y)
Boolean Function Representation
1. Truth Table
Lists all possible input combinations and outputs.
2. Boolean Expression
Algebraic formula using Boolean operations.
3. Logic Circuit
Diagram using logic gates (covered in next topic).
4. Karnaugh Map (K-map)
Graphical method for simplification (covered in Minimization topic).
Standard Forms
Sum of Products (SOP)
Definition: OR of AND terms
Example: f = xy + x¬y + ¬x¬y
Minterms: Each AND term where function = 1
Product of Sums (POS)
Definition: AND of OR terms
Example: f = (x + y)(x + ¬y)(¬x + y)
Maxterms: Each OR term where function = 0
Complete Boolean Functions
Functionally Complete Sets
A set of Boolean operations is functionally complete if any Boolean function can be expressed using only those operations.
Examples of Complete Sets:
- {AND, OR, NOT}
- {AND, NOT}
- {OR, NOT}
- {NAND} (alone!)
- {NOR} (alone!)
Why NAND is Complete:
- NOT x = x NAND x
- x AND y = (x NAND y) NAND (x NAND y)
- x OR y = (x NAND x) NAND (y NAND y)
Applications of Boolean Functions
1. Digital Circuits
Every digital circuit can be represented as a Boolean function.
2. Computer Programming
If-else statements, loops conditions use Boolean logic.
3. Database Queries
SQL WHERE clauses use Boolean expressions.
4. Search Engines
Boolean operators (AND, OR, NOT) refine searches.
5. Control Systems
Automation and robotics use Boolean logic for decision-making.
Key Points for Exams
- Boolean variables have only 2 values: 0 and 1
- Know all basic operations: NOT, AND, OR, XOR, NAND, NOR
- De Morgan’s Laws are crucial for simplification
- NAND and NOR are functionally complete
- Truth tables have 2ⁿ rows for n variables
- Use Boolean identities to simplify expressions
- Complement law: x + ¬x = 1, x·¬x = 0
- Idempotent: x + x = x, x·x = x
- Absorption laws are very useful
- Practice simplification using algebraic methods
Practice Problems
-
Create truth table for f(x, y, z) = x¬y + yz
-
Simplify: (x + y)(x + ¬y)
-
Prove using Boolean algebra: x + xy = x
-
Express XOR using only AND, OR, NOT
-
Simplify using De Morgan’s: ¬(xy + ¬x¬y)
-
How many Boolean functions exist for 2 variables?
-
Express NOT and OR using only NAND
-
Evaluate f(1,0,1) where f(x,y,z) = (x+y)¬z
-
Prove: x(x+y) = x using Boolean identities
-
Convert to SOP form: f(x,y) = x → y