Studied by 1 person
Utsagn
Noe som kan være sant eller usant
Atomære
Kan ikke deles mer
Sammensatte utsagn
atomære utsagn satt sammen ved hjelp av bindeord
Utsagnsvariabel
en variabel som representerer en atomær formel
Logiske konnektiver
∧,∨,→,¬
Negasjon
¬ F, “ikke F”
Konjunksjon
F∧G, “F og G”
Disjunksjon
F∨G, “F eller G”
Implikasjon
F → G, “Hvis F, så G”
Hovedkonnektiv
Det ytterste konnektivet, det konnektivet som blir regnet sist i et sammensatt utrykk
Tilstrekkelig
P er tilstrekkelig for Q betyr at hvis P er sant, så må Q være sant. Tilsvarer P → Q. Q trenger ikke være usant når P er isant, men den må være sant når P er sant.
Nødvendig
P er nødvendig for Q betyr at P må være sant for at Q skal være sant. Hvis P er usant er det garantert at Q er usant. Tilsvarer ¬P → ¬Q eller Q→P
A↔B
A hvis og bare hvis B
Presedensen
Hvem binder sterkest, typ regnerekkefølge; nkdi, noen kan det ikke, ¬∧∨→. ∀ og ∃ binder like sterkt som ¬
Valuasjon
Tilordning av sannhetsverdier, skrives med v
Sannhetsverditabell
En tabell som viser sannhetsverdien til en sammensatt utsagnslogisk formel på bakgrunn av hvilke sannhetsverdier som er tilordnet utsagnsvariablene
Logisk ekvivalens
To formler F og G er ekvivalente dersom de har samme sannhetsverdi for enhver tilordning av sannhetsverdier. Dvs. at F er alltid sann når G er sant og vice versa. F ⇔ G
Distributive lover
De Morgans lover
Assosiative lover
Kommutative lover
Dobbel negasjon
¬¬A ⇔ A
Implikasjon
A → B ⇔ ¬A ∨ B
Logisk ekvivalens
M er en mengde av utsagnslogiske formler. F er en utsagnslogisk formel. Hvis F er sann for alle valuasjoner som gjør alle formlene i M sanne samtidig, er F en logisk konsekvens av formlene i M, og vi skriver dett som M ⊨ F
Gyldig/holdbart argument
Hvis konklusjonen er en logisk konsekvens av premisser
Oppfyllbarhet
v gjør F sant, i dette tilfelle skriver vi v ⊨ F. Vi sier at F er oppfyllbar dersom det finnes det finnes en valuasjon som oppfyller F
Falsifiserbarhet
v gjør F usant. Vi sier at F er falsifiserbar dersom det finnes en valuasjon som falsifiserer den.
Tautologi/gyldighet
Hvis F er sant for alle valuasjoner, ⊨F
Motsigelse/kontradiksjon
Hvis F er usant for alle valuasjoner
⊤
Utsagnslogiskformel som heter “topp” eller “sann”
⊥
Utsagnslogiskformel som heter “bunn” eller “usann”
Uavhengig formel
En formel F er uavhengig av en mengde formler M hvis hverken F eller ¬F er en logisk konsekvens av M
Uavhengig mengde
En mengde formler er uavhengig hvis enhver formel er uavhengig av mengden av de andre formlene
Bevis
En rekke logiske slutninger som viser hvordan vi kommer fra antakelse til påstanden
For hvert steg må konklusjonen være en logisk konsekvens av antakelsene
Formodning
En påstand som vi tror, eller har god grunn til å tro er sann, men som vi ikke har bevist eller motbevist
Direkte bevis
Vi har en påstand på formen “hvis F, så G”. Et direkte bevis bevis begynner med antakelsen om F er sann og ender med konklusjonen om at G er sann
Eksistansbevis
Vi har en påstand som sier at noe eksisterer. Finn et objekt som gjør påstanden sann. Gi en metode for å finne et slikt objekt.
Bevis ved tilfeller
En bevismetode hvor hvert enkelt tilfelle blir bevist hver for seg
Bevis for universelle påstander
En påstand som sier noe om alle objekter av en bestemt type. For å bevise påstanden, begynn med å velge et vilkårlig objekt fra den gitte mengden og vis at dette objektet har den ønskede egenskapen.
Moteksempler
Den letteste måten å motbevise en unviersell påstand er å komme med et moteksempel
Kontrapositive bevis
Påstanden er “hvis F, så G”, men den er logisk ekvivalent med ¬G → ¬F. Kontrapositiv bevis bruker denne ekvivalensen for å bevise en påstand
Motsigelsesbevis
Begynner med å anta at påstanden er usann og viser hvordan denne antagelsen fører til en motsigelse
Konstruktiv bevis
Viser fram eller gir en metode for å finne et objekt
Ikke-konstruktiv bevis
Viser ikke objektet eller gir en metode
Binære relasjon fra S til T
En delmengde av S X T (kartesisk produkt)
Binære relasjon på mengden S
En delmengde av S X S
n-ær relasjon
En delmengde av A1 x … x An
n-ær relasjon på mengden A
En delmengde av A x … x A
Identitetsrelasjonen
{<x,x>| x ∈ S}
Den tomme relasjonen
Ø
Den unvierselle relasjonen
mengden S x T
Infiksnotasjon
anta at <a,b> ∈ R, da kan vi skrive dette sånn aRb
refleksiv
Relasjonen R er refleksiv dersom det for alle x i S er slik at <x,x> ∈ R
symmetrisk
Relasjonen R er symmetrisk hvis det for alle x, y er slik av hvis <x,y> ∈ R så er <y,x> ∈ R
transitiv
Relasjonen R er transitiv hvis det for alle x, y, z er slik at hvis <x, y> ∈ R og <y, z> ∈ R så er <x, z> ∈ R
Ekvivalensrelasjon
Er en relasjon som er refleksiv, symmetrisk og transitiv
anti-symmetrisk
En relasjon R er anti-symmetrisk hvis det for alle x, y er slik at hvis <x, y> ∈ R og <y, x> ∈ R så er x = y
irrefleksiv
Relasjon R er irrefleksiv hvis det ikke er noen x ∈ S slik at <x, x> ∈ R
Partiell ordning
En relasjon som er refleksiv, transitiv og anti-symmetrisk
Total ordning
En partiell ordning kalles en total ordning hvis det hvis det for alle x og y i S er slik at xRy eller yRx
asymmetrisk
Relasjonen R er asymmetrisk dersom det er slik at hvis xRy så er ikke yRx
f: A → B
f er funksjonen fra A til B. A: definisjonsområdet og B: verdiområdet
Identitetsfunksjonen
idA(x) = x, funksjonen der verdien er lik argumentet
injektiv/en-til-en
Funksjonen f er injektiv/en-til-en dersom det for alle x,y ∈ A slik at x ≠ y så er f(x) ≠ f(y)
surjektiv/på
Funksjonen f er surjektiv/på dersom det for alle y ∈ B, finnes en x ∈ A slik at f(x) = y
bijektiv/en-til-en korrespondanse
Funksjonen f er bijektiv/en-til-en korrespondanse, dersom den er både inektiv og surjektiv
Bildet av
La X være en delmengde av A. Da kalles {f(x)|x∈X} bildet av x under f, og skrives f[X]
Bildemengden
Bildet av hele A under f, altså f[A]
Unær operasjon
En unær operasjon på en mengde A er en funksjon fra A til Å
Binær operasjon
En binær operasjon på en mengde A er en funksjon fra A til A x A
Den universelle mengden
Alle kontekster har en undeliggende mengde som inneholder alle elementer
Komplementet
Komplementet til mengden M er mengden av alle elementer som er i den universelle mengden, men ikke i M. Komplementet til M skrives 𝑀‾.
Potensmengden
Potensmengden til en mengde M er mengden av alle delmengder av M.
Kardinalitet
Kardinalitet betyr intuitivt «størrelse». To mengder har lik kardinalitet hvis det finnes en bijeksjon mellom dem. Mindre kardinalitet betyr at det finnes en bijeksjon mellom en mengde og en delmengde av den andre. Hvis M er endelig, er kardinaliteten til M lik antall elementer i M
Tellbar
En uendelig mengde M er tellbar hvis det er en en-til-en korrespondanse mellom elementene i M og de naturlige tallene. Alle endelige mengder er tellbare.
Overtellbar
Hvis det ikke er en en-til-en korrespondanse mellom elementene i M og de naturlige tallene.
Mengde lukket
At M er lukket under en gitt operasjon på A betyr at når vi utfører denne operasjonen på ett eller flere elementer i M, så er vi garantert å få et element i M.
Tilukningen
Den minste mengden som inneholder M og er lukker under en eller flere operasjoner kalles tilukningen av M.
Tilukningen av R
Den minste mengden som inneholder R og har en gitt egenskap(eks. refleksiv, symmetrisk, transitiv) kalles tilukningen av R
Induktivt definert mengde
En induktiv definert mengde er den minste mengde som inneholder en gitt mengde (basismengde) og som er lukker under gitte operasjoner.
Å definere en mengde induktivt har tre steg:
Basissteget: å spesifisere basismengde
Induksjonsteget: Å spesifisere operasjonene
Tilukningen: å ta den minste mengden som inneholder basis mengde og er lukket under operasjonene
Konkatenering
Operasjonen som består av å slå sammen lister, strenger eller språk: To strenger s og t slås sammen til én, st. To lister, L og M, slås sammen med funksjonen + til L+M, for eksempel (1,2,3)+(4,5,6)=(1,2,3,4,5,6)(1,2,3)+(4,5,6)=(1,2,3,4,5,6). Hvis L og M er språk, er konkateneringen av L og M, språket LM={st∣s∈L og t∈M}.
Rekursivt definerte funksjoner
En rekursivt funksjon f med definisjonsområdet M defineres slik:
Basissteget: for hvert element x i basismengden, spesifiserer vi en verdi f(x)
Rekursjonssteget: for hvert element x i M som forekommer i induksjonsteget, definerer vi verdien f(x) ved å bruke de tidligere definerte verdiene for f
Matematisk induksjon
Bevismetode for å vise at en påstand er sant for alle natulige tall.
Basissteget: Vis at påstanden holder for tallet 0
Induksjonssteget: Hvis påstanden holder for et vilkårlig tall n (induksjonshypotesen), så holder den for n + 1
Strukturell induksjon
Bevismetode for å vise at noe er sant for alle elementer i en induktiv definert mengde.
Basissteget: Bevis at påstanden holder for alle elementer som kommer i basismengde
Induksjonssteget: Hvis mengden er lukker under en operasjon som gjør at x fremkommer fra x1, x2, …, xn og påstanden holder for alle disse (induksjonshypotesen), holder påstanden også for x
Førsteordens logikk
Utvider utsagnslogikk med blant annet kvantorer
Kvantorer
∀, leses som «for alle», ∃, leses som «det finnes»
Førsteordens språk
Består av følgende:
Logiske symboler:
De logiske konnektivene ∧,∨,→ og ¬
Kvantorene ∀ og ∃
En uendelig tellbar mengde av variabler
Parenteser og kommaer
Ikke-logiske symboler:
Mengden av konstantssymboler
Mengde av funksjonssymboler
Mengde av relasjonssymboler
Aritet
Egenskap ved funksjons- og relasjonssymbol som forteller hvor mange termer som trengs for å lage henholdsvis termer og atomære formler.
Signatur
Angir mengden av konstant-, funksjons- og relasjonssymboler for et førsteordens språk.
⟨konstantsymboler; funksjonssymboler; relasjonssymboler⟩
Mengden av førsteordens termer
Basismengden består av alle konstant og variabel symbolene.
Induksjonssteget er hvis t1, …, tn er termer og f er en funksjon med aritet n, så er f(t1, …, tn) en term
Mengden av førsteordens formler
Basismengde består av alle atomære formler
Hvis F og G er formler, så er ¬𝐹, 𝐹 ∧ 𝐺 , (𝐹 ∨ 𝐺) og (𝐹 → 𝐺) formler
Hvis F er en formel og x er en variabel, så er r ∀𝑥𝐹 og ∃𝑥F en formel
Bundet
I formlene ∀𝑥F og ∃𝑥F er alle forekomster av x i F bundet og innenfor skopet til kvantoren. En variabel er fri hvis den ikke er bundet. En formel er lukket hvis den ikke inneholder noen frie variabler.
Predikat
Et uttrykk som inneholder en eller flere plassholdere og blir til sant/usant når vi erstatter plassholdere med verdier
Modell
En modell består av en ikke-tom mengde kalt domenet |M| og en funksjon som tolker ikke-logiske symbolene
Lukket term
En term er lukket hvis den ikke inneholder noen variabler
Oppfyllbar lukket formel
Hvis det finnes en modell som gjør den sant
Kontradiktorisk lukket formel
Hvis det ikke finnes en modell som gjør den sant
Gyldig lukket formel
Dersom alle modeller gjør den sann
Falsifiserbar lukket formel
Dersom ikke alle modeller gjør den sann
Teori
En mengde med formler
Note
Flashcard