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:

  1. Reflexive: (a, a) ∈ R for all a ∈ A.
  2. Symmetric: If (a, b) ∈ R, then (b, a) ∈ R.
  3. 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:

  1. Reflexive: (a, a) ∈ R for all a ∈ A.
  2. Anti-symmetric: If (a, b) ∈ R and (b, a) ∈ R, then a = b.
  3. 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).
To check if a Hasse diagram represents a lattice, pick any two elements and verify they have a unique GLB (common ancestor) and a unique LUB (common descendant).

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.

  1. Algebraic Manipulation: Using Boolean algebra laws (De Morgan's, distributive, etc.) to simplify.
  2. Karnaugh Maps (K-Maps): A graphical method for functions of 2, 3, or 4 variables. (See notes for DSC 101, Unit 2).
  3. Quine-McCluskey (Tabulation) Method: A tabular method that is more systematic and can be programmed. (See notes for DSC 101, Unit 2).