Wahrheitsbelegungen/Endlich/Auswertung/Aufgabe/Lösung

Aus Wikiversity
Zur Navigation springen Zur Suche springen
  1. ist nicht injektiv, da beispielsweise und Tautologien sind und daher beide auf die konstante Abbildung geschickt werden, die jeder Belegung den Wert zuordnet.
  2. Es sei eine Teilmenge. Es gibt die natürliche Abbildung

    die jeder Belegung auf die eingeschränkte Belegung auf der Teilmenge zuordnet. Diese Abbildung ist surjektiv, da man jede Belegung auf zu einer Belegung auf fortsetzen kann, indem man auf willkürlich Wahrheitswerte festlegt (beispielsweise konstant gleich ). Mit Hilfe dieser Abbildung ist durch

    eine Abbildung festgelegt. Diese ist injektiv: wenn zwei Abbildungen verschieden sind, so gibt es eine Belegung mit . Dann gilt dies auch für eine Fortsetzung von auf ganz , und somit sind die Bilder von und von in verschieden.

  3. Sei . Dann ist für jede Belegung

    also ist

    Für ist

    Für ist

    und ebenso für das Minimum.

  4. Wir betrachten die Abbildung , die die konstante Nullbelegung auf und jede andere Belegung auf abbildet. Wir müssen zeigen, dass diese Abbildung nicht von einer Abbildung aus zu einer endlichen Teilmenge herrührt. Sei also endlich gegeben. Da unendlich ist, gibt es ein , . Es sei die Belegung auf , die auf der Teilmenge den Wert hat und an den Wert (und an den anderen Variablen einen beliebigen Wert) und die konstante Nullbewertung auf . Dann ist und . Wegen

    besitzen aber die beiden auf eingeschränkten Belegungen unter jedem den gleichen Wert und somit ist

  5. Es sei endlich. Die Belegungen auf entsprechen den Teilmengen aus , indem man mit identifiziert. Zu jeder Belegung gibt es eine Abbildung , die diese Belegung auf und alle anderen Belegungen auf abbildet. Dabei gilt

    da der zweite Ausdruck für eine Belegung genau dann den Wert liefert, wenn für alle die Beziehung

    genau dann gilt, wenn ist, was genau bei der Fall ist. Da die zu gehören und unter der Verknüpfung mit und unter den Minima von (endlich vielen) Abbildungen abgeschlossen ist, gehören die zu .

    Ein Abbildung ist dadurch festgelegt, für welche Belegungen sie den Wert ergibt. Wenn , , diese Belegungen sind, so ist

    Da unter den Maxima von (endlich vielen) Abbildungen abgeschlossen ist, gehört zu .

  6. Sei zuerst . Dann gibt es eine endliche Teilmenge mit . Nach Teil (5), angewendet auf , gehört zu der in mit den gleichen Rekursionsvorschriften erzeugten Menge und damit zu . Wenn umgekehrt ist, so wird rekursiv erzeugt. Dabei gehen nur endlich viele Startglieder ein. Den Konstruktionsprozess, der zu führt, kann man daher auch über der endlichen Menge durchführen, und somit ist nach Teil (3).
  7. Den Nachweis, dass zu jedem das Bild zu gehört, führen wir rekursiv über den Aufbau von . Zu einer Aussagenvariablen ist

    Zu ist

    wenn also nach abgebildet wird, so auch die Negation. Wegen

    und

    werden mit und auch die Konjunktion und die Disjunktion nach abgebildet. Da man die Implikation und die Äquivalenz durch die anderen Junktoren ausdrücken kann, und für semantisch äquivalente Ausdrücke der Wert unter gleich bleibt, werden mit den Bestandteilen auch und nach abgebildet.

    Zum Nachweis, dass jede Abbildung zum Bild gehört, gehen wir rekursiv über den Aufbau von vor. Für die Evaluationen gilt

    Wenn zum Bild gehört, sagen wir

    so gehört wegen

    auch zum Bild. Wenn und zum Bild gehören, sagen wir

    und

    so gehören wegen

    und

    auch das Minimum und das Maximum dazu.

Zur gelösten Aufgabe