Logikk Cheatsheet

Logikk Cheatsheet

Gloser

Kardinalitet
Antall elementer i et sett/Lengden på settet.
Skrives slik:

|M|

Potensmengde
(eng: Power Set)
Alle mulige subset av et sett (Inkludert det tomme settet).
Eks:

M={1,2}P(M)={{},{1},{2},{1,2}}

Kardinalitet av en potensmengde av et sett er

|P(M)|=2|M|=22=4

Binærrelasjon
En binærrelasjon er en vilkårlig relasjon mellom to sett.
F.eks. om man har to sett:

Personer={Arne,Ina}Frukt={Eple,Appelsin,Kiwi}

Så kan man lage en binærrelasjon

Liker={(Arne,Eple),(Arne,Kiwi),(Ina,Eple)}

Dette forteller oss at Arne like Eple og Kiwi. Ina liker kune Eple.
Det vil alltid gjelde at en binær relasjon vil være et subset av kryssproduktet mellom de to settene. Dette kan skrives slik:

LikerPersoner×Frukt

Funksjon
En relasjon er en funksjon hvis og bare hvis alle elementer i det første settet har en relasjon til det andre settet OG alle elementene fra det første settet har relasjon til kun ett element i det andre settet.
Sagt på en annen måte, uansett hvilket element du velger fra sett 1 vil du finne én relasjon til ett element i det andre settet.

Tillukning

En tillukning er en utvidelse av relasjonen på den minste mulige måten man kan for å tilfredsstille kravet. Man må altså alltid huske å ta med originalsettet.

Refleksiv tillukning
Den refleksive tillukningen til en relasjon er et sett med den originale relasjonen i tillegg til å legge til alle relasjoner hvor elementene peker på seg selv.
Eks:

A={(1,2)}RefleksivTillukningAvA={(1,2),(1,1),(2,2),(3,3)}

Symmetrisk tillukning
En symmetrisk tillukning av et sett er et sett der alle relasjoner peker begge veier.
Eks:

Rel={(1,2)}SymmetrikTillukningAvRel={(1,2),(2,1)}

Transitive tillukningen

Dersom man kommer seg fra element X til Y og fra Y til Z, så må man også komme seg fra X til Z.
Eks:

Rel={(1,2),(2,3)}TransitivTillukningAvRel={(1,2),(2,3),(1,3)}

Vi la til (1,3) fordi vi kommer fra 1 til 2 og 2 til 3, men ikke fra 1 til 3 i originalsettet.
Enklere sagt: Om man kommer seg fra a til b med mer enn ett steg, så må man også legge til en kobling mellom a og b slik at man kan komme seg der med ett steg.

Ekvivalensrelasjon
En relasjon kan kalles en ekvivalensrelasjon dersom den er transitiv, symmetrisk og refleksiv.

Anti-symmetrisk
En relasjon er anti-symmetrisk dersom ingen av relasjonene har en symmetrisk relasjo. (a,b), (b,a) er symmetrisk. (a,b),(b,c) er anti-symmetrisk

Partiell ordning
En relasjon er en partiell ordning dersom den er transitiv, refleksiv og anti-symmetrisk.