Alle begrippen die de rekenmachine, de gidsen en de oefeningen gebruiken, op één plek gedefinieerd.
Zoek een begrip op, bekijk de notatie en open het voorbeeld in de rekenmachine om het aan het werk te zien. Begrippen van hier worden in een gids gemarkeerd zodra ze voor het eerst voorkomen.
Alle 62 begrippen
De studie van welke conclusies werkelijk uit welke aannames volgen.
De logica bestudeert de vorm van het redeneren, niet de inhoud. De formele logica vervangt zinnen door symbolen, zodat aan de vorm van een argument alleen al te beslissen valt of een conclusie volgt, en dat machinaal te controleren is.
Een bewering die waar of onwaar is, maar niet allebei.
Een propositie is een mededelende zin met precies één waarheidswaarde. “Het regent” is een propositie; een vraag of een bevel niet, want daaraan valt niets waar of onwaar te noemen.
Een van de twee waarden die een propositie kan aannemen: waar of onwaar.
De klassieke logica geeft elke propositie precies één van twee waarheidswaarden, geschreven ⊤ en ⊥ (of 1 en 0). Elke rij van een waarheidstabel is één toekenning van waarden aan de variabelen, met de waarde die de formule daar aanneemt.
Een propositie zonder enig connectief erin.
Een atomaire propositie valt niet in kleinere proposities uiteen: er zit geen negatie, conjunctie of ander connectief in. Al het overige is samengesteld, uit atomen opgebouwd, en de waarheidswaarde ervan ligt met die van de atomen vast.
Een letter als p of A die voor een willekeurige propositie staat.
Een propositievariabele is een plaatshouder voor welke propositie dan ook. De rekenmachine neemt losse letters als variabelen en geeft elke een kolom van de waarheidstabel, met een rij voor elke mogelijke combinatie van waarden.
In de rekenmachinep → qEen rij symbolen die de grammatica van de taal ook werkelijk toelaat.
Een welgevormde formule wordt volgens de regels gebouwd: een variabele is er een, en elke formule die met een connectief uit kleinere formules ontstaat ook. “p ∧ ∨ q” is er geen, en daarom meldt de rekenmachine een fout in plaats van te gokken.
Eén toekenning van waarheidswaarden aan alle variabelen van een formule.
Een interpretatie zegt wat elke variabele waard is en legt daarmee de waarde van de hele formule vast. Een formule met n variabelen heeft 2ⁿ interpretaties, precies de rijen van haar waarheidstabel.
Premissen die ter ondersteuning van een conclusie worden aangevoerd.
Een argument beweert dat zijn conclusie uit zijn premissen volgt. Typ er een in de rekenmachine met een afleidingsteken — premissen ervoor, conclusie erna — en elke rij wordt gecontroleerd op een geval waarin de premissen gelden en de conclusie faalt.
In de rekenmachinep → q, p ⊨ qEen bewering die een argument aanneemt om bij zijn conclusie te komen.
Premissen zijn het vertrekpunt van een argument. Geldigheid vraagt alleen of de conclusie geldt overal waar alle premissen gelden; of ze feitelijk waar zijn is een andere vraag, en die voegt deugdelijkheid toe.
In de rekenmachinep → q, p ⊨ qDe bewering die een argument wil vestigen.
De conclusie is waarvoor de premissen worden aangevoerd. In de rekenmachine is het de uitdrukking na het afleidingsteken, en een argument is geldig wanneer geen enkele interpretatie de premissen waar en de conclusie onwaar maakt.
In de rekenmachinep → q, p ⊨ qEen symbool dat uit eenvoudiger proposities een samengestelde bouwt.
Een connectief zoals ¬, ∧, ∨, → of ↔ voegt proposities samen tot een grotere waarvan de waarheidswaarde alleen van die van de delen afhangt. Precies die afhankelijkheid legt een waarheidstabel vast, één rij per combinatie van invoerwaarden.
Keert een waarheidswaarde om: ¬p is waar precies als p onwaar is.
De negatie is het enige eenplaatsige connectief van de propositielogica. Geschreven ¬p, ~p of !p maakt zij waar tot onwaar en onwaar tot waar, zodat tweemaal ontkennen de oorspronkelijke propositie teruggeeft.
In de rekenmachine¬pAlleen waar als beide delen waar zijn: p ∧ q.
Een conjunctie beweert beide delen, de conjuncten. Zij is waar in precies één rij van haar waarheidstabel — die waarin beide conjuncten waar zijn — en daarmee het strengste van de tweeplaatsige connectieven.
In de rekenmachinep ∧ qWaar wanneer minstens één deel waar is: p ∨ q.
De disjunctie is in de logica inclusief: p ∨ q is waar als p waar is, als q waar is en als beide waar zijn. De exclusieve lezing van “of”, alleen waar bij verschillende delen, is een apart connectief.
In de rekenmachinep ∨ qWaar wanneer precies één van twee proposities waar is.
De exclusieve disjunctie, geschreven ⊕ of XOR, geldt wanneer haar delen verschillen en faalt wanneer ze overeenstemmen. Zij is de negatie van het bi-implicatie-connectief en kan worden geschreven als (p ∨ q) ∧ ¬(p ∧ q).
In de rekenmachine(p ∨ q) ∧ ¬(p ∧ q)p → q, alleen onwaar als p waar en q onwaar is.
De materiële implicatie zegt niets meer dan “niet: antecedent waar en consequent onwaar”, en geldt dus automatisch zodra het antecedent faalt. Daarom is p → q equivalent met ¬p ∨ q.
In de rekenmachinep → qp ↔ q, waar wanneer beide delen dezelfde waarheidswaarde hebben.
De bi-implicatie beweert elke kant onder voorwaarde van de andere: zij is waar als beide delen waar zijn en als beide onwaar zijn. Een bi-implicatie die een tautologie is, drukt precies een logische equivalentie uit.
In de rekenmachinep ↔ qHet “als”-deel van een implicatie: de p in p → q.
Het antecedent is de voorwaarde waarvan een implicatie afhangt. Is het onwaar, dan is de hele implicatie waar wat het consequent ook zegt, en daar komen de meeste verrassingen in de tabel van → vandaan.
In de rekenmachinep → qHet “dan”-deel van een implicatie: de q in p → q.
Het consequent is wat een implicatie beweert te volgen als haar antecedent geldt. Een waar consequent maakt de implicatie waar, maar het antecedent niet: dat afleiden is een formele drogreden.
In de rekenmachinep → qDe implicatie met de twee delen verwisseld: q → p.
Het omgekeerde van p → q is q → p, en de twee zijn niet equivalent: de rekenmachine vindt een rij waarin de een geldt en de ander faalt. Ze als uitwisselbaar behandelen is het consequent bevestigen.
In de rekenmachineq → p¬q → ¬p, altijd met dezelfde waarheidswaarde als p → q.
De contrapositie ontkent beide delen van een implicatie en verwisselt ze. Anders dan het omgekeerde is zij werkelijk equivalent met het origineel, en daarom is bewijs door contrapositie in de wiskunde geldig.
In de rekenmachine(p → q) ≡ (¬q → ¬p)De negatie van een conjunctie: waar tenzij beide invoeren waar zijn.
NAND, geschreven ↑, is ¬(p ∧ q). Het is functioneel volledig: elk ander connectief kan uit NAND alleen worden gebouwd, en daarom is het een werkpaard van het ontwerp van digitale schakelingen.
In de rekenmachine¬(p ∧ q)De negatie van een disjunctie: alleen waar als beide invoeren onwaar zijn.
NOR, geschreven ↓, is ¬(p ∨ q). Net als NAND is het op zichzelf functioneel volledig, zodat een schakeling volledig uit NOR-poorten kan worden opgebouwd.
In de rekenmachine¬(p ∨ q)Welk connectief het eerst bindt als haakjes ontbreken.
De negatie bindt het sterkst, dan de conjunctie, de disjunctie, de implicatie en ten slotte de bi-implicatie. Zo leest ¬p ∧ q ∨ r als ((¬p) ∧ q) ∨ r; haakjes doorbreken die volgorde zodra de bedoelde lezing anders is.
In de rekenmachine¬p ∧ q ∨ rEén rij per toekenning van waarden, met de waarde van de formule.
Een waarheidstabel somt alle 2ⁿ interpretaties van de n variabelen van een formule op en berekent haar waarde in elke. Omdat ze uitputtend is beslist ze elke semantische vraag van de propositielogica: equivalentie, geldigheid, vervulbaarheid en de rest.
In de rekenmachinep → qEen formule die onder elke interpretatie waar is.
Een tautologie is in elke rij van haar waarheidstabel waar en zegt dus niets over de wereld: p ∨ ¬p is waar wat p ook is. Twee formules zijn precies dan equivalent wanneer de bi-implicatie ertussen een tautologie is.
In de rekenmachinep ∨ ¬pEen formule die onder elke interpretatie onwaar is.
Een contradictie als p ∧ ¬p is in elke rij van haar waarheidstabel onwaar. Er een uit een verzameling aannames afleiden laat zien dat die niet allemaal kunnen gelden — de motor van het bewijs uit het ongerijmde.
In de rekenmachinep ∧ ¬pEen formule die onder sommige interpretaties waar is en onder andere onwaar.
Een contingente formule is noch tautologie noch contradictie: haar waarheidstabel heeft minstens één ware en minstens één onware rij. Vrijwel elke formule die iemand opschrijft is contingent, en juist daarom informatief.
In de rekenmachinep ∧ qOf enige interpretatie de formule waar maakt.
Een formule is vervulbaar wanneer minstens één rij van haar waarheidstabel waar is, en die rij is er een model van. Vervulbaarheid beslissen is het centrale probleem van SAT-solvers en daarmee van veel automatisch redeneren.
In de rekenmachinep ∧ (p → q)Twee formules met identieke waarheidstabellen.
Equivalente formules stemmen onder elke interpretatie overeen, zodat de een de ander overal kan vervangen zonder de inhoud te wijzigen. Zet een gelijkteken tussen twee uitdrukkingen en de rekenmachine vergelijkt hun kolommen rij voor rij.
In de rekenmachine(p → q) ≡ (¬p ∨ q)De conclusie geldt in elke interpretatie waarin de premissen gelden.
Geschreven Γ ⊨ φ is het logisch gevolg wat een geldig argument claimt. Het wordt gecontroleerd door een tegenvoorbeeld te zoeken: een interpretatie die alle premissen waar en de conclusie onwaar maakt. Is die er niet, dan geldt het gevolg.
In de rekenmachinep → q, p ⊨ qGeen interpretatie maakt de premissen waar en de conclusie onwaar.
Geldigheid is een eigenschap van de vorm van een argument, niet van de feiten: een geldig argument mag onware premissen en een onware conclusie hebben. Wat het niet kan hebben zijn ware premissen naast een onware conclusie.
In de rekenmachinep → q, p ⊨ qEen geldig argument waarvan de premissen bovendien waar zijn.
Deugdelijkheid voegt een feitelijke bewering toe aan een formele: het argument is geldig en zijn premissen gelden. De eerste helft beslecht de logica alleen; de tweede hoort bij het onderwerp waarover het argument gaat.
Een interpretatie die de premissen waar en de conclusie onwaar maakt.
Een tegenmodel bewijst dat een argument ongeldig is — één rij volstaat. De rekenmachine toont de rij die zij vindt, en daarmee wordt “dit volgt niet” een concrete toekenning die je met de hand kunt nagaan.
In de rekenmachinep → q ⊨ q → pEnige interpretatie maakt alle beweringen in de verzameling tegelijk waar.
Een verzameling premissen is consistent wanneer ze allemaal samen kunnen gelden. Inconsistente premissen impliceren letterlijk alles, zodat een argument dat erop rust technisch geldig is en niets waard.
In de rekenmachinep → q, ¬q ⊨ ¬pEen variabele of haar negatie, zoals p of ¬p.
Literalen zijn de atomen van de normaalvormen: een clausule is een disjunctie van literalen en een minterm een conjunctie ervan. Een literaal is positief als de variabele kaal staat en negatief als zij ontkend is.
In de rekenmachine¬pEen disjunctie van literalen, zoals p ∨ ¬q ∨ r.
Een clausule is een van de groepen tussen haakjes waaruit een conjunctieve normaalvorm bestaat. Omdat een conjunctie alleen waar is als elk deel waar is, geldt een CNF-formule precies wanneer al haar clausules gelden.
In de rekenmachinep ∨ ¬q ∨ rEen OF van ENs: een disjunctie van conjuncties van literalen.
Elke formule heeft een disjunctieve normaalvorm, en die is rechtstreeks uit de waarheidstabel af te lezen: één conjunctie per ware rij, verbonden met ∨. De rekenmachine geeft ook een geminimaliseerde DNF, die hetzelfde zegt met minder literalen.
In de rekenmachine(p ∧ q) ∨ (¬p ∧ r)Een EN van OFs: een conjunctie van clausules.
De conjunctieve normaalvorm wordt uit de onware rijen van de waarheidstabel afgelezen, één clausule per rij. Het is het invoerformaat dat SAT-solvers verwachten, wat omzetting naar CNF een routinestap van automatisch redeneren maakt.
In de rekenmachine(p ∨ q) ∧ (¬p ∨ r)Een conjunctie die precies één rij van de waarheidstabel aanwijst.
Een minterm noemt elke variabele één keer, ontkend of niet, zodat precies één interpretatie hem vervult. De mintermen van de ware rijen verzamelen en met ∨ verbinden geeft de disjunctieve normaalvorm van de formule.
In de rekenmachinep ∧ ¬q ∧ rEen disjunctie die precies één rij van de waarheidstabel uitsluit.
Een maxterm noemt elke variabele één keer en is in één enkele interpretatie onwaar. De maxterm van elke onware rij nemen en ze met ∧ verbinden geeft de conjunctieve normaalvorm van de formule.
In de rekenmachinep ∨ ¬q ∨ rNegatie maakt van ∧ een ∨ en van ∨ een ∧: ¬(p ∧ q) ≡ ¬p ∨ ¬q.
De wetten van De Morgan duwen een negatie naar binnen over een conjunctie of disjunctie en kantelen daarbij het connectief. Zo wordt een formule naar een normaalvorm gebracht, en zo worden negaties in code en in schakelingen vereenvoudigd.
In de rekenmachine¬(p ∧ q) ≡ ¬p ∨ ¬qTweemaal ontkennen geeft het origineel: ¬¬p ≡ p.
De dubbele negatie geldt in de klassieke logica in beide richtingen, zodat ¬¬p en p altijd uitwisselbaar zijn. De intuïtionistische logica houdt alleen de richting van p naar ¬¬p over, en daar scheiden de twee systemen.
In de rekenmachine¬¬p ≡ pDe algebra van twee waarden, met ∧, ∨ en ¬ als bewerkingen.
Booleaanse algebra is propositielogica geschreven als rekenen met 0 en 1, met wetten — commutativiteit, distributiviteit, absorptie, De Morgan — die uitdrukkingen laten herschrijven en vereenvoudigen. Het is de wiskunde waarin digitale schakelingen worden ontworpen.
In de rekenmachine(p ∧ q) ∨ (p ∧ ¬q) ≡ pEen raster van de waarheidstabel dat vereenvoudigingen zichtbaar maakt.
Een Karnaugh-diagram rangschikt de rijen zo dat naburige cellen in één variabele verschillen, en de randen sluiten op elkaar aan. Het wordt ook K-map of kmap geschreven. Rechthoekige groepen aangrenzende enen van grootte 1, 2, 4 of 8 lezen dan direct als termen van een minimale uitdrukking.
In de rekenmachine(p ∧ q) ∨ (p ∧ ¬r)Een groep op het diagram die niet verder kan worden vergroot.
Een implicant is een conjunctie van literalen die de formule waar dwingt; hij is priem wanneer het weglaten van welk literaal ook dat zou verbreken. Op een Karnaugh-diagram zijn de priemimplicanten de maximale rechthoeken van enen.
De enige priemimplicant die een bepaalde één afdekt.
Hoort een één op het diagram bij slechts één maximale groep, dan moet die groep in elke minimale afdekking voorkomen en wordt zij eerst genomen. Wat overblijft is het deel van de afdekking dat werkelijk moet worden gezocht.
Een schakelelement dat één connectief op zijn invoeren berekent.
AND-, OR-, NOT-, NAND-, NOR- en XOR-poorten zijn de hardware-tegenhanger van de connectieven. Een formule en een schakeling zijn hetzelfde object, twee keer getekend, en daarom kan de rekenmachine een uitdrukking als poortschema weergeven.
In de rekenmachine(p ∧ q) ∨ ¬rEen toegestane stap van al afgeleide formules naar een nieuwe.
Een afleidingsregel is een patroon zoals modus ponens dat mag worden toegepast zodra formules van de juiste vorm beschikbaar zijn. Bewijssystemen bestaan uit een handvol ervan, zo gekozen dat alleen volgende conclusies afleidbaar zijn.
Uit p → q en p volgt q.
Modus ponens is de basisregel van de implicatie: gegeven een implicatie en haar antecedent volgt het consequent. De geldigheid blijkt uit de waarheidstabel — de enige rij met beide premissen waar heeft ook de conclusie waar.
In de rekenmachinep → q, p ⊨ qUit p → q en ¬q volgt ¬p.
Modus tollens doorloopt een implicatie achterwaarts: faalt het consequent, dan kan het antecedent niet hebben gegolden. Dat is de contrapositie aan het werk, en de vorm van elk argument dat een hypothese via haar voorspellingen weerlegt.
In de rekenmachinep → q, ¬q ⊨ ¬pUit p → q en q → r volgt p → r.
Het hypothetisch syllogisme koppelt implicaties aaneen, en dat maakt lange afleidingen mogelijk: elke schakel brengt het argument een stap verder zonder dat een premisse wordt beweerd.
In de rekenmachinep → q, q → r ⊨ p → rUit p ∨ q en ¬p volgt q.
Het disjunctief syllogisme schrapt de uitgesloten optie: geldt een van twee alternatieven en de eerste niet, dan moet de tweede gelden. Het is de regel achter redeneren door uitsluiting.
In de rekenmachinep ∨ q, ¬p ⊨ qEen conclusie bewijzen door stap voor stap regels toe te passen.
Natuurlijke deductie leidt een conclusie uit premissen af met introductie- en eliminatieregels voor elk connectief, waarbij tijdelijke aannames mogen worden gemaakt en later ontladen. Zij bewijst wat een waarheidstabel controleert, zonder elke rij af te lopen.
Neem het tegendeel aan, leid een tegenspraak af, concludeer het origineel.
Om φ te bewijzen neem je ¬φ aan en leid je iets van de vorm ψ ∧ ¬ψ af. Omdat geen interpretatie een tegenspraak waar maakt, kan de aanname niet gelden en volgt φ. Zo verlopen bewijzen van irrationaliteit en oneindigheid gewoonlijk.
In de rekenmachinep ∧ ¬pDe ongeldige stap van p → q en q naar p.
Een waar consequent vestigt het antecedent niet: iets anders kan het hebben veroorzaakt. De rekenmachine toont het tegenmodel — p onwaar, q waar — de rij die dit van modus ponens onderscheidt.
In de rekenmachinep → q, q ⊨ pDe ongeldige stap van p → q en ¬p naar ¬q.
Een implicatie zegt niets over wat er gebeurt als haar antecedent faalt, dus het antecedent uitsluiten laat het consequent open. Het tegenmodel is de rij waarin p onwaar en q waar is.
In de rekenmachinep → q, ¬p ⊨ ¬qLogica die in proposities kijkt, naar objecten en hun eigenschappen.
De predicatenlogica voegt predicaten, termen en kwantoren toe, zodat “elk priemgetal groter dan twee is oneven” een formule wordt in plaats van één letter. Zij is strikt expressiever dan de propositielogica, en geen waarheidstabel kan haar beslissen.
Een symbool dat zegt van hoeveel objecten een predicaat geldt.
De twee klassieke kwantoren zijn ∀ (alle) en ∃ (minstens één), en elk is de negatie van de ander met ontkende kern. De variabele die een kwantor bindt, onderscheidt de predicatenlogica van de propositielogica.
∀x φ: φ geldt van elk object in het domein.
Een universele bewering wordt door één tegenvoorbeeld weerlegd en geldt leeg over een leeg domein. ∀x φ is equivalent met ¬∃x ¬φ, de kwantor-tegenhanger van de wetten van De Morgan.
∃x φ: φ geldt van minstens één object in het domein.
Een existentiële bewering wordt gevestigd door één getuige aan te wijzen. ∃x φ is equivalent met ¬∀x ¬φ, zodat elke kwantor uit de andere en de negatie te definiëren is.
Logica uitgebreid met “noodzakelijk” (□) en “mogelijk” (◇).
De modale logica evalueert formules in mogelijke werelden in plaats van in één interpretatie: □φ geldt wanneer φ in elke toegankelijke wereld geldt, ◇φ wanneer zij in een ervan geldt. Variëren wat “toegankelijk” betekent geeft de verschillende modale systemen.
