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:
- 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).
- 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:
- a ∨ 1 = 1
- a ∧1= a
- a ∨0=a
- a ∧0=0
Sats: Bevisa att varje ändligt gitter L = {a1,a2,a3....an} är avgränsad.
Bevis: Vi har gett det finita gittret:
L = {a1,a2,a3....an}
inkapsling java
Således är det största elementet i gitter L a1∨ a2∨ a3∨....∨an.
Det minsta elementet i gitter L är också a1∧ a2∧a3∧....∧an.
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 L1av ett galler L. Sedan L1kallas ett sub-gitter av L om L1i sig är ett gitter, dvs. driften av L, dvs. a ∨ b ∈ L1och a ∧ b ∈ L1närhelst en ∈ L1och b ∈ L1.
Exempel: Betrakta gittret för alla +ve heltal I+under funktion av delbarhet. Gallret Dnav alla divisorer av n > 1 är ett subgitter av I+.
Bestäm alla undergitter för D30som innehåller minst fyra element, D30={1,2,3,5,6,10,15,30}.
Lösning: Undergittren till D30som 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 L1och jag2kallas isomorfa gitter om det finns en bijektion från L1till mig2dvs f: L1⟶ L2, 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:
- a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
- a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
Om gittret L inte uppfyller ovanstående egenskaper kallas det ett icke-distributivt gitter.
Exempel:
- 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). - 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 (L1∨1∧1)och jag2∨2∧2) vara två galler. Då (L, ∧,∨) är den direkta produkten av gitter, där L = L1x L2där den binära operationen ∨(join) och ∧(meet) på L är sådana att för någon (a1,b1) och (a2,b2) i L.
(a1,b1)∨( a2,b2)=(a1∨1a2,b1∨2b2)
och (a1,b1) ∧ ( en2,b2)=(a1∧1a2,b1∧2b2).
Exempel: Betrakta ett gitter (L, ≦) som visas i fig. där L = {1, 2}. Bestäm gittren (L2, ≦), där L2=L x L.
Lösning: Gallret (L2, ≦) visas i fig:
