Aussagenvariablen/Gleichung mit Variablen/Einbettung/Aufgabe/Lösung


  1. Wir definieren die Abbildung rekursiv über den Aufbau von . Für eine Aussagenvariable setzen wir

    Für

    setzen wir

    und für

    setzen wir

    und entsprechend für .

  2. Wir beweisen die Injektivität in der Form, dass sich aus

    die Verschiedenheit

    ergibt, und zwar durch Induktion über den Aufbau von (simultan für alle ).

    Für

    ist entweder eine andere Aussagenvariable, sagen wir mit oder ein Ausdruck, der zumindest einen aussagenlogischen Junktor enthält. Im ersten Fall ist

    und im zweiten Fall enthält mindestens einen Junktor und ist deshalb von verschieden.

    Es sei nun

    und dies sei von verschieden. Wenn keine Negation ist, so ist auch keine Negation und damit von verschieden. Wenn hingegen eine Negation ist, so ist und wegen der Verschiedenheit ist . Nach Induktionsvoraussetzung ist

    und dies überträgt sich auf die negierten Ausdrücke.

    Es sei nun

    und dies sei von verschieden. Wenn kein konjugierter Ausdruck ist, so ist auch kein konjugierter Ausdruck und damit ist . Wenn hingegen ebenfalls ein konjugierter Ausdruck ist, so ist und wegen der Verschiedenheit ist oder . Sagen wir der erste Fall liegt vor. Nach Induktionsvoraussetzung ist dann

    und dies überträgt sich auf die konjugierten Ausdrücke.

  3. Die Abbildung ist nicht surjektiv, da der Ausdruck nicht zum Bild gehört, da jedes mindestens eine Aussagenvariable und somit mindestens eine Variable enthält.
  4. Es gelte zunächst

    Dann gibt es eine Ableitung im Aussagenkalkül für diesen Ausdruck. Diese Ableitung beruht allein auf aussagenlogischen Grundtautologien und dem Modus ponens. Wenn man in dieser Ableitung überall die Aussagenvariablen durch ersetzt, so werden aus den aussagenlogischen Grundtautologien prädikatenlogische Grundtautologien und der Modus ponens bleibt erhalten. Man erhält also durch diese Ersetzung eine prädikatenlogische Ableitung für und somit ist .

    Wenn hingegen

    gilt, so ist nach dem Vollständigkeitssatz der Aussagenlogik nicht allgemeingültig. Es gibt also eine Wahrheitsbelegung für die Aussagenvariablen derart, dass unter der zugehörigen (aussagenlogischen) Interpretation den Wahrheitswert bekommt. Es sei nun eine zweielementige Menge. Wir definieren eine -Interpretation auf durch

    und

    Mit dieser Festlegung ist genau dann, wenn ist. Da die aussagenlogischen Junktoren unter und gleichermaßen interpretiert werden, ist wegen auch . Daher ist nicht allgemeingültig und kann wegen der Korrektheit des Ableitungkalküls für die Prädikatenlogik auch nicht ableitbar sein. Also .