Låt L vara en icke-tom uppsättning stängd under två binära operationer som kallas meet and join, betecknade med ∧ och ∨. Då kallas L ett gitter om följande axiom gäller där a, b, c är element i L:

e-r modelldiagram

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

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

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

Dualitet:

Dualen av varje påstående i ett gitter (L,∧ ,∨ ) definieras som ett påstående som erhålls genom att byta ut ∧ och ∨.

Till exempel , dualen av a ∧ (b ∨ a) = a ∨ a är a ∨ (b ∧ a )= a ∧ a

Avgränsade gitter:

Ett gitter L kallas ett begränsat gitter om det har största element 1 och minst element 0.

Exempel:

1. Effektmängden P(S) för mängden S under operationerna för skärning och förening är ett begränsat gitter eftersom ∅ är det minsta elementet av P(S) och mängden S är det största elementet av P(S).
2. Mängden +ve heltal I₊under den vanliga ordningen ≦ är inte ett begränsat gitter eftersom det har ett minsta element 1 men det största elementet existerar inte.

Egenskaper för avgränsade gitter:

Om L är ett begränsat gitter, så har vi för alla element a ∈ L följande identiteter:

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

Sats: Bevisa att varje ändligt gitter L = {a₁,a₂,a₃....a_n} är avgränsad.

Bevis: Vi har gett det finita gittret:

L = {a₁,a₂,a₃....a_n}

inkapsling java

Således är det största elementet i gitter L a₁∨ a₂∨ a_{3∨....∨an.}

Det minsta elementet i gitter L är också a₁∧ a₂∧a₃∧....∧a_n.

Eftersom de största och minsta elementen finns för varje finit gitter. Därför är L begränsat.

Sub-gitter:

Tänk på en icke-tom delmängd L₁av ett galler L. Sedan L₁kallas ett sub-gitter av L om L₁i sig är ett gitter, dvs. driften av L, dvs. a ∨ b ∈ L₁och a ∧ b ∈ L₁närhelst en ∈ L₁och b ∈ L₁.

Exempel: Betrakta gittret för alla +ve heltal I₊under funktion av delbarhet. Gallret D_nav alla divisorer av n > 1 är ett subgitter av I₊.

Bestäm alla undergitter för D₃₀som innehåller minst fyra element, D₃₀={1,2,3,5,6,10,15,30}.

Lösning: Undergittren till D₃₀som innehåller minst fyra element är följande:

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}

Isomorfa gitter:

Två galler L₁och jag₂kallas isomorfa gitter om det finns en bijektion från L₁till mig₂dvs f: L₁⟶ L₂, så att f (a ∧ b) =f(a)∧ f(b) och f (a ∨ b) = f (a) ∨ f (b)

Exempel: Bestäm om gittren som visas i fig är isomorfa.

Lösning: Gitterna som visas i fig är isomorfa. Betrakta mappningen f = {(a, 1), (b, 2), (c, 3), (d, 4)}. Till exempel f (b ∧ c) = f (a) = 1. Vi har f (b) ∧ f(c) = 2 ∧ 3 = 1

Distributionsgitter:

Ett gitter L kallas distributionsgitter om det för några element a, b och c i L uppfyller följande fördelningsegenskaper:

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

Om gittret L inte uppfyller ovanstående egenskaper kallas det ett icke-distributivt gitter.

Exempel:

1. Effektuppsättningen P (S) för uppsättningen S under drift av korsning och förening är en fördelningsfunktion. Eftersom,
   a ∩ (b ∪ c) = (a ∩ b) ∪ (a ∩ c)
   och även a ∪ (b ∩ c) = (a ∪ b) ∩ (a ∪c) för alla mängder a, b och c av P(S).
2. Gallret som visas i fig II är ett fördelningsorgan. Eftersom den uppfyller fördelningsegenskaperna för alla ordnade trippel som är tagna från 1, 2, 3 och 4.

Kompletterande och kompletterade gitter:

Låt L vara ett avgränsat gitter med nedre gräns o och övre gräns I. Låt a vara ett element om L. Ett element x i L kallas ett komplement till a om a ∨ x = I och a ∧ x = 0

Ett gitter L sägs vara komplementerat om L är begränsat och varje element i L har ett komplement.

Exempel: Bestäm komplementet till a och c i fig.

numpy unik

Lösning: Komplementet till a är d. Eftersom a ∨ d = 1 och a ∧ d = 0

Komplementet till c finns inte. Eftersom det inte finns något element c så att c ∨ c'=1 och c ∧ c'= 0.

Modular galler:

Ett gitter (L, ∧,∨) kallas ett modulärt gitter om a ∨ (b ∧ c) = (a ∨ b) ∧ c närhelst a ≦ c.

Direkt produkt av gitter:

Låt (L₁∨₁∧₁)och jag₂∨₂∧₂) vara två galler. Då (L, ∧,∨) är den direkta produkten av gitter, där L = L₁x L₂där den binära operationen ∨(join) och ∧(meet) på L är sådana att för någon (a₁,b₁) och (a₂,b₂) i L.

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

Exempel: Betrakta ett gitter (L, ≦) som visas i fig. där L = {1, 2}. Bestäm gittren (L², ≦), där L²=L x L.

Lösning: Gallret (L², ≦) visas i fig: