Boolean Algebra
- Tags
- logic
Is an algebra [see page 21, defined] using the set \( B = \{ 0, 1 \} \) with 3 operations complementation \( x' \), summation \( x + y \) and product \( x \cdot y \). These operations must satisfy the laws in tbl:bool-laws.
Laws and Rules
| Name | LHS | RHS |
|---|---|---|
| Commutativity | \( x + y \) | \( y + x \) |
| \( x \cdot y \) | \( y \cdot x \) | |
| Associativity | \( (x + y) + z \) | \( x + (y + x) \) |
| \( (x \cdot y) \cdot z \) | \( x \cdot (y \cdot z) \) | |
| Distributivity | \( x + (y \cdot z) \) | \( (x + y) \cdot (x + z) \) |
| \( x \cdot (y + z) \) | \( (x \cdot y) + (x \cdot z) \) | |
| Identity | \( x + 0 \) | \( x \) |
| \( x \cdot 1 \) | \( x \) | |
| Complement | \( x + x' \) | 1 |
| \( x \cdot x' \) | 0 |
| Name | LHS | RHS |
|---|---|---|
| Distributive Laws | \( (x + y) \cdot z \) | \( x \cdot z + y \cdot z \) |
| \( x \cdot y + z \) | \( (x + z) \cdot (y + z) \) | |
| Idempotence Laws | \( x + x \) | \( x \) |
| \( x \cdot x \) | \( x \) | |
| Domination Laws | \( x + 1 \) | \( 1 \) |
| \( x \cdot 0 \) | \( 0 \) | |
| Absorption Laws | \( x + x \cdot y \) | \( x \) |
| \( x \cdot (x + y) \) | \( x \) | |
| Calculating Equality | \( x + y = x + z \) AND \( x \cdot y = x \cdot z \) | \( y = z \) |
| Uniquess of Complement | \( x + y = 1 \) AND \( x \cdot y = 0 \) | \( y = x' \) |
| Involution Law | \( (x')' \) | \( x \) |
| Complements of Constants | \( 0' \) | \( 1 \) |
| \( 1' \) | \( 0 \) | |
| De Morgans Laws | \( (x + y)' \) | \( x' \cdot y' \) |
| \( (x \cdot y)' \) | \( x' + y' \) |
Relation to other Algebra
Boolean algebra the underlying mathematical structure of sets and propositional logic. Its the reason the laws for sets and propositional logic are so similar.
TO unfold the secret laws and relations of those high faculties of thought by which all beyond the merely perceptive knowledge of the world and of ourselves is attains or matured, is a object which does not stand in need of commendation to a rational mind.
- [see page 23, George Bool]
Propositional algebra gives [see page 24, rise] to a boolean algebra where: \( 0 \equiv \text{False} \), \( 1 \equiv \text{true} \), \( + \equiv \lor \), \( \cdot \equiv \land \), and \( ' \equiv \neg \). Set algebra gives [see page 24, rise] to a boolean algebra where: \( 0 \equiv \varnothing \), \( 1 \equiv \mathcal{U} \), \( + \equiv \cup \), \( \cdot \equiv \cap \), and \( ' \equiv \overline{\phantom{x}} \).