Ein- und Ersetzung, wichtige Äquivalenzen und Tautologien

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

(770)

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.