Introduction to Lattices and Posets

Partially ordered sets (posets) and lattices form the mathematical bedrock for modeling hierarchical relationships, structured data, and algebraic logic. This guide details the transition from general ordered structures to the algebraic specifications of lattices, culminating in the formulation of Boolean algebra and canonical Boolean functions.

1. Lattices as Partially Ordered Sets (Posets)

A partially ordered set (poset) is a mathematical structure defined by a set $S$ combined with a binary relation $\le$ that is reflexive, antisymmetric, and transitive.

A lattice is a specialized poset $\langle L, \le \rangle$ in which every pair of elements $a, b \in L$ has a unique greatest lower bound (GLB) and a unique least upper bound (LUB).

text

       Lattice Example                      Non-Lattice Poset Example
       
            1 (LUB)                             d         e
           / \                                   \       / 
          /   \                                   \     /   
         a     b                                     c      
          \   /                                   /     \   
           \ /                                   /       \  
            0 (GLB)                             a         b
            
  (Every pair has a unique              (The pair {a, b} has upper bound c,
     GLB and unique LUB)                 but the pair {d, e} has multiple
                                         lower bounds with no unique GLB)

Meet and Join Operations

Greatest Lower Bound (GLB / Infimum / Meet): The largest element in $L$ that is smaller than or equal to both $a$ and $b$ . It is denoted algebraically as: $a \wedge b \quad \text{or} \quad a * b$
Least Upper Bound (LUB / Supremum / Join): The smallest element in $L$ that is larger than or equal to both and . It is denoted algebraically as:

For a poset to be a lattice, these bounds must exist and be unique for every single pair of elements within the set.

Core Examples of Lattices

The Power Set Lattice: Let $S$ $S$ be any set and $P(S)$ $P (S)$ be its power set. Under the subset relation $\subseteq$ $\subseteq$ , the poset $\langle P(S), \subseteq \rangle$ $⟨ P (S), \subseteq ⟩$ is a lattice.
- $\text{GLB}(A, B) = A \cap B$ (Set Intersection)

2. The Duality Principle

For any lattice $\langle L, \le \rangle$ , there exists an associated dual lattice $\langle L, \ge \rangle$ obtained by reversing the partial order relation.

The Duality Principle states:

If any statement (theorem or identity) is true for all lattices, then its dual statement—obtained by swapping all meet ( $*$ ) and join ( $+$ ) operators, and reversing all order relations ( $\le$ to $\ge$ and vice versa)—is also true for all lattices.

For example, if the identity $a * (a + b) = a$ holds, its dual identity is: $a + (a * b) = a$

This symmetry halves the effort required to prove general lattice properties, as proving one identity automatically validates its dual.

3. Algebraic Properties of Lattices

Lattices can be defined purely algebraically as a algebraic structure $\langle L, *, + \rangle$ containing a set $L$ and two binary operations satisfying the following four foundational postulates for all $a, b, c \in L$ :

| Postulate | Meet Operation ( $*$ ) | Join Operation ( $+$ ) | | :--- | :--- | :--- | | Idempotence | $a * a = a$ | $a + a = a$ | | Commutativity | $a * b = b * a$ | | | | | | | | | |

Inducing the Partial Order

The algebraic definition is equivalent to the poset definition. If we have an algebraic lattice, we can define the partial order relation $\le$ using either operation: $a \le b \iff a * b = a \iff a + b = b$

Proof of Poset Axioms via Algebraic Postulates

We can prove that the relation $\le$ induced by the algebraic operations is a valid partial order:

Reflexivity ( $a \le a$ ): From the idempotency of meet, we know $a * a = a$ . By the definition of the induced order, this directly implies $a \le a$ .
Antisymmetry ( $a \le b \text{ and } b \le a \implies a = b$ ): If , then . If , then . By commutativity, . Thus, substituting the values:

4. Isotonicity and Sublattices

Isotonicity

The partial order relation in any lattice is preserved under both meet and join operations. This property is called isotonicity.

$\text{If } a \le b, \text{ then for any } c \in L:$ $a * c \le b * c$ $a + c \le b + c$

Sublattices

A non-empty subset $S \subseteq L$ is a sublattice of $L$ if and only if it is closed under the operations of $L$ .

$\forall a, b \in S \implies (a * b) \in S \quad \text{and} \quad (a + b) \in S$

text

     Lattice L                        Subset S (Not a Sublattice)
     
        1                                     1
       / \                                   / 
      b   c                                 b   
     / \ /                                 / \  
    d   e                                 d   e 
     \ /                                   \ /  
      0                                     0
      
                                     (S is a poset under the same order,
                                      but LUB(d, e) in L is e, whereas in
                                      the subset S, the join is b. S is not
                                      closed under L's join operation.)

5. Direct Product and Homomorphisms

Direct Product

Given two lattices $\langle L_1, *_1, +_1 \rangle$ and $\langle L_2, *_2, +_2 \rangle$ , their is the lattice where operations are executed component-wise:

An important application is the $n$ -cube lattice $L^n$ , formed by the Cartesian product of $n$ two-element lattices $L = \{0, 1\}$ .

Lattice Homomorphisms

A function $g: L \to S$ between two lattices $L$ and $S$ is a homomorphism if it preserves both algebraic operations: $g(a * b) = g(a) * g(b)$

Isomorphism: A bijective (one-to-one and onto) homomorphism.
Endomorphism: A homomorphism mapping a lattice to itself ( $g: L \to L$ ).
Automorphism: A bijective endomorphism.

Every lattice homomorphism is inherently order-preserving: $a \le b \implies g(a) \le g(b)$

6. Special Types of Lattices

text

                     [ Posets ]
                         |
                 [ General Lattices ]
                         |
                 [ Bounded Lattices ]
                     /       \
                    /         \
       [ Complemented ]     [ Distributive ]
                    \         /
                     \       /
                 [ Boolean Algebras ]

Complete Lattices

A lattice is complete if every non-empty subset (finite or infinite) has both a greatest lower bound (GLB) and a least upper bound (LUB).

All finite lattices are complete.
Complete lattices must contain a unique least element (denoted $0$ ) and a unique greatest element (denoted $1$ ).

Bounded Lattices

A lattice $L$ is bounded if it contains a lower bound $0$ and an upper bound $1$ such that for all $a \in L$ : $a \le 1 \quad \text{and} \quad a \ge 0$

These elements satisfy the boundary conditions: $a * 0 = 0, \quad a * 1 = a$ $a + 0 = a, \quad a + 1 = 1$

Complemented Lattices

In a bounded lattice $L$ , an element $b \in L$ is a complement of $a \in L$ if: $a * b = 0 \quad \text{and} \quad a + b = 1$

A lattice is complemented if it is bounded and every element $a \in L$ has at least one complement $a' \in L$ .

Distributive Lattices

A lattice is distributive if the meet and join operations distribute over each other: $a * (b + c) = (a * b) + (a * c)$ $a + (b * c) = (a + b) * (a + c)$

Non-Distributive Templates

The most common non-distributive structures are the Pentagon lattice ( $N_5$ ) and the Diamond lattice ( $M_5$ ):

text

         Pentagon Lattice (N5)                 Diamond Lattice (M5)
         
                 1                                     1
                / \                                   /|\
               b   \                                 / | \
              /     c                               a  b  c
             a     /                                 \ | /
              \   /                                   \|/
                0                                      0

Theorem: A lattice is distributive if and only if it does not contain a sublattice isomorphic to $N_5$ or $M_5$ .
Theorem: Every chain (a totally ordered set) is a distributive lattice.
Theorem: In a distributive lattice, if an element $a$ has a complement $a'$ , that complement is .

7. Boolean Algebra as a Lattice

Formally, a Boolean algebra is defined as a complemented distributive lattice. It is written as a 6-tuple structure: $\langle B, *, +, ', 0, 1 \rangle$

Where:

$\langle B, *, + \rangle$ is a distributive lattice.
$0$ and $1$ are the unique lower and upper bounds of $B$ .
$'$ is the unary complement operation satisfying and for all .

Classic Examples

The Two-Element Boolean Algebra: $\mathbf{B_2} = \langle \{0, 1\}, \wedge, \vee, \neg, 0, 1 \rangle$ , which governs binary computer systems.
Power Set Boolean Algebra: $⟨ P (S), \cap, \cup, \sim, \emptyset,$ where represents the absolute set complement.

8. Atoms, Maxterms, and Canonical Forms

Atoms (Minterms) and Maxterms (Anti-atoms)

In any finite Boolean algebra:

Join-Irreducible Elements: Elements that cannot be represented as the join of other smaller elements.
Atoms (Minterms): The minimal non-zero elements of the algebra. An element $a \in B$ is an atom if $a \neq 0$ and for all $x \in B$ , $x \le a \implies x = 0$ or . Atoms directly cover the zero element ().

Boolean Functions

A Boolean function of $n$ variables is a mapping $f: B^n \to B$ , where $B = \{0, 1\}$ .

For $n$ input variables, there are $2^n$ distinct valuation states, leading to $2^{2^n}$ possible unique Boolean functions.

Canonical Representation of Boolean Functions

1. Sum-of-Products (SOP) / Disjunctive Normal Form (DNF)

Every Boolean function can be expressed uniquely as a sum (join) of distinct product terms (minterms). Each minterm contains every variable exactly once, in either its complemented or uncomplemented form.

Minterms are mutually exclusive: $m_i * m_j = 0$ for all $i \neq j$ .

2. Product-of-Sums (POS) / Conjunctive Normal Form (CNF)

Conversely, every Boolean function can be expressed uniquely as a product (meet) of distinct sum terms (maxterms).

Step-by-Step Canonical Form Conversions

Let us convert the Boolean expression $f(x, y) = x + y'$ into canonical Sum-of-Products (SOP) form.

Step 1: Identify Missing Variables

The expression contains two variables $x$ and $y$ .

The term $x$ is missing the variable $y$ .
The term $y'$ is missing the variable $x$ .

Applying the Idempotence Law ( $x y' + x y' = x y'$ ): $f (x, y) = x y + x y^{'} +$

This is the completed canonical SOP expression of the function.

Summary

A lattice is a poset where every pair of elements has a unique supremum (LUB, join) and infimum (GLB, meet).
Lattices can be defined as algebraic structures obeying idempotence, commutativity, associativity, and absorption laws.
The Duality Principle ensures that any valid lattice theorem remains valid if we swap meet/join operations and reverse inequality signs.
Distributive lattices are defined by the distribution of meet and join operations. In such lattices, complements are unique if they exist.
Boolean algebras are complemented, distributive lattices that serve as the foundation for binary logic and boolean functions.
Atoms (minterms) and maxterms represent the irreducible building blocks used to construct canonical SOP and POS representations of Boolean functions.

Assessed progress

Introduction to Lattices and Posets

Key Concepts

Lattice

Duality Principle

Distributive Lattice

Bounded & Complemented Lattice

Boolean Algebra

Quick Check

Discrete Mathematical Structures

Discrete Mathematical Structures