Bei aussagenlogischen Formel sind aussagenlogisch indeterminiert, oder es handelt sich um Tautologien oder Kontradiktionen.
.) Tautologie – (immer wahr) wenn die Aussage unabhängig von ihren Variablen wahr ist. Z. B. (p→p)↔(¬q∨q)
.) Kontradiktion – (immer falsch) ist unabhängig von ihren Variablen falsch. Z. B. (p↔¬p)∨(r∧¬r)
.) Aussagenlogisch Indeterminiert – wenn die Aussage für mindestens eine Belegung der Variablen wahr und für mindestens eine Belegung falsch ist. Z. B. p→q∨r
Tautologien und aussagenlogisch indeterminierte Aussagen werden auch als erfüllbare Aussagen bezeichnet.
In der Aussagenlogik ist man u.a. an der Charakterisierung und Erzeugung von Tautologien interessiert.
Die Einsetzung
a[p/b] ist die Formel die aus a entsteht, wenn für jedes Vorkommen der Variable p in der Aussage a durch die Formel b eingesetzt wird.
Z. B.: a: p→q→p
b: (r∨s)
a[p/b]: (r∨s)→q→(r∨s)
Einsetzungstheorem – Ist a eine Tautologie bzw. eine Kontradiktion, dann ist es auch a[p/b].
Durch Einsetzen wird aus einer Tautologie wieder eine Tautologie, bzw. aus einer Kontradiktion eine Kontradiktion.
Ersetzung
I) Jede Formel a ist Teilformel von sich selbst.
II) Ist a eine zusammengesetzte Formel, z. B. ¬b, b∨c, b→c, usw. dann sind auch b und c Teilformeln von a.
III) Jede Teilformel einer Teilformel von a ist ebenfalls eine Teilformel von a.
Z. B.: a: p→((¬q∨r)→s)
Teilformeln:
lt I) p→((¬q∨r)→s)
lt II) p, (¬q∨r)→s
lt III) ¬q∨r, s
lt III) ¬q∨r, s
lt III) ¬q, r
lt III) q
Ersetzungen sind mehrdeutig. 2 Formeln a und b sind äquivalent oder logisch gleich, wenn die Formel a↔b eine Tautologie ist.
Es gilt das Ersetzungstheorem:
Wenn b↔c ist, dann ist a↔a[[b/c]]
Wichtige Sätze bzw. Äquivalenzen und Tautologien der Aussagenlogik
a↔a | Reflexivität der Äquivalenz |
¬(¬a)↔a | Gesetz der doppelten Verneinung (Negation) |
¬(a∧¬a) | Satz vom Widerspruch |
a ∨ a ↔ a | Idempotenz der Disjunktion |
a∨b↔b∨a | Kommutativität der Disjunktion |
a∨(b∨c)↔(a∨b)∨c | Assozativität der Disjunktion |
a∨(b∧c)↔(a∨b)∧(a∨c) | Distributivität der Disjunktion bzgl. der Konjunktion |
a∨(a∧b)↔a | Verschmelzungsgesetz (Absorptionsgesetz) |
a∧a→a bzw. a∧w↔a bzw. a∧f↔f | Idempodenz der Konjunktion |
¬(a∨b)↔(¬a∧¬b) | Gesetze von De Morgan |
a∨b↔¬a→b | |
¬(a∧b)→(¬a∨¬b) | |
a∧b→¬(a→¬b) | |
a→b↔¬a∨b | |
a→b↔¬(a∧¬b) |
a→(b→c)↔b→(a→c) | Vertauschungsgesetz für Prämissen |
(a↔b)↔(b↔a) | Kommutativgesetz der Äquivalenz |
(a↔(b↔c))↔((a↔b)↔c) | Assoziativgesetz der Äquivalenz |
(a↔b)↔(a∧b)∨(¬a∧¬b) | |
(a↔b)↔(¬a∨b)∧(a∨¬b) | |
(a↔b)↔(a→b)∧(b→a) |
Folgen die sich aus dem Ersetzungstheorem ergeben und in der Tabelle oben ersichtlich sind:
- Junktoren können durch andere ersetzt werden
- Wegen der Assoziativität von ∧,∨,↔ können Klammern weggelassen werden
- Wegen der Kommutativität von ∧,∨,↔ können Formeln vertauscht werden
Wichtige Tautologien
a→a | |
a∨¬a | tertium non datur Gesetz vom ausgeschlossenen Dritten |
a→¬¬a | |
¬¬a→a | |
a∧¬a→b | ex falso quodlibet aus Falschem folgt Beliebiges |
a∧b→a | |
a∧b→b | |
a→a∨b | Verdünnungsgesetz |
a∧(a→b)→b | Modus Ponens Abtrennungsregel |
(a→b)∧¬b→¬a | Modus Tollens (aufhebend, Widerlegung) |
(a→b)→(¬b→¬a) | Kontraposition (schwach) |
(¬a→¬b)→(b→a) | Kontraposition (stark) |
( a→b)∧(b→c)→(a→c) | Transitivitätsgesetz |
a→(b→a) | verum e quodlibet |
(a→(b→c))→((a→b)→(a→c)) | Transitivität der Implikation |
Weblinks:
Boolesche Algebra, Schaltalgebra 4 Absorptionsgesetze und Die De Morgan’sche Umwandlung
Mathe für Nicht-Freaks: Beweis: Beweismethoden Transitive Relation