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