Unit 3: Ordering Relations, Lattices and Boolean Algebra
Table of Contents
3.1 Partial Ordering vs. Equivalence Relations
This unit builds on the relations from Unit 2.
Equivalence Relations
A relation R on set A is an equivalence relation if it is:
- Reflexive: (a, a) ∈ R for all a ∈ A.
- Symmetric: If (a, b) ∈ R, then (b, a) ∈ R.
- Transitive: If (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R.
An equivalence relation partitions a set A into disjoint equivalence classes. The class of a, denoted [a], is the set of all elements related to a.
Example: "Congruence modulo 3" on ℤ. [0] = \{..., -3, 0, 3, 6, ...\}, [1] = \{..., -2, 1, 4, 7, ...\}, [2] = \{..., -1, 2, 5, 8, ...\}.
Partial Ordering Relations (Posets)
A relation R on set A is a partial order if it is:
- Reflexive: (a, a) ∈ R for all a ∈ A.
- Anti-symmetric: If (a, b) ∈ R and (b, a) ∈ R, then a = b.
- Transitive: If (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R.
Example: The "divides" relation on the set \{1, 2, 3, 6\}.
3.2 Lattices
In a poset (S, ≤), for any two elements a, b ∈ S:
- Upper Bound: u is an upper bound of \{a, b\} if a ≤ u and b ≤ u.
- Least Upper Bound (LUB): The smallest of all upper bounds. Denoted a \lor b (join).
- Lower Bound: l is a lower bound of \{a, b\} if l ≤ a and l ≤ b.
- Greatest Lower Bound (GLB): The largest of all lower bounds. Denoted a \land b (meet).
A lattice is a poset in which every pair of elements has a unique LUB (join) and a unique GLB (meet).
3.3 Bounded, Distributive, and Complemented Lattices
- Bounded Lattices: A lattice that has a greatest element (I or 1) (the LUB of all elements) and a least element (0) (the GLB of all elements).
- a \lor 1 = 1, a \land 1 = a
- a \lor 0 = a, a \land 0 = 0
- Distributive Lattices: A lattice that satisfies the distributive laws for all a, b, c:
- a \land (b \lor c) = (a \land b) \lor (a \land c)
- a \lor (b \land c) = (a \lor b) \land (a \lor c)
- Complements: In a bounded lattice, a and b are complements if a \lor b = 1 and a \land b = 0. An element can have zero, one, or multiple complements.
- Complemented Lattices: A bounded lattice where every element has at least one complement.
3.4 Introduction to Boolean Algebra
A Boolean Algebra is a complemented, distributive lattice.
This is the mathematical foundation for the digital logic circuits (from DSC 101). A Boolean algebra (B, +, ·, ', 0, 1) consists of a set B, two binary operators (+ for join/OR, · for meet/AND), a unary operator (' for complement/NOT), and the bounds 0 and 1, satisfying specific axioms (identity, complement, commutative, distributive).
Example: The set B = \{0, 1\} with the standard logic gates (OR, AND, NOT) is the simplest Boolean algebra. The power set P(A) with operators (∪, ∩, ') also forms a Boolean algebra.
3.5 Boolean Functions: Representation and Minimization
Boolean Functions
A Boolean function f: Bn \to B maps n inputs from a Boolean set B (e.g., \{0, 1\}) to a single output.
Representation
Any Boolean function can be represented in Sum-of-Products (SOP) form (like DNF from Unit 1) or Product-of-Sums (POS) form (like CNF from Unit 1).
- SOP: A sum (OR) of product (AND) terms. Example: f(x,y,z) = x'y'z + xyz'
- POS: A product (AND) of sum (OR) terms. Example: f(x,y,z) = (x+y)(x'+z)
Minimization of Boolean Functions
The goal is to find the simplest equivalent expression (one that uses the fewest gates or literals). This is a direct application from DSC 101.
- Algebraic Manipulation: Using Boolean algebra laws (De Morgan's, distributive, etc.) to simplify.
- Karnaugh Maps (K-Maps): A graphical method for functions of 2, 3, or 4 variables. (See notes for DSC 101, Unit 2).
- Quine-McCluskey (Tabulation) Method: A tabular method that is more systematic and can be programmed. (See notes for DSC 101, Unit 2).