Wahrheitsbelegungen/Endlich/Auswertung/Aufgabe/Lösung

${}\Psi$ ist nicht injektiv, da beispielsweise ${}p\wedge p$ und ${}p\rightarrow p$ Tautologien sind und daher beide auf die konstante Abbildung geschickt werden, die jeder Belegung den Wert ${}1$ zuordnet.
Es sei ${}W\subseteq V$ eine Teilmenge. Es gibt die natürliche Abbildung
$\operatorname {Bel} \,{\left(V\right)}\longrightarrow \operatorname {Bel} \,{\left(W\right)},\,\lambda \longmapsto \lambda {|}_{W},$

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

$\Phi _{W}\colon \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}\longrightarrow \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)},\,\varphi \longmapsto {\left(\lambda \mapsto \varphi {\left(\lambda {|}_{W}\right)}\right)},$

eine Abbildung festgelegt. Diese ist injektiv: wenn zwei Abbildungen ${}\varphi ,\theta \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}$ verschieden sind, so gibt es eine Belegung ${}\lambda \in \operatorname {Bel} \,{\left(W\right)}$ mit ${}\varphi (\lambda )\neq \theta (\lambda )$ . Dann gilt dies auch für eine Fortsetzung ${}{\tilde {\lambda }}$ von ${}\lambda$ auf ganz ${}V$ , und somit sind die Bilder von ${}\varphi$ und von ${}\theta$ in ${}\operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$ verschieden.
Es sei ${}p\in W$ . Dann ist für jede Belegung ${}\lambda \in \operatorname {Bel} \,{\left(V\right)}$
${}\Phi _{W}(\operatorname {ev} _{p})(\lambda )=\operatorname {ev} _{p}(\lambda {|}_{W})=\lambda {|}_{W}(p)=\lambda (p)=\operatorname {ev} _{p}(\lambda )\,,$

also ist

${}\Phi _{W}(\operatorname {ev} _{p})=\operatorname {ev} _{p}\,.$

Für ${}\varphi \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}$ ist

${}{\begin{aligned}\Phi _{W}(\tau \circ \varphi )(\lambda )&=(\tau \circ \varphi )(\lambda {|}_{W})\\&=\tau (\varphi (\lambda {|}_{W}))\\&=\tau (\Phi _{W}(\varphi )(\lambda ))\\&=(\tau \circ \Phi _{W})(\varphi )(\lambda ).\end{aligned}}$

Für ${}\varphi ,\theta \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}$ ist

${}{\begin{aligned}{\max {\left(\Phi _{W}(\varphi ),\Phi _{W}(\theta )\right)}}(\lambda )&={\max {\left(\Phi _{W}(\varphi )(\lambda ),\Phi _{W}(\theta )(\lambda )\right)}}\\&={\max {\left(\varphi (\lambda {|}_{W}),\theta (\lambda {|}_{W})\right)}}\\&={\max {\left(\varphi ,\theta \right)}}(\lambda {|}_{W})\\&=\Phi _{W}{\left({\max {\left(\varphi ,\theta \right)}}\right)}(\lambda )\end{aligned}}$

und ebenso für das Minimum.
Wir betrachten die Abbildung ${}\psi \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$ , die die konstante Nullbelegung auf ${}0$ und jede andere Belegung auf ${}1$ abbildet. Wir müssen zeigen, dass diese Abbildung nicht von einer Abbildung aus ${}\operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}$ zu einer endlichen Teilmenge ${}W\subseteq V$ herrührt. Es sei also ${}W\subseteq V$ endlich gegeben. Da ${}V$ unendlich ist, gibt es ein ${}p\in V$ , ${}p\notin W$ . Es sei ${}\lambda$ die Belegung auf ${}V$ , die auf der Teilmenge ${}W$ den Wert ${}0$ hat und an ${}p$ den Wert ${}1$ (und an den anderen Variablen einen beliebigen Wert) und ${}\lambda _{0}$ die konstante Nullbewertung auf ${}V$ . Dann ist ${}\psi (\lambda )=1$ und ${}\psi (\lambda _{0})=0$ . Wegen
${}\lambda {|}_{W}=\lambda _{0}{|}_{W}=0\,$

besitzen aber die beiden auf ${}W$ eingeschränkten Belegungen unter jedem ${}\varphi \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}$ den gleichen Wert und somit ist

${}\psi \neq \varphi \,.$
Es sei ${}V$ endlich. Die Belegungen auf ${}V$ entsprechen den Teilmengen aus ${}V$ , indem man ${}\lambda$ mit ${}\lambda ^{-1}(1)$ identifiziert. Zu jeder Belegung ${}\lambda \in \operatorname {Bel} \,{\left(V\right)}$ gibt es eine Abbildung ${}\varphi _{\lambda }\in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$ , die diese Belegung auf ${}1$ und alle anderen Belegungen auf ${}0$ abbildet. Dabei gilt
${}\varphi _{\lambda }={\min {\left({\min {\left(\operatorname {ev} _{p},p\in \lambda ^{-1}(1)\right)}},{\min {\left(\tau \circ \operatorname {ev} _{p},p\in \lambda ^{-1}(0)\right)}}\right)}}\,,$

da der zweite Ausdruck für eine Belegung ${}\delta$ genau dann den Wert ${}1$ liefert, wenn für alle ${}p$ die Beziehung

${}\operatorname {ev} _{p}(\delta )=\delta (p)=1\,$

genau dann gilt, wenn ${}p\in \lambda ^{-1}(1)$ ist, was genau bei ${}\delta =\lambda$ der Fall ist. Da die ${}\operatorname {ev} _{p}$ zu ${}N$ gehören und ${}N$ unter der Verknüpfung mit ${}\tau$ und unter den Minima von (endlich vielen) Abbildungen abgeschlossen ist, gehören die ${}\varphi _{\lambda }$ zu ${}N$ .
Ein Abbildung ${}\varphi \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$ ist dadurch festgelegt, für welche Belegungen sie den Wert ${}1$ ergibt. Wenn ${}\lambda _{i}$ , ${}i\in I$ , diese Belegungen sind, so ist

${}\varphi ={\max {\left(\varphi _{\lambda _{i}},i\in I\right)}}\,.$

Da ${}M$ unter den Maxima von (endlich vielen) Abbildungen abgeschlossen ist, gehört ${}\varphi$ zu ${}N$ .
Es sei zuerst ${}\varphi \in N$ . Dann gibt es eine endliche Teilmenge ${}W\subseteq V$ mit ${}\varphi \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}$ . Nach Teil (5), angewendet auf ${}W$ , gehört ${}\varphi$ zu der in ${}\operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}$ mit den gleichen Rekursionsvorschriften erzeugten Menge ${}M_{W}$ und damit zu ${}M$ . Wenn umgekehrt ${}\varphi \in M$ ist, so wird ${}\varphi$ rekursiv erzeugt. Dabei gehen nur endlich viele Startglieder ${}\operatorname {ev} _{p_{1}},\ldots ,\operatorname {ev} _{p_{n}}$ ein. Den Konstruktionsprozess, der zu ${}\varphi$ führt, kann man daher auch über der endlichen Menge ${}W=\{p_{1},\ldots ,p_{n}\}$ durchführen, und somit ist ${}\varphi \in N$ nach Teil (3).
Den Nachweis, dass zu jedem ${}\alpha$ das Bild ${}\Psi (\alpha )$ zu ${}M$ gehört, führen wir rekursiv über den Aufbau von ${}L^{V}$ . Zu einer Aussagenvariablen ${}p\in V$ ist
${}\Psi (p)=\operatorname {ev} _{p}\in M\,.$

Zu ${}\alpha \in L^{V}$ ist

${}\Psi (\neg \alpha )=\tau \circ \Psi (\alpha )\,,$

wenn also ${}\alpha$ nach ${}M$ abgebildet wird, so auch die Negation. Wegen

${}\Psi (\alpha \wedge \beta )={\min {\left(\Psi (\alpha ),\Psi (\beta )\right)}}\,$

und

${}\Psi (\alpha \vee \beta )={\max {\left(\Psi (\alpha ),\Psi (\beta )\right)}}\,$

werden mit ${}\Psi (\alpha )$ und ${}\Psi (\beta )$ auch die Konjunktion und die Disjunktion nach ${}M$ 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 ${}\Psi$ gleich bleibt, werden mit den Bestandteilen auch ${}\alpha \rightarrow \beta$ und ${}\alpha \leftrightarrow \beta$ nach ${}M$ abgebildet.
Zum Nachweis, dass jede Abbildung ${}\varphi \in M$ zum Bild gehört, gehen wir rekursiv über den Aufbau von ${}M$ vor. Für die Evaluationen ${}\operatorname {ev} _{p}$ gilt

${}\Psi (p)=\operatorname {ev} _{p}\,.$

Wenn ${}\varphi$ zum Bild gehört, sagen wir

${}\Psi (\alpha )=\varphi \,,$

so gehört wegen

${}\Psi (\neg \alpha )=\tau \circ \varphi \,$

auch ${}\tau \circ \varphi$ zum Bild. Wenn ${}\varphi$ und ${}\theta$ zum Bild gehören, sagen wir

${}\Psi (\alpha )=\varphi \,$

und

${}\Psi (\beta )=\theta \,,$

so gehören wegen

${}\Psi (\alpha \wedge \beta )={\min {\left(\varphi ,\theta \right)}}\,$

und

${}\Psi (\alpha \vee \beta )={\max {\left(\varphi ,\theta \right)}}\,$

auch das Minimum und das Maximum dazu.

Zur gelösten Aufgabe