Formelsammlung Logik

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Dies ist eine Formelsammlung zum mathematischen Teilgebiet der Logik.

Aussagenlogik[Bearbeiten | Quelltext bearbeiten]

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:

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.“

Verknüpfungen zweier Aussagen[Bearbeiten | Quelltext bearbeiten]

Name sprachliche Umschreibung Darstellung Wahrheitstabelle Logik­gatter
durch Negator, Konjunktor und Disjunktor durch andere Junktoren A=1 A=0
B=1 B=0 B=1 B=0
Konjunktion A und B A ∧ B 1 0 0 0 AND
Exklusion, konträrer Gegensatz nicht zugleich A und B ¬(A ∧ B) = ¬A ∨ ¬B A|B = (A → ¬B) = (B → ¬A) 0 1 1 1 NAND
Disjunktion A oder B (oder beide) A ∨ B (¬A → B) = (¬B → A) 1 1 1 0 OR
Nihilition, Rejektion weder A noch B ¬(A ∨ B) = ¬A ∧ ¬B 0 0 0 1 NOR
Kontravalenz, kontradiktorischer Gegensatz entweder A oder B (A ∧ ¬B) ∨ (¬A ∧ B) = (A ∨ B) ∧ (¬A ∨ ¬B) A ⊻ B = ¬(A ↔ B) 0 1 1 0 XOR
Bikonditional, Bisubjunktion, materiale Äquivalenz nur wenn A dann B, genau dann B wenn A (A ∧ B) ∨ (¬A ∧ ¬B) = (A ∨ ¬B) ∧ (¬A ∨ B) (A ↔ B) = (A → B) ∧ (B → A) 1 0 0 1 XNOR
Konditional, Subjunktion, materiale Implikation Implikation wenn A dann B ¬A ∨ B (A → B) = (¬B → ¬A) 1 0 1 1
Replikation wenn B dann A ¬B ∨ A (B → A) = (¬A → ¬B) 1 1 0 1
Inhibition Postsektion A und nicht B A ∧ ¬B ¬(A → B) 0 1 0 0
Präsektion B und nicht A B ∧ ¬ A ¬(B → A) 0 0 1 0

Logische Grundgesetze[Bearbeiten | Quelltext bearbeiten]

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

Schlussregeln[Bearbeiten | Quelltext bearbeiten]

Modus Ponens
Modus tollens
Hypothetischer Syllogismus
Disjunktiver Syllogismus

Prädikatenlogik[Bearbeiten | Quelltext bearbeiten]

Quantoren[Bearbeiten | Quelltext bearbeiten]

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

Pränexform[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]

Quasiordnung[Bearbeiten | Quelltext bearbeiten]

ist im Folgenden eine Quasiordnung zwischen Aussagen.

Konjunktion[Bearbeiten | Quelltext bearbeiten]

und werden durch folgende Regeln definiert.

Disjunktion[Bearbeiten | Quelltext bearbeiten]

und werden durch folgende Regeln definiert.

Heyting-Implikation und -Negation[Bearbeiten | Quelltext bearbeiten]

wird durch die Regel

definiert, und per .

Es gelten

  • ,
  • und
  • .

Ko-Heyting-Implikation und -Negation[Bearbeiten | Quelltext bearbeiten]

Dual zu und sind und .

,

.

Es gelten

  • und
  • .

Beziehung zwischen den Negationen[Bearbeiten | Quelltext bearbeiten]

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

Quantoren[Bearbeiten | Quelltext 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.

.