Wahrheitsbelegungen/Endlich/Auswertung/Aufgabe/Lösung

1. ${}\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.
2. 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.

3. 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.

4. 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 \,.$

5. 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$.

6. 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).
7. 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