Alle de begreber, lommeregneren, guiderne og øvelserne bruger, defineret ét sted.
Slå et begreb op, se dets notation, og åbn eksemplet i lommeregneren for at se det virke. Begreber herfra fremhæves, første gang de optræder i en guide.
Alle 62 begreber
Studiet af hvilke konklusioner der faktisk følger af hvilke antagelser.
Logik studerer ræsonnementets form frem for dets indhold. Formel logik erstatter sætninger med symboler, så spørgsmålet om, hvorvidt en konklusion følger, kan afgøres alene ud fra argumentets form og kontrolleres mekanisk.
En påstand, der er enten sand eller falsk, men ikke begge dele.
Et udsagn er en konstaterende sætning med præcis én sandhedsværdi. „Det regner“ er et udsagn; et spørgsmål eller en befaling er det ikke, for der er intet ved dem, der kan være sandt eller falsk.
En af de to værdier, et udsagn kan have: sand eller falsk.
Klassisk logik giver hvert udsagn præcis én af to sandhedsværdier, skrevet ⊤ og ⊥ (eller 1 og 0). Hver række i en sandhedstabel er én tildeling af værdier til variablerne og den værdi, formlen får dér.
Et udsagn uden noget konnektiv i sig.
Et atomart udsagn kan ikke deles i mindre udsagn: det indeholder hverken negation, konjunktion eller andre konnektiver. Alt andet er sammensat, bygget af atomer, og dets sandhedsværdi følger af deres.
Et bogstav som p eller A, der står for et vilkårligt udsagn.
En udsagnsvariabel er en pladsholder for et hvilket som helst udsagn. Lommeregneren tager enkeltbogstaver som variable og giver hver en kolonne i sandhedstabellen med en række for hver mulig kombination af værdier.
I lommeregnerenp → qEn streng af symboler, som sprogets grammatik faktisk tillader.
En velformet formel bygges efter reglerne: en variabel er en, og det samme er enhver formel dannet af mindre formler ved et konnektiv. „p ∧ ∨ q“ er det ikke, og derfor melder lommeregneren en fejl i stedet for at gætte.
Én tildeling af sandhedsværdier til alle variable i en formel.
En fortolkning siger, hvad hver variabel er værd, og fastlægger dermed hele formlens værdi. En formel med n variable har 2ⁿ fortolkninger – præcis rækkerne i dens sandhedstabel.
Præmisser fremført til støtte for en konklusion.
Et argument hævder, at dets konklusion følger af præmisserne. Skriv et i lommeregneren med et følgetegn – præmisser før, konklusion efter – og hver række tjekkes for et tilfælde, hvor præmisserne holder og konklusionen svigter.
I lommeregnerenp → q, p ⊨ qEn påstand, et argument antager for at nå sin konklusion.
Præmisser er argumentets udgangspunkt. Gyldighed spørger kun, om konklusionen holder overalt, hvor alle præmisser holder; om de faktisk er sande, er et andet spørgsmål – det, holdbarhed tilføjer.
I lommeregnerenp → q, p ⊨ qDen påstand, et argument forsøger at godtgøre.
Konklusionen er det, præmisserne skal støtte. I lommeregneren er den udtrykket efter følgetegnet, og et argument er gyldigt, når ingen fortolkning gør præmisserne sande og konklusionen falsk.
I lommeregnerenp → q, p ⊨ qEt symbol, der bygger et sammensat udsagn af enklere.
Et konnektiv som ¬, ∧, ∨, → eller ↔ forbinder udsagn til et større, hvis sandhedsværdi kun afhænger af deres. Netop den afhængighed registrerer en sandhedstabel, én række per kombination af input.
Vender en sandhedsværdi om: ¬p er sand netop når p er falsk.
Negation er udsagnslogikkens eneste et-pladsede konnektiv. Skrevet ¬p, ~p eller !p gør den sandt til falsk og falsk til sandt, så to negationer giver det oprindelige udsagn igen.
I lommeregneren¬pSand kun når begge dele er sande: p ∧ q.
En konjunktion hævder begge sine dele, konjunkterne. Den er sand i præcis én række af sin sandhedstabel – den, hvor begge konjunkter er sande – hvilket gør den til det strengeste af de to-pladsede konnektiver.
I lommeregnerenp ∧ qSand når mindst én del er sand: p ∨ q.
Disjunktion er i logikken inklusiv: p ∨ q er sand, når p er sand, når q er sand, og når begge er det. Den eksklusive læsning af „eller“, kun sand når delene er forskellige, er et selvstændigt konnektiv.
I lommeregnerenp ∨ qSand når præcis ét af to udsagn er sandt.
Eksklusiv disjunktion, skrevet ⊕ eller XOR, holder, når delene er forskellige, og svigter, når de stemmer overens. Den er negationen af bikonditionalen og kan skrives som (p ∨ q) ∧ ¬(p ∧ q).
I lommeregneren(p ∨ q) ∧ ¬(p ∧ q)p → q, falsk kun når p er sand og q er falsk.
Den materielle konditional siger ikke andet end „ikke: forled sandt og efterled falsk“, så den holder automatisk, når forleddet svigter. Derfor er p → q ækvivalent med ¬p ∨ q.
I lommeregnerenp → qp ↔ q, sand når begge dele har samme sandhedsværdi.
Bikonditionalen hævder hver side på betingelse af den anden: den er sand, når begge dele er sande, og når begge er falske. En bikonditional, der er en tautologi, udtrykker præcis en logisk ækvivalens.
I lommeregnerenp ↔ q„Hvis“-delen af en konditional – p'et i p → q.
Forleddet er den betingelse, en konditional afhænger af. Når det er falsk, er hele konditionalen sand uanset efterleddet, og derfra kommer de fleste overraskelser i tabellen for →.
I lommeregnerenp → q„Så“-delen af en konditional – q'et i p → q.
Efterleddet er det, en konditional hævder følger, hvis forleddet holder. Et sandt efterled gør konditionalen sand, men gør ikke forleddet sandt: at slutte det er en formel fejlslutning.
I lommeregnerenp → qKonditionalen med de to dele byttet om: q → p.
Den omvendte af p → q er q → p, og de to er ikke ækvivalente: lommeregneren finder en række, hvor den ene holder og den anden svigter. At behandle dem som udskiftelige er at bekræfte efterleddet.
I lommeregnerenq → p¬q → ¬p, som altid har samme sandhedsværdi som p → q.
Kontrapositionen negerer begge dele af en konditional og bytter om på dem. I modsætning til den omvendte er den virkelig ækvivalent med originalen, og det er derfor bevis ved kontraposition er legitimt i matematik.
I lommeregneren(p → q) ≡ (¬q → ¬p)Negationen af en konjunktion: sand medmindre begge input er sande.
NAND, skrevet ↑, er ¬(p ∧ q). Den er funktionelt komplet: ethvert andet konnektiv kan bygges af NAND alene, og derfor er den en arbejdshest i digitalt kredsløbsdesign.
I lommeregneren¬(p ∧ q)Negationen af en disjunktion: sand kun når begge input er falske.
NOR, skrevet ↓, er ¬(p ∨ q). Ligesom NAND er den funktionelt komplet i sig selv, så et kredsløb kan bygges udelukkende af NOR-porte.
I lommeregneren¬(p ∨ q)Hvilket konnektiv der binder først, når parenteser mangler.
Negation binder stærkest, derefter konjunktion, disjunktion, konditional og til sidst bikonditional. Så ¬p ∧ q ∨ r læses som ((¬p) ∧ q) ∨ r; parenteser sætter rækkefølgen ud af kraft, når den ønskede læsning er en anden.
I lommeregneren¬p ∧ q ∨ rEn række per værditildeling med formlens værdi i hver.
En sandhedstabel opregner alle 2ⁿ fortolkninger af en formels n variable og beregner dens værdi i hver. Fordi den er udtømmende, afgør den ethvert semantisk spørgsmål i udsagnslogikken: ækvivalens, gyldighed, opfyldelighed og resten.
I lommeregnerenp → qEn formel, der er sand under enhver fortolkning.
En tautologi er sand i hver række af sin sandhedstabel og siger derfor intet om verden: p ∨ ¬p er sand, uanset hvad p er. To formler er ækvivalente netop når bikonditionalen mellem dem er en tautologi.
I lommeregnerenp ∨ ¬pEn formel, der er falsk under enhver fortolkning.
En modsigelse som p ∧ ¬p er falsk i hver række af sin sandhedstabel. At udlede en af et sæt antagelser viser, at antagelserne ikke alle kan holde – det er motoren i modstridsbeviset.
I lommeregnerenp ∧ ¬pEn formel, der er sand under nogle fortolkninger og falsk under andre.
En kontingent formel er hverken tautologi eller modsigelse: dens sandhedstabel har mindst én sand og mindst én falsk række. De fleste formler, nogen skriver, er kontingente, og det er dét, der gør dem informative.
I lommeregnerenp ∧ qOm nogen fortolkning gør formlen sand.
En formel er opfyldelig, når mindst én række i dens sandhedstabel er sand, og den række er en model af den. At afgøre opfyldelighed er SAT-løseres centrale problem og dermed en stor del af automatisk ræsonnement.
I lommeregnerenp ∧ (p → q)To formler med identiske sandhedstabeller.
Ækvivalente formler stemmer overens under enhver fortolkning, så den ene kan erstatte den anden overalt uden at ændre indholdet. Sæt et lighedstegn mellem to udtryk, og lommeregneren sammenligner deres kolonner række for række.
I lommeregneren(p → q) ≡ (¬p ∨ q)Konklusionen holder i enhver fortolkning, hvor præmisserne holder.
Skrevet Γ ⊨ φ er logisk følge det, et gyldigt argument hævder. Den kontrolleres ved at lede efter et modeksempel: en fortolkning, der gør alle præmisser sande og konklusionen falsk. Findes der ingen, holder følgen.
I lommeregnerenp → q, p ⊨ qIngen fortolkning gør præmisserne sande og konklusionen falsk.
Gyldighed er en egenskab ved argumentets form, ikke ved kendsgerningerne: et gyldigt argument må gerne have falske præmisser og en falsk konklusion. Det, det ikke kan have, er sande præmisser sammen med en falsk konklusion.
I lommeregnerenp → q, p ⊨ qEt gyldigt argument, hvis præmisser desuden er sande.
Holdbarhed føjer en faktisk påstand til en formel: argumentet er gyldigt, og dets præmisser holder. Logikken alene afgør den første halvdel; den anden hører til det, argumentet handler om.
En fortolkning, der gør præmisserne sande og konklusionen falsk.
En modmodel beviser, at et argument er ugyldigt – én række er nok. Lommeregneren viser den række, den finder, og gør dermed „dette følger ikke“ til en konkret tildeling, du kan efterprøve i hånden.
I lommeregnerenp → q ⊨ q → pNogen fortolkning gør alle udsagn i mængden sande på én gang.
En mængde præmisser er konsistent, når de alle kan holde sammen. Inkonsistente præmisser medfører hvad som helst, så et argument bygget på dem er teknisk gyldigt og intet værd.
I lommeregnerenp → q, ¬q ⊨ ¬pEn variabel eller dens negation, såsom p eller ¬p.
Literaler er normalformernes atomer: en klausul er en disjunktion af literaler, og en minterm er en konjunktion af dem. En literal er positiv, når variablen står bar, og negativ, når den er negeret.
I lommeregneren¬pEn disjunktion af literaler, såsom p ∨ ¬q ∨ r.
En klausul er en af de parentesgrupper, en konjunktiv normalform består af. Da en konjunktion kun er sand, når hver del er det, holder en KNF-formel netop når alle dens klausuler holder.
I lommeregnerenp ∨ ¬q ∨ rEt ELLER af OG'er: en disjunktion af konjunktioner af literaler.
Enhver formel har en disjunktiv normalform, og den kan læses direkte af sandhedstabellen: én konjunktion per sand række, forbundet med ∨. Lommeregneren giver også en minimeret DNF, som siger det samme med færre literaler.
I lommeregneren(p ∧ q) ∨ (¬p ∧ r)Et OG af ELLER'er: en konjunktion af klausuler.
Konjunktiv normalform læses af sandhedstabellens falske rækker, én klausul per række. Det er det inputformat, SAT-løsere forventer, hvilket gør omskrivning til KNF til et rutinetrin i automatisk ræsonnement.
I lommeregneren(p ∨ q) ∧ (¬p ∨ r)En konjunktion, der udpeger præcis én række i sandhedstabellen.
En minterm nævner hver variabel én gang, negeret eller ej, så præcis én fortolkning opfylder den. At samle mintermerne fra de sande rækker og forbinde dem med ∨ giver formlens disjunktive normalform.
I lommeregnerenp ∧ ¬q ∧ rEn disjunktion, der udelukker præcis én række i sandhedstabellen.
En maksterm nævner hver variabel én gang og er falsk i en enkelt fortolkning. At tage makstermen for hver falsk række og forbinde dem med ∧ giver formlens konjunktive normalform.
I lommeregnerenp ∨ ¬q ∨ rNegation gør ∧ til ∨ og ∨ til ∧: ¬(p ∧ q) ≡ ¬p ∨ ¬q.
De Morgans love skubber en negation indad over en konjunktion eller disjunktion og vender konnektivet undervejs. Sådan drives en formel mod en normalform, og sådan forenkles negationer i kode og i kredsløb.
I lommeregneren¬(p ∧ q) ≡ ¬p ∨ ¬qTo negationer giver originalen: ¬¬p ≡ p.
Dobbeltnegation gælder i klassisk logik begge veje, så ¬¬p og p altid kan byttes om. Intuitionistisk logik beholder kun retningen fra p til ¬¬p, og dér skilles de to systemer.
I lommeregneren¬¬p ≡ pAlgebraen med to værdier og ∧, ∨ og ¬ som operationer.
Boolesk algebra er udsagnslogik skrevet som regning med 0 og 1, med love – kommutativitet, distributivitet, absorption, De Morgan – der lader udtryk omskrives og forenkles. Det er den matematik, digitale kredsløb designes i.
I lommeregneren(p ∧ q) ∨ (p ∧ ¬q) ≡ pEt gitter over sandhedstabellen, der gør forenklinger synlige.
Et Karnaugh-kort ordner rækkerne, så nabofelter kun adskiller sig i én variabel, og kanterne hænger sammen. Det skrives også K-kort, K-map eller kmap. Rektangulære grupper af naboliggende 1-taller af størrelse 1, 2, 4 eller 8 læses så direkte som led i et minimalt udtryk.
I lommeregneren(p ∧ q) ∨ (p ∧ ¬r)En gruppe på kortet, der ikke kan gøres større.
En implikant er en konjunktion af literaler, der tvinger formlen til at være sand; den er prim, når fjernelse af en hvilken som helst literal ville ødelægge det. På et Karnaugh-kort er primimplikanterne de maksimale rektangler af 1-taller.
Den eneste primimplikant, der dækker et bestemt 1-tal.
Når et 1-tal på kortet kun hører til én maksimal gruppe, må den gruppe indgå i enhver minimal dækning og tages derfor først. Det, der bliver tilbage, er den del af dækningen, der virkelig skal søges.
Et kredsløbselement, der beregner ét konnektiv på sine input.
AND-, OR-, NOT-, NAND-, NOR- og XOR-porte er konnektivernes modstykke i hardware. En formel og et kredsløb er den samme genstand tegnet to gange, og derfor kan lommeregneren vise et udtryk som et portdiagram.
I lommeregneren(p ∧ q) ∨ ¬rEt tilladt skridt fra allerede udledte formler til en ny.
En slutningsregel er et mønster som modus ponens, der må anvendes, så snart formler af den rette form foreligger. Bevissystemer bygges af en håndfuld af dem, valgt så kun konklusioner, der følger, kan udledes.
Af p → q og p sluttes q.
Modus ponens er konditionalens grundregel: givet en konditional og dens forled følger efterleddet. Gyldigheden ses i sandhedstabellen – den eneste række med begge præmisser sande har også konklusionen sand.
I lommeregnerenp → q, p ⊨ qAf p → q og ¬q sluttes ¬p.
Modus tollens går baglæns gennem en konditional: svigter efterleddet, kan forleddet ikke have holdt. Det er kontrapositionen i arbejde og formen på ethvert argument, der gendriver en hypotese ved at afprøve dens forudsigelser.
I lommeregnerenp → q, ¬q ⊨ ¬pAf p → q og q → r sluttes p → r.
Den hypotetiske syllogisme kæder konditionaler sammen, og det er dét, der gør lange udledninger mulige: hvert led fører argumentet et skridt videre, uden at nogen præmis hævdes.
I lommeregnerenp → q, q → r ⊨ p → rAf p ∨ q og ¬p sluttes q.
Den disjunktive syllogisme stryger den udelukkede mulighed: holder en af to muligheder, og den første ikke gør, må den anden gøre det. Det er reglen bag udelukkelsesmetoden.
I lommeregnerenp ∨ q, ¬p ⊨ qAt bevise en konklusion ved at anvende slutningsregler skridt for skridt.
Naturlig deduktion udleder en konklusion af præmisser med introduktions- og eliminationsregler for hvert konnektiv og tillader midlertidige antagelser, der senere afvikles. Den beviser det, en sandhedstabel kontrollerer, men uden at gennemgå hver række.
Antag det modsatte, udled en modsigelse, slut det oprindelige.
For at bevise φ antager man ¬φ og udleder noget af formen ψ ∧ ¬ψ. Da ingen fortolkning gør en modsigelse sand, kan antagelsen ikke holde, og φ følger. Sådan forløber beviser for irrationalitet og uendelighed som regel.
I lommeregnerenp ∧ ¬pDet ugyldige skridt fra p → q og q til p.
Et sandt efterled godtgør ikke forleddet: noget andet kan have frembragt det. Lommeregneren viser modmodellen – p falsk, q sand – som er den række, der adskiller dette fra modus ponens.
I lommeregnerenp → q, q ⊨ pDet ugyldige skridt fra p → q og ¬p til ¬q.
En konditional siger intet om, hvad der sker, når forleddet svigter, så at udelukke forleddet lader efterleddet stå åbent. Modmodellen er den række, hvor p er falsk og q sand.
I lommeregnerenp → q, ¬p ⊨ ¬qLogik, der ser ind i udsagn, på genstande og deres egenskaber.
Prædikatlogik tilføjer prædikater, termer og kvantorer, så „ethvert primtal større end to er ulige“ bliver en formel og ikke et enkelt bogstav. Den er strengt mere udtryksfuld end udsagnslogik, og ingen sandhedstabel kan afgøre den.
Et symbol, der siger, hvor mange genstande et prædikat gælder for.
De to klassiske kvantorer er ∀ (alle) og ∃ (mindst én), og hver er den andens negation med negeret krop. Den variabel, en kvantor binder, er dét, der adskiller prædikatlogik fra udsagnslogik.
∀x φ: φ gælder for hver genstand i domænet.
En universel påstand gendrives af et eneste modeksempel og holder tomt over et tomt domæne. ∀x φ er ækvivalent med ¬∃x ¬φ, kvantorernes modstykke til De Morgans love.
∃x φ: φ gælder for mindst én genstand i domænet.
En eksistenspåstand godtgøres ved at fremvise ét vidne. ∃x φ er ækvivalent med ¬∀x ¬φ, så hver kvantor kan defineres ud fra den anden sammen med negationen.
Logik udvidet med „nødvendigvis“ (□) og „muligvis“ (◇).
Modallogik vurderer formler i mulige verdener frem for i én fortolkning: □φ holder, når φ holder i enhver tilgængelig verden, ◇φ når den holder i mindst én. At variere, hvad „tilgængelig“ betyder, giver de forskellige modalsystemer.
