Niech L będzie niepustym zbiorem zamkniętym dwiema operacjami binarnymi zwanymi spotkaniem i złączeniem, oznaczonymi przez ∧ i ∨. Następnie L nazywa się kratą, jeśli obowiązują następujące aksjomaty, gdzie a, b, c są elementami w L:

1) Prawo przemienne: -
(a) za ∧ b = b ∧ za (b) za ∨ b = b ∨ a

2) Prawo stowarzyszeniowe: –
(a) (a ∧ b)∧ do = za ∧(b∧ do) (b) (a ∨ b) ∨ do = za ∨ (b ∨ do)

konwencje nazewnictwa Java

3) Prawo absorpcji: -
(a) za ∧ ( za ∨ b) = za (b) za ∨ ( za ∧ b) = za

Dwoistość:

Podwójność dowolnego stwierdzenia w siatce (L,∧,∨) definiuje się jako stwierdzenie uzyskane przez zamianę ∧ i ∨.

Na przykład , liczba podwójna a ∧ (b ∨ a) = a ∨ a to a ∨ (b ∧ a )= a ∧ a

Ograniczone kraty:

Sieć L nazywa się siecią ograniczoną, jeśli ma największy element 1 i najmniejszy element 0.

Przykład:

1. Zbiór potęg P(S) zbioru S w ramach operacji przecięcia i sumy jest siatką ograniczoną, ponieważ ∅ jest najmniejszym elementem P(S), a zbiór S jest największym elementem P(S).
2. Zbiór +ve liczby całkowitej I₊w zwykłym porządku ≦ nie jest siatką ograniczoną, ponieważ ma najmniejszy element 1, ale największy element nie istnieje.

Właściwości ograniczonych krat:

Jeśli L jest siatką ograniczoną, to dla dowolnego elementu a ∈ L mamy następujące tożsamości:

jednostka arytmetyczno-logiczna

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

Twierdzenie: Udowodnić, że każda skończona sieć L = {a₁,A₂,A₃....A_N} jest ograniczona.

Dowód: Podaliśmy skończoną kratę:

L = {a₁,A₂,A₃....A_N}

Zatem największym elementem krat L jest a₁∨ a₂∨ a_{3∨.....∨aN.}

Ponadto najmniejszym elementem sieci L jest a₁∧ a₂∧a₃∧....∧a_N.

Ponieważ dla każdej skończonej sieci istnieją największe i najmniejsze elementy. Zatem L jest ograniczone.

Podsieci:

Rozważmy niepusty podzbiór L₁siatki L. Następnie L₁nazywa się podsiecią L, jeśli L₁samo w sobie jest siecią, tj. działaniem L, tj. a ∨ b ∈ L₁oraz a ∧ b ∈ L₁kiedykolwiek a ∈ L₁oraz b ∈ L₁.

Przykład: Rozważmy kratę wszystkich +ve liczb całkowitych I₊w ramach działania podzielności. Krata D_Nwszystkich dzielników n > 1 jest podsiecią I₊.

Wyznacz wszystkie podsieci D₃₀zawierające co najmniej cztery elementy, D₃₀={1,2,3,5,6,10,15,30}.

Rozwiązanie: Podsieci D₃₀zawierające co najmniej cztery elementy, są następujące:

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}

pobierz filmy z YouTube vlc

Kraty izomorficzne:

Dwie kraty L₁i ja₂nazywane są kratami izomorficznymi, jeśli istnieje bijekcja z L₁do L₂tj. f: L₁⟶ L₂, takie, że f (a ∧ b) =f(a)∧ f(b) i f (a ∨ b) = fa (a) ∨ f (b)

Przykład: Określ, czy sieci pokazane na rys. są izomorficzne.

Rozwiązanie: Kraty pokazane na rys. są izomorficzne. Rozważmy odwzorowanie f = {(a, 1), (b, 2), (c, 3), (d, 4)}. Na przykład f (b ∧ c) = f (a) = 1. Ponadto, my mieć f (b) ∧ f(c) = 2 ∧ 3 = 1

Krata rozdzielcza:

Sieć L nazywa się siecią rozdzielczą, jeśli dla dowolnych elementów a, b i c sieci L spełnia następujące własności rozdzielcze:

1. za ∧ (b ∨ do) = (a ∧ b) ∨ (a ∧ do)
2. za ∨ (b ∧ do) = (a ∨ b) ∧ (a ∨ do)

Jeżeli sieć L nie spełnia powyższych właściwości, nazywa się ją siecią nierozdzielną.

Przykład:

1. Zbiór mocy P (S) zbioru S pod działaniem przecięcia i sumy jest funkcją rozdzielczą. Od,
   za ∩ (b ∪ c) = (a ∩ b) ∪ (a ∩ do)
   i także a ∪ (b ∩ c) = (a ∪ b) ∩ (a ∪c) dla dowolnych zbiorów a, b i c P(S).
2. Krata pokazana na rys. II jest rozdzielnicą. Ponieważ spełnia właściwości rozdzielcze dla wszystkich uporządkowanych trójek, które pochodzą z 1, 2, 3 i 4.

Uzupełnienia i uzupełnione kraty:

Niech L będzie kratą ograniczoną z dolną granicą o i górną granicą I. Niech a będzie elementem, jeśli L. Element x w L nazywa się dopełnieniem a, jeśli a ∨ x = I i a ∧ x = 0

Mówi się, że krata L jest uzupełniona, jeśli L jest ograniczona i każdy element w L ma dopełnienie.

Przykład: Określ uzupełnienie a i c na rys.:

ciąg na liczbę całkowitą

Rozwiązanie: Dopełnieniem a jest d. Ponieważ a ∨ d = 1 i a ∧ d = 0

Dopełnienie c nie istnieje. Nie istnieje bowiem żaden element c taki, że c ∨ c'=1 i c ∧ c'= 0.

Krata modułowa:

Kratę (L, ∧,∨) nazywa się siecią modułową, jeśli a ∨ (b ∧ c) = (a ∨ b) ∧ c, gdy a ≦ c.

string.format w Javie

Bezpośredni produkt krat:

Niech (l₁∨₁∧₁)i ja₂∨₂∧₂) będą dwiema kratami. Wtedy (L, ∧,∨) jest bezpośrednim iloczynem sieci, gdzie L = L₁x L₂w którym operacje binarne ∨(łączenie) i ∧(spotykanie) na L są takie, że dla dowolnego (a₁,B₁) i (a₂,B₂) w l.

(A₁,B₁)∨(a₂,B₂)=(a₁∨₁A₂,B₁∨₂B₂)
i (a₁,B₁) ∧ ( a₂,B₂)=(a₁∧₁A₂,B₁∧₂B₂).

Przykład: Rozważmy kratę (L, ≦), jak pokazano na ryc. gdzie L = {1, 2}. Wyznacz kraty (L², ≦), gdzie L²= dł. x dł.

Rozwiązanie: Krata (L², ≦) pokazano na rys.: