IN1150 - begreper

Mengde

En endelig eller uendelig samling av objekter, hvor rekkefølge og antall forekomster av hvert objekt ignoreres. { }

Union

Mengden som inneholder alle elementer som befinner seg i mengden A og B. U

Snitt

Mengden som inneholder kun elementer som er tilfelles for mengden A og B. ∩

Mengdedifferanse

Mengden A minus Mengden B. \

Delmengde

En mengde hvor alle elementer også er inneholdt i en annen mengde. ⊆

Tuppel

En samling av n-objekter (n-tuppel), hvor rekke og antall forekomster har betydning. <>

Utsagn

Noe som kan være sant eller usant. Eks. En setning, ytring eller påstand.

Atomære utsagn

Et utsagn som ikke kan brytes ned til andre utsagn.

Utsagnsvariabel

En variabel som er enten sann eller usann. Også kjent som en atomær formell. P, Q, R

Konnektiv

Symboler som beskriver forholdet mellom utsagnsvariabler.

Negasjon ¬

Konjunksjon ∧

Disjunksjon ∨

Implikasjon →

Utsagnslogisk formell

Utsagnsvariabler og konnektiver som tilsammen gir en sannhetsverdi.

Presedensregler

Regler som avgjør hvordan formler skal tolkes hvis parantes ikke er tilstedet. NKDI, noen kan det ikke.

Negasjon

Snur sannhetsverdien til P. ¬P

Konjunksjon

Er sann dersom både P og Q er sann. P ∧ Q

Disjunksjon

Er sann dersom enten P eller Q er sann. P ∨ Q

Implikasjon

Er sann dersom Q er sann, og uansett sannhetsverdien til P (om Q er sann). Konnektivet er også sann dersom både P og Q er usann. P → Q

Sannhetsverdi

Sann eller usann. 1 eller 0. (T uttales topp og ⊥ uttales bunn.)

Valuasjon

En tilordning av sannhetsverdier til en utsagnslogisk formell.

Logisk ekvivalens

Når F har samme valuasjon som G. F ⇔ G

De Morgans lover

Hvis ikke både A og B er sanne, er A usann eller B usann. ¬(A ∨ B) ⇔ (¬A ∧ ¬B)

Hvis hverken A eller B er sanne, er både A usann og B usann. ¬(A ∧ B) ⇔ (¬A ∨ ¬B)

Assosiative lover

Dersom det er kun konjunksjoner eller kun disjunksjoner i en formell, så kan parentesene plasseres fritt.

A ∧ (B ∧ C) ⇔ (A ∧ B) ∧ C

A ∧ (B ∨ C) ⇔ (A ∨ B) ∧ C

Kommutative lover

Rekkefølgen til en formell spiller ingen rolle.

A ∧ B ⇔ B ∧ A

A ∨ B ⇔ B ∨ A

Ekvivalenser for →

A → B ⇔ ¬A ∨ B

¬(A → B) ⇔ A ∨ ¬B

Logisk konsekvens

En utsagnslogisk formell F som er sann for alle valuasjoner for en mengde av utsagnslogiske formler M sanne. M |= F

Gyldig argument

Et premiss som er en konklusjon av en mengde av en mengde gyldige argument.

Oppfyllbarhet

En utsagnslogisk formell som er sann for minst en valuasjon

Falsifiserbarhet

En utsagnslogisk formell som er usann minst en valuasjon

Tautologi

En utsagnslogisk formell som er sann for alle valuasjoner

Kontradiksjon

En utsagnslogisk formell som er usann for alle valuasjoner

Uavhengig formell

En formell F hvor hverken F eller ¬F er en logisk konsekvens for en mengde M.

Direkte bevis

Et logisk gyldig resonnement. Det antas at F er sann og konkluderes med at G er sann.

Eksistens bevis

Å peke til et objekt som gjør en påstand sann.

Bevis ved tilfeller

Å dele et bevis inn i alle mulige tilfeller, og deretter bevise hvert enkelt tilfelle

Bevis for universelle påstander

Å bevise en påstand for et vilkårlig objekt, som representerer alle objekter med en ønsket egenskap.

Moteksempler

Et bevis som viser at en påstand er usann

Kontrapositiv bevis

Et bevis som antar at dersom en konklusjon G er usann, så må påstanden F være usann.

Motsigelses bevis

Et bevis som antar en negativ påstand (F er usann) for å vise at denne antakelsen fører til en motsigelse, altså en positiv påstand (som da betyr at F må være sann).

Konstruktive bevis

Et bevis som viser frem eller gir en metode for å finne et ønsket objekt som gjør en påstand sann.

Ikke-konstruktive bevis (motsigelsesbevis)

Et bevis som ikke viser frem eller gir en metode for å finne et ønsket objekt som gjør en påstand sann.

n-ær relasjon

En delmengde av A^n, hvor A er en mengde

Bin. relasjon fra/til

En delmengde av A x B (fra en mengde A til en mengde B)

Bin. relajson På

En delmengde av A x A (fra en mengde A til seg selv)

Transitiv

Alle relasjoner som kan gjøres i 2. steg, må også gjøres i 1. steg.

Refleksiv

Alle elementer er relatert til seg selv.

Irrefleksiv

Ingen elementer er relatert til seg selv.

Symmetrisk

En relasjon fra x til y, går fra y til x også

Anti-symmetrisk

En relasjon fra x til y, kan ikke også gå fra y til x (bortsett fra y = x)

Identitets relasjonen

Alle elementer på en mengde S er relatert til seg selv. Er refleksiv

Tomme relasjonen

Ingen elementer fra en mengde S til en mengde T er relatert

Universelle relasjonen

Alle elementer i en mengde S er relatert til alle elementer i en mengde T.

Ekvivalens relasjonen

Refleksiv, transitiv og symmetrisk

Partiell ordning

Binær relasjon som er refleksiv, transitiv og anti-symmetrisk

Total ordning

En binær relasjon R på en mengde S som er slik at alle elementer i S er relatert til hverandre.

Å telle relasjoner

På en mengde S, så er det 2^|S|² relasjoner

Argument

Input til en funksjon, x

Verdi

Output til en funksjon, y

Definisjonsområdet

En mengde som inneholder argumenter. A

Verdiområdet

En mengde som inneholder verdier. B

Funksjon

f: A → B. En binær relasjon f fra mengden A til mengden B, slik at for ethvert element x ∈ A er det nøyaktig ett element y ∈ B, slik at <x, y> ∈ f.

Bildemengde

En mengde som inneholder alle elementer i verdiområdet som er relatert til et element i definisjonsområdet. f[x] = {...}

Identitetsfunksjonen

En funksjon id_A på A, slik at id_A(x) = x for alle x ∈ A

Injektiv

Ethvert argument har en unik verdi. For alle x, y ∈ A hvis X ikke er lik y, så f(x) ikke er lik f(y). En-til-en

Surjektiv

Enhver verdi har et unikt argument. For alle y ∈ B, finnes det en x ∈ A slik at f(x) = y. På

Bijektiv

En funksjon som er både injektiv og surjektiv. En-til-en korrespondanse

Unær operasjon

Må være fra A til A. f(x) = x + 1

Binær operasjon

Må være fra AxA til A.

f(x) = x+x,

f(x) =x-x

N-ær operasjon

Må være fra A^N til A.

f(x) = x + x + x … + x.

f(x) = x - x - x … - x

Å telle funksjoner

Fra en mengde A til en mengde B har B^A funksjoner

Den universelle mengden

En underliggende mengde vi alltids antar eksisterer

Komplementet til M

En mengde som inneholder alt i den universelle mengden utenom M.

Potensmengden til M

En mengde som inneholder alle delmengder av M. P(M)

Kardinalitet

Størrelsen til en mengde, som er tilsvarende antall elementer i en mengde M. |M|

Lik kardinalitet

Dersom |M| = |N| og f: M → N så er f bijektiv

Tellbar

Dersom det finnes en en-til-en korrespondanse mellom elementene i en mengde M og De naturlige tallene.

Overtellbar

En mengde som ikke har en-til-en korrespondanse med de naturlige tallene

Lukket

En mengde M hvor en gitt operasjon på ett eller flere elementer i M resulterer i at du kun får elementer fra M

Tillukning

Den minste mengden som er lukket under gitt operasjon(er).

Basismengde

Den minste mengden som inneholder en gitt mengde

Induktivt definert mengde

Basissteget: Å spesifisere basismengden

Induksjonssteget: Å spesifisere en eller flere operasjoner

Tillukningen: Å ta tillukningen av basismengden

Liste

En endelig sekvens av elementer, som (fra et matematisk ståsted) ikke skiller seg mye fra tupler, men som må aksesseres i henhold til hvordan de ble lagt i listen. x :: ()

Binært tre

En samling av elementer hvor hvert element x er relatert til opptil 2 “barne”-elementer V og H. (V, x, H)

Node

Et element i et binært tre, x.

Bladnode

En node x som har tomme binære trær som barne-noder. ((), x, ())

Alfabetet

En mengde A som består av tegn

Streng

En samling av tegn hvor rekkefølgen endrer betydning. En tom streng uttrykkes som Λ. Λs = sΛ = s

Språk

En mengde av strenger hvor dersom s ∈ A*, og x ∈ A, så er sx ∈ A*

Rekursjon

Fra latin: å “løpe tilbake” eller “returnere”

Rekursiv funksjon

En måte å definere en funksjon med en induktiv definert mengde M som definisjonsområde. Funksjonen består av 2 steg:

1. Basissteget: Å spesifisere basismengden og gi en verdi til hvert element.

   1. Rekusjonssteget: Å spesifisere verdien til f(n+1) med f(n)

Matematisk induksjon

En bevismetode for en påstand som består av 3 deler:

1. Basissteget; Å sjekke at påstanden holder for 0

2. Induksjonshypotesen: Antakelsen at påstanden holder for n

3. Induksjonssteget: Å sjekke at påstanden holder for n+1

Strukturell induksjon

En bevismetode for en mengde av påstander som består av 3 deler:

1. Basissteget: Å sjekke at påstanden holder for alle elementer i mengden

2. Induksjonshypotesen: Antakelsen at påstanden holder for x1, x2, x3, …, xn

3. Induksjonssteget: Å sjekke at påstanden holder for n+1

Utsagnslogikk

Språket som består av utsagnsvariabler og konnektivene.

Førsteordens logikk

Utvider utsagnslogikk med kvantorer. Kan deles inn i logiske og ikke-logiske symboler

Logiske symbol

Symboler som alltids blir tolket på samme måte, eks. konnektiver og kvantorer

Ikke-logiske symbol

Symboler som kan tolkes fritt (variabler, konstant-, funksjons-, og relasjonssymboler). Disse er disjunkte

Kvantor

Et symbol for å representere kvantifiserte utsagn. Disse har høyest presedens (samme som ¬).

Eksistenskvantoren

En kvantor som beskriver at det finnes et element x som har en gitt egenskap, ∃x

Allkvantoren

En kvantor som beskriver at for alle elementer x har x en gitt egenskap, ∀x

Førsteordens språk

En samling av logiske symboler (¬, ∧, ∨, →, ∀ og ∃) og ikke-logiske symboler (variabler, konstantsymboler, funksjonssymboler og relasjonssymboler).

Signatur

En skrivemåte som beskriver hvilke konstant-, funksjons- og relasjonssymboler som er definert for et førsteordens språk. (a, b; f, g; P, R)

Aritet

Antall argumenter som skal tas inn i en funksjon eller relasjon.