| 이산수학 Discrete Mathematics | ||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" | 이론 | |
| <colbgcolor=#3CC> 기본 대상 | 수학기초론(수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열(뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의(점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수(/공식) · 순열(완전 순열 · 염주 순열) · 치환 · 분할(분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기(해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리(파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 (예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
1. 개요
lattice / 格子격자 또는 속은 임의의 원소쌍의 상한과 하한이 존재하는 부분순서집합을 뜻한다. 격자는 크게 두 가지 방법으로 정의할 수 있으며, 둘 다 같은 대상을 나타낸다.
2. 정의
2.1. 순서를 이용한 정의
2.1.1. 부분순서집합
집합 [math(A)]에 대해 다음 조건을 만족하는 이항관계 [math({\preceq}\bigl(\subseteq A^2\bigr))]를 부분순서[partial order]라고 한다.- 반사성\[reflexivity\]: 임의의 원소 [math(a(\in A))]에 대해 [math(a \preceq a)]이다.
- 반대칭성\[antisymmetry\]: 임의의 원소 [math(a,b(\in A))]에 대해 [math(a \preceq b)]이고 [math(b \preceq a)]이면 [math(a = b)]이다.
- 추이성\[transitivity\]: 임의의 원소 [math(a,b,c(\in A))]에 대해 [math(a \preceq b)]이고 [math(b \preceq c)]이면 [math(a \preceq c)]이다.
부분순서는 어떤 두 원소 사이에 순서 관계가 있음을 나타내지만, 꼭 모든 원소 사이에 순서 관계가 있을 필요는 없다. 예를 들어, 집합의 부분집합 관계 [math(\subseteq)]를 생각하자. 이 관계는 다음과 같이 반사성, 비대칭성, 추이성을 모두 만족하므로 부분순서이다.
- 반사성
임의의 집합 [math(A)]를 생각하자. 임의의 원소 [math(a(\in A))]에 대해 [math(a \in A)]이므로 [math(A \subseteq A)]이다. - 반대칭성
[math(A \subseteq B)]와 [math(B \subseteq A)]를 만족하는 임의의 집합 [math(A,B)]를 생각하면 집합의 상등 정의에 의해 [math(A = B)]이다. - 추이성
[math(A \subseteq B)]와 [math(B \subseteq C)]를 만족하는 임의의 집합 [math(A,B,C)]를 생각하자. 임의의 원소 [math(a(\in A))]에 대해, [math(A \subseteq B)], [math(a \in A)]에서 [math(a \in B)]이고, [math(B \subseteq C)], [math(a \in B)]에서 [math(a \in C)]이므로, [math(A \subseteq C)]이다.
부분순서 [math({\preceq})]가 주어진 집합 [math(A)]를 부분순서집합\[partially ordered set, poset\]이라고 하고, [math((A,{\preceq}))]로 표기한다. 앞에서 [math({\subseteq})]가 부분순서임을 알았으므로 원소가 집합인 임의의 집합은 부분순서집합임을 알 수 있다. 다음 예시를 생각하자.
- [math(P_1 = \{\{1\},\{2\},\{1,2\},\{2,3\},\{1,2,3\}\})]이라고 정의된 집합 [math(P_1)]은 부분순서 [math({\subseteq})][1]를 가지므로 부분순서집합이고, [math((P_1,{\subseteq}))]로 표기한다.
- [math(P_2 = \{\{2\},\{1,2\},\{2,3\},\{2,3,4\}\})]라고 정의된 집합 [math(P_2)]는 부분순서 [math({\subseteq})][2]를 가지므로 부분순서집합이고, [math((P_2,{\subseteq}))]로 표기한다.
집합이 아닌 원소를 가지는 격자의 예시로는 다음이 있다.
- [math(Q_1 = \{1,e,\pi\})]라고 정의된 집합 [math(Q_1)]은 부분순서 [math({\le})][3]를 가지므로 부분순서집합이고, [math((Q_1,{\le}))]로 표기한다.
- [math(Q_2 = (-1,1))][4]이라고 정의된 집합 [math(Q_2)]는 부분순서 [math({\le})][5]를 가지므로 부분순서집합이고, [math((Q_2,{\le}))]로 표기한다.
집합 [math(A)]에 대해 다음 조건을 만족하는 이항관계 [math({\prec}\bigl(\subseteq A^2\bigr))]를 순부분순서[strict partial order]라고 한다.
- 비반사성\[irreflexivity\]: 임의의 원소 [math(a(\in A))]에 대해 [math(a \nprec a)]이다.
- 비대칭성\[asymmetry\]: 임의의 원소 [math(a,b(\in A))]에 대해 [math(a \prec b)]이면 [math(b \nprec a)]이다.[6]
- 추이성: 임의의 원소 [math(a,b,c(\in A))]에 대해 [math(a \prec b)]이고 [math(b \prec c)]이면 [math(a \prec c)]이다.
순부분순서의 예시로는 진부분집합 관계 [math({\subset})]가 있다. 사실 임의의 부분순서에 대해, 부분순서에서 반사적인 원소만 빼는 방식으로 순부분순서를 자연스럽게 정의할 수 있다. 예를 들어 앞의 [math((P_2,{\subseteq}))]에서 순부분순서 [math({\subset})]를 [math({\subset} = \{(\{2\},\{1,2\}),(\{2\},\{2,3\}),(\{2\},\{2,3,4\}),(\{2,3\},\{2,3,4\})\})]라고 정의할 수 있다. 이제부터는 임의의 부분순서집합 [math((A,{\preceq}))]에 대해, 부분순서 [math({\preceq})]와 순부분순서 [math({\prec})], 그리고 이의 역관계 [math({\succeq})]와 [math({\succ})]를 자연스럽게 정의해 사용하기로 한다. 주의해야 할 것은, [math({\npreceq})]와 [math({\succ})]가 같을 이유가 없고, [math({\nprec})]와 [math({\succeq})]가 같을 이유가 없다는 점이다.
2.1.2. 상한과 하한
부분순서집합 [math((A,{\preceq}))]의 임의의 원소 [math(a)]에 대해 [math(g \nprec a)]를 만족하는 원소 [math(g(\in A))]를 [math(A)]의 극대원소\[maximal element\]라고 한다. 또, 임의의 원소 [math(a(\in A))]에 대해 [math(m \nsucc a)]를 만족하는 원소 [math(m(\in A))]을 [math(A)]의 극소원소\[minimal element\]라고 한다. 부분순서집합에서 극대원소와 극소원소는 하나만 존재할 수도, 여러 개가 존재할 수도, 존재하지 않을 수도 있다. 예를 들어, 앞의 [math((P_1,{\subseteq}))]의 경우, 극대원소로는 [math(\{1,2,3\})]이 유일하게 존재하고, 극소원소로는 [math(\{1\},\{2\})]가 존재한다. [math((P_2,{\subseteq}))]의 경우에는 극대원소로는 [math(\{1,2\},\{2,3,4\})]가 존재하고, 극소원소로는 [math(\{2\})]가 유일하게 존재한다. 또, [math((Q_1,{\le}))]의 경우에는 극대원소와 극소원소로 각각 [math(\pi)], [math(1)]이 유일하게 존재하지만, [math((Q_2,{\le}))]의 경우에는 극대원소와 극소원소 모두 존재하지 않는다.부분순서집합 [math((A,{\preceq}))]의 임의의 원소 [math(a)]에 대해 [math(g \succeq a)]를 만족하는 원소 [math(g(\in A))]를 [math(A)]의 최대원소\[greatest element\]라고 한다. 또, 임의의 원소 [math(a(\in A))]에 대해 [math(m \preceq a)]를 만족하는 원소 [math(m(\in A))]을 [math(A)]의 최소원소\[least element\]라고 한다. 부분순서집합에서 최대원소와 최소원소는 존재하지 않을 수도 있지만, 존재한다면 유일하다. 예를 들어, [math((P,{\subseteq}))]의 경우 최대원소로는 [math(\{1,2,3\})]이 유일하게 존재하지만 최소원소는 존재하지 않는다. [math((P_2,{\subseteq}))]에서는 반대로 최대원소는 존재하지 않지만 최소원소로는 [math(\{2\})]가 유일하게 존재한다. [math((Q_1,{\le}))]에서는 최대원소와 최소원소로 각각 [math(\pi)], [math(1)]이 유일하게 존재한다.
부분순서집합 [math((A,{\preceq}))]의 부분집합 [math(B)]를 생각하자. 임의의 원소 [math(b(\in B))]에 대해 [math(g \succeq b)]를 만족하는 원소 [math(g(\in A))]를 [math(B)]의 상계\[upper bound\]라고 한다. 또, 임의의 원소 [math(b(\in B))]에 대해 [math(m \preceq b)]를 만족하는 원소 [math(m(\in A))]을 [math(B)]의 하계\[lower bound\]라고 한다. 상계와 하계는 굳이 [math(B)]의 원소일 필요가 없으며, 하나만 존재할 수도, 여러 개가 존재할 수도, 존재하지 않을 수도 있다. 예를 들어, [math((P_1,{\subseteq}))]의 부분집합 [math(\{\{1\},\{2\}\})]의 경우 상계로 [math(\{1,2\},\{1,2,3\})]이 존재하지만 하계는 존재하지 않는다. [math((P_2,{\subseteq}))]의 부분집합 [math(\{\{1,2\},\{2,3\}\})]의 경우 상계는 존재하지 않지만 하계로는 [math(\{2\})]가 유일하게 존재한다.
부분순서집합 [math((A,{\preceq}))]와 부분집합 [math(B)]에 대해, [math(B)]의 상계 중 최소인 원소를 [math(B)]의 상한\[supremum\] 또는 최소상계\[least upper bound\]라고 하고, [math(B)]의 하한 중 최대인 원소를 [math(B)]의 하한\[infimum\] 또는 최대하계\[greatest lower bound\]라고 한다. 상한과 하한은 존재하지 않을 수도 있지만, 존재하다면 유일하다. 예를 들어, [math((P_1,{\subseteq}))]의 부분집합 [math(\{\{1\},\{2\}\})]의 경우 상한으로 [math(\{1,2\})]가 유일하게 존재하지만 하계는 존재하지 않는다.
2.1.3. 반격자와 격자
이제 격자를 정의하자. 임의의 원소쌍의 상한이 존재하는 부분순서집합을 이음반격자\[join-semilattice\]라고 한다. 상한은 존재하면 유일하므로 이음반격자의 임의의 원소쌍의 상한은 유일하게 존재한다. 예를 들어, [math((P_1,{\subseteq}))]은 임의의 원소쌍의 상한이 존재하므로 이음반격자이지만, [math((P_2,{\subseteq}))]는 원소쌍 [math(\{\{1,2\},\{2,3\}\})]의 상한이 존재하지 않으므로 이음반격자가 아니다. 임의의 원소쌍의 하한이 존재하는 부분순서집합을 만남반격자\[meet-semilattice\]라고 한다. 하한은 존재하면 유일하므로 이음반격자의 임의의 원소쌍의 하한은 유일하게 존재한다. 예를 들어, [math((P_1,{\subseteq}))]은 원소쌍 [math(\{\{1\},\{2\}\})]의 하한이 존재하지 않으므로 만남반격자가 아니지만, [math((P_2,{\subseteq}))]는 임의의 원소쌍의 하한이 존재하므로 만남반격자이다. 이음반격자와 만남반격자를 통틀어 반격자\[semilattice\]라고 한다.이음반격자이면서 만남반격자인 부분순서집합, 즉, 임의의 원소쌍의 상한과 하한이 존재하는 부분순서집합을 격자\[lattice\]라고 한다. [math((Q_1,{\le}))]과 [math((Q_2,{\le}))]는 이음반격자이면서 만남반격자이므로 격자이다.
다음은 순서를 이용해 정의한 격자의 예시이다.
- 이하 관계 [math({\le})]를 가지는 실수 집합 [math((\R,{\le}))]
- 집합 [math(A)]에 대해, 부분집합 관계 [math({\subseteq})]를 가지는, [math(A)]의 멱집합 [math((\mathcal P(A),{\subseteq}))]
- 나누어떨어짐 관계 [math(|)][7]를 가지는 양의 정수 집합 [math((\Z^+,|))]
2.2. 대수학적 정의
이번에는 대수학적으로 격자를 정의한다. 다음 조건을 만족하는 연산 [math({\land}:S^2 \rightarrow S)]을 가지는 집합 [math(S)]를 반격자\[semilattice\]라고 하고, [math((S,{\land}))]로 표기한다.- 결합법칙[associativity]: 임의의 원소 [math(a,b,c(\in S))]에 대해 [math((a \land b) \land c = a \land (b \land c))]이다.
- 교환법칙[commutativity]: 임의의 원소 [math(a,b(\in S))]에 대해 [math(a \land b = b \land a)]이다.
- 멱등법칙\[idempotency\]: 임의의 원소 [math(a(\in S))]에 대해 [math(a \land a = a)]이다.
다음 조건을 만족하는 연산 [math({\lor}:L^2 \rightarrow L)]과 [math({\land}:L^2 \rightarrow L)]을 가지는 집합 [math(L)]을 격자\[lattice\]라고 하고, [math((L,{\lor},{\land}))]로 표기한다. 이때 [math({\lor})]을 이음 연산, [math({\land})]을 만남 연산이라고 한다.
- 결합법칙: 임의의 원소 [math(a,b,c(\in L))]에 대해 [math((a \lor b) \lor c = a \lor (b \lor c))]이고 [math((a \land b) \land c = a \land (b \land c))]이다.
- 교환법칙: 임의의 원소 [math(a,b(\in L))]에 대해 [math(a \lor b = b \lor a)]이고 [math(a \land b = b \land a)]이다.
- 멱등법칙: 임의의 원소 [math(a(\in L))]에 대해 [math(a \lor a = a)]이고 [math(a \land a = a)]이다.[8]
- 흡수법칙\[absorption\]: 임의의 원소 [math(a,b(\in L))]에 대해 [math(a \lor (a \land b) = a)]이고 [math(a \land (a \lor b) = a)]이다.
다음은 대수학적으로 정의한 격자의 예시이다.
- 최댓값 연산 [math(\max:\R^2 \rightarrow \R)]와 최솟값 연산 [math(\min:\R^2 \rightarrow \R)]을 가지는 실수 집합 [math((\R,\max,\min))]
- 집합 [math(A)]에 대해, 합집합 연산 [math({\cup})]과 교집합 연산 [math({\cap})]을 가지는, [math(A)]의 멱집합 [math((\mathcal P(A),{\cup},{\cap}))]
- 최소공배수 연산 [math(\mathrm{lcm}:\left(\Z^+\right)^2 \rightarrow \Z^+)]과 최대공약수 연산 [math(\gcd:\left(\Z^+\right)^2 \rightarrow \Z^+)]를 가지는 양의 정수 집합 [math((\Z^+,\mathrm{lcm},\gcd))]
2.3. 두 정의 사이의 관계
이제 두 정의가 같음을 보인다. 먼저 순서를 이용해 정의한 격자 [math((A,{\preceq}))]를 생각하자. [math(A)] 위의 이항연산 [math({\lor}:A^2 \rightarrow A)]과 [math({\land}:A^2 \rightarrow A)]을 각각 원소쌍의 상한과 하한으로 정의한다. 즉, 임의의 원소 [math(a,b(\in A))]에 대해 [math(a \lor b)]와 [math(a \land b)]는 각각 [math(\{a,b\})]의 상한과 하한을 나타낸다. 격자의 정의에서 원소쌍의 상한과 하한이 유일하게 존재하므로 두 연산이 잘 정의됨을 알 수 있다. 이제 이 두 연산이 대수학적 정의를 만족함을 보이자.- 결합법칙
임의의 원소 [math(a,b,c(\in A))]에 대해, [math(\{a \lor b,c\})]의 모든 상계의 집합을 [math(G_1)], [math(\{a,b \lor c\})]의 모든 상계의 집합을 [math(G_2)]라고 하자. 그러면 [math(G_1)]과 [math(G_2)]는 다음을 만족한다. - [math(G_1)]의 임의의 원소 [math(g)]를 생각하자. [math(g \succeq a \lor b)], [math(a \lor b \succeq a)]에서 [math(g \succeq a)]이다. 또, [math(g \succeq a \lor b)], [math(a \lor b \succeq b)]에서 [math(g \succeq b)]이고, [math(g \succeq b)], [math(g \succeq c)]에서 [math(g)]가 [math(\{b,c\})]의 상계이므로, [math(\{b,c\})]의 상한 [math(b \lor c)]에 대해 [math(g \succeq b \lor c)]이다. 따라서 [math(g)]는 [math(\{a,b \lor c\})]의 상계, 즉, [math(G_2)]의 원소이고, 여기서 [math(G_1 \subseteq G_2)]이다.
- [math(G_2)]의 임의의 원소 [math(g)]를 생각하자. [math(g \succeq b \lor c)], [math(b \lor c \succeq b)]에서 [math(g \succeq b)]이고, [math(g \succeq a)], [math(g \succeq b)]에서 [math(g)]가 [math(\{a,b\})]의 상계이므로, [math(\{a,b\})]의 상한 [math(a \lor b)]에 대해 [math(g \succeq a \lor b)]이다. 또, [math(g \succeq b \lor c)], [math(b \lor c \succeq c)]에서 [math(g \succeq c)]이다. 따라서 [math(g)]는 [math(\{a \lor b,c\})]의 상계, 즉, [math(G_1)]의 원소이고, 여기서 [math(G_2 \subseteq G_1)]이다.
- 교환법칙
임의의 원소 [math(a,b(\in A))]에 대해 [math(a \lor b)]와 [math(b \lor a)] 모두 [math(\{a,b\})]의 상한을 나타낸다. 따라서 [math(a \lor b = b \lor a)]이다. 같은 방식으로 [math(a \land b = b \land a)]임도 보일 수 있다. - 멱등법칙
임의의 원소 [math(a(\in A))]는 [math(a \succeq a)]에서 [math(\{a\}(= \{a,a\}))]의 상계이고, [math(\{a\})]의 임의의 상계 [math(g(\in A))]에 대해 [math(g \succeq a)]이므로 [math(a)]는 [math(\{a\})]의 상한이다. 따라서 [math(a \lor a = a)]이다. 같은 방식으로 [math(a \land a = a)]임도 보일 수 있다. - 흡수법칙
임의의 원소 [math(a,b(\in A))]를 생각하자. [math(a \succeq a)], [math(a \succeq a \land b)]에서 [math(a)]는 [math(\{a,a \land b\})]의 상계이고, [math(\{a,a \land b\})]의 임의의 상계 [math(g(\in A))]에 대해 [math(g \succeq a)]이므로 [math(a)]는 [math(\{a,a \land b\})]의 상한이다. 따라서 [math(a \lor (a \land b) = a)]이다. 같은 방식으로 [math(a \land (a \lor b) = a)]임도 보일 수 있다.
앞에서 [math(G_1 \subseteq G_2)]이고 [math(G_2 \subseteq G_1)]이므로 [math(G_1 = G_2)]이다. [math(\{a \lor b,c\})]의 모든 상계의 집합과 [math(\{a,b \lor c\})]의 모든 상계의 집합이 서로 같으므로, 각 집합의 최소원소, 즉, [math(\{a \lor b,c\})]의 상한과 [math(\{a,b \lor c\})]의 상한도 서로 같다. 따라서 [math((a \lor b) \lor c = a \lor (b \lor c))]이다. 같은 방식으로 [math((a \land b) \land c = a \land (b \land c))]임도 보일 수 있다.
이번에는 대수학적으로 정의한 격자 [math((L,{\lor},{\land}))]을 생각하자. [math(L)] 위의 이항관계 [math({\preceq}\bigl(\subseteq L^2\bigr))]를 [math({\preceq} = \bigl\{(a,b) \in L^2 \bigm| a \lor b = b\bigr\})]이라고 정의한다. 먼저 이 관계가 부분순서임을 보이자.
- 반사성
임의의 원소 [math(a(\in L))]에 대해 [math(a \lor a = a)]이므로 [math(a \preceq a)]이다. - 반대칭성
[math(a \preceq b)]와 [math(b \preceq a)]를 만족하는 임의의 원소 [math(a,b(\in L))]에 대해 [math(a \lor b = b)]이고 [math(b \lor a = a)]이므로 [math(a = b \lor a = a \lor b = b)]이다. - 추이성
[math(a \preceq b)]와 [math(b \preceq c)]를 만족하는 임의의 원소 [math(a,b,c(\in L))]에 대해 [math(a \lor b = b)], [math(b \lor c = c)]에서 [math(a \lor c = a \lor (b \lor c) = (a \lor b) \lor c = b \lor c = c)]이므로 [math(a \preceq c)]이다.
[math(a \lor (a \lor b) = (a \lor a) \lor b = a \lor b)]에서 [math(a \preceq a \lor b)]이고, [math(b \lor (a \lor b) = (a \lor b) \lor b = a \lor (b \lor b) = a \lor b)]에서 [math(b \preceq a \lor b)]이므로, [math(a \lor b)]는 [math(\{a,b\})]의 상계이다. 또, [math(\{a,b\})]의 임의의 상계 [math(g(\in L))]에 대해, [math(a \lor g = g)], [math(b \lor g = g)]에서 [math((a \lor b) \lor g = a \lor (b \lor g) = a \lor g = g)]이므로 [math(a \lor b \preceq g)]이다. 따라서 [math(a \lor b)]는 [math(\{a,b\})]의 상한이다. 같은 방식으로 [math(a \land b)]가 [math(\{a,b\})]의 하한임도 보일 수 있다.[9]
따라서 대수학적으로 정의한 격자가 순서를 이용한 격자의 정의를 만족함을 알 수 있고, 두 정의가 같은 대상을 나타냄을 알 수 있다. 두 정의 문단에서 보인 격자 예시는 순서대로 같은 격자를 나타낸다. 즉, [math((\R,{\le}) = (\R,\max,\min))]이고, [math((\mathcal P(A),{\subseteq}) = (\mathcal P(A),{\cup},{\cap}))], [math((\Z^+,|) = (\Z^+,\mathrm{lcm},\gcd))]이다. 일반적으로 순서를 이용해 정의한 격자에서는 이음 연산과 만남 연산을 각각 원소쌍의 상한과 하한으로 자연스럽게 정의할 수 있고, 대수학적으로 정의한 격자에서는 부분순서를 [math(a \preceq b \Leftrightarrow a \lor b = b \Leftrightarrow a \land b = a)]이라고 자연스럽게 정의할 수 있다.
3. 종류
3.1. 유계격자
최대원소와 최소원소가 존재하는 격자를 유계격자\[bounded lattice\]라고 한다. 예를 들어, 격자 [math((\mathcal P(\{1,2,3\}),\subseteq))]은 최대원소 [math(\{1,2,3\})]과 최소원소 [math(\varnothing)]을 가지고, 격자 [math(([0,1],\le))]은 최대원소 [math(1)]과 최소원소 [math(0)]을 가지므로 모두 유계격자이지만, 격자 [math((\R,\le))]는 최대원소와 최소원소 모두 존재하지 않으므로 유계격자가 아니다. 일반적으로 최대원소는 [math(1)], 최소원소는 [math(0)]으로 표기한다.3.2. 여원을 가지는 격자
유계격자 [math((A,\preceq))]의 어떤 원소 [math(a)]에 대해, [math(a \lor b = 1)]과 [math(a \land b = 0)]을 만족하는 원소 [math(b(\in A))]를 [math(a)]의 여원\[complement\]이라고 한다. 예를 들어, [math(0)]의 여원은 [math(1)]뿐이고, [math(1)]의 여원은 [math(0)]뿐이다. 여원은 원소에 따라 하나만 존재할 수도, 여러 개가 존재할 수도, 존재하지 않을 수도 있다. 모든 원소가 여원을 가지는 유계격자를 여원을 가지는 격자\[complemented lattice\]라고 한다. 예를 들어, 유계격자 [math((\mathcal P(\{1,2,3\}),\subseteq))]은 임의의 원소 [math(a(\subseteq \{1,2,3\}))]에 대해 여원 [math(\{1,2,3\} \setminus a(\subseteq \{1,2,3\}))]를 가지므로 여원을 가지는 격자이다. 하지만, 유계격자 [math(([0,1],\le))]은 원소 [math(\dfrac{1}{2})]의 여원이 존재하지 않으므로 여원을 가지는 격자가 아니다.3.3. 분배격자
이음 연산 [math(\lor)]과 만남 연산 [math(\land)]이 다음 조건을 만족하는 격자 [math((L,\lor,\land))]을 분배격자\[distributive lattice\]라고 한다.- 분배법칙[distributivity]: 임의의 원소 [math(a,b,c(\in L))]에 대해 [math(a \land (b \lor c) = (a \land b) \lor (a \land c))]이다.[10]
예를 들어, 격자 [math((\{\varnothing,\{1\},\{2\},\{3\},\{1,2,3\}\},\subseteq))]은 [math(\{1\} \land (\{2\} \lor \{3\}) = \{1\} \land \{1,2,3\} = \{1\})]이지만 [math((\{1\} \land \{2\}) \lor (\{1\} \land \{3\})= \varnothing \lor \varnothing = \varnothing)]이므로 분배격자가 아니다. 하지만, 격자 [math((\R,\le))]는 이음 연산 [math(\max)]와 만남 연산 [math(\min)] 사이의 분배법칙이 성립하므로 분배격자이다.
3.4. 전순서집합
집합 [math(A)]에 대해 다음 조건을 만족하는 이항관계 [math({\preceq}\bigl(\subseteq A^2\bigr))]를 전순서[total order]라고 한다.- 반사성: 임의의 원소 [math(a(\in A))]에 대해 [math(a \preceq a)]이다.
- 반대칭성: 임의의 원소 [math(a,b(\in A))]에 대해 [math(a \preceq b)]이고 [math(b \preceq a)]이면 [math(a = b)]이다.
- 추이성: 임의의 원소 [math(a,b,c(\in A))]에 대해 [math(a \preceq b)]이고 [math(b \preceq c)]이면 [math(a \preceq c)]이다.
- 강한 연결성\[strong connectivity\]: 임의의 원소 [math(a,b(\in A))]에 대해 [math(a \preceq b)] 또는 [math(b \preceq a)]이다.
전순서는 임의의 두 원소 사이에 순서 관계가 있음을 나타낸다. 전순서가 주어진 집합을 전순서집합\[totally ordered set\]이라고 한다.
집합 [math(A)]에 대해 다음 조건을 만족하는 이항관계 [math({\prec}\bigl(\subseteq A^2\bigr))]를 순전순서\[strict total order\]라고 한다.
- 비반사성: 임의의 원소 [math(a(\in A))]에 대해 [math(a \nprec a)]이다.
- 비대칭성: 임의의 원소 [math(a,b(\in A))]에 대해 [math(a \prec b)]이면 [math(b \nprec a)]이다.[11]
- 추이성: 임의의 원소 [math(a,b,c(\in A))]에 대해 [math(a \prec b)]이고 [math(b \prec c)]이면 [math(a \prec c)]이다.
- 연결성\[connectivity\]: 서로 다른 임의의 원소 [math(a,b(\in A))]에 대해 [math(a \prec b)] 또는 [math(b \prec a)]이다.
순전순서는 순부분순서와 비슷하게 전순서에서 반사적인 원소만 빼는 방식으로 자연스럽게 정의할 수 있다.
전순서는 부분순서이므로 전순서 [math({\preceq})]가 주어진 집합 [math(A)]를 부분순서집합 [math((A,{\preceq}))]로 생각할 수 있다. 이제 이 전순서집합이 격자임을 보이자. 임의의 원소 [math(a,b(\in A))]에 대해 일반성을 잃지 않고 [math(a \preceq b)]라고 가정하자. [math(b \succeq a)], [math(b \succeq b)]에서 [math(b)]는 [math(\{a,b\})]의 상계이고, [math(\{a,b\})]의 임의의 상계 [math(g(\in A))]에 대해 [math(b \preceq g)]이므로 [math(b)]는 [math(\{a,b\})]의 상한이다. 같은 방식으로 [math(a)]가 [math(\{a,b\})]의 하한임도 보일 수 있다. 따라서 [math((A,{\preceq}))]는 격자이다.
추가적으로 [math((A,{\preceq}))]의 이음 연산과 만남 연산이 분배법칙을 만족함을 보일 수 있다. 임의의 원소 [math(a,b,c(\in A))]에 대해, 가능한 순서 관계는 [math(a \preceq b \preceq c)], [math(a \preceq c \preceq b)], [math(b \preceq a \preceq c)], [math(b \preceq c \preceq a)], [math(c \preceq a \preceq b)], [math(c \preceq b \preceq a)]의 6가지뿐이다. [math(a \preceq b \preceq c)]인 경우, [math(a \land (b \lor c) = a \land c = a)], [math((a \land b) \lor (a \land c) = a \lor a = a)]에서 [math(a \land (b \lor c) = (a \land b) \lor (a \land c))]이다. 같은 방식으로 나머지 5가지 경우에 대해서 분배법칙이 성립함도 보일 수 있다. 따라서 이음 연산과 만남 연산이 분배법칙을 만족하므로 [math((A,{\preceq}))]는 분배격자이다.
3.5. 불 격자
여원을 가지는 격자이면서 분배격자인 격자를 불 격자\[Boolean lattice\] 또는 불 대수\[Boolean algebra\]라고 한다. 불 격자는 임의의 원소의 여원이 유일하게 존재한다는 성질이 있다. 불 격자 [math((A,{\preceq}))]의 어떤 원소 [math(a)]가 서로 다른 여원 [math(b,c(\in A))]를 가진다고 가정하자. 그러면 [math(b = b \land 1 = b \land (a \lor c) = (b \land a) \lor (b \land c) = 0 \lor (b \land c) = (a \land c) \lor (b \land c) = (a \lor b) \land c = 1 \land c = c)]에서 모순이 발생한다. 따라서 불 격자의 임의의 원소는 각각 유일한 여원을 가진다. 그래서 추가로 여원 연산 [math(\lnot)]을 정의할 수 있다.임의의 유한 불 격자는 어떤 유한집합의 멱집합과 부분순서 [math({\subseteq})]로 구성된 격자와 동형이다. 유한멱집합의 원소의 개수는 [math(2)]의 거듭제곱수이므로 유한 불 격자의 원소의 개수도 [math(2)]의 거듭제곱수이다. 원소의 개수가 가장 작은 불 격자는 원소의 개수가 [math(1\bigl(= 2^0\bigr))]인 불 격자이다. 이를 자명한 불 격자라고 하며, 여기서는 [math(0 = 1)]이 성립한다.
자명하지 않은 불 격자 중 원소의 개수가 최소인 격자는, 보통 불 대수라고 하면 떠올리는, 원소의 개수가 [math(2bigl(= 2^1bigr))]인 불 격자이다. [math(0)]은 거짓, [math(1)]은 참, [math({\lor})]은 논리합 연산, [math({\land})]은 논리곱 연산, [math(\lnot)]은 부정 연산이라고 생각하면 알고 있는 대로 모두 잘 작동함을 알 수 있다.
[1] [math({\subseteq} = \{(\{1\},\{1\}),(\{1\},\{1,2\}),(\{1\},\{1,2,3\}),\dots,(\{1,2,3\},\{1,2,3\})\})][2] [math({\subseteq} = \{(\{2\},\{2\}),(\{2\},\{1,2\}),(\{2\},\{2,3\}),\dots,(\{2,3,4\},\{2,3,4\})\})][3] [math({\le} = \{(1,1),(1,e),(1,\pi),\dots,(\pi,\pi)\})][4] 여기서 소괄호는 열린 구간을 뜻한다.[5] [math({\le} = \bigl\{(a,b) \in (-1,1)^2 \bigm| -1 < a \le b < 1\bigr\})][6] 비대칭성은 비반사성과 추이성에서 유도할 수 있으므로 조건에서 빼기도 한다. 여기서는 부분순서와의 비교를 위해 명시했다.[7] [math(m \mathbin| n)]은 [math(n)]이 [math(m)]으로 나누어떨어짐을 나타낸다. 예를 들어, [math(2 \mathbin| 4)]이다.[8] 멱등법칙은 흡수법칙에서 유도할 수 있으므로 조건에서 빼기도 한다. 여기서는 반격자와의 비교를 위해 명시했다.[9] 참고로 [math(a \lor b = b)]이면 [math(a \land b = a \land (a \lor b) = a)]이고, [math(a \land b = a)]이면 [math(a \lor b = (a \land b) \lor b = b \lor (a \land b) = b \lor (b \land a) = b)]이다. 즉, [math(a \lor b = b \Leftrightarrow a \land b = a)]이다.[10] 이것만 만족하면 임의의 원소 [math(a,b,c(\in L))]에 대해 [math(a \lor (b \land c) = (a \lor b) \land (a \lor c))]이기도 하다.[11] 비대칭성은 비반사성과 추이성에서 유도할 수 있으므로 조건에서 빼기도 한다. 여기서는 전순서와의 비교를 위해 명시했다.