Formelsammlung Logik
Dies ist eine Formelsammlung zum mathematischen Teilgebiet der Logik.
Aussagenlogik Bearbeiten
Logische Werte:
- wahr (true) 1
- falsch (false) 0
Erweiterte Logik:
- unbestimmt (Don’t-Care) X
Aussagen können durch logische Operatoren, auch Junktoren genannt, verknüpft werden. Die üblichen Junktoren sind:
Name | Symbol | sprachliche Umschreibung | Operation | Definition |
---|---|---|---|---|
Negator | nicht | Negation | Die Negation eines logischen Werts ist genau dann wahr, wenn der Wert falsch ist. | |
Konjunktor | und | Konjunktion | Die Konjunktion von zwei Werten ist genau dann wahr, wenn beide Werte wahr sind. | |
Disjunktor | oder | Disjunktion | Die Disjunktion von zwei Werten ist genau dann wahr, wenn mindestens ein Wert wahr ist. |
Um die Symbole des Konjunktors und des Disjunktors leicht auseinanderhalten zu können, gibt es die Eselsbrücke mit den drei O: „Oder ist Oben Offen.“ Alternativ merkt man sich "And" (Englisch) für und, sowie "vel" (Latein) für oder.
Verknüpfungen zweier Aussagen Bearbeiten
Name | sprachliche Umschreibung | Darstellung | Wahrheitstabelle | Logikgatter | |||||
---|---|---|---|---|---|---|---|---|---|
durch Negator, Konjunktor und Disjunktor | durch andere Junktoren | A=1 | A=0 | ||||||
B=1 | B=0 | B=1 | B=0 | ||||||
Konjunktion | A und B | 1 | 0 | 0 | 0 | AND | |||
Exklusion, konträrer Gegensatz | nicht zugleich A und B | 0 | 1 | 1 | 1 | NAND | |||
Disjunktion | A oder B (oder beide) | 1 | 1 | 1 | 0 | OR | |||
Nihilition, Rejektion | weder A noch B | 0 | 0 | 0 | 1 | NOR | |||
Kontravalenz, kontradiktorischer Gegensatz | entweder A oder B | 0 | 1 | 1 | 0 | XOR | |||
Bikonditional, Bisubjunktion, materiale Äquivalenz | nur wenn A dann B, genau dann B wenn A | 1 | 0 | 0 | 1 | XNOR | |||
Konditional, Subjunktion, materiale Implikation | Implikation | wenn A dann B | 1 | 0 | 1 | 1 | |||
Replikation | wenn B dann A | 1 | 1 | 0 | 1 | ||||
Inhibition | Postsektion | A und nicht B | 0 | 1 | 0 | 0 | |||
Präsektion | B und nicht A | 0 | 0 | 1 | 0 |
Logische Grundgesetze Bearbeiten
Gesetz der doppelten Negation | ||
Kommutativgesetze | ||
Assoziativgesetze | ||
Distributivgesetze | ||
Idempotenz | ||
Gesetze der Negation (Tautologie / Kontradiktion) | ||
Absorptionsgesetze | ||
Neutralität | ||
De Morgansche Gesetze |
Schlussregeln Bearbeiten
Modus ponens | |
Modus tollens | |
Hypothetischer Syllogismus | |
Disjunktiver Syllogismus |
Prädikatenlogik Bearbeiten
Quantoren Bearbeiten
p ist Platzhalter für eine prädikatenlogische Aussageform.
Pränexform Bearbeiten
und sind im Folgenden Platzhalter für prädikatenlogische Aussageformen. Die Umformungen in Zeilen 1, 2, 4 und 5 der Tabelle gelten nur, wenn x innerhalb von nicht frei vorkommt, d. h. wenn durch das Verschieben des Quantors keine Variablenbindung entsteht (bzw. aufgelöst wird), die zuvor nicht da war (bzw. da war). Die letzte Umformung gilt nur, wenn x innerhalb von nicht frei vorkommt, d. h. wenn durch das Verschieben des Quantors keine Variablenbindung entsteht (bzw. aufgelöst wird), die zuvor nicht da war (bzw. da war).
Unproblematisch ist das, wenn die Variablen in den Aussageformen und jeweils unterschiedlich benannt sind.
= , | = ; |
= , | = . |
= | = . |
= , | = . |
= , | = . |
Minimale Schlussregeln Bearbeiten
Quasiordnung Bearbeiten
ist im Folgenden eine Quasiordnung zwischen Aussagen.
Konjunktion Bearbeiten
und werden durch folgende Regeln definiert.
Disjunktion Bearbeiten
und werden durch folgende Regeln definiert.
Heyting-Implikation und -Negation Bearbeiten
wird durch die Regel
definiert, und per .
Es gelten
- ,
- und
- .
Ko-Heyting-Implikation und -Negation Bearbeiten
Dual zu und sind und .
,
.
Es gelten
- und
- .
Beziehung zwischen den Negationen Bearbeiten
Es gilt immer . Gilt auch , erhält man klassische Logik.
Quantoren Bearbeiten
Es sei eine Abbildung. Eine beliebige Aussage über Elemente von kann per in eine Aussage über -Elemente transformiert werden. Notation: . ist ein Funktor. Seine rechts- und linksadjungierten sind, respektive, All- und Existenzquantor. D.h.
.