logo

TechCodeview

격자:

L을 ∧와 ∨로 표시되는 만남과 결합이라는 두 개의 이진 연산으로 닫혀 있는 비어 있지 않은 집합으로 둡니다. 그런 다음 a, b, c가 L의 요소인 경우 다음 공리가 유지되면 L을 격자라고 합니다.

1) 교환법칙: -
(a) a ∧ b = b ∧ a (b) a ∨ b = b ∨ a

2) 결합법:-
(a) (a ∧ b)∧ c = a ∧(b∧ c) (b) (a ∨ b) ∨ c = a ∨ (b ∨ c)

3) 흡수 법칙: -
(a) a ∧ ( a ∨ b) = a (b) a ∨ ( a ∧ b) = a

이중성:

격자(L,∧,∨)에 있는 임의의 진술의 쌍대성은 ∧와 ∨를 교환하여 얻은 진술로 정의됩니다.

정수를 문자열로

예를 들어 , a ∧ (b ∨ a) = a ∨ a의 쌍대는 a ∨ (b ∧ a )= a ∧ a입니다.

경계 격자:

격자 L이 가장 큰 요소 1과 가장 작은 요소 0을 갖는 경우 경계 격자(bounded lattice)라고 합니다.

예:

  1. 교집합과 합집합의 연산에 따른 집합 S의 거듭제곱 집합 P(S)는 ∅가 P(S)의 최소 원소이고 집합 S가 P(S)의 최대 원소이므로 유계 격자입니다.
  2. +ve 정수 I의 집합+일반적인 순서에 따라 도안은 최소 요소 1이 있지만 최대 요소가 존재하지 않기 때문에 경계 격자가 아닙니다.

경계 격자의 속성:

L이 경계 격자이면 모든 요소 a ∈ L에 대해 다음과 같은 항등식을 갖습니다.

  1. a ∨ 1 = 1
  2. a ∧1= a
  3. a ∨0=a
  4. ∧0=0

정리: 모든 유한 격자 L = {a1,ㅏ2,ㅏ삼....ㅏN}는 제한되어 있습니다.

증거: 우리는 유한 격자를 제공했습니다:

엘 = {a1,ㅏ2,ㅏ삼....ㅏN}

따라서 격자 L의 가장 큰 요소는1∨ 에2∨ 에3∨....∨aN.

또한, 격자 L의 최소 요소는1∧ 에2∧a삼∧....∧아N.

왜냐하면 모든 유한 격자에는 가장 큰 요소와 가장 작은 요소가 존재하기 때문입니다. 따라서 L은 유계입니다.

하위 격자:

비어 있지 않은 부분 집합 L을 고려하십시오.1격자 L. 그러면 L1L이면 L의 부격자(sub-lattice)라고 불린다.1그 자체는 격자입니다. 즉, L의 연산, 즉 a ∨ b ∈ L1그리고 a ∧ b ∈ L1∈L이 될 때마다1그리고 b ∈ L1.

메모리 교환

예: 모든 +ve 정수 I의 격자를 고려하십시오.+나눗셈의 작동 하에서. 격자 DNn > 1의 모든 약수는 I의 하위 격자입니다.+.

D의 모든 하위 격자를 결정합니다.30최소한 4개의 요소를 포함하는 D30={1,2,3,5,6,10,15,30}.

해결책: D의 하위 격자304개 이상의 요소를 포함하는 요소는 다음과 같습니다.

1. {1, 2, 6, 30} 2. {1, 2, 3, 30}
3. {1, 5, 15, 30} 4. {1, 3, 6, 30}
5. {1, 5, 10, 30} 6. {1, 3, 15, 30}
7. {2, 6, 10, 30}

동형 격자:

격자 2개 L1그리고 나2L로부터 전단사(bijection)가 있는 경우 동형 격자(isomorphic lattice)라고 불립니다.1L에게2즉, f:L1⟶ 엘2, f (a ∧ b) =f(a)∧ f(b) 및 f (a ∨ b) = f (a) ∨ f (b)

예: 그림에 표시된 격자가 동형인지 확인하십시오.

해결책: 그림에 표시된 격자는 동형입니다. f = {(a, 1), (b, 2), (c, 3), (d, 4)} 매핑을 고려하십시오. 예를 들어 f (b ∧ c) = f (a) = 1입니다. 또한, f(b) ∧ f(c) = 2 ∧ 3 = 1이 됩니다.

격자

분포 격자:

L의 임의의 요소 a, b 및 c에 대해 다음 분배 특성을 만족하는 격자 L을 분포 격자라고 합니다.

  1. a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
  2. a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)

격자 L이 위의 성질을 만족하지 않는 경우, 이를 비분배 격자라고 합니다.

예:

  1. 교집합과 합집합의 연산에서 집합 S의 거듭제곱 집합 P(S)는 분배함수이다. 부터,
    a ∩ (b ∪ c) = (a ∩ b) ∪ (a ∩ c)
    그리고 P(S)의 임의의 세트 a, b 및 c에 대해 a ∪ (b ∩ c) = (a ∪ b) ∩ (a ∪c)입니다.
  2. 그림 II에 표시된 격자는 분포형입니다. 이후 1, 2, 3, 4에서 가져온 모든 순서 트리플에 대한 분배 속성을 만족합니다.
격자

보완 및 보완 격자:

L을 하한 o와 상한 I를 갖는 경계 격자로 둡니다. L인 경우 a를 요소로 둡니다. a ∨ x = I이고 a ∧ x = 0인 경우 L의 요소 x를 a의 보수라고 합니다.

L이 유계이고 L의 모든 요소가 보수를 갖는 경우 격자 L은 보수라고 합니다.

예: 그림에서 a와 c의 보수를 결정합니다.

격자

해결책: a의 보수는 d이다. 이후, a ∨ d = 1 및 a ∧ d = 0

자바 익명 함수

c의 보수는 존재하지 않습니다. 왜냐하면 c ∨ c'=1이고 c ∧ c'= 0인 요소 c는 존재하지 않기 때문입니다.

모듈형 격자:

a ∨ (b ∧ c) = (a ∨ b) ∧ c인 경우 격자(L, ∧,∨)는 a ≤ c인 경우 모듈형 격자라고 합니다.

격자의 직접 생성물:

렛(엘1∨1∧1)그리고 나2∨2∧2) 두 개의 격자가 되어야 합니다. 그러면 (L, ∧,∨)는 격자의 직접 곱입니다. 여기서 L = L1xL2여기서 L의 이진 연산 ∨(결합) 및 ∧(만남)은 임의의 (a1,비1) 그리고 (a2,비2) 안에.

(ㅏ1,비1)∨(2,비2)=(아1∨1ㅏ2,비1∨2비2)
그리고 (a1,비1) ∧ (2,비2)=(아1∧1ㅏ2,비1∧2비2).

예: 그림과 같이 격자 (L, ≤)를 고려하십시오. 여기서 L = {1, 2}입니다. 격자 결정(L2, ≤), 여기서 L2=L x L.

격자

해결책: 격자(L2, ≤)가 그림에 표시됩니다.

격자