Unit 5: Relations, Posets, Lattices & Boolean Algebra

1. Binary Relations and Foundational Properties

A binary relation $R$ from a set $A$ to a set $B$ is a subset of the Cartesian product $A \times B$. When $A = B$, $R \subseteq A \times A$ is called a binary relation on $A$. We write $a R b$ to denote $(a, b) \in R$.

Core Properties on Set $A$:

1. Reflexive: $\forall x \in A, \; (x, x) \in R$.

2. Irreflexive: $\forall x \in A, \; (x, x) \notin R$.

3. Symmetric: $\forall x, y \in A, \; (x, y) \in R \implies (y, x) \in R$.

4. Antisymmetric: $\forall x, y \in A, \; [(x, y) \in R \land (y, x) \in R] \implies x = y$.

5. Transitive: $\forall x, y, z \in A, \; [(x, y) \in R \land (y, z) \in R] \implies (x, z) \in R$.

2. Relational Closures and Warshall's Algorithm

The closure of a relation $R$ with respect to property $P$ is the minimal relation $R^* \supseteq R$ that satisfies property $P$.

• Reflexive Closure: $R \cup \Delta_A$, where $\Delta_A = \{(x, x) \mid x \in A\}$.
• Symmetric Closure: $R \cup R^{-1}$, where $R^{-1} = \{(y, x) \mid (x, y) \in R\}$.
• Transitive Closure ($R^+$): The reachability relation:

Warshall's Algorithm computes the transitive closure boolean matrix $W$ in $O(n^3)$ operations:

3. Equivalence Relations and Fundamental Partition Theorem

Definition 5.1 (Equivalence Relation): A relation $R$ on a set $A$ is an equivalence relation if and only if it is reflexive, symmetric, and transitive.

For any $a \in A$, the equivalence class of $a$ modulo $R$ is:

Theorem 5.1 (Fundamental Partition Theorem): Let $R$ be an equivalence relation on $A$.

1. For any $a, b \in A$, $[a] = [b] \iff (a, b) \in R$.
2. Any two equivalence classes are either identical or completely disjoint:

1. The family of equivalence classes partitions $A$ into non-empty, pairwise disjoint blocks whose union is $A$:

Conversely, any partition of $A$ uniquely induces an equivalence relation.

1. Partially Ordered Sets (Posets)

Definition 5.2 (Poset): A relation $R$ on set $A$ is a partial order (denoted $\le$ or $\preceq$) if it is reflexive, antisymmetric, and transitive. The pair $(A, \preceq)$ is called a partially ordered set or poset.

If every pair of elements in $A$ is comparable (i.e., $\forall x, y \in A$, either $x \preceq y$ or $y \preceq x$), then $(A, \preceq)$ is a totally ordered set (or chain / linear order).

2. Hasse Diagrams

A Hasse diagram is a graphical representation of a finite poset that eliminates redundant reflexive loops and transitive edges:

• Element $y$ covers $x$ (written $x \prec\!\!\cdot \; y$) if $x \prec y$ and there is no $z$ such that $x \prec z \prec y$.
• In the Hasse diagram, a directed upward line connects $x$ to $y$ if and only if $y$ covers $x$.

Extremal Elements in Posets:

• Maximal element: $m \in A$ such that $\forall x \in A, \; m \preceq x \implies x = m$.
• Minimal element: $m \in A$ such that $\forall x \in A, \; x \preceq m \implies x = m$.
• Greatest element (Maximum / Top $\mathbf{1}$): $g \in A$ such that $\forall x \in A, \; x \preceq g$ (unique if it exists).
• Least element (Minimum / Bottom $\mathbf{0}$): $\ell \in A$ such that $\forall x \in A, \; \ell \preceq x$ (unique if it exists).

3. Topological Sorting

A topological sort of a finite poset $(A, \preceq)$ is a linear extension $\le_L$ of $\preceq$ such that:

Algorithmically, topological sorting arranges the vertices of a Directed Acyclic Graph (DAG) such that every directed edge $(u, v)$ has $u$ appearing before $v$.

• Kahn's Algorithm: Repeatedly find a vertex with in-degree 0 (a minimal element), output it, and remove its outgoing edges. Runs in $O(|V| + |E|)$ time.

1. Poset-Theoretic Definition of Lattices

Let $(L, \preceq)$ be a poset. For any subset $S \subseteq L$:

• An upper bound of $S$ is $u \in L$ such that $\forall s \in S, s \preceq u$. The least upper bound (lub) or join is denoted $\sup(S)$ or $\bigvee S$. For two elements, $a \lor b = \text{lub}(a, b)$.
• A lower bound of $S$ is $\ell \in L$ such that $\forall s \in S, \ell \preceq s$. The greatest lower bound (glb) or meet is denoted $\inf(S)$ or $\bigwedge S$. For two elements, $a \land b = \text{glb}(a, b)$.

Definition 5.3 (Lattice): A poset $(L, \preceq)$ is a lattice if every pair of elements $\{a, b\} \subseteq L$ has a unique join ($a \lor b$) and a unique meet ($a \land b$).

2. Algebraic Definition of Lattices

Equivalently, a lattice is an algebraic structure $(L, \lor, \land)$ with two binary operations satisfying:

1. Idempotent Laws: $a \lor a = a, \quad a \land a = a$.

2. Commutative Laws: $a \lor b = b \lor a, \quad a \land b = b \land a$.

3. Associative Laws: $(a \lor b) \lor c = a \lor (b \lor c), \quad (a \land b) \land c = a \land (b \land c)$.

4. Absorption Laws: $a \lor (a \land b) = a, \quad a \land (a \lor b) = a$.

The partial order is recovered algebraically by:

3. Distributive, Bounded, and Complemented Lattices

• Distributive Lattice: Satisfies the distributive identities for all $a, b, c \in L$:

(Birkhoff's Theorem: A lattice is distributive iff it does not contain the pentagon lattice $N_5$ or the diamond lattice $M_3$ as a sublattice).

• Bounded Lattice: Contains a bottom element $\mathbf{0}$ and top element $\mathbf{1}$:

• Complemented Lattice: In a bounded lattice, an element $b$ is a complement of $a$ if $a \lor b = \mathbf{1}$ and $a \land b = \mathbf{0}$.

In a distributive lattice, complements are unique whenever they exist.

1. Axiomatic Definition of Boolean Algebra

Definition 5.4 (Boolean Algebra): A Boolean algebra is a 6-tuple $(B, +, \cdot, ', \mathbf{0}, \mathbf{1})$ consisting of a set $B$, two binary operations $+$ (join / OR) and $\cdot$ (meet / AND), a unary operation $'$ (complement / NOT), and two distinct constants $\mathbf{0}, \mathbf{1} \in B$ satisfying Huntington's axioms:

1. Closure: $\forall a, b \in B, \; a + b \in B \text{ and } a \cdot b \in B$.
2. Commutativity: $a + b = b + a$ and $a \cdot b = b \cdot a$.
3. Distributivity:

1. Identity Elements: $a + \mathbf{0} = a$ and $a \cdot \mathbf{1} = a$.
2. Complements: $a + a' = \mathbf{1}$ and $a \cdot a' = \mathbf{0}$.

2. Principle of Duality

The Duality Principle: Any algebraic theorem in Boolean algebra remains strictly valid if one interchanges $+$ with $\cdot$, and $\mathbf{0}$ with $\mathbf{1}$ throughout the entire statement.

3. Canonical Representations: SOP and POS

Let $f(x_1, x_2, \dots, x_n)$ be a Boolean function of $n$ variables.

1. Minterm ($m_i$): A product (AND) of $n$ literals in which each variable appears once in either uncomplemented or complemented form. There are $2^n$ possible minterms.

2. Canonical Sum-of-Products (SOP / DNF):

3. Maxterm ($M_i$): A sum (OR) of $n$ literals.

4. Canonical Product-of-Sums (POS / CNF):

1. Karnaugh Map (K-Map) Theory

A Karnaugh map is a visual representation of a Boolean function where adjacent cells represent minterms that differ by exactly one bit (Hamming distance 1). This is achieved by organizing row and column indices using Gray code sequences:

``` CD AB 00 01 11 10 00 m0 m1 m3 m2 01 m4 m5 m7 m6 11 m12 m13 m15 m14 10 m8 m9 m11 m10 ```

Looping Rules for Minimization:

• Groups (implicants) must be rectangular powers of two ($1, 2, 4, 8, 16$).
• Opposite edges wrap around (toroidal topology: top wraps to bottom, left wraps to right).
• Groups must be as large as possible.
• An Essential Prime Implicant (EPI) is an implicant containing at least one minterm $1$ that is not covered by any other prime implicant.

2. The Quine-McCluskey Algorithmic Reduction

For functions with $\ge 5$ variables, visual K-maps become unwieldy. The Quine-McCluskey algorithm provides an exact, tabular algebraic optimization:

1. Group minterms by the number of 1s in their binary representation (Hamming weight).
2. Compare terms in adjacent groups differing by a single bit position; combine them using $x y + x y' = x$ and mark with a dash ($-$).
3. Repeat iteratively until no further combinations are possible. The uncombined terms are the Prime Implicants (PI).
4. Construct the Prime Implicant Chart (PI rows $\times$ minterm columns).
5. Identify columns with a single $\times$ to select Essential Prime Implicants, delete covered columns, and solve the remaining minimal covering problem (via Petrick's method).