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]]
Ein- und Ersetzung, wichtige Äquivalenzen und Tautologien weiterlesen →