Lattice and Boolean Algebra

Lecturer

Li Hui

grid

The lattice defined by the partially ordered set

A partially ordered set ${\langle}S, {\leq}{\rangle}$, any subset $T$ ($T{\subseteq}S$) may not have a maximum lower bound and a minimum upper bound. For example, take the partially ordered set as shown in the figure.

$S=\{a, b, c, d, e, f\}$

The minimum upper bound $c$ of $T_1=\{a, b\}$ has no maximum lower bound;

$T_2=\{e, f\}$ has no minimum upper bound. The maximum lower bound is $d$;

$T_3=\{c, d\}$The minimum upper bound is $d$, and the maximum lower bound is $c$.

The following partially ordered sets all have a common property.

It is in this partially ordered set that any two elements have a minimum upper bound and a maximum lower bound.

We call a partially ordered set with this property a lattice.

Definition: Suppose ${\langle}L, {\leq}{\rangle}$ is a partially ordered set. If any two elements $a$ and $b$ in $L$ have a minimum upper bound and a maximum lower bound in L, then ${\langle}L, {\leq}{\rangle}$ is called a lattice. The lattice defined in this way is also called partially ordered lattice.

Generally, $a{\vee}b$, $LUB\{a, b\}$ or $sup\{a, b\}$ are used to represent the minimum upper bound (join or supremum) of $a$ and $b$. Use $a{\wedge}b$, $GLB\{a, b\}$ or $inf\{a, b\}$ to represent the maximum lower bound (meet or infimum) of $a$ and $b$. ${\vee}$ and ${\wedge}$ are called the join operation and meet operation, respectively.

Example: Suppose $Z^+$ is a set of positive integers, define the divisibility relationship | on $Z^+$: For any $a, b{\in}Z$ For ${\forall}a, b{\in}Z^+$, ${\langle}a, b{\rangle}{\in}|$ if and only if $a$ divides $b$, Then the partially ordered set ${\langle} Z^+, | {\rangle}$ is a lattice.

Proof:\[|=\{{\langle}a, b{\rangle}| a, b{\in}Z^+, a|b\}{\rangle}\] For ${\forall}a, b{\in}Z^+$, their minimum upper bound and maximum lower bound are the least common multiple and greatest common divisor of the two elements, that is: \[a{\vee}b=lcm(a, b){\in}Z^+, \] \[a{\wedge}b=gcd(a, b){\in}Z^+,\] Therefore ${\langle}Z^+, |{\rangle}$ is a lattice.

Example: For any set $S, P(S)$ is the power set of $S$, then the partially ordered set ${\langle}P(S), \subseteq{\rangle}$ is a lattice.

Proof: \[{\subseteq} = \{{\langle}X, Y{\rangle}|X, Y{\in}P(S), X{\subseteq}Y\}\] Because ${\subseteq}$ is a partial ordering relationship on $P(S)$, and ${\forall}A, B{\in}P(S)$, their minimum upper bound and maximum lower bound are the union and intersection of the two sets respectively.

Right now \[A{\vee}B=A{\cup}B{\in}P(S)\] \[A{\wedge}B=A{\cap}B{\in}P(S)\] So it is a lattice. ${\langle}P(S), {\subseteq}{\rangle}$ is called the power set lattice of the set.

Example: Suppose $S=\{a, b\}$,

$P(S)=\{\phi, \{a\}, \{b\}, \{a, b\}\}$,

Then ${\langle}P(S), {\subseteq}{\rangle}$ is the lattice.

Example: Suppose $n$ is a positive integer, $S_n$ is the set of all positive factors of $n$. For example: \[S_6=\{1, 2, 3, 6\}\] \[S_8=\{1, 2, 4, 8\}\] \[S_{24}=\{1, 2, 3, 4, 6, 8, 12, 24\}\] Also assuming that | is a divisibility relation, then the partially ordered set ${\langle}S_n, |{\rangle}$ is a lattice.

Suppose ${\langle}L, {\leq}{\rangle}$ are lattice, ${\geq}$ is the inverse relation of ${\leq}$, then lattice ${\langle}L, {\geq}{\rangle}$ is called the dual lattice of lattice ${\langle}L, {\leq}{\rangle}$ (each other is dual lattice), The relation ${\leq}$ and the relation ${\geq}$ are called dual relations.

Theorem: If ${\langle}L, {\leq}{\rangle}$ is a lattice, then ${\langle}L, {\geq}{\rangle}$ is also a lattice, and the union-preserving operation and intersection-preserving operation (expressed by ${\bigoplus}$ and ${\bigotimes}$) in the lattice ${\langle}L, {\geq}{\rangle}$ are the same as the lattice ${}L, The union-preserving operation and intersection-preserving operation (represented by ${\vee}$ and ${\wedge}$) in {}{}$ satisfy the following relationship:

For ${\forall} a, b{\in}L$, we have $a{\vee}b=a{\bigotimes}b, a{\wedge}b=a{\bigoplus}b$.

Definition: The dual proposition of a proposition $P$ consisting of the elements in the lattice ${\langle}L, {\leq}{\rangle}$ and the symbols ${\vee}, {\wedge}, =$ and ${\leq}$ is the proposition $P^*$, which replaces ${\leq}$ in $P$ with ${\geq}$, The proposition obtained by replacing ${\vee}$ with ${\wedge}$ and ${\wedge}$ with ${\vee}$.

For example, the dual form of the proposition $(a{\vee}b){\wedge}c{\leq}c$ is the proposition $(a{\wedge}b){\vee}c{\geq}c$. In fact, $(a{\vee}b){\wedge}c{\leq}c$ is the lattice ${\langle}L, {\leq}{\rangle}$, and $(a{\wedge}b){\vee}c{\geq}c$ is a proposition in the lattice ${\langle}L, {\geq}{\rangle}$ proposition.

Theorem: (Duality Principle) For any true proposition $P$ in the lattice ${\langle}L, {\leq}{\rangle}$, its dual proposition $P^*$ is also a true proposition.

Example: The dual proposition $A{\cup}B{\supseteq}A$ of the true proposition $A{\cap}B{\subseteq}A$ in the lattice ${\langle}P(S), {\subseteq}{\rangle}$ is also a true proposition.

Theorem: Suppose ${\langle}L, {\leq}{\rangle}$ is a lattice, then for any elements $a$, $b$ and $c$ in L:

$a{\leq}a{\vee}b, b{\leq}a{\vee}b$, $a{\wedge}b{\leq}a, a{\wedge}b{\leq}b$
If $a{\leq}b, a{\leq}c$, then: $a{\leq}b{\wedge}c$. If $a{\leq}c, b{\leq}c$, then: $a{\vee}b{\leq}c$.
If $a{\leq}b, c{\leq}d$, then: $a{\vee}c{\leq}b{\vee}d$, $a{\wedge}c{\leq}b{\wedge}d$.
If $b{\leq}c$, then: $a{\vee}b{\leq}a{\vee}c$, $a{\wedge}b{\leq}a{\wedge}c$.

Theorem: Suppose ${\langle}L, {\leq}{\rangle}$ is a lattice, then for any elements $a$, $b$ and $c$ in $L$, the following laws hold.

Idempotence law $a{\vee}a=a, a{\wedge}a=a$
Commutative law $a{\vee}b=b{\vee}a, a{\wedge}b=b{\wedge}a$
Associative law $(a{\vee}b){\vee}c=a{\vee}(b{\vee}c)$, $(a{\wedge}b){\wedge}c=a{\wedge}(b{\wedge}c)$
Absorption law $a{\vee}(a{\wedge}b)=a$, $a{\wedge}(a{\vee}b)=a$

Theorem: Suppose ${\langle}L, {\leq}{\rangle}$ is a lattice, then for any elements $a$ and $b$ in L, we have $a{\leq}b{\Leftrightarrow}a{\wedge}b=a{\Leftrightarrow}a{\vee}b=b.$

Theorem: Suppose ${\langle}L, {\leq}{\rangle}$ is a lattice, then for any elements $a$, $b$ and $c$ in $L$, we have:

$a{\vee}(b{\wedge}c){\leq}(a{\vee}b){\wedge}(a{\vee}c)$.
$a{\wedge}(b{\vee}c){\geq}(a{\wedge}b){\vee}(a{\wedge}c)$.

The relation ${\geq}$ is the dual relation of the relation ${\leq}$.

Theorem: Suppose ${\langle}L, {\leq}{\rangle}$ is a lattice, then for any elements $a$, $b$ and $c$ in $L$, we have: $a{\leq}c{\Leftrightarrow}a{\vee}(b{\wedge}c){\leq}(a{\vee}b){\wedge}c.$

\[ \begin{array}{ll} {\langle}L, {\leq}{\rangle}& {\langle}L, {\geq}{\rangle}\\ a{\leq}a & a{\geq}a \\ a{\leq}b{and}b{\leq}a{\Rightarrow}a=b&a{\geq}b{and}b{\geq}a{\Rightarrow}a=b\\ a{\leq}b{and}b{\leq}c{\Rightarrow}a{\leq}c&a{\geq}b{and}b{\geq}c{\Rightarrow}a{\geq}c\\ a{\wedge}b{\leq}a;a{\wedge}b{\leq}b&a{\bigoplus}b{\geq}a;a{\bigoplus}b{\geq}b\\ c{\leq}a{and}c{\leq}b{\Rightarrow}c{\leq}a{\wedge}b&c{\geq}a{and}c{\geq}b{\Rightarrow}c{\geq}a{\bigoplus}b\\ a{\wedge}b=b{\wedge}a & a{\bigoplus}b=b{\bigoplus}a \\ (a{\wedge}b){\wedge}c=a{\wedge}(b{\wedge}c) & (a{\bigoplus}b){\bigoplus}c=a{\bigoplus}(b{\bigoplus}c)\\ a{\wedge}(a{\vee}b)=a & a{\bigoplus}(a{\bigotimes}b)=a\\ a{\wedge}a=a & a{\bigoplus}a=a\\ \end{array} \]

\[ \begin{array}{ll} {\langle}L, {\leq}{\rangle}& {\langle}L, {\geq}{\rangle}\\ a{\leq}b{\Rightarrow}a{\wedge}b=a & a{\geq}b{\Rightarrow}a{\bigoplus}b=a\\ a{\leq}b{\Rightarrow}a{\vee}b=b & a{\geq}b{\Rightarrow}a{\bigotimes}b=b\\ a{\leq}b{and}c{\leq}d& a{\geq}b{and}c{\geq}d\\ {\Rightarrow}a{\wedge}c{\leq}b{\wedge}d & {\Rightarrow}a{\bigoplus}c{\geq}b{\bigoplus}d\\ a{\leq}b{\Rightarrow}a{\wedge}c{\leq}b{\wedge}c & a{\geq}b{\Rightarrow}a{\bigoplus}c{\geq}b{\bigoplus}c \\ a{\vee}(b{\wedge}c){\leq}(a{\vee}b){\wedge}(a{\vee}c) & a{\bigotimes}(b{\bigoplus}c){\geq}(a{\bigotimes}b){\bigoplus}(a{\bigotimes}c)\\ a{\leq}c{\Leftrightarrow} & a{\geq}c{\Leftrightarrow}\\ a{\vee}(b{\wedge}c){\leq}(a{\vee}b){\wedge}c & a{\bigotimes}(b{\bigoplus}c){\leq}(a{\bigotimes}b){\bigoplus}c \end{array} \]

Lattice defined by algebraic system

Definition: Suppose ${\langle}L, {\vee}, {\wedge}{\rangle}$ (or ${\langle}L, {\wedge}, {\vee}{\rangle}$) is an algebraic system, ${\vee}$ and ${\wedge}$ are two binary operations on $L$, if these two operations satisfy the elements in $L$:

Commutative law $a{\vee}b=b{\vee}a$, $a{\wedge}b=b{\wedge}a$
Associative law $(a{\vee}b){\vee}c=a{\vee}(b{\vee}c)$, $(a{\wedge}b){\wedge}c=a{\wedge}(b{\wedge}c)$
Absorption law $a{\vee}(a{\wedge}b)=a$, $a{\wedge}(a{\vee}b)=a$

Then the algebraic system ${\langle}L, {\vee}, {\wedge}{\rangle}$ is said to be a lattice. The lattice defined in this way is also called algebraic lattice.

Theorem: The lattice defined by an algebraic system and the lattice defined by a partially ordered set are equivalent. That is, an algebraic lattice must be a partially ordered lattice; a partially ordered lattice must be an algebraic lattice.

Example: For any set $S, P(S)$ is the power set of $S$. The union ${\cup}$ and the intersection ${\cap}$ of the sets are two binary operations on $P(S)$, which satisfy the commutative law, associative law and absorption law, so ${\langle}P(S), {\cup}, {\cap}{\rangle}$ is a lattice.

It is consistent with the lattice ${\langle}P(S), {\subseteq}{\rangle}$ mentioned earlier, and for any $A, B{\in}P(S)$, we have \[A{\subseteq}B{\Leftrightarrow}A{\cap}B=A{\Leftrightarrow}A{\cup}B=B.\]

Example: For the algebraic system ${\langle}N, {\vee}, {\wedge}{\rangle}$, the two binary operations ${\vee}$, ${\wedge}$ are respectively defined as: for ${\forall}a, b{\in}N$, $a{\vee}b=max\{a, b\}, a {\wedge} b=min\{a, b\}$. Prove: ${\langle}N, {\vee}, {\wedge}{\rangle}$ is a lattice.

prove:

Commutative law. ${\forall}a, b{\in}N$, $a{\vee}b=max\{a, b\}=max\{b, a\}=b{\vee}a$.
Associative law. ${\forall}a, b, c{\in}N$, $a{\vee}(b{\vee}c)=max(a, max\{b, c\})=max(a, b, c) = max(max(a, b), c)=(a{\vee}b){\vee}c$. $\,\,a{\wedge}(b{\wedge}c)=min(a, min\{b, c\})=min(a, b, c) =min(min(a, b), c)=(a{\wedge}b){\wedge}c$.
Absorption law. ${\forall}a, b, c{\in}N$, $a{\vee}(a{\wedge}b)= a{\vee}min(a, b)=max(a, min(a, b))=a$, $a{\wedge}(a{\vee}b)= a{\wedge}max(a, b)=min(a, max(a, b))=a$.

So ${\langle}N, {\vee}, {\wedge}{\rangle}$ is a lattice. Similarly, ${\langle}Z, {\vee}, {\wedge}{\rangle}$ is also a lattice. The partial order lattice corresponding to ${\langle}N, {\vee}, {\wedge}{\rangle}$ and ${\langle}Z, {\vee}, {\wedge}{\rangle}$ is ${\langle}N, {\leq}{\rangle}$ and ${\langle}Z, {\leq}{\rangle}$, that is, the less than or equal relationship on the natural number set, A lattice formed by the less than or equal relation on the set of integers.

Homomorphism of sublattice and lattice

Sublattice

Definition: Suppose ${\langle}L, {\vee}, {\wedge}{\rangle}$ is a lattice, and $S$ is a non-empty subset of $L$. If ${\langle}S, {\vee}, {\wedge}{\rangle}$ still forms a lattice, then ${\langle}S, {\vee}, {\wedge}{\rangle}$ is called a sublattice of ${\langle}L, {\vee}, {\wedge}{\rangle}$.

Definition: Suppose ${\langle}L, {\vee}, {\wedge}{\rangle}$ is a lattice, $S$ is a non-empty subset of $L$, if for any elements $a$ and $b$ in $S$, there is:

$a{\vee}b{\in}S$
$a{\wedge}b{\in}S$

Then ${\langle}S, {\vee}, {\wedge}{\rangle}$ is said to be a sublattice of ${\langle}L, {\vee}, {\wedge}{\rangle}$.

The sublattice must be a lattice. Because when the operation is restricted to $S$, the commutative law, associative law and absorption law are also established.

Example: Assume ${\langle}Z, {\vee}, {\wedge}{\rangle}$ is a lattice, and the two binary operations ${\vee}$ and ${\wedge}$ are:

For any $a, b{\in}Z$, we have: $a{\vee}b=max\{a, b\}, \,\,a{\wedge}b=min\{a, b\}$.

Suppose $Z^+$ is the set of all positive integers. Obviously $Z^+{\subseteq}Z$ is not empty, and for any $a, b{\in}Z^+$, there is: \[a{\vee}b=max\{a, b\}{\in}Z^+, \,\,a{\wedge}b=min\{a, b\}{\in}Z^+.\] Therefore, ${\langle} Z^+, {\vee}, {\wedge}{\rangle}$ is the sublattice of ${\langle}Z, {\vee}, {\wedge}{\rangle}$.

The corresponding partial order lattice is: ${\langle}Z^+, {\leq}{\rangle}$ and ${\langle}Z, {\leq}{\rangle}$.

When the lattice is defined in the form of a partially ordered set ${\langle}L, {\leq}{\rangle}$, another definition of the sublattice:

Definition: Let ${\langle}L, {\leq}{\rangle}$ be a lattice, $S$ be a non-empty subset of $L$, if for any $a, b{\in}S$, $\{a, b\}$, the minimum upper bound $a{\vee}b$ and the maximum lower bound $a{\wedge}b$ obtained in $L$ are still in $S$, then it is called ${\langle}S, {\leq}{\rangle}$ is the sublattice of ${\langle}L, {\leq}{\rangle}$.

Example: Suppose ${\langle}L, {\leq}{\rangle}$ is a lattice, where: \[L=\{a, b, c, d, e, f, g, h, \},\] The Hasse diagram is shown in the figure:

Take \[S_1=\{a, b, d, f\}\] \[S_2=\{c, e, g, h\}\] \[S_3=\{a, b, c, d, e, g, h\}\] Determine which of $S_1$, $S_2$ and $S_3$ can form the sublattice of $L$.

S₁:{a, b, d, f} and S₂:{c, e, g, h}, are both sublattices of L

S₃:{a, b, c, d, e, g, h}, S₃ is a lattice, but not a sublattice of L, because the maximum lower bound f of b and d is not within S₃.

Example: Suppose ${\langle}L, {\leq}{\rangle}$ is a grid, $a{\in}L, S{\subseteq}L$ is defined as: \[S=\{x|x{\in}L, a{\leq}x\}\] Then ${\langle}S, {\leq}{\rangle}$ is the sublattice of ${\langle}L, {\leq}{\rangle}$.

Proof: For ${\forall}x_1, x_2{\in}S{\subseteq}L$, we have: \[x_1{\vee}x_2{\in}L, x_1{\wedge}x_2{\in}L,\,\,\,a{\leq}x_1, a{\leq}x_2\] Obtained: $a{\leq}x_1{\vee}x_2$, $a{\leq}x_1{\wedge}x_2$,

Therefore: $x_1{\vee}x_2{\in}S$, $x_1{\wedge}x_2{\in}S$,

Therefore ${\langle}S, {\leq}{\rangle}$ is the sublattice of ${\langle}L, {\leq}{\rangle}$.

Homomorphisms of Lattice

Definition: Suppose ${\langle}L, {\vee}, {\wedge}{\rangle}$ and ${\langle}S, {\bigoplus}, {\bigotimes}{\rangle}$ are two grids. If there is a mapping $f$:$L{\rightarrow}S$, then for ${\forall}a, b{\in}L$, there is:

\[f(a{\vee}b)=f(a){\bigoplus}f(b)\] \[f(a{\wedge}b)= f(a){\bigotimes}f(b)\]

Then $f$ is said to be a lattice homomorphic mapping from ${\langle}L, {\vee}, {\wedge}{\rangle}$ to ${\langle}S, {\bigoplus}, {\bigotimes}{\rangle}$, referred to as homomorphic mapping.

If $f$ is injective, surjective or bijective, then $f$ is said to be monomorphic mapping, full homomorphic mapping and isomorphic mapping respectively.

In particular, the lattice homomorphic mapping from ${\langle}L, {\vee}, {\wedge}{\rangle}$ to ${\langle}L, {\vee}, {\wedge}{\rangle}$ is called automorphic mapping; The lattice isomorphism mapping from ${\langle}L, {\vee}, {\wedge}{\rangle}$ to ${\langle}L, {\vee}, {\wedge}{\rangle}$ is called automorphism mapping.

If there is an isomorphic mapping from ${\langle}L, {\vee}, {\wedge}{\rangle}$ to ${\langle}S, {\bigoplus}, {\bigotimes}{\rangle}$, it is called ${\langle}L, {\vee}, {\wedge}{\rangle}$ and ${\langle}S, {\bigoplus}, {\bigotimes}{\rangle}$ are isomorphic. Two isomorphic Getchhasian graphs are the same.

Example: Suppose ${\langle}Z^+, {\vee}, {\wedge}{\rangle}$ is a lattice, where ${\vee}, {\wedge}$ is defined as for any $m, n{\in}Z^+$, we have: \[m{\vee}n=max\{m, n\}, m{\wedge}n=min\{m, n\}\] Also assume the grid ${\langle}S, {\bigoplus}, {\bigotimes}{\rangle}$, where: $S=\{3^k|k{\in}Z^+\}$. Define the binary operations ${\bigoplus}$ and ${\bigotimes}$ on $S$ as: for any $3^m, 3^n{\in}S$, there is: \[3^m{\bigoplus}3^n=3^{max\{m, n\}},\,\,\,3^m{\bigotimes}3^n=3^{min\{m, n\}}.\]

Define the bijective function $f:m{\rightarrow}3^m$ from $Z^+$ to $S$. Verify: $f$ is an isomorphic mapping from ${\langle}Z^+, {\vee}, {\wedge}{\rangle}$ to ${\langle}S, {\bigoplus}, {\bigotimes}{\rangle}$.

Proof: For ${\forall}m, n{\in}Z^+$.

\[f (m{\vee}n) = f (max\{m, n\})=3^{max\{m, n\}}=3^m{\bigoplus}3^n = f (m){\bigoplus}f (n)\] \[f (m{\wedge}n) = f (min\{m, n\})=3^{min\{m, n\}}=3^m{\bigotimes}3^n = f (m){\bigotimes}f (n)\] Therefore, $f$ is a lattice homomorphic mapping from ${\langle} Z^+, {\vee}, {\wedge}{\rangle}$ to ${\langle}S, {\bigoplus}, {\bigotimes}{\rangle}$.

And because $f$ is bijective, $f$ is also an isomorphic mapping from ${\langle}Z^+, {\vee}, {\wedge}{\rangle}$ to ${\langle}S, {\bigoplus}, {\bigotimes}{\rangle}$.

Definition: Suppose ${\langle}L, {\leq}_L{\rangle}$ and ${\langle}S, {\leq}_S{\rangle}$ are two lattices. If there is a mapping $f:L{\rightarrow}S$, then any element $a$, $b$ in $L$. When $a{\leq}_Lb$, there is $f(a){\leq}_Sf(b)$, then $f$ is said to be a lattice order-preserving mapping (order-preserving mapping) from ${\langle}L, {\leq}_L{\rangle}$ to ${\langle}S, {\leq}_S{\rangle}$, which is referred to as order-preserving mapping.

Theorem: Suppose ${\langle}L, {\leq}_L{\rangle}$ and ${\langle}S, {\leq}_S{\rangle}$ are two lattice.

Mapping $f:L{\rightarrow}S$, if $f$ is a homomorphic mapping from ${\langle}L, {\vee}, {\wedge}{\rangle}$ to ${\langle}S, {\bigoplus}, {\bigotimes}{\rangle}$, then $f$ is an order-preserving mapping.

That is, for any $a, b{\in}L$, if $a{\leq}_Lb$, there is: $f(a){\leq}_Sf(b)$.

Among them: ${\leq}_L$ is the partial ordering relationship on the set $L$ corresponding to the operations ${\vee}$ and ${\wedge}$, ${\leq}_S$ is the partial ordering relationship on the set $S$ corresponding to the operations ${\bigoplus}$ and ${\bigotimes}$.

Example: ${\langle}S, {\leq}{\rangle}$ is a lattice, where $S=\{a, b, c, d, e\}$, As shown in the figure, ${\langle}P(S), {\subseteq}{\rangle}$ is a power set lattice. Define mapping: $f:S{\rightarrow}P(S)$, so that ${\forall}x{\in}S$, we have: \[f(x)=\{y|y{\in}S, y{\leq}x\}\] Ask whether $f$ is an order-preserving mapping? Is it a homomorphic mapping?

Solution: $f(a)=\{y|y{\in}S, y{\leq}a\}=\{a, b, c, d, e\}$ \[f(b)=\{y|y{\in}S, y{\leq}b\}=\{b, e\}\] \[f(c)=\{y|y{\in}S, y{\leq}c\}=\{c, e\}\] \[f(d)=\{y|y{\in}S, y{\leq}d\}=\{d, e\}\] \[f(e)=\{y|y{\in}S, y{\leq}e\}=\{e\}\] When $x{\leq}y$ is $f(x){\subseteq}f(y)$, so $f$ is an order-preserving mapping.

However, $b{\vee}d=a$, $f(b{\vee}d){\neq}f(b){\cup}f(d)$. Therefore $f$ is not a homomorphic mapping.

Example: As shown in the figure, the lattices ${\langle}L, {\leq}_L{\rangle}$ and ${\langle}S, {\leq}_S{\rangle}$ represented by the two Hasse diagrams define the mapping:

$f(a_1)=b_1$, $f(a_2)= b_2$

$f(a_3)= b_2$, $f(a_4)= b_3$

Obviously $f$ is an order-preserving mapping from ${\langle}L, {\leq}_L{\rangle}$ to ${\langle}S, {\leq}_S{\rangle}$;

But it is not a homomorphic mapping. because:

$f(a_2{\vee}_La_3)=f(a_1)=b_1$,

$f(a_2){\vee}_Sf(a_3)=b_2{\vee}_Sb_2 =b_2$,

$f(a_2{\vee}_{L}a_3){\neq}f(a_2){\vee}_Sf(a_3)$.

Distribution and complementation

Distribution grid

Definition: Suppose ${\langle}L, {\vee}, {\wedge}{\rangle}$ is a lattice. If ${\vee}$ satisfies the distributive law for ${\wedge}$ and ${\wedge}$ for ${\vee}$, that is, for any $a, b, c{\in}L$, there is: \[a{\vee}(b{\wedge}c) = (a{\vee}b){\wedge}(a{\vee}c)\] \[a{\wedge}(b{\vee}c) = (a{\wedge}b){\vee}(a{\wedge}c)\] Then ${\langle}L, {\vee}, {\wedge}{\rangle}$ is said to be a distributive lattice.

Try to prove: ${\langle}P(S), {\cup}, {\cap}{\rangle}$ is a distribution lattice. Among them, $S$ is any set, $P(S)$ is the power set of $S$, ${\cup}$ is the union of sets, and ${\cap}$ is the intersection of sets.

prove: Since ${\langle}P(S), {\cup}, {\cap}{\rangle}$ is a lattice, And for any $A, B, C{\in}P(S)$, we have \[A{\cup}(B{\cap}C)=(A{\cup}B){\cap}(A{\cup}C),\,\,\,A{\cap}(B{\cup}C)=(A{\cap}B){\cup}(A{\cap}C)\] is established, so ${\langle}P(S), {\cup}, {\cap}{\rangle}$ is a distributive lattice.

An example that is not a distribution grid (diamond grid):

\[b{\wedge}(c{\vee}d)=b{\wedge}a=b\]

\[(b{\wedge}c){\vee}(b{\wedge}d)=e{\vee}e=e\] so:

\[b{\wedge}(c{\vee}d)≠(b{\wedge}c){\vee}(b{\wedge}d)\]

Examples that are not distribution grids (pentagonal grid):

\[c{\wedge}(b{\vee}d)=c{\wedge}a=c\]

\[(c{\wedge}b){\vee}(c{\wedge}d)=e{\vee}d=d\] so:

\[c{\wedge}(b{\vee}d){\neq}(c{\wedge}b){\vee}(c{\wedge}d).\]

Theorem: In the lattice ${\langle}L, {\vee}, {\wedge}{\rangle}$, if the intersection-preserving operation ${\wedge}$ is distributable to the union-preserving operation ${\vee}$, then the union-preserving operation ${\vee}$ must also be distributable to the intersection-preserving operation ${\wedge}$. vice versa.

Proof: Let $a, b, c$ be any elements in the lattice, if \[a{\wedge}(b{\vee}c)=(a{\wedge}b){\vee}(a{\wedge}c)\] but \[(a{\vee}b){\boxed\wedge}(a{\boxed\vee}c)\] \[=((a{\vee}b){\boxed\wedge}a){\boxed\vee}((a{\vee}b){\boxed\wedge}c)\] \[=a{\vee}((a{\boxed\vee}b){\boxed\wedge}c)\] \[=a{\vee}({(a{\boxed\wedge}c){\boxed\vee}(b{\boxed\wedge}c)})\] \[=a{\vee}(b{\wedge}c).\] The other half can prove the same thing.

Theorem: Suppose ${\langle}L, {\vee}, {\wedge}{\rangle}$ is a distributive lattice, for any $a, b, c{\in}L$, if $a{\wedge}b=a{\wedge}c, a{\vee}b=a{\vee}c$ Established, then $b=c$.

Proof: Because $(a{\wedge}b){\vee}c=(a{\wedge}c){\vee}c=c$, and \[(a{\wedge}b){\vee}c=(a{\vee}c){\wedge}(b{\vee}c)\] \[=(a{\vee}b){\wedge}(b{\vee}c)\] \[=b{\vee}(a{\wedge}c)\] \[=b{\vee}(a{\wedge}b)\] \[=b\] Therefore $b=c$.

Theorem: The necessary and sufficient conditions for the lattice ${\langle}L, {\vee}, {\wedge}{\rangle}$ to be a distributive lattice are: ${\langle}L, {\vee}, {\wedge}{\rangle}$ does not contain any sublattice isomorphic to the diamond lattice and the pentagonal lattice.

Contains diamond grid, not distribution grid

Contains pentagonal grid, not distribution grid

There is a complement

Definition: For the lattice ${\langle}L, {\vee}, {\wedge}{\rangle}$, if the number of elements in $L$ is limited, then ${\langle}L, {\vee}, {\wedge}{\rangle}$ is called finite lattice.

Example: For the set $S=\{a, b\}$, then ${\langle}P(S), {\cup}, {\cap}{\rangle}$ is a finite lattice.

Because: $P(S)=\{\phi, \{a\}, \{b\}, \{a, b\}\}$ is a finite set.

Example: For the lattice ${\langle}L, {\leq}{\rangle}, {\leq}$, the Haas diagram is as shown in the figure,

Then ${\langle}L, {\leq}{\rangle}$ is a finite lattice.

Definition: For the lattice ${\langle}L, {\vee}, {\wedge}{\rangle}$, if there is an element $a{\in}L$, and for ${\forall}x{\in}L$, there is $x{\leq}a(a{\leq}x)$, then $a$ is said to be a maximum (minimum) element of the lattice $L$.

If a lattice has a minimum element and a maximum element, they are called the bounds of the lattice, and $\mathbf{0}$ and $\mathbf{1}$ are used to represent the minimum element and maximum element respectively.

Example: The power set lattice ${\langle}P(S), {\subseteq}{\rangle} ({\langle}P(S), {\cup}, {\cap}{\rangle})$ has a maximum element S and a minimum element $\phi$. For example: if $S=\{a, b\}$, \[P(S)=\{\phi, \{a\}, \{b\}, \{a, b\}\},\,\,\mathbf{1}=\{a, b\}, \mathbf{0} = \phi.\]

Definition: If a lattice has both a minimum element and a maximum element, the lattice is called a bounded lattice.

Example: Suppose $S=\{2, 3, 4, 5, 6, 7\}$, for the less than or equal relationship between ordinary numbers ${\leq}, {\langle}S, {\leq}{\rangle}$ form a bounded lattice. The minimum element $\mathbf{0}=2$, the maximum element $\mathbf{1}=7$.

Finite lattice are all bounded lattice. For example, power set lattice ${\langle}P(S), {\subseteq}{\rangle}$, $S=\{a, b\}$ It is bounded.

Example: Assume $N$ natural number set, for the less than or equal relationship between ordinary numbers ${\leq}$, ${\langle}N, {\leq}{\rangle}$ form a lattice.

Among them, the minimum element $\mathbf{0}=0$ has no maximum element. It is not a bounded lattice.

Theorem: Suppose ${\langle}L, {\vee}, {\wedge}{\rangle}$ is a bounded lattice, then for any $a{\in}L$, Must have:

(1)$a{\vee}\mathbf{1}=\mathbf{1}$, $a{\wedge}\mathbf{1}=a$; (2)$a{\vee}\mathbf{0}=a$, $a{\wedge}\mathbf{0}=\mathbf{0}$.

prove: (1) Because $a{\vee}\mathbf{1}{\in}L$, there is $a{\vee}\mathbf{1}{\leq}\mathbf{1}$. And because $\mathbf{1}{\leq}a{\vee}\mathbf{1}$, therefore $a{\vee}\mathbf{1}=\mathbf{1}$.

Because $a{\leq}a$, $a{\leq}\mathbf{1}$, there is $a{\leq}a{\wedge}\mathbf{1}$. And because $a{\wedge}\mathbf{1}{\leq}a$, therefore $a{\wedge}\mathbf{1}=a$. (2) can be proved similarly.

Definition: Let ${\langle}L, {\vee}, {\wedge}{\rangle}$ be a bounded lattice, for an element $a$ in $L$.

If $b{\in}L$ exists, such that $a{\vee}b=\mathbf{1}$, $a{\wedge}b=\mathbf{0}$, then $b$ is said to be the complement of $a$.

In the picture on the left, $\mathbf{1}$ and $\mathbf{0}$ are complementary; The complement of $a$ is $e$;

$b$ has no complement; the complement of $c$ is $d$; The complements of $d$ are $c$ and $e$;

The complements of $e$ are $a$ and $d$.

In the picture on the right, $\mathbf{1}$ and $\mathbf{0}$ are complementary; The complements of $a$ are $b$, $c$ and $d$;

The complements of $b$ are $a$ and $c$; The complements of $c$ are $a$, $b$ and $d$;

The complements of $d$ are $a$ and $c$.

Supplementary elements have the following characteristics:

The complements are mutual, that is, if $b$ is the complement of $a$, then $a$ is also the complement of $b$;
$\mathbf{0}$ and $\mathbf{1}$ are complements of each other;
Not every element in a bounded lattice has a complement, and even if it exists, it may not be unique.

Definition: In a bounded lattice ${\langle}L, {\vee}, {\wedge}{\rangle}$, if every element in $L$ has a complement element, then this lattice is called complementary lattice.

(1) There is no complement (b has no complement) (2) There is a complement

(3) has a complement (4) does not have a complement

Theorem: The complement of elements $\mathbf{0}$ and $\mathbf{1}$ in the complement ${\langle}L, {\vee}, {\wedge}{\rangle}$ is unique.

Definition: If a figure is both complementary and distributive, it is called complementary and distributive.

Example: Suppose $S$ is a non-empty finite set, then ${\langle}P(S), {\cup}, {\cap}{\rangle}$ is a complementary partition.

Because $\mathbf{1}= S$, $\mathbf{0}=\phi$, and for any $A{\in}P(S)$ ($A{\subseteq}S$), there is a unique complement element ${\sim}A=S-A{\in}P(S)$ (${\sim}A{\subseteq}S$), the complement of $A$ is the complement of $A$. $A{\cup}{\sim}A=S$, $A{\cap}{\sim}A=\phi$.

Theorem: The complement of every element in a complemented lattice is unique.

Proof (proof by contradiction): Suppose ${\langle}L, {\vee}, {\wedge}{\rangle}$ is a complemented distribution, $a$ is an element in $L$, assuming it has two complements $b$ and $c$, then:

\[a{\vee}b=\mathbf{1},\,\, a{\wedge}b=\mathbf{0},\,\,a{\vee}c=\mathbf{1},\,\, a{\wedge}c=\mathbf{0}\]

That is: $a{\vee}b=a{\vee}c$, $a{\wedge}b=a{\wedge}c$.

According to the properties of the distributive lattice, there is $b=c$. So the complement of $a$ is unique.

The unique complement of any element $a$ in the complemented partition can be represented by ${\sim}a$ (or $a^\prime$).

Theorem: For every element $a$ in the complementary distribution lattice, there is $(a^{\prime})^{\prime}=a$.(Composition Law)

Proof: Because $a{\vee}a^{\prime}=\mathbf{1}, a{\wedge}a^{\prime}=\mathbf{0}$, From the commutative law: $a^{\prime}{\vee}a=\mathbf{1}, a^{\prime}{\wedge}a=\mathbf{0}$, Therefore, the complement of $a ^{\prime}$ is $a$, and the uniqueness of the complement is $(a^{\prime})^{\prime}=a$.

Theorem (De Morgan’s law): Suppose ${\langle}L, {\vee}, {\wedge}{\rangle}$ is a complementary partition, then for any elements $a$ and $b$ in $L$, we have

$(a{\vee}b)^{\prime}= a^{\prime}{\wedge}b^{\prime}$
$(a{\wedge}b)^{\prime}= a^{\prime}{\vee}b^{\prime}$

Proof: (1) From the distributive law we know:

\[(a{\vee}b){\vee}(a^{\prime}{\wedge}b^{\prime})=\] \[(a{\vee}b{\vee}a^{\prime}){\wedge}(a{\vee}b{\vee}b^{\prime}) =\mathbf{1}{\wedge}\mathbf{1}=\mathbf{1}\]

\[(a{\vee}b){\wedge}(a^{\prime}{\wedge}b^{\prime})=\] \[(a{\wedge}a^{\prime}{\wedge}b^{\prime}){\vee}(b{\wedge}a^{\prime}{\wedge}b^{\prime}) =\mathbf{0}{\vee}\mathbf{0}=\mathbf{0}\]

From the uniqueness of the complement, we can get $(a{\vee}b)^{\prime}= a^{\prime}{\wedge}b^{\prime}$. In the same way, formula (2) can be proved.

Theorem: For any elements $a$ and $b$ with complementary lattice, we have: $a{\leq}b{\Leftrightarrow}a{\wedge}b^{\prime}=\mathbf{0}{\Leftrightarrow}a^{\prime}{\vee}b=\mathbf{1}$.

prove: \[a{\leq}b{\Rightarrow}a{\wedge}b^{\prime}=(a{\wedge}b^{\prime}){\vee}(b{\wedge}b^{\prime})=(a{\vee}b){\wedge}b^{\prime}=b{\wedge}b^{\prime}=\mathbf{0}.\] in turn, \[a{\wedge}b^\prime=\mathbf{0}{\Leftrightarrow}(a{\wedge}b^\prime)^\prime=a^\prime{\vee}b=\mathbf{1}\] \[{\Rightarrow}a{\vee}b=(a{\vee}b)\wedge(a^\prime{\vee}b)=(a{\wedge}a^\prime){\vee}b=b{\Rightarrow}a{\leq}b.\]

Definition: A complemented lattice is called Boolean algebra.

In the complemented distribution, since each element $a$ has a unique complement $a^{\prime}$, a unary operation $^{\prime}$ can be defined so that $a^{\prime}$ is the complement of $a$. This unary operation is called complement operation.

Boolean algebra is generally represented by ${\langle}B, {\vee}, {\wedge}, ^{\prime}{\rangle}$ or ${\langle}B, {\vee}, {\wedge}, ^{\prime}, \mathbf{0}, \mathbf{1}{\rangle}$.

For example, Boolean algebra: \[{\langle}P(S), {\cup}, {\cap}, {\sim}{\rangle} or {\langle}P(S), {\cup}, {\cap}, {\sim}, \phi, S {\rangle}.\]

Definition: A Boolean algebra with a finite number of elements is called a finite Boolean algebra.

Definition: Let ${\langle}B, {\vee}, {\wedge}, ^{\prime}, \mathbf{0}, \mathbf{1}{\rangle}$ be a Boolean algebra, $A{\subseteq}B$ and non-empty, if ${\langle}A, {\vee}, {\wedge}, ^{\prime}, \mathbf{0}, \mathbf{1}{\rangle}$ is also Boolean algebra, then ${\langle}A, {\vee}, {\wedge}, ^{\prime}, \mathbf{0}, \mathbf{1}{\rangle}$ is ${\langle}B, {\vee}, {\wedge}, ^{\prime}, 0, **Sub(Boolean) algebra** of 1{\rangle}$.

Theorem: Let ${\langle}B, {\vee}, {\wedge}, ^{\prime}, \mathbf{0}, \mathbf{1}{\rangle}$ be a Boolean algebra, $A{\subseteq}B$ and $A$ contain elements $\mathbf{0}$ and $\mathbf{1}$, if $A$ operates on ${\vee}$, ${\wedge}$ and $^\prime$ are closed, then ${\langle}A, {\vee}, {\wedge}, ^{\prime}, \mathbf{0}, \mathbf{1}{\rangle}$ is ${\langle}B, {\vee}, {\wedge}, ^{\prime}, \mathbf{0}, Subalgebras of \mathbf{1}{\rangle}$.

Definition: Let ${\langle}A, {\vee}, {\wedge}, ^{\prime}, \mathbf{0}, \mathbf{1}{\rangle}$ and ${\langle}B, {\vee}, {\wedge}, ^{\prime}, \mathbf{0}, \mathbf{1}{\rangle}$ be two Boolean algebras, If there is a function $f$ from $A$ to $B$, such that for any $a, b{\in}A$, there is: \[f(a{\vee}b)=f(a){\vee}f(b)\] \[f(a{\wedge}b)=f(a){\wedge}f(b)\] \[f(a^{\prime})=(f(a))^{\prime}\] Then $f$ is said to be a Boolean algebra ${\langle}A, {\vee}, {\wedge}, ^{\prime}, \mathbf{0}, \mathbf{1}{\rangle}$ to a Boolean algebra ${\langle}B, {\vee}, {\wedge}, ^{\prime}, \mathbf{0}, Homomorphism (mapping) of \mathbf{1}{\rangle}$.

If $f$ is injective, it is called single homomorphism;

If $f$ is surjective, it is called full homomorphism;

If $f$ is bijective, it is called isomorphism;

If there is an isomorphic mapping f, it is called Boolean algebra ${\langle}A, {\vee}, {\wedge}, ^{\prime}, \mathbf{0}, \mathbf{1}{\rangle}$ and Boolean algebra ${\langle}B, {\vee}, {\wedge}, ^{\prime}, \mathbf{0}, \mathbf{1}{\rangle}$ isomorphism.

Example: Let $U={\langle}K, {\vee}, {\wedge}, {\sim}, \mathbf{0}_K, \mathbf{1}_K{\rangle}$ and $V={\langle}L, {\cup}, {\cap}, -, \mathbf{0}_L, \mathbf{1}_L{\rangle}$ be two Boolean algebras, And let $f$ be a homomorphic mapping from $U$ to $V$. That is, for any $a, b{\in}K$, we have \[f(a{\vee}b)=f(a){\cup}f(b),\,\,f(a{\wedge}b)=f(a){\cap}f(b),\,\,f({\sim}a)=-f(a).\] Try to prove: $f(\mathbf{0}_K)=\mathbf{0}_L$, $f(\mathbf{1}_K)=\mathbf{1}_L$.

Proof: Because $\mathbf{0}_K, \mathbf{1}_K{\in}K$, $\mathbf{0}_L, \mathbf{1}_L{\in}L$, therefore: \[f(\mathbf{0}_K), f(\mathbf{1}_K){\in}L,\,\,f(\mathbf{0}_K)=f({\sim}\mathbf{1}_K)=-f(\mathbf{1}_K),\,\,f(\mathbf{1}_K)=f({\sim}\mathbf{0}_K)=-f(\mathbf{0}_K)\] It can be seen that $f(\mathbf{0}_K)$ and $f(\mathbf{1}_K)$ are complementary. so: $f(\mathbf{0}_K){\cup}f(\mathbf{1}_K)=\mathbf{1}_L,\,\,f(\mathbf{0}_K){\cap}f(\mathbf{1}_K)=\mathbf{0}_L$.

again: \[f(\mathbf{1}_K)=f(\mathbf{0}_K{\vee}\mathbf{1}_K)=f(\mathbf{0}_K){\cup}f(\mathbf{1}_K)=\mathbf{1}_L\] \[f(\mathbf{0}_K)=f(\mathbf{0}_K{\wedge}\mathbf{1}_K)=f(\mathbf{0}_K){\cap}f(\mathbf{1}_K)=\mathbf{0}_L\] so: $f(\mathbf{1}_K)=\mathbf{1}_L,\,\,f(\mathbf{0}_K)=\mathbf{0}_L$.