DISKRĒTĀS MATEMĀTIKAS REŽĢI - DISKRĒTĀ MATEMĀTIKA

Apzīmēsim ar ∧ un ∨ apzīmētu kopu, kas nav tukša. Tad L sauc par režģi, ja pastāv šādas aksiomas, kur a, b, c ir L elementi:

1) Komutatīvais likums: -
(a) a ∧ b = b ∧ a (b) a ∨ b = b ∨ a

2) Asociatīvās tiesības:
(a) (a ∧ b) ∧ c = a ∧(b∧ c) (b) (a ∨ b) ∨ c = a ∨ (b ∨ c)

3) Absorbcijas likums: -
(a) a ∧ ( a ∨ b) = a (b) a ∨ ( a ∧ b) = a

Dualitāte:

Jebkura apgalvojuma duālis režģī (L,∧ ,∨ ) ir definēts kā apgalvojums, kas iegūts, mainot ∧ un ∨.

Piemēram , a duālis ∧ (b ∨ a) = a ∨ a ir a ∨ (b ∧ a )= a ∧ a

Ierobežotie režģi:

Režģi L sauc par ierobežotu režģi, ja tajā ir lielākais elements 1 un mazākais elements 0.

Piemērs:

Kopas S jaudas kopa P(S) krustošanās un savienojuma operācijās ir ierobežots režģis, jo ∅ ir P(S) mazākais elements un kopa S ir P(S) lielākais elements.
+ve vesela skaitļa kopa I ₊parastajā secībā ≦ nav ierobežots režģis, jo tai ir vismazākais elements 1, bet lielākais elements neeksistē.

Ierobežoto režģu īpašības:

Ja L ir ierobežots režģis, tad jebkuram elementam a ∈ L mums ir šādas identitātes:

a ∨ 1 = 1
a ∧1= a
a ∨0=a
a ∧0=0

Teorēma: Pierādīt, ka katrs galīgais režģis L = {a ₁,a ₂,a ₃....a _n} ir ierobežots.

Pierādījums: Mēs esam devuši ierobežoto režģi:

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

Tādējādi lielākais režģa L elements ir a ₁∨ a ₂∨ a _{3∨....∨a _n.}

Arī režģa L mazākais elements ir a ₁∧ a ₂∧a ₃∧....∧a _n.

Tā kā lielākais un mazākais elements pastāv katram ierobežotam režģim. Tādējādi L ir ierobežots.

Apakšrežģi:

Apsveriet apakškopu L, kas nav tukša ₁no režģa L. Tad L ₁sauc par L apakšrežģi, ja L ₁pati par sevi ir režģis, t.i., L darbība, t.i., a ∨ b ∈ L ₁un a ∧ b ∈ L ₁ikreiz, kad ∈ L ₁un b ∈ L ₁.

Piemērs: Apsveriet visu +ve veselo skaitļu režģi I ₊saskaņā ar dalāmības operāciju. Režģis D _nno visiem n > 1 dalītājiem ir I apakšrežģis ₊.

Nosakiet visus D apakšrežģus ₃₀kas satur vismaz četrus elementus, D ₃₀={1,2,3,5,6,10,15,30}.

Risinājums: D apakšrežģi ₃₀kas satur vismaz četrus elementus, ir šādi:

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}

Izomorfie režģi:

Divi režģi L ₁un L ₂tiek saukti par izomorfiem režģiem, ja ir bijekcija no L ₁uz L ₂t.i., f: L ₁⟶ L ₂, lai f (a ∧ b) = f(a) ∧ f(b) un f (a ∨ b) = f (a) ∨ f (b)

Piemērs: Nosakiet, vai attēlā parādītie režģi ir izomorfi.

Risinājums: Attēlā redzamie režģi ir izomorfi. Apsveriet kartējumu f = {(a, 1), (b, 2), (c, 3), (d, 4)}. Piemēram, f (b ∧ c) = f (a) = 1. ir f (b) ∧ f (c) = 2 ∧ 3 = 1

Sadales režģis:

Režģi L sauc par sadales režģi, ja jebkuram L elementam a, b un c tas atbilst šādām sadales īpašībām:

a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)

Ja režģis L neapmierina iepriekš minētās īpašības, to sauc par nesadalošo režģi.

Piemērs:

Kopas S jaudas kopa P (S) krustojuma un savienojuma darbībā ir sadales funkcija. Kopš,
a ∩ (b ∪ c) = (a ∩ b) ∪ (a ∩ c)
un arī a ∪ (b ∩ c) = (a ∪ b) ∩ (a ∪c) jebkurai P(S) kopai a, b un c.
II attēlā parādītais režģis ir sadalījums. Tā kā tas atbilst sadales īpašībām visiem pasūtītajiem trīskāršiem, kas ņemti no 1, 2, 3 un 4.

Papildinājumi un papildinātie režģi:

Lai L ir ierobežots režģis ar apakšējo robežu o un augšējo robežu I. Lai a ir elements, ja L. Elementu x sauc par a papildinājumu, ja a ∨ x = I un a ∧ x = 0

Tiek uzskatīts, ka režģis L ir papildināts, ja L ir ierobežots un katram L elementam ir papildinājums.

Piemērs: Nosakiet a un c papildinājumu attēlā:

Risinājums: A papildinājums ir d. Tā kā a ∨ d = 1 un a ∧ d = 0

C papildinājums neeksistē. Tā kā nepastāv tāds elements c, ka c ∨ c'=1 un c ∧ c'= 0.

Moduļu režģis:

Režģi (L, ∧,∨) sauc par modulāro režģi, ja a ∨ (b ∧ c) = (a ∨ b) ∧ c ikreiz, kad a ≦ c.

Tiešais režģu produkts:

Ļaujiet (L ₁∨ ₁∧ ₁) un (L ₂∨ ₂∧ ₂) ir divi režģi. Tad (L, ∧, ∨) ir režģu tiešais reizinājums, kur L = L ₁x L ₂kurā binārā darbība ∨(pievienoties) un ∧(satiekas) uz L ir tāda, ka jebkurai (a ₁,b ₁) un (a ₂,b ₂) L.