Studied by 0 people
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:
Basissteget: Å spesifisere basismengden og gi en verdi til hvert element.
Rekusjonssteget: Å spesifisere verdien til f(n+1) med f(n)
Matematisk induksjon
En bevismetode for en påstand som består av 3 deler:
Basissteget; Å sjekke at påstanden holder for 0
Induksjonshypotesen: Antakelsen at påstanden holder for n
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:
Basissteget: Å sjekke at påstanden holder for alle elementer i mengden
Induksjonshypotesen: Antakelsen at påstanden holder for x1, x2, x3, …, xn
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.
Note
Flashcard