Boolean Algebra Laws
Notation
The following defines the notation used for Boolean algebra on this page. This is just one of many notations, none of which is right or wrong.
- True
- 1
- False
- 0
- X AND Y
- X · Y, also X Y (juxtaposition)
- X OR Y
- X + Y
- X XOR Y
- X ⊕ Y
- NOT X
- X
- Precedence
- AND (highest), XOR, OR (lowest). Examples:
- X + Y·Z = X + (Y·Z)
- X ⊕ Y·Z = X ⊕ (Y·Z)
- X + Y⊕Z = X + (Y⊕Z)
Basic laws
Commutativity
AND and OR are commutative:
- X · Y = Y · X
- X + Y = Y + X
Constants
AND:
- 0 · 0 = 0
- 0 · 1 = 0
- 1 · 1 = 1
OR:
- 0 + 0 = 0
- 0 + 1 = 1
- 1 + 1 = 1
NOT:
- 0 = 1
- 1 = 0
Constant and variable
AND:
- 0 · X = 0
- 1 · X = X
OR:
- 0 + X = X
- 1 + X = 1
One variable
AND:
- X · X = X
- X · X = 0
OR:
- X + X = X
- X + X = 1
NOT:
- NOT X = X
De Morgan’s laws
NAND and NOR have alternative definitions:
- X · Y = X + Y
- X + Y = X · Y
Associativity
AND and OR are associative:
- (X · Y) · Z = X · (Y · Z)
- (X + Y) + Z = X + (Y + Z)
Distributivity
AND distributes over OR, OR distributes over AND:
- X · (Y+Z) = X·Y + X·Z
- X + (Y·Z) = (X+Y) · (X+Z)
XOR function
Definition in terms of AND, OR, and NOT:
- X ⊕ Y = X·Y + X·Y
- X ⊕ Y = (X+Y) · (X+Y)
- X ⊕ Y = (X+Y) · (X·Y)
Commutativity:
- X ⊕ Y = Y ⊕ X
Constants:
- 0 ⊕ 0 = 0
- 0 ⊕ 1 = 1
- 1 ⊕ 1 = 0
Constant and variable:
- 0 ⊕ X = X
- 1 ⊕ X = X
One variable:
- X ⊕ X = 0
- X ⊕ X = 1
Associativity:
- (X ⊕ Y) ⊕ Z = X ⊕ (Y ⊕ Z)
Distributivity – AND distributes over XOR
- X · (Y⊕Z) = X·Y ⊕ X·Z
Redundancy laws
All of these laws will be proved with the basic laws. Counterintuitively, it is sometimes necessary to complicate before simplifying.
Absorption
- X + X·Y = X
-
X + X·Y
= X·1 + X·Y
= X · (1+Y)
= X · 1
= X - X · (X+Y) = X
-
X · (X+Y) = X
= (X+0) · (X+Y)
= X + (0·Y)
= X + 0
= X
No name
- X + X·Y = X + Y
-
X + X·Y
= (X+X) · (X+Y)
= 1 · (X+Y)
= X + Y - X · (X+Y) = X · Y
-
X · (X+Y)
= X·X + X·Y
= 0 + X·Y
= X · Y - X·Y + X·Y = X
-
X·Y + X·Y
= X · (Y+Y)
= X · 1
= X - (X+Y) · (X+Y) = X
-
(X+Y) · (X+Y)
= X + (Y·Y)
= X + 0
= X
Consensus
- X·Y + X·Z + Y·Z = X·Y + X·Z
-
X·Y + X·Z + Y·Z
= X·Y + X·Z + 1·Y·Z
= X·Y + X·Z + (X+X)·Y·Z
= X·Y + X·Z + X·Y·Z + X·Y·Z
= X·Y + X·Y·Z + X·Z + X·Y·Z
= X·Y·1 + X·Y·Z + X·1·Z + X·Y·Z
= X·Y·(1+Z) + X·Z·(1+Y)
= X·Y·1 + X·Z·1
= X·Y + X·Z - (X+Y) · (X+Z) · (Y+Z) = (X+Y) · (X+Z)
-
(X+Y) · (X+Z) · (Y+Z)
= (X+Y) · (X+Z) · (0+Y+Z)
= (X+Y) · (X+Z) · (X·X + Y + Z)
= (X+Y) · (X+Z) · (X+Y+Z) · (X+Y+Z)
= (X+Y) · (X+Y+Z) · (X+Z) · (X+Y+Z)
= (X+Y+0) · (X+Y+Z) · (X+0+Z) · (X+Y+Z)
= (X + Y + 0·Z) · (X + Z + 0·Y)
= (X + Y + 0) · (X + Z + 0)
= (X+Y) · (X+Z)
Links
- Wikipedia: Boolean algebra (logic)
- Play-Hookey: Boolean Algebra
- MathWorld: Boolean algebra
- Lessons In Electric Circuits: Boolean Algebra (hosted at All About Circuits)
Last modified: 2007-09-25-Tue
Created: 2007-09-22-Sat