Lad L være et ikke-tomt sæt lukket under to binære operationer kaldet meet and join, angivet med ∧ og ∨. Så kaldes L et gitter, hvis følgende aksiomer gælder, hvor a, b, c er elementer i L:

1) Kommutativ lov: -
(a) a ∧ b = b ∧ a (b) a ∨ b = b ∨ a

2) Associativ ret:-
(a) (a ∧ b)∧ c = a ∧(b∧ c) (b) (a ∨ b) ∨ c = a ∨ (b ∨ c)

3) Absorptionslov: -
(a) a ∧ ( a ∨ b) = a (b) a ∨ ( a ∧ b) = a

Dualitet:

Dualen af ​​ethvert udsagn i et gitter (L,∧ ,∨ ) er defineret til at være et udsagn, der opnås ved at ombytte ∧ og ∨.

For eksempel , dualen af ​​a ∧ (b ∨ a) = a ∨ a er a ∨ (b ∧ a )= a ∧ a

Afgrænsede gitter:

Et gitter L kaldes et afgrænset gitter, hvis det har det største element 1 og et mindste element 0.

Eksempel:

1. Potensmængden P(S) af mængden S under operationerne af skæring og forening er et afgrænset gitter, da ∅ er det mindste element af P(S), og mængden S er det største element af P(S).
2. Sættet af +ve heltal I₊under den sædvanlige rækkefølge af ≦ er ikke et afgrænset gitter, da det har et mindste element 1, men det største element eksisterer ikke.

Egenskaber af afgrænsede gitter:

Hvis L er et afgrænset gitter, så har vi for ethvert element a ∈ L, følgende identiteter:

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

Sætning: Bevis, at hvert endeligt gitter L = {a₁,en₂,en₃....en_n} er afgrænset.

Bevis: Vi har givet det endelige gitter:

java regex $

L = {a₁,en₂,en₃....en_n}

Således er det største element i gitter L a₁∨ en₂∨ en_{3∨....∨an.}

Det mindste element i gitter L er også a₁∧ a₂∧a₃∧....∧a_n.

Siden eksisterer de største og mindste elementer for hvert endeligt gitter. Derfor er L afgrænset.

Undergitter:

Overvej en ikke-tom delmængde L₁af et gitter L. Derefter L₁kaldes et undergitter af L, hvis L₁i sig selv er et gitter, dvs. driften af ​​L, dvs. a ∨ b ∈ L₁og a ∧ b ∈ L₁hver gang en ∈ L₁og b ∈ L₁.

Eksempel: Overvej gitteret af alle +ve heltal I₊under drift af delelighed. Gitteret D_naf alle divisorer af n > 1 er et undergitter af I₊.

Bestem alle undergitter af D₃₀der indeholder mindst fire elementer, D₃₀={1,2,3,5,6,10,15,30}.

Løsning: Undergitteret af D₃₀der indeholder mindst fire elementer er som følger:

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}

Isomorfe gitter:

To gitter L₁og L₂kaldes isomorfe gitter, hvis der er en bijektion fra L₁til L₂dvs. f: L₁⟶ L₂, sådan at f (a ∧ b) =f(a)∧ f(b) og f (a ∨ b) = f (a) ∨ f (b)

Eksempel: Bestem, om gitterne vist i fig. er isomorfe.

Løsning: Gitterne vist i fig. er isomorfe. Overvej kortlægningen f = {(a, 1), (b, 2), (c, 3), (d, 4)}. For eksempel f (b ∧ c) = f (a) = 1. Vi har f (b) ∧ f(c) = 2 ∧ 3 = 1

Fordelingsgitter:

Et gitter L kaldes fordelingsgitter, hvis det for nogle af elementerne a, b og c i L opfylder følgende fordelingsegenskaber:

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

Hvis gitteret L ikke opfylder ovenstående egenskaber, kaldes det et ikke-distributivt gitter.

Eksempel:

1. Effektsættet P (S) af sættet S under driften af ​​kryds og forening er en fordelingsfunktion. Siden,
   a ∩ (b ∪ c) = (a ∩ b) ∪ (a ∩ c)
   og også a ∪ (b ∩ c) = (a ∪ b) ∩ (a ∪c) for enhver mængde a, b og c af P(S).
2. Gitteret vist i fig. II er et distributivt. Da det opfylder fordelingsegenskaberne for alle ordnede tripler, som er taget fra 1, 2, 3 og 4.

Komplementer og komplementerede gitter:

Lad L være et afgrænset gitter med nedre grænse o og øvre grænse I. Lad a være et element, hvis L. Et element x i L kaldes et komplement til a, hvis a ∨ x = I og a ∧ x = 0

Et gitter L siges at være komplementeret, hvis L er afgrænset, og hvert element i L har et komplement.

Eksempel: Bestem komplementet til a og c i fig.

Løsning: Komplementet af a er d. Da a ∨ d = 1 og a ∧ d = 0

Komplementet af c eksisterer ikke. Da der ikke eksisterer noget element c, således at c ∨ c'=1 og c ∧ c'= 0.

Modulært gitter:

Et gitter (L, ∧,∨) kaldes et modulært gitter, hvis a ∨ (b ∧ c) = (a ∨ b) ∧ c hver gang a ≦ c.

Direkte produkt af gitter:

Lad (L₁∨₁∧₁) og (L₂∨₂∧₂) være to gitter. Så (L, ∧,∨) er det direkte produkt af gitter, hvor L = L₁x L₂hvor den binære operation ∨(join) og ∧(mødes) på L er sådan, at for enhver (a₁,b₁) og (en₂,b₂) i L.

(en₁,b₁)∨( en₂,b₂)=(a₁∨₁-en₂,b₁∨₂b₂)
og (a₁,b₁) ∧ ( en₂,b₂)=(a₁∧₁-en₂,b₁∧₂b₂).

Eksempel: Betragt et gitter (L, ≦) som vist i fig. hvor L = {1, 2}. Bestem gitterne (L², ≦), hvor L²=L x L.

Løsning: Gitteret (L², ≦) er vist i fig.