Ett gitter eller lattice är inom matematiken en partiellt ordnad mängd i vilken varje par av element har en minsta övre gräns och en största undre gräns. De kan även kategoriseras som algebraiska strukturer som uppfyller vissa axiomatiska identiteter. Varje gitter kan representeras av ett Hassediagram.

Gitter som partiellt ordnade mängderRedigera

En partiellt ordnad mängd (L,<) är ett gitter om varje par av element i mängden har en minsta övre gräns och en största undre gräns. För ett sådant par (a, b) betecknas den minsta övre gränsen med a   b, den största undre gränsen med a   b. På detta vis definierar vi gränserna som binära operationer. Motsvarande mängdoperation, att från en icketom ändlig delmängd   erhålla minsta övre gräns (respektive största undre gräns) betecknas   (resp. ). Gittret är komplett om mängdoperationen kan utsträckas till alla delmängder av L, även den tomma mängden och eventuella oändliga delmängder.

Ett gitter (L,   kallas en Boolesk algebra om det är distributivt och varje element har ett komplement. Ett slutet gitter har ett största och ett minsta element, vilka normalt betecknas med 1 respektive 0. Ett komplett gitter är alltid slutet, med   och  . Omvänt är ett ändligt slutet gitter alltid komplett.

Se ävenRedigera

KällorRedigera

  • Birkhoff, G. Lattice Theory, Am. Math. Soc., 1967.
  • Bäckström, Karl-Johan, Diskret matematik, Studentlitteratur, 1986.