Boolean Algebra
Simplifying expressions with two-valued variables using the Boolean laws.
Overview
Boolean algebra is the branch of algebra where variables and constants have exactly two values: true and false, usually denoted as 1 and 0 respectively.
Why is it Important?
- Used in programming for conditionals and loops
- Forms the basis for digital circuits in computer hardware
- Powers search engine queries and filters
Key Concepts
Operators and Precedence
The core operators (AND, OR, NOT, XOR) and their order of precedence in Boolean Algebra are identical to those used in Bit-String Flicking.
View Operators and Precedence in Bit-String Flicking →XNOR Operation
The XNOR of two values is true whenever the values are the same. It is the NOT of the XOR function.
Uses the ⊙ operator: x ⊙ y = x ⊕ y
Can be built from basic operators: x ⊙ y = xy + xy
XNOR (⊙)
| x | y | x ⊙ y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Boolean Laws and Properties
Commutative Law
Similar to the commutative property in regular algebra - the order of operands does not matter for a single operation.
x + y = y + x
x · y = y · x
Associative Law
Regrouping of the terms in an expression doesn't change the value.
(x + y) + z = x + (y + z)
x · (y · z) = (x · y) · z
Idempotent Law
A term OR itself or AND itself is equal to that term.
x + x = x
x · x = x
Annihilator Law
A term that is OR'ed with 1 is 1; a term AND'ed with 0 is 0.
x + 1 = 1
x · 0 = 0
Identity Law
A term OR'ed with 0 or AND'ed with 1 will equal that term.
x + 0 = x
x · 1 = x
Complement Law
A term OR'ed with its opposite equals 1; AND'ed with its opposite equals 0.
x + x = 1
x · x = 0
Absorptive Law
Expressions can be simplified by absorbing like terms.
x + xy = x
x + xy = x + y
x(x + y) = x
Distributive Law
Similar to the distributive property in regular algebra - distributing an operation over a set of operands yields the same result.
x · (y + z) = xy + xz
(x + y) · (p + q) = xp + xq + yp + yq
(x + y)(x + z) = x + yz
DeMorgan's Law
An OR (AND) expression that is negated equals the AND (OR), with each term negated.
x + y = x · y
x · y = x + y
Double Negation
A term that is inverted twice is equal to the original term.
x = x
XOR and XNOR Relationship
x ⊙ y = x ⊕ y = x ⊕ y = x ⊕ y
Examples
Apply the laws one step at a time:
- Factor A out of the first two terms (distributive law):
A(B + B) + AB
- B + B = 1 (complement law), and A · 1 = A (identity law):
A + AB
- x + xy = x + y (absorptive law):
A + B
Simplified expression: A + B
How many ordered pairs (A, B) make AB + AB true? Build the truth table and count the rows whose result is 1.
| A | B | AB | AB | Result |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 |
Two ordered pairs, (0,1) and (1,0), make the expression true. (This expression is A ⊕ B.)
Practice Problems
Type complements with an apostrophe (for example, A' for A) if you need them in an answer.
Problem 1 Junior
Simplify the following Boolean expression:
A(AB + B) + B(A + B)
Solution
- Distribute A in first term:
AAB + AB + B(A + B)
- Simplify AAB using idempotent law (A·A = A):
AB + AB + B(A + B)
- Distribute B in last term:
AB + AB + BA + BB
- BB = 0 by complement law:
AB + AB + BA
- AB = BA by commutative law:
AB + AB + AB
- AB + AB = AB by idempotent law:
AB + AB
- Factor out A:
A(B + B)
- B + B = 1 by complement law:
A(1) = A
- Final answer: A
Problem 2 Junior
How many ordered pairs make the following Boolean expression TRUE?
AB + B(A + C) + AC
Solution
- Let's create a truth table for three variables (A, B, C):
A B C AB B(A+C) AC Result 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 - Count the rows where the Result is 1: 5 rows
Therefore, 5 ordered pairs make this expression TRUE.
Problem 3 Intermediate
Simplify the following Boolean expression:
(A + B)(A + B) + AB
Solution
- Distribute first term (A + B)(A + B):
AA + AB + AB + BB
- Simplify AA using idempotent law:
A + AB + AB + BB
- BB = 0 by complement law:
A + AB + AB
- Factor out A:
A(1 + B + B)
- B + B = 1 by complement law:
A(1 + 1)
- 1 + 1 = 1 by idempotent law:
A(1) = A
- Final answer: A
Problem 4 Intermediate
How many ordered triples make the following Boolean expression FALSE?
A(B + C) + B(A + C) + ABC
Solution
- Let's create a truth table for three variables (A, B, C):
A B C A(B+C) B(A+C) ABC Result 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 1 0 1 1 1 1 1 1 0 1 - Count the rows where the Result is 0: 2 rows
- The expression is FALSE when:
- (A,B,C) = (0,0,1)
- (A,B,C) = (0,1,1)
Therefore, 2 ordered triples make this expression FALSE.
Problem 5 Senior
Simplify the following Boolean expression:
(A + B)(AB)(A + B)(AB)
Solution
- Let's examine each term:
- (A + B): Either A or B is 1
- (AB): Both A and B are 0
- (A + B): A is 1 or B is 0
- (AB): A is 0 and B is 1
- Looking at (AB) and (AB):
These require B to be both 0 and 1, which is impossible
- When we AND terms with contradictory requirements:
The result must be 0
- Final answer: 0
This expression is a contradiction because it requires B to be both 0 and 1 simultaneously, which is impossible in Boolean algebra.