Alle Begriffe, die Rechner, Anleitungen und Übungen verwenden – an einer Stelle definiert.
Schlage einen Begriff nach, sieh dir seine Notation an und öffne das Beispiel im Rechner. Begriffe von hier werden in den Anleitungen bei ihrem ersten Auftreten hervorgehoben.
Alle 62 Begriffe
Die Lehre davon, welche Schlüsse aus welchen Annahmen wirklich folgen.
Die Logik untersucht die Form des Schließens, nicht seinen Inhalt. Die formale Logik ersetzt Sätze durch Symbole, sodass sich allein an der Gestalt eines Arguments entscheiden lässt, ob eine Konklusion folgt – und zwar maschinell prüfbar.
Ein Satz, der entweder wahr oder falsch ist, aber nicht beides.
Eine Aussage ist ein Behauptungssatz mit genau einem Wahrheitswert. „Es regnet“ ist eine Aussage; eine Frage oder ein Befehl ist keine, denn an ihnen gibt es nichts, was wahr oder falsch sein könnte.
Einer der beiden Werte einer Aussage: wahr oder falsch.
Die klassische Logik gibt jeder Aussage genau einen von zwei Wahrheitswerten, geschrieben ⊤ und ⊥ (oder 1 und 0). Jede Zeile einer Wahrheitstabelle ist eine Belegung der Variablen samt dem Wert, den die Formel dort annimmt.
Eine Aussage, in der kein Junktor vorkommt.
Eine atomare Aussage lässt sich nicht in kleinere Aussagen zerlegen: Sie enthält weder Negation noch Konjunktion noch einen anderen Junktor. Alles Übrige ist zusammengesetzt, aus Atomen gebaut, und sein Wahrheitswert ergibt sich aus deren Werten.
Ein Buchstabe wie p oder A, der für eine beliebige Aussage steht.
Eine Aussagenvariable ist ein Platzhalter für irgendeine Aussage. Der Rechner nimmt einzelne Buchstaben als Variablen und gibt jeder eine Spalte der Wahrheitstabelle, mit einer Zeile für jede mögliche Wertkombination.
Im Rechnerp → qEine Zeichenfolge, die die Grammatik der Sprache tatsächlich zulässt.
Eine wohlgeformte Formel entsteht nach den Regeln: Eine Variable ist eine, und jede aus kleineren Formeln durch einen Junktor gebildete Formel ebenfalls. „p ∧ ∨ q“ ist keine – deshalb meldet der Rechner einen Fehler, statt zu raten.
Eine Zuweisung von Wahrheitswerten an alle Variablen einer Formel.
Eine Interpretation sagt, was jede Variable gilt, und legt damit den Wert der ganzen Formel fest. Eine Formel mit n Variablen hat 2ⁿ Interpretationen – genau die Zeilen ihrer Wahrheitstabelle.
Prämissen, die zur Stützung einer Konklusion angeführt werden.
Ein Argument behauptet, dass seine Konklusion aus seinen Prämissen folgt. Gib eines mit einem Folgerungszeichen in den Rechner ein – Prämissen davor, Konklusion danach – und jede Zeile wird auf einen Fall geprüft, in dem die Prämissen gelten und die Konklusion scheitert.
Im Rechnerp → q, p ⊨ qEine Annahme, von der ein Argument zu seiner Konklusion ausgeht.
Prämissen sind der Ausgangspunkt eines Arguments. Gültigkeit fragt nur, ob die Konklusion überall dort gilt, wo alle Prämissen gelten; ob diese tatsächlich wahr sind, ist eine eigene Frage – die der Schlüssigkeit.
Im Rechnerp → q, p ⊨ qDer Satz, den ein Argument begründen will.
Die Konklusion ist das, wofür die Prämissen sprechen sollen. Im Rechner ist sie der Ausdruck hinter dem Folgerungszeichen, und ein Argument ist gültig, wenn keine Interpretation die Prämissen wahr und die Konklusion falsch macht.
Im Rechnerp → q, p ⊨ qEin Symbol, das aus einfacheren Aussagen eine zusammengesetzte bildet.
Ein Junktor wie ¬, ∧, ∨, → oder ↔ verbindet Aussagen zu einer größeren, deren Wahrheitswert allein von deren Werten abhängt. Genau diese Abhängigkeit hält eine Wahrheitstabelle fest, eine Zeile pro Eingabekombination.
Kehrt einen Wahrheitswert um: ¬p ist wahr genau dann, wenn p falsch ist.
Die Negation ist der einzige einstellige Junktor der Aussagenlogik. Geschrieben ¬p, ~p oder !p, macht sie aus wahr falsch und aus falsch wahr – zweimal negiert ergibt wieder die ursprüngliche Aussage.
Im Rechner¬pNur wahr, wenn beide Teile wahr sind: p ∧ q.
Eine Konjunktion behauptet beide Teile, die Konjunkte. Sie ist in genau einer Zeile ihrer Wahrheitstabelle wahr – der, in der beide Konjunkte wahr sind – und damit der strengste der zweistelligen Junktoren.
Im Rechnerp ∧ qWahr, wenn mindestens ein Teil wahr ist: p ∨ q.
Die Disjunktion ist in der Logik einschließend: p ∨ q ist wahr, wenn p wahr ist, wenn q wahr ist und wenn beide es sind. Das ausschließende „oder“, das nur bei verschiedenen Teilen wahr ist, ist ein eigener Junktor.
Im Rechnerp ∨ qWahr, wenn genau eine der beiden Aussagen wahr ist.
Die ausschließende Disjunktion, geschrieben ⊕ oder XOR, gilt, wenn ihre Teile verschieden sind, und scheitert, wenn sie übereinstimmen. Sie ist die Negation der Bikonditionale und lässt sich als (p ∨ q) ∧ ¬(p ∧ q) schreiben.
Im Rechner(p ∨ q) ∧ ¬(p ∧ q)p → q, falsch nur, wenn p wahr und q falsch ist.
Das materiale Konditional sagt nichts weiter als „nicht: Antezedens wahr und Konsequens falsch“ und gilt daher automatisch, sobald das Antezedens scheitert. Deshalb ist p → q äquivalent zu ¬p ∨ q.
Im Rechnerp → qp ↔ q, wahr, wenn beide Teile denselben Wahrheitswert haben.
Das Bikonditional behauptet jede Seite unter der Bedingung der anderen: Es ist wahr, wenn beide Teile wahr sind, und wenn beide falsch sind. Ein Bikonditional, das eine Tautologie ist, drückt genau eine logische Äquivalenz aus.
Im Rechnerp ↔ qDer „wenn“-Teil eines Konditionals – das p in p → q.
Das Antezedens ist die Bedingung, von der ein Konditional abhängt. Ist es falsch, so ist das ganze Konditional wahr, gleichgültig was das Konsequens sagt – daher stammen die meisten Überraschungen in der Tabelle von →.
Im Rechnerp → qDer „dann“-Teil eines Konditionals – das q in p → q.
Das Konsequens ist das, was ein Konditional für den Fall behauptet, dass sein Antezedens gilt. Ein wahres Konsequens macht das Konditional wahr, aber nicht das Antezedens: Das zu schließen ist ein formaler Fehlschluss.
Im Rechnerp → qDas Konditional mit vertauschten Teilen: q → p.
Die Umkehrung von p → q ist q → p, und die beiden sind nicht äquivalent: Der Rechner findet eine Zeile, in der das eine gilt und das andere scheitert. Sie gleichzusetzen heißt, das Konsequens zu bejahen.
Im Rechnerq → p¬q → ¬p, immer mit demselben Wahrheitswert wie p → q.
Die Kontraposition negiert beide Teile eines Konditionals und vertauscht sie. Anders als die Umkehrung ist sie dem Original wirklich äquivalent, und deshalb ist der Beweis durch Kontraposition in der Mathematik zulässig.
Im Rechner(p → q) ≡ (¬q → ¬p)Die Negation einer Konjunktion: wahr, außer wenn beide Eingaben wahr sind.
NAND, geschrieben ↑, ist ¬(p ∧ q). Es ist funktional vollständig: Jeder andere Junktor lässt sich allein aus NAND aufbauen, weshalb es ein Arbeitspferd des Digitalschaltungsentwurfs ist.
Im Rechner¬(p ∧ q)Die Negation einer Disjunktion: wahr nur, wenn beide Eingaben falsch sind.
NOR, geschrieben ↓, ist ¬(p ∨ q). Wie NAND ist es für sich allein funktional vollständig, sodass sich eine Schaltung vollständig aus NOR-Gattern bauen lässt.
Im Rechner¬(p ∨ q)Welcher Junktor zuerst bindet, wenn Klammern fehlen.
Am stärksten bindet die Negation, dann Konjunktion, Disjunktion, Konditional und zuletzt Bikonditional. So liest sich ¬p ∧ q ∨ r als ((¬p) ∧ q) ∨ r; Klammern setzen diese Reihenfolge außer Kraft, wo die gemeinte Lesart abweicht.
Im Rechner¬p ∧ q ∨ rEine Zeile je Belegung, mit dem Wert der Formel in jeder.
Eine Wahrheitstabelle listet alle 2ⁿ Interpretationen der n Variablen einer Formel und berechnet ihren Wert in jeder. Da sie vollständig ist, entscheidet sie jede semantische Frage der Aussagenlogik: Äquivalenz, Gültigkeit, Erfüllbarkeit und alles Weitere.
Im Rechnerp → qEine Formel, die unter jeder Interpretation wahr ist.
Eine Tautologie ist in jeder Zeile ihrer Wahrheitstabelle wahr und sagt daher nichts über die Welt: p ∨ ¬p ist wahr, was immer p ist. Zwei Formeln sind genau dann äquivalent, wenn das Bikonditional zwischen ihnen eine Tautologie ist.
Im Rechnerp ∨ ¬pEine Formel, die unter jeder Interpretation falsch ist.
Eine Kontradiktion wie p ∧ ¬p ist in jeder Zeile ihrer Wahrheitstabelle falsch. Leitet man aus Annahmen eine ab, zeigt das, dass die Annahmen nicht alle gelten können – der Motor des Widerspruchsbeweises.
Im Rechnerp ∧ ¬pEine Formel, die unter manchen Interpretationen wahr, unter anderen falsch ist.
Eine kontingente Formel ist weder Tautologie noch Kontradiktion: Ihre Wahrheitstabelle hat mindestens eine wahre und mindestens eine falsche Zeile. Die meisten Formeln, die jemand aufschreibt, sind kontingent – und deshalb informativ.
Im Rechnerp ∧ qOb irgendeine Interpretation die Formel wahr macht.
Eine Formel ist erfüllbar, wenn mindestens eine Zeile ihrer Wahrheitstabelle wahr ist, und diese Zeile ist ein Modell von ihr. Die Erfüllbarkeit zu entscheiden ist das zentrale Problem der SAT-Solver und damit weiter Teile des automatischen Schließens.
Im Rechnerp ∧ (p → q)Zwei Formeln mit identischen Wahrheitstabellen.
Äquivalente Formeln stimmen unter jeder Interpretation überein, sodass eine die andere überall ersetzen kann, ohne den Inhalt zu ändern. Schreib ein Gleichheitszeichen zwischen zwei Ausdrücke, und der Rechner vergleicht ihre Spalten Zeile für Zeile.
Im Rechner(p → q) ≡ (¬p ∨ q)Die Konklusion gilt in jeder Interpretation, in der die Prämissen gelten.
Geschrieben Γ ⊨ φ, ist die logische Folgerung das, was ein gültiges Argument behauptet. Geprüft wird sie durch die Suche nach einem Gegenbeispiel: einer Interpretation, die alle Prämissen wahr und die Konklusion falsch macht. Gibt es keines, gilt die Folgerung.
Im Rechnerp → q, p ⊨ qKeine Interpretation macht die Prämissen wahr und die Konklusion falsch.
Gültigkeit ist eine Eigenschaft der Form eines Arguments, nicht der Tatsachen: Ein gültiges Argument darf falsche Prämissen und eine falsche Konklusion haben. Was es nicht haben kann, sind wahre Prämissen neben einer falschen Konklusion.
Im Rechnerp → q, p ⊨ qEin gültiges Argument, dessen Prämissen zudem wahr sind.
Schlüssigkeit fügt einer formalen Behauptung eine inhaltliche hinzu: Das Argument ist gültig, und seine Prämissen gelten. Die erste Hälfte klärt die Logik allein; die zweite gehört dem Gegenstand, von dem das Argument handelt.
Eine Interpretation, die die Prämissen wahr und die Konklusion falsch macht.
Ein Gegenmodell beweist, dass ein Argument ungültig ist – eine Zeile genügt. Der Rechner zeigt die gefundene Zeile an und macht so aus „das folgt nicht“ eine konkrete Belegung, die man von Hand nachprüfen kann.
Im Rechnerp → q ⊨ q → pEine Interpretation macht alle Sätze der Menge zugleich wahr.
Eine Menge von Prämissen ist konsistent, wenn sie alle zusammen gelten können. Aus inkonsistenten Prämissen folgt schlechthin alles, sodass ein darauf gebautes Argument technisch gültig und wertlos ist.
Im Rechnerp → q, ¬q ⊨ ¬pEine Variable oder ihre Negation, etwa p oder ¬p.
Literale sind die Atome der Normalformen: Eine Klausel ist eine Disjunktion von Literalen, ein Minterm eine Konjunktion von ihnen. Ein Literal ist positiv, wenn die Variable unnegiert steht, und negativ, wenn sie negiert ist.
Im Rechner¬pEine Disjunktion von Literalen, etwa p ∨ ¬q ∨ r.
Eine Klausel ist eine der geklammerten Gruppen, aus denen eine konjunktive Normalform besteht. Da eine Konjunktion nur wahr ist, wenn jeder Teil wahr ist, gilt eine KNF-Formel genau dann, wenn jede ihrer Klauseln gilt.
Im Rechnerp ∨ ¬q ∨ rEin ODER von UNDs: eine Disjunktion von Konjunktionen von Literalen.
Jede Formel hat eine disjunktive Normalform, und sie lässt sich direkt aus der Wahrheitstabelle ablesen: eine Konjunktion je wahrer Zeile, verbunden mit ∨. Der Rechner gibt zusätzlich eine minimierte DNF an, die dasselbe mit weniger Literalen sagt.
Im Rechner(p ∧ q) ∨ (¬p ∧ r)Ein UND von ODERs: eine Konjunktion von Klauseln.
Die konjunktive Normalform liest man aus den falschen Zeilen der Wahrheitstabelle ab, eine Klausel je Zeile. Sie ist das Eingabeformat, das SAT-Solver erwarten, weshalb die Umwandlung in KNF ein Routineschritt des automatischen Schließens ist.
Im Rechner(p ∨ q) ∧ (¬p ∨ r)Eine Konjunktion, die genau eine Zeile der Wahrheitstabelle benennt.
Ein Minterm nennt jede Variable einmal, negiert oder nicht, sodass ihn genau eine Interpretation erfüllt. Sammelt man die Minterme der wahren Zeilen und verbindet sie mit ∨, erhält man die disjunktive Normalform der Formel.
Im Rechnerp ∧ ¬q ∧ rEine Disjunktion, die genau eine Zeile der Wahrheitstabelle ausschließt.
Ein Maxterm nennt jede Variable einmal und ist in genau einer Interpretation falsch. Nimmt man den Maxterm jeder falschen Zeile und verbindet sie mit ∧, erhält man die konjunktive Normalform der Formel.
Im Rechnerp ∨ ¬q ∨ rNegation macht aus ∧ ein ∨ und aus ∨ ein ∧: ¬(p ∧ q) ≡ ¬p ∨ ¬q.
Die De-Morgan-Gesetze schieben eine Negation über eine Konjunktion oder Disjunktion nach innen und kippen dabei den Junktor. So bringt man eine Formel auf Normalform, und so vereinfacht man Negationen im Code wie in Schaltungen.
Im Rechner¬(p ∧ q) ≡ ¬p ∨ ¬qZweimal negiert ergibt das Original: ¬¬p ≡ p.
Die doppelte Negation gilt in der klassischen Logik in beide Richtungen, sodass ¬¬p und p stets austauschbar sind. Die intuitionistische Logik behält nur die Richtung von p zu ¬¬p – dort trennen sich die beiden Systeme.
Im Rechner¬¬p ≡ pDie Algebra zweier Werte, mit ∧, ∨ und ¬ als Operationen.
Die boolesche Algebra ist Aussagenlogik als Rechnen mit 0 und 1, mit Gesetzen – Kommutativität, Distributivität, Absorption, De Morgan –, die das Umformen und Vereinfachen von Ausdrücken erlauben. In ihr werden Digitalschaltungen entworfen.
Im Rechner(p ∧ q) ∨ (p ∧ ¬q) ≡ pEin Raster der Wahrheitstabelle, das Vereinfachungen sichtbar macht.
Ein Karnaugh-Diagramm ordnet die Zeilen so an, dass benachbarte Felder sich in einer Variablen unterscheiden, und die Ränder gehen ineinander über. Es wird auch K-Map oder kmap geschrieben. Rechteckige Gruppen benachbarter Einsen der Größe 1, 2, 4 oder 8 liest man dann als Terme eines minimalen Ausdrucks.
Im Rechner(p ∧ q) ∨ (p ∧ ¬r)Eine Gruppe im Diagramm, die sich nicht weiter vergrößern lässt.
Ein Implikant ist eine Konjunktion von Literalen, die die Formel wahr macht; er ist prim, wenn das Weglassen eines Literals das zerstören würde. Im Karnaugh-Diagramm sind die Primimplikanten die maximalen Rechtecke aus Einsen.
Der einzige Primimplikant, der eine bestimmte Eins abdeckt.
Gehört eine Eins im Diagramm nur zu einer einzigen maximalen Gruppe, muss diese Gruppe in jeder minimalen Überdeckung vorkommen und wird zuerst genommen. Was übrig bleibt, ist der Teil, der wirklich durchsucht werden muss.
Ein Schaltungselement, das einen Junktor auf seinen Eingängen berechnet.
UND-, ODER-, NICHT-, NAND-, NOR- und XOR-Gatter sind das Hardware-Gegenstück der Junktoren. Formel und Schaltung sind dasselbe Objekt, zweimal gezeichnet – deshalb kann der Rechner einen Ausdruck als Gatterschaltbild darstellen.
Im Rechner(p ∧ q) ∨ ¬rEin erlaubter Schritt von schon Abgeleitetem zu etwas Neuem.
Eine Schlussregel ist ein Muster wie der Modus ponens, das angewandt werden darf, sobald Formeln der passenden Gestalt vorliegen. Beweissysteme bestehen aus einer Handvoll von ihnen, gewählt so, dass sich nur folgende Konklusionen ableiten lassen.
Aus p → q und p folgt q.
Der Modus ponens ist die Grundregel des Konditionals: Liegen ein Konditional und sein Antezedens vor, folgt das Konsequens. Seine Gültigkeit zeigt die Wahrheitstabelle – die einzige Zeile mit beiden Prämissen wahr hat auch die Konklusion wahr.
Im Rechnerp → q, p ⊨ qAus p → q und ¬q folgt ¬p.
Der Modus tollens durchläuft ein Konditional rückwärts: Scheitert das Konsequens, kann das Antezedens nicht gegolten haben. Das ist die Kontraposition bei der Arbeit und die Form jedes Arguments, das eine Hypothese an ihren Vorhersagen widerlegt.
Im Rechnerp → q, ¬q ⊨ ¬pAus p → q und q → r folgt p → r.
Der hypothetische Syllogismus verkettet Konditionale, was lange Ableitungen erst möglich macht: Jedes Glied trägt das Argument einen Schritt weiter, ohne dass eine Prämisse behauptet würde.
Im Rechnerp → q, q → r ⊨ p → rAus p ∨ q und ¬p folgt q.
Der disjunktive Syllogismus streicht die ausgeschlossene Möglichkeit: Gilt eine von zwei Alternativen und die erste nicht, muss die zweite gelten. Das ist die Regel hinter dem Ausschlussverfahren.
Im Rechnerp ∨ q, ¬p ⊨ qEine Konklusion Schritt für Schritt mit Schlussregeln beweisen.
Das natürliche Schließen leitet eine Konklusion aus Prämissen mit Einführungs- und Beseitigungsregeln für jeden Junktor ab und erlaubt vorübergehende Annahmen, die später wieder getilgt werden. Es beweist, was eine Wahrheitstabelle prüft, ohne jede Zeile durchzugehen.
Das Gegenteil annehmen, einen Widerspruch ableiten, das Ursprüngliche schließen.
Um φ zu beweisen, nimmt man ¬φ an und leitet etwas der Form ψ ∧ ¬ψ ab. Da keine Interpretation einen Widerspruch wahr macht, kann die Annahme nicht gelten, und φ folgt. So laufen Beweise der Irrationalität und der Unendlichkeit gewöhnlich ab.
Im Rechnerp ∧ ¬pDer ungültige Schritt von p → q und q zu p.
Ein wahres Konsequens begründet das Antezedens nicht: Es kann etwas anderes herbeigeführt haben. Der Rechner zeigt das Gegenmodell – p falsch, q wahr – und damit genau die Zeile, die dies vom Modus ponens trennt.
Im Rechnerp → q, q ⊨ pDer ungültige Schritt von p → q und ¬p zu ¬q.
Ein Konditional sagt nichts darüber, was geschieht, wenn sein Antezedens scheitert; das Antezedens auszuschließen lässt das Konsequens also offen. Das Gegenmodell ist die Zeile, in der p falsch und q wahr ist.
Im Rechnerp → q, ¬p ⊨ ¬qLogik, die in die Aussagen hineinsieht – auf Gegenstände und Eigenschaften.
Die Prädikatenlogik fügt Prädikate, Terme und Quantoren hinzu, sodass „jede Primzahl größer als zwei ist ungerade“ zu einer Formel wird statt zu einem einzelnen Buchstaben. Sie ist ausdrucksstärker als die Aussagenlogik, und keine Wahrheitstabelle kann sie entscheiden.
Ein Symbol dafür, auf wie viele Gegenstände ein Prädikat zutrifft.
Die beiden klassischen Quantoren sind ∀ (alle) und ∃ (mindestens einer), und jeder ist die Negation des anderen mit negiertem Rumpf. Die Variable, die ein Quantor bindet, unterscheidet die Prädikatenlogik von der Aussagenlogik.
∀x φ: φ trifft auf jeden Gegenstand des Bereichs zu.
Eine Allaussage wird durch ein einziges Gegenbeispiel widerlegt und gilt über einem leeren Bereich leer. ∀x φ ist äquivalent zu ¬∃x ¬φ – das Quantoren-Gegenstück zu den De-Morgan-Gesetzen.
∃x φ: φ trifft auf mindestens einen Gegenstand des Bereichs zu.
Eine Existenzaussage wird durch einen einzigen Zeugen belegt. ∃x φ ist äquivalent zu ¬∀x ¬φ, sodass sich jeder Quantor aus dem anderen und der Negation definieren lässt.
Logik erweitert um „notwendigerweise“ (□) und „möglicherweise“ (◇).
Die Modallogik wertet Formeln in möglichen Welten statt in einer einzigen Interpretation aus: □φ gilt, wenn φ in jeder erreichbaren Welt gilt, ◇φ, wenn es in einer gilt. Verschiedene Auffassungen von „erreichbar“ ergeben die verschiedenen Modalsysteme.
