Wahrheitsbelegungen/Endlich/Auswertung/Aufgabe/Lösung

${\displaystyle {}W\subseteq V}$

${\displaystyle \operatorname {Bel} \,{\left(V\right)}\longrightarrow \operatorname {Bel} \,{\left(W\right)},\,\lambda \longmapsto \lambda {|}_{W},}$

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

${\displaystyle \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 ${\displaystyle {}\varphi ,\theta \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}}$ verschieden sind, so gibt es eine Belegung ${\displaystyle {}\lambda \in \operatorname {Bel} \,{\left(W\right)}}$ mit ${\displaystyle {}\varphi (\lambda )\neq \theta (\lambda )}$. Dann gilt dies auch für eine Fortsetzung ${\displaystyle {}{\tilde {\lambda }}}$ von ${\displaystyle {}\lambda }$ auf ganz ${\displaystyle {}V}$, und somit sind die Bilder von ${\displaystyle {}\varphi }$ und von ${\displaystyle {}\theta }$ in ${\displaystyle {}\operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}}$ verschieden.

${\displaystyle {}p\in W}$

${\displaystyle {}\lambda \in \operatorname {Bel} \,{\left(V\right)}}$

${\displaystyle {}\Phi _{W}(\operatorname {ev} _{p})(\lambda )=\operatorname {ev} _{p}(\lambda {|}_{W})=\lambda {|}_{W}(p)=\lambda (p)=\operatorname {ev} _{p}(\lambda )\,,}$

also ist

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

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

${\displaystyle {}{\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 ${\displaystyle {}\varphi ,\theta \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}}$ ist

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

${\displaystyle {}\psi \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}}$

${\displaystyle {}0}$

${\displaystyle {}1}$

${\displaystyle {}\operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}}$

${\displaystyle {}W\subseteq V}$

${\displaystyle {}W\subseteq V}$

${\displaystyle {}V}$

${\displaystyle {}p\in V}$

${\displaystyle {}p\notin W}$

${\displaystyle {}\lambda }$

${\displaystyle {}V}$

${\displaystyle {}W}$

${\displaystyle {}0}$

${\displaystyle {}p}$

${\displaystyle {}1}$

${\displaystyle {}\lambda _{0}}$

${\displaystyle {}V}$

${\displaystyle {}\psi (\lambda )=1}$

${\displaystyle {}\psi (\lambda _{0})=0}$

${\displaystyle {}\lambda {|}_{W}=\lambda _{0}{|}_{W}=0\,}$

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

${\displaystyle {}\psi \neq \varphi \,.}$

${\displaystyle {}V}$

${\displaystyle {}V}$

${\displaystyle {}V}$

${\displaystyle {}\lambda }$

${\displaystyle {}\lambda ^{-1}(1)}$

${\displaystyle {}\lambda \in \operatorname {Bel} \,{\left(V\right)}}$

${\displaystyle {}\varphi _{\lambda }\in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}}$

${\displaystyle {}1}$

${\displaystyle {}0}$

${\displaystyle {}\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 ${\displaystyle {}\delta }$ genau dann den Wert ${\displaystyle {}1}$ liefert, wenn für alle ${\displaystyle {}p}$ die Beziehung

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

genau dann gilt, wenn ${\displaystyle {}p\in \lambda ^{-1}(1)}$ ist, was genau bei ${\displaystyle {}\delta =\lambda }$ der Fall ist. Da die ${\displaystyle {}\operatorname {ev} _{p}}$ zu ${\displaystyle {}N}$ gehören und ${\displaystyle {}N}$ unter der Verknüpfung mit ${\displaystyle {}\tau }$ und unter den Minima von (endlich vielen) Abbildungen abgeschlossen ist, gehören die ${\displaystyle {}\varphi _{\lambda }}$ zu ${\displaystyle {}N}$.

Ein Abbildung ${\displaystyle {}\varphi \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}}$ ist dadurch festgelegt, für welche Belegungen sie den Wert ${\displaystyle {}1}$ ergibt. Wenn ${\displaystyle {}\lambda _{i}}$, ${\displaystyle {}i\in I}$, diese Belegungen sind, so ist

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

Da ${\displaystyle {}M}$ unter den Maxima von (endlich vielen) Abbildungen abgeschlossen ist, gehört ${\displaystyle {}\varphi }$ zu ${\displaystyle {}N}$.

${\displaystyle {}\alpha }$

${\displaystyle {}\Psi (\alpha )}$

${\displaystyle {}M}$

${\displaystyle {}L^{V}}$

${\displaystyle {}p\in V}$

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

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

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

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

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

und

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

werden mit ${\displaystyle {}\Psi (\alpha )}$ und ${\displaystyle {}\Psi (\beta )}$ auch die Konjunktion und die Disjunktion nach ${\displaystyle {}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 ${\displaystyle {}\Psi }$ gleich bleibt, werden mit den Bestandteilen auch ${\displaystyle {}\alpha \rightarrow \beta }$ und ${\displaystyle {}\alpha \leftrightarrow \beta }$ nach ${\displaystyle {}M}$ abgebildet.

Zum Nachweis, dass jede Abbildung ${\displaystyle {}\varphi \in M}$ zum Bild gehört, gehen wir rekursiv über den Aufbau von ${\displaystyle {}M}$ vor. Für die Evaluationen ${\displaystyle {}\operatorname {ev} _{p}}$ gilt

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

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

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

so gehört wegen

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

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

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

und

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

so gehören wegen

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

und

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

auch das Minimum und das Maximum dazu.