Utsagnslogikk og Bevis
Logiske konnektiver, Logisk konsekvens, Gyldige argument, Oppfyllbarhet, Falsifiserbarhet, Tautologi, Sannhetsverditabeller
🇳🇴
In Norwegian
In Norwegian
Practice Known Questions
Stay up to date with your due questions
Complete 5 questions to enable practice
Exams
Exam: Test your skills
Test your skills in exam mode
Learn New Questions
Manual Mode [BETA]
Select your own question and answer types
Specific modes
Learn with flashcards
Listening & SpellingSpelling: Type what you hear
multiple choiceMultiple choice mode
SpeakingAnswer with voice
Speaking & ListeningPractice pronunciation
TypingTyping only mode
Utsagnslogikk og Bevis - Leaderboard
Utsagnslogikk og Bevis - Details
Levels:
Questions:
113 questions
| 🇳🇴 | 🇳🇴 |
| ℕ | N = naturlige tall {0, 1, 2, 3, 4, 5, ...} |
| ℤ | Z = heiltall {..., -3, -2, -1, 0, 1, 2, 3, ... } |
| ℚ | Q = rasjonelle tall/brøktall |
| ℝ | R = reelle tall Finst på ei kontinuerleg talllinje eks: e, π, √ (nesten alt) {4.25, √25, e, -33, π, √2} |
| Snitt | A ∩ B |
| Union | A ∪ B |
| A \ B | Alt som er i A, som ikkje er i B |
| ∅ | Den tomme mengda |
| A ∩ B | Snitt |
| A ∪ B | Union |
| A \ B | Alt som er i A, som ikkje er i B |
| A ⊆ B | Delmengde Kvart element i A er i B |
| A ∈ B | A er et element i B |
| A ∉ B | A er ikke et element i B |
| ∅ | Den tomme mengda |
| Det kartesiske produkt | Krysspunktet av n mengde |
| A x B | Det kartesiske produkt/Kryssproduktet av n mengde {b} og {1,2,3} er: {(b,1), (b, 2), (b, 3)} Mengde A x B: mengden av alle par <x, y> slik at x ∈ A og y ∈ B Dersom ein tar X x Ø, vill ein alltid få den tomme mengda uansett kva X er |
| {x ∈ A | x har egenskapen P} | Mengdebyggar {n|n ∈ N og n < 207} = en mengde av alle naturlige tall mindre enn 207 |
| ꓥ (A) | Og |
| ꓦ | Eller |
| → (->) | Impliserer/hvis så |
| ¬ | Ikkje |
| NA | NA |
| Negasjon | Det motsatte (avhenger av kva samnheitsverdien til P er) |
| Konjunksjon | Begge må være sanne |
| NA | NA |
| Disjunksjon | Begge eller ein må være sann |
| NA | NA |
| Implikasjon | Berre usann dersom første sann og andre usann |
| ⇔ (<->) | Logisk ekvivalens To formlar har same sannheitsverdi |
| Logisk konsekvens | Når andre formlar enn dei gitte er nødt til å være sanne basert på tilgjengelege sannhetsverdiar. Eks: Vi veit P ⋀ Q er sanne. ¬Q ⋁ R og R ⋁ S, må dermed også være sanne. Men ein kan ikke vete om det S er sann eller ikke i den siste ettersom det er eller |
| Gyldige argument | Eit argument er gyldig eller holdbart hvis konklusjonen er en logisk konsekvens av mengden av premisser: Hvis solen skinner, så er jeg glad: (S->G) Hvis S sann så G sann, dermed er G ein logisk konsekvens av mengda som består av (S->G) og S |
| Oppfyllbarheit | Hvis en valusjon gjør en utsagnslogisk formel sann, sier vi at valusjonen oppfyller formelen og skriver v|=F |
| Falsifiserbarheit | Hvis en valusjon gjør en utsagnslogisk formel usann, sier vi at valusjonen falsifiserer. |
| Tautologi | En utsagnslogisk formel som er sann for alle valuasjoner |
| Motsigelse/kontradiksjon | Dersom ein utsagnslogisk formel er usann for alle valuasjonar |
| Bevis | Et Bevis for en påstand fra en mengde gitte antakelser er en rekke logiske slutninger som viser hvordan vi kommer fra antakelsene til påstanden. For hvert steg må konklusjonen være en logisk konsekvens av antakelsene. |
| Formodning | En formodning er en påstand som vi tror, eller har god grunn til å tro, er sann, men som vi ikke har bevist eller motbevist. |
| Direkte Bevis | Et direkte bevis for en påstand på formen "hvis F, så G" er et logisk gyldig resonnement som begynner med antakelsen om at F er sann og som ender med konklusjonen om at G er sann. Eks: Anta at en valuasjon er gitt. Bevis påstanden "hvis valuasjonen gjør (P A Q) sann, så gjør valuasjonen P sann". Svar: Anta at valuasjonen gjør (P A Q) sann. Da må valuasjonen gjøre både P og Q sanne, fordi det er slik A-formler tolkes, og spesielt må valuasjonen gjøre P sann. Det følger derfor at hvis (P A Q) er sann, så er P sann. |
| Eksistensbevis | En eksistenspåstand er en påstand som sier at noe eksisterer. Vi beviser eksistenspåstander ved å enkelt finne objektet som gjør påstanden sann. Eks: Bevis påstanden "det finnes et naturlig tall x slik at x + x = 8" La x være tallet 4. Da må x + x være lik 4 + 4 som er lik 8. |
| Kontrapositivt bevis | Et kontrapositivt bevis for en påstand på formen "hvis F, så G", er et logisk gyldig resonnement som begynner med antakelsen om at G er usann, og som konkluderer med at F er usann. Den kontrapositive av formelen (F -> G) er formelen (-G -> -F). |
| Direkte Bevis | Et direkte bevis for en påstand på formen "hvis F, så G" er et logisk gyldig resonnement som begynner med antakelsen om at F er sann og som ender med konklusjonen om at G er sann. Eks: Anta at en valuasjon er gitt. Bevis påstanden "hvis valuasjonen gjør (P A Q) sann, så gjør valuasjonen P sann". Svar: Anta at valuasjonen gjør (P A Q) sann. Da må valuasjonen gjøre både P og Q sanne, fordi det er slik A-formler tolkes, og spesielt må valuasjonen gjøre P sann. Det følger derfor at hvis (P A Q) er sann, så er P sann. |
| Motsigelsesbevis | Et motsigelsesbevis for en påstand er et bevis som begynner med antakelsen om at påstanden er usann og som viser hvordan denne antakelsen fører til en motsigelse. Beviset konkluderer med at påstanden må være sann. |
| Binær relasjon | Er ein delmengde av S x T (mengda S og T) |
| Identitelsrelasjon | Alle element relaterer til seg sjølv {⟨x,x⟩|x ∈ S} {⟨1,1⟩, ⟨2,2⟩, ⟨3,3⟩} |
| Tom relasjon | Den tomme relasjonen fra S til T, som ikke relaterer noen elementer til hverandre: Ø. Her er den tomme relasjonen på mengden {1,2,3}: |
| Universiell Relasjon | Den universelle relasjonen frå S til T, som relaterer alle elementer i S til alle elementer i T: S ⨉ T. Her er den universelle relasjonen på mengden {1,2,3}: {⟨1,1⟩, ⟨1,2⟩, ⟨1,3⟩, ⟨2,1⟩, ⟨2,2⟩, ⟨2,3⟩, ⟨3,1⟩, ⟨3,2⟩, ⟨3,3⟩} |
| Refleksiv relasjon | Hvis det for alle x i S er slik at ⟨x,x⟩ ∈ R. Alle relaterer til seg selv |
| Symmetrisk relasjon | Hvis det for alle x, y er slik at hvis ⟨x,y⟩ ∈ R, så ⟨y,x⟩ ∈ R. Dersom a relaterer til b, må b relatere til a |
| Transitiv relasjon | Hvis det for alle x, y, z er slik at hvis ⟨x,y⟩ ∈ R og ⟨y,z⟩ ∈ R, så ⟨x,z⟩ ∈ R. Alt du kan gjøre i to steg, kan du også gjøre i ett steg |
| Ekvivalensrelasjon | Hvis den er refleksiv, symmetrisk og transitiv |
| Anti-symmetrisk | Hvis det for alle x,y er slik at hvis ⟨x,y⟩ ∈ R og ⟨y,x⟩ ∈ R, så x = y. |
| Irrefleksivitet | Hvis det ikke er noen x ∈ S slik at ⟨x,x⟩ ∈ R. (S er mengda og R relasjonen til mengda) |
| Partiell ordning | Hvis den er refleksiv, transitiv og antisymmetrisk |
| Total ordning/Linær ordning | Hvis det for alle x og y i S er slik at xRy eller yRx |
| Funksjon | En funksjon fra A til B er en binær relsasjon f fra A til B slik at for enhver x ∈ A, er det nøyaktig ett element y ∈ B slik at ⟨x,y⟩ ∈ f. Vi skriver f(x)=y når ⟨x,y⟩ ∈ f. I dette tilfellet kaller vi x for argumentet og f(x) for verdien til funksjonen. Vi skriver f: A -> B for funksjonen f når den er en funksjon fra A til B. |
| Definisjons området | La f være en funksjon fra A til B. Mengden A kalles definisjonsområdet til f |
| Verdiområdet | La f være en funksjon fra A til B. Mengden B kalles verdiområdet til f |
| Injektiv | En funksjon f: A -> B er injektiv hvis det for alle elementer x og y i A slik at hvis x ≠ y, så f(x) ≠ f(y). Vi sier i så fall at f er en injeksjon og en-til-en. |
| Surjektiv | En funksjon f: A -> B er surjektiv hvis det for alle y ∈ B, finnes en x ∈ A slik at f(x) = y. |
| Bijektiv | En funksjon er bijektiv hvis den er injektiv og surjektiv. Vi sier også at funksjonen er en bijeksjon og en en-til-en korrespondanse. |
| Bildemengde | La f være en funksjon fra A til B, og la X være en delmengde av A. Mengden {f(x)|x ∈ X} kalles bildet av X under f, og skrives f[x]. Bildet av hele A under f, f[A], kalles bildemengden til f. Bildemengden til en funksjon er det som blir «truffet» av funksjonen. |
| Definere mengde induktivt | Bygger dei opp innan/nedanfrå Fordelar: - god kontroll på kva element som er i mengda - enklare å bevise |
| Lukka Mengde | Ei mengde er lukka under ein gikk operasjon innebære at når operasjonen utførast foreligger det garanti på at resultatet fins i same mengde |
| Induktivt definerte mengder | En induktivt definer mengde er den minste mengden som inneholder en gitt mengde – kalt en basismengde – og som er lukket under gitte operasjoner. En mengde definers induktivt I følgende tre steg: Basissteget: å spesifisere en basismengde Induksjonssteget: å spesifisere operasjonene Tillukningen: å ta den minste mengden som inneholder basismengden og som er lukket under operasjonene La oss induktivt definere partall: Basismengde {0} Operasjonene: en som tar x som argument og som gir x +2 som verdi, og en som tar x som argument og som gir x -2 som Verdi Element i basismengden: 0 Steg 1: 2, -2 Steg 2: 4, -4 Steg 3: 6, -6 |
| Rekursive funksjonar | Rekursjon tar utgangspunkt I induktivt definerte mengder, og bygger videre på disse Plassholder: kan være x, y [], input. Eksepel f(x) = 2x + 1 (x er plassholder). Husk: vi kan ikke bruke reserverte symboler som plassholdere ( feks + og - ) Rekursiv funksjon: “hvis en mengde M er induktivt definert, kan vi definer en reukrsiv funksjon f med definisjonsområdet M på følgende mate: For hvert element x I basismengden til M, spesifiser en Verdi for f(x). Dette kalles basissteget eller basistilfellet for en funksjon For hvert element x I M som fremkommer I et induksjonssteg, definer verdien til f(x) ved å bruke de tidligere definerte verdiene for f. Dette kalles rekursjonssteget. |
| Graf | Består av noder og kanter |
| NA | NA |
| Løkke | En kant som går fra en node til seg selv i en pseudograf |
| Hamiltonsykel | En hamiltonsykel er en sykel som inneholder hver node fra G nøyaktig én gang. En graf som har en hamiltonsykel kalles hamiltonsk. |
| Parallelle kanta | To eller flere kanter som forbinder de samme nodene i en multigraf |
| Hamiltonsykel | En hamiltonsykel er en sykel som inneholder hver node fra G nøyaktig én gang. En graf som har en hamiltonsykel kalles hamiltonsk. |
| Enkel | Multigraf eller pseudograf som hverken har løkker eller parallelle kanter. |
| Hamiltonsykel | En hamiltonsykel er en sykel som inneholder hver node fra G nøyaktig én gang. En graf som har en hamiltonsykel kalles hamiltonsk. |
| Rettet graf | Ein graf der kantene er ordnede par ⟨u, v⟩ i stedet for mengder {u, v} |
| NA | NA |
| Tom graf/nullgraf | En graf uten kanter |
| Komplett graf | En enkel graf er komplett hvis hver node er nabo med enhver annen node |
| Komplement | Hvis G er en graf, er komplementet til G grafen som har de samme nodene som G, men hvor to noder er naboer hvis og bare hvis nodene ikke er naboer i G. Vi skriver G for komplementet til G. |
| Graden til ein node | Antall kanter som ligger inntil noden Graden til en node v er antall kanter som ligger inntil v. En løkke teller som to kanter. Med deg (v) mener vi graden til v. En node med grad 0 kalles isolert. |
| Isomorfi | La G og H være to grafer. En isomorfi fra G til H er en bijektiv funksjon f fra nodene i G til nodene i H som er slik at nodene u og v er naboer i G hvis og bare hvis nodene f(u) og f(v) er naboer i H. En bijektiv funksjon f fra nodene I G og H som er slik at nodene u og v er naboer I G hvis og bare hvis nodene også er naboer i H. |
| Vandring/Tur | Vi kan skrive en vandring i en graf som en sekvens av noder og kanter ... (finn ut dette)/ En sekvens av noder |
| Sti | Dersom ingen noder forekommer meir enn ein gang under ei vandring En sekvens av noder (og kan- tene som forbinder dem) der in- gen node gjentas |
| Vei | En sekvens av noder (og kan- tene som forbinder dem) der in- gen kant gjentast |
| Lukket vandring | En vandring hvor den første og siste noden sammenfaller kalles lukket |
| Krets | Ei lukka vandring der ingen kant forekommer meir enn ein gang |
| Sykel/lukka sti | Ein kan sjekke dette ved at ingen kant eller node førekomme meir enn ein gang under vandringa. Den må innehalde minst 3 noder. En graf uten sykler kalles asyklisk |
| Sammanhengande | En graf er sammenhengende hvis det finnes en sti mellom alle par av noder i grafen, det vil si at det er mulig å komme fra enhver node til enhver annen node ved å følge kantene |
| Eulervei | La G være en sammenhengende graf. En eulervei er en vandring som inneholder hver kant fra G nøyaktig én gang |
| Eulerkrets | En eulerkrets er en eulervei hvor den første og den siste noden sammenfaller Ein kan sjekke dette ved å sjå om grafen er samanhengande og om kvar node har eit partal som grad |
| Eulersk | En sammenhengende graf som har en eulerkrets |
| Tre | Et tre er en sammenhengende, asyklisk graf (betyr utan sykkel). En node med grad én i et tre kalles en løvnode. En graf hvor alle komponentene er trær kalles en skog. |
| Hamiltonsti | La G være en sammenhengende graf. En hamiltonsti er en sti som inneholder hver node fra G nøyaktig én gang |
| Hamiltonsykel | En hamiltonsykel er en sykel som inneholder hver node fra G nøyaktig én gang. En graf som har en hamiltonsykel kalles hamiltonsk. |
| Hamiltonsykel | En hamiltonsykel er en sykel som inneholder hver node fra G nøyaktig én gang. En graf som har en hamiltonsykel kalles hamiltonsk. |