Lattice

1. Lattices as Partially Ordered Sets

 

Definition 1

A partially ordered set (or poset) $\langle L, \preceq \rangle$이 만약 모든 L pair에 대해 lub와 glb를 가지면 lattice라고 부른다.

lub는 보통 a+b,

glb는 보통 a*b로 표시된다.

 

ex1) L = {a, b, a+b, a*b}

ex2) $x \preceq y \iff x \text{ divides } y$

ex3) $x \preceq y \iff x \subseteq y$ 

 

모두 lattice에 해당!

 

Theorem 1

$\langle L, \preceq \rangle$이 lattice라고 하고, x*y가 glb, x+y가 lub를 나타낼 때,
$\forall a, b, c \in L$에 대해

1) a * a = a, a + a = a (idempotent)
2) a * b = b * a, a + b = b + a (commutative)
3) (a * b) * c = a * (b * c) (associative)
4) a * (a + b) = a, a + (a * b) = a (absorption)

proof) absorption (a * (a+b) = a)

1) (show that $a \ast (a + b) \preceq a$)

$a \ast (a + b)$는 {a, a + b}의 glb. glb의 정의에 의해 $a \ast (a + b) \preceq a$, $a \ast (a + b) \preceq a + b$를 만족한다.

2)  (show that $a \preceq a \ast (a+b)$)

(a + b)는 {a, b}의 lub. lub 정의에 의해 $a \preceq (a + b)$, $b \preceq (a + b)$. $\preceq$은 reflexive하기 때문에(partially ordered) a는 {a, a+b}의 lb이다. a는 그냥 lb고 $a \ast (a + b)$는 glb이기 때문에 $a \ast (a + b) = a$.

 

Theorem 2

$\langle L, \preceq \rangle$이 lattice라면 $\forall a, b \in L, a \preceq b \iff a \ast b = a$가 만족한다.
($\forall a, b \in L, a \preceq b \iff a + b = b$) 

Proof) (if $\Leftarrow$)

$a \ast b = a$이면 a는 {a, b}의 glb이다. 따라서 $a \preceq a$와 $a \preceq b$를 만족시킨다.

 

(only if $\Rightarrow$)

$a \preceq b$와 reflexive 관계 $a \preceq a$를 이용해서 a가 {a, b}의 lb인 것을 알 수 있다.

a * b는 {a, b}의 glb이기 때문에 $a \preceq a \ast b \preceq {a, b}$를 만족시킨다. 즉 $a \preceq a \ast b \preceq a$이기 때문에

$\preceq$은 antisymmetric이기 때문에 a * b = a를 만족한다.

 

Corollary 3

$\langle L, \preceq \rangle$을 lattice라고 하면, $\forall a, b \in L, a \ast b = a \iff a + b = b$

Theorem 4

$\langle L, \preceq \rangle$이 lattice라고 할 때, $\forall a, b, c \in L, b \preceq c \Rightarrow a \ast b \preceq a \ast c \land a + b \ preceq a + c$

proof) we can prove $a * b \preceq a$ by showing that $a \ast b = (a \ast b) \ast (a \ast c)$

 

if $b \preceq c$, $(a \ast b) \ast (a \ast c) \preceq a \ast c$이다. (by definition of glb)

 

1) By theorem 2, $b \preceq c \iff b \ast c = b$

2) by associativity, commutativity, and idempotent of glb

$$a \ast b = a \ast (b \ast c) = (a \ast a) \ast (b \ast c) = (a \ast b) \ast (a \ast c)$$

We have now shown that

$$a \ast b = (a \ast b) \ast (a \ast c) \preceq a \ast c \Leftarrow b \preceq c$$

 

Theorem 5

$\langle L, \preceq \rangle$이 lattice일 때, $\forall a, b, c \in L, a + (b \ast c) \preceq (a + b) \ast (a + c) \land (a \ast b) + (a \ast c) \preceq a \ast (b + c)$ 

proof)

 

$a \preceq (a + b)$와 $a \preceq (a+c)$가 만족한다. (definition of lub)

 

$$a \preceq (a + b) \ast (a + c) ------ (1)$$

 

a는 lb이며, glb와 lub의 정의에 의해 $(b \ast c) \preceq b$, $(b \ast c) \preceq c$ $b \preceq (a + b)$, $c \preceq (a + c)$이다.

$\preceq$은 transitive하기 때문에, $(b \ast c) \preceq b \preceq (a + b)$이고, $(b \ast c) \preceq c \preceq (a + c)$이다.

그러므로 (b * c)는 {b, a + b}의 lb이다. (a + b) * (a + c)는 {a + b, a + c}의 glb이기 때문에

 

$$(b \ast c) \preceq (a + b) \ast (a + c) ------ (2)$$

 

(1)과 (2)로부터 (a+b)*(a+c)는 {a, b * c}의 ub임을 알 수 있다. a + (b * c)는 {a, (b * c)}의 lub이기 때문에,

$$a + (b \ast c) \preceq (a + b) \ast (a + c)$$

 

Example 4)

$\langle \mathbb{Z}, \le \rangle$가 lattice라고 할 때,

 

1) min(a, b) = a $\iff a \le b$

2) max(a,b) = b $\iff a \le b$

3) $b \le c \iff min(a,b) \le min(a, c)$

4) $b \le c \iff max(a,b) \le max(a.c)$

5) $max(a, min(b,c)) \le min(max(a,b), max(a,c))$

6) $max(min(a,b), min(a,c)) \le min(a, max(b,c))$

 

2. Lattice as Algebraic Structure

Theorem 6

$\langle A, \ast, + \rangle$이 다음과 같은 특징을 가진다고 할 때,

1) $x \ast x = x, x + x = x$(idempotent)
2) x * y = y * x, x + y = y + x(commutative)
3) (x * y) * z = x * (y * z) (associative)
4) x * (x + y) = x, x + (x * y) = x (absorption)

그렇다면 $\langle A, \preceq \rangle$인 lattice가 존재한다. ($x \preceq y \iff x \ast y = x (x + y = y) \forall x, y \in A$)

Proof)

1) Show that $\preceq$ is partial ordering

2) Show that x * y and x + y are the glb and lub of {x, y}

 

Proof)

1)

reflexive

$\forall x \in A, x \ast x = x$이다. 왜냐면 idempotent이기 때문

따라서 $x \ast x = x \iff x \preceq x$.

 

antisymmetric

$\forall x, y \in A, x \ast y = y \ast x(\because \text{commuatative})$

$x \preceq y \iff x \ast y = x$이기 때문에 $y \preceq x \iff y \ast x = y$

$\therefore x = y$

 

transitive

assume $(x, y) \in \preceq, (y, z) \in \preceq$ 이라고 하면 각각 $x \ast y = x$, $y \ast z = y$를 만족한다.

*는 associative하기 때문에 $x \ast y = x \ast (y \ast z) = (x \ast y) \ast z = x \ast z = x \iff x \preceq z$

 

$\therefore \preceq \text{ is partial ordering}$

 

2) x*y가 glb인 것을 보이기 위해 $z \preceq (x \ast y)$인 lb인 모든 z에 대해 $z \preceq (a \ast b)$인 것을 보여야 한다.

$\forall x, y \in A, (x \ast y) + x = x$ and $(y \ast x) + y = y$ (by absorption)

$x \preceq y \iff x + y = y$이기 때문에 $(x \ast y) \preceq x$, $(y \ast x) \preceq y$이다.

 

z가 x, y의 임의의 lb라고 한다면 $z \preceq x$, $z \preceq y$이다.

$z \ast x = z$, $z \ast y = z$이며,

 

$$z = z * x = (z * y) * x = z * (y * x) = z * (x * y)$$

$$z * (x * y) = z \iff z \preceq (x * y)$$

 

따라서 x * y는 glb가 된다.

 

Definition 2

algebraic structure로 정의된 lattice는 다음과 같은 조건을 가진다.

1) x * y = y * x, x + y = y + x(commutative)
2) (x * y) * z = x * (y * z) (associative)
3) x * (x + y) = x, x + (x * y) = x (absorption)

idempotent는 absorption으로 이끌어낼 수 있다.

Remark 2

lattice는 poset 또는 algebraic structure로 정의될 수 있다.

Definition 3

$\langle L, \ast, + \rangle$가 lattice이고, S를 L의 subset이라고 한다면, $(S \subseteq L)$ algebraic $\langle S, \ast, + \rangle$은 *과 +에 대해 closed 됐을 때 $\langle L, \ast, + \rangle$의 sublattice이다.

3. Bounded Lattices with Extreme Elements

Definition 5

least and greatest elements of a lattice가 만약 존재한다면 bounds of the lattice라고 부른다. 0과 1로 표현한다.

Definition 6

bounded lattice는 least element와 greatest element를 가지고 있는 lattice를 칭한다.

Definition 7

다음 bounded lattice에서 $\langle L, \ast, +, 0, 1 \rangle$, $a \ast b = 0 \land a + b = 1$일 때, b를 a의 complement라고 부른다.

Theorem 7

bounded lattice $\langle L, \ast, +, 0, 1 \rangle$에서 0의 complement는 1 하나 이고, 1의 complement는 0 하나이다.

 

3-1. Boolean Lattices

Definition 8

$\langle L, \ast, +, 0, 1 \rangle$인 lattice에서 모든 element가 적어도 하나 이상의 complement를 가지고 있을 때, complemented lattice라고 부른다.

Definition 9

$\langle L, \ast, +, 0, 1 \rangle$인 lattice에서 $\forall a, b, c \in L, a \ast (b + c) = (a \ast b) + (a \ast c) \land a + (b \ast c) = (a + b) \ast (a + c)$이면 distributive lattice이다.

$a + (b * c) \preceq (a + b) \ast (a + c)$와 $(a \ast b) + (a \ast c) \preceq a \ast (b + c)$는 원래 Theorem 5에 의해 만족한다.

Definition 10

distributive하고 complemented한 lattice는 Boolean lattice라고 부른다!

Theorem 8

만약 lattice가 diamond lattice와 pentagon lattice를 sublattices에서 가지고 있지 않으면 distributive lattice이다.

왼쪽이 pentagon lattice, 오른쪽이 diamond lattice

4. Boolean Algebras and Functions

4-1. Boolean Algebras

Definition 11

B가 {0, 1}일 때, x가 오로지 B에 있는 값만을 가질 때 변수 x는 Boolean variable이라 불린다.

Definition 12

Boolean expression은 Boolean variables $x_1 ,x_2, ..., x_n$과 기호들이 아래 규칙에 맞게 재귀적으로 정의된 형태이다.
(1) 0, 1, $x_1, x_2, ..., x_n$은 boolean expression이다.
(2) p와 q가 boolean expression일 때, $\bar{p}, (p \ast q), (p + q)$는 boolean expression이다.

Definition 13

두개의 boolean expression $\alpha, \beta$가 서로 equivalent하다는 것은,
한 식이 다른 식을 유한한 수의 applications of identities를 통해 얻어낼 수 있다는 것을 뜻한다.

ex)

$$f(x, y) = x \ast y$$

$$g(x, y) = (x \ast y) + 0$$

$$h(x, y) = (x \ast y) \ast 1$$

은 모두 equivalent하다.

 

4-2. Boolean Functions

Definition 14

$f : B^n \rightarrow B$인 f가 Boolean expression과 n개의 Boolean variables로 구성되어 있을 때 n차원의 Boolean function으로 부른다. 

Degree가 n일 때, 가능한 서로 다른 Boolean function의 개수는 $2^{2^n}$이다.

 

Definition 15

Boolean algebra란, algebra $\langle B, +, \ast, \bar{}, 0, 1 \rangle$ 를 뜻하고 다음을 만족시킨다.

1) $x \ast 1 = x, x + 0 = x$ (identity)
2) $x \ast \bar x = 0  x + \bar x = 1$ (complement)
3) $x \ast y = y \ast x.  x + y = y + x$ (commutative)
4) $(x \ast y) \ast z = x \ast (y \ast z),  (x + y) + z = x + (y + z)$ (associative)
5) $x \ast (y + z) = (x \ast y) + (x \ast z), x + (y \ast z) = (x + y) \ast (x + z)$ (distributive)

B = {0, 1} 은 가장 단순한 Boolean algebra set이다.

 

Example 8

$\langle B, +, \ast, \bar{}, 0, 1 \rangle$ 일 때, B = {0, 1}이고, +는 Boolean sum, $\ast$는 Boolean product, $\bar{}$가 Boolean complement operator일 때 이를 Boolean algebra라고 부른다.

Example 9

$\langle B, \land, \lor, \bar{}, F, T \rangle$일 때, B = {propositions}이고 $\land$이 logical and, $\lor$이 logical or, $\bar{}$이 negation operator일 때, Boolean Algebra이다.

Example 10

$\langle B, \cup, \cap, \bar{}, \emptyset, U \rangle$이고 B가 $\mathcal{P}(U)$일 때 이 또한 Boolean algebra이다.

Boolean Algebra의 +,$\ast$-는 일반적인 더하기, 곱하기와는 다르다.

Example 11

$\langle \mathbb{Z}, +, \ast \rangle$은 Boolean algebra가 아니다. 왜냐면

$$2+(3 \ast 4) \neq (2+3) \ast (2+4) \tag{distributive}$$ 
이기 때문이다.

Example 12

$\langle B, +, \ast, \bar{}, 0, 1 \rangle$이 algebra이고,
(1) 0 < 1
(2) x + y = max(x, y), x $\ast$ y = min(x, y)이고
(3) $\bar{x} = 1 - x$일 때,
B가 이러한 operation에 대해서 Boolean Algebra가 성립한다는 것을 보여라

위의 식이 Boolean Algebra의 5개의 axiom을 만족시킨다는 것을 보이면 된다.

 

Example 13

Boolean algebra에서 idempotent laws가 성립하는 것을 구해라($x \ast x = x, x + x = x$)

$$\begin{align} x \ast x &= (x \ast x) + 0 \tag{identity}\\&= (x \ast x) + (x \ast \bar{x}) \tag{complement}\\&= x \ast (x + \bar{x}) \tag{distributive}\\&= x \ast 1 \tag{complement}\\&= x \tag{identity}\end{align}$$

 

Example 14

Boolean algebra에서 domination laws가 성립하는 것을 구해라($x \ast 0 = 0, x + 1 = 1$)

$$\begin{align} x\ast 0 &= x\ast (x \ast \bar{x}) \tag{complement} \\&= (x \ast x) \ast \bar{x} \tag{associative}\\&= x \ast \bar{x} \tag{idempotent}\\&= 0 \tag{complement}\end{align}$$

Example 15

Boolean algebra에서 absorption laws가 성립하는 것을 구해라($x \ast (x + y) = x, x + (x \ast y) = x$)

$$\begin{align} x\ast (x + y) &= (x + 0) \ast (x + y) \tag{identity}\\ &= x + (0 \ast y) \tag{distributive} \\ &= x + 0 \tag{domination}\\ &= x \tag{identity} \end{align}$$

 

5. Boolean Algebra as a Lattice

Boolean Algebra는 lattice로 표현 가능하다.

1) $\langle L, \preceq \rangle$을 bounded lattice라 할 때,

2) B = {0, 1}이라 두고, 0을 least element, 1을 greatest element로 둔다. 즉 $\forall x \in L, 0 \preceq x \land x \preceq 1 \text{ and } B \subseteq L$

3) $\bar{0} = 1, \bar{1} = 0$

 

=> glb(x, y)를 $\ast$, lub(x, y)를 +로 놓으면 identity, complement, distributive laws가 성립한다. (commutative와 associative는 이미 성립)

 

Theorem 9

$\langle B, \ast, +, \bar{}, 0, 1 \rangle$을 Boolean algebra라고 할 때, $\langle B, \preceq \rangle$은 Boolean lattice이다. $\preceq$이 다음과 같을 때,
$$\preceq = {\langle x, y \rangle | x \ast y = x (\text{alternatively, } x + y = y) \forall x, y \in B}$$

1) truth table에 의해 $\preceq = {(0, 0), (0, 1), (1, 1)}$이다. 해당 relation은 reflexive, antisymmetric, transitive하기 때문에 $\preceq$은 partial ordering이다.

2) table에 의해 $x \ast y \preceq x, x \ast y \preceq y, x \preceq x + y, y \preceq x + y$이기 때문에 $x \ast y, x+ y$는 glb(x,y)와 lub(x, y)이다.

 

Remark 5

Theorem 9는 ${0,1} \subset B$인 B에 대해서도 성립한다. B = ${0, 1, \alpha, \beta}$라고 할 때,
$$\preceq = \{\langle x, y \rangle | x \ast y = x \land x + y = y, \forall x, y \in B\},$$
1) $(0, \alpha) \in \preceq, \    \because 0 \ast \alpha = 0 \land 0 + \alpha = \alpha$
2) $(\alpha, 1) \in \preceq, \    \because \alpha \ast 1 = \alpha \land \alpha + 1 = 1$
3) $(\alpha, \alpha) \in \preceq, \    \because \alpha \ast \alpha = \alpha \land \alpha + \alpha = 1$
4) $(\beta, \beta), (0, \beta), (\beta, 1) \in \preceq$

여전히 partial ordering이다. 또한 *, +가 glb(x, y), lub(x, y)이기 때문에 여전히 $\langle L, \preceq \rangle$은 Boolean lattice이다.

5-1. Boolean Lattice vs Boolean Algebra

Boolean Lattice

 

lattice $\langle L, \preceq \rangle$는 poset이고, $\ast$, +는 idempotent, commutative, associatice and absorption을 만족시킨다.

A bounded lattice $\langle L, \ast, +, 0, 1 \rangle$은 complemented하고 distributive할 경우 Boolean lattice이다.

 

Boolean Algebra

 

lattice  $\langle L, \ast, + \rangle$은 commutative, associative, absorption일 경우 algebra이다.

Boolean algebra  $\langle B, \ast, +, \bar{}, 0, 1 \rangle$은 identity, commutative, associative, complemented, distributive할 경우에 성립한다.

 

5-2. Stone's Representation Theorem

Theorem 13

모든 Boolean algebra $\langle B, \ast, +, \bar{}, 0, 1 \rangle$에 대해 isomorphic한 power set algebra $\langle \mathcal{P}(A), \cap, \cup, \bar{}, \emptyset, A \rangle$이 존재한다.

Proof)

주어진 Boolean algebra $\langle B, \ast, +, \bar{}, 0, 1 \rangle$에 대해 

1) atom을 다음과 같이 정의하고(for $x, y \in B, x \text{ covers } y \Leftrightarrow \nexist z \in B $ )