Formelsammlung Logik

Dies ist eine Formelsammlung zum mathematischen Teilgebiet der Logik.

Aussagenlogik

Logische Werte:

  • wahr (true) 1
  • falsch (false) 0

Erweiterte Logik:

Aussagen können durch logische Operatoren, auch Junktoren genannt, verknüpft werden. Die üblichen Junktoren sind:

NameSymbolsprachliche UmschreibungOperationDefinition
NegatornichtNegationDie Negation eines logischen Werts ist genau dann wahr, wenn der Wert falsch ist.
KonjunktorundKonjunktionDie Konjunktion von zwei Werten ist genau dann wahr, wenn beide Werte wahr sind.
DisjunktoroderDisjunktionDie 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

Namesprachliche UmschreibungDarstellungWahrheitstabelleLogik­gatter
durch Negator, Konjunktor und Disjunktordurch andere JunktorenA=1A=0
B=1B=0B=1B=0
KonjunktionA und B1000AND
Exklusion, konträrer Gegensatznicht zugleich A und B0111NAND
DisjunktionA oder B (oder beide)1110OR
Nihilition, Rejektionweder A noch B0001NOR
Kontravalenz, kontradiktorischer Gegensatzentweder A oder B0110XOR
Bikonditional, Bisubjunktion, materiale Äquivalenznur wenn A dann B, genau dann B wenn A1001XNOR
Konditional, Subjunktion, materiale ImplikationImplikationwenn A dann B1011
Replikationwenn B dann A1101
InhibitionPostsektionA und nicht B0100
PräsektionB und nicht A0010

Logische Grundgesetze

Gesetz der doppelten Negation
Kommutativgesetze
Assoziativgesetze
Distributivgesetze
Idempotenz
Gesetze der Negation (Tautologie / Kontradiktion)
Absorptionsgesetze
Neutralität
De Morgansche Gesetze

Schlussregeln

Modus ponens
Modus tollens
Hypothetischer Syllogismus
Disjunktiver Syllogismus

Prädikatenlogik

Quantoren

p ist Platzhalter für eine prädikatenlogische Aussageform.

Pränexform

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

Quasiordnung

ist im Folgenden eine Quasiordnung zwischen Aussagen.

Konjunktion

und werden durch folgende Regeln definiert.

Disjunktion

und werden durch folgende Regeln definiert.

Heyting-Implikation und -Negation

wird durch die Regel

definiert, und per .

Es gelten

  • ,
  • und
  • .

Ko-Heyting-Implikation und -Negation

Dual zu und sind und .

,

.

Es gelten

  • und
  • .

Beziehung zwischen den Negationen

Es gilt immer . Gilt auch , erhält man klassische Logik.

Quantoren

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.

.