Benutzer:Dirk Huenniger/var

Diese Seite ist eine Frage zu einem Skript der Fernuni Hagen. Sie erhebt nicht den Anspruch algemein verständlich oder auch nur sinnvoll zu sein.

Sei K die Menge der Variablen. Was eine Variable ist bleibt unklar scheint aber auch nicht wichtig.

Sei

$V\subset K$

V sei endlich.

Die Elemente von V werden entsprechend bezeichnet als

$X_{i}|i\in \{1..n\}$

Sei:

$H=\{0,1\}$

Eine Einsetzung $\phi$ ist eine Abbildung.

$\phi :V\rightarrow H$

Sei P die Menge aller Einsetzungen.

Sei $a_{\phi }$ ein n-Tupel mit Elementen aus H. Dessen Komponenten seien wie folgt definiert.

$(a_{\phi })_{i}=\phi (X_{i})|i\in \{1..n\}$

Die Abbildung die einer Einsetzung einen solchen n-Tupel zuordnet sei.

$\Psi :P\rightarrow H^{n},\phi \mapsto a_{\phi }$

Es scheint mir offensichtlich, dass diese Abbildung bijektiv ist.

Im Alphabet gibt es nur Funktionssymbole $f_{i}$. Diese Stelligkeit der i-ten Funktion sei. s(i). Für jedes Funtionssymbol muss man eine Funktion definieren:

${\tilde {f}}_{i}:H^{n}\rightarrow H$

Hierbei habe ich eine Tilde über das $f_{i}$ geschrieben um den Unterschied zwischen der Funktion und dem Funktionssymbol zu definieren. Will man nun den Definitionsbereicht der Einsetzungen $\phi$ auf die Menge der erweiterten Boolschen Ausdrücke ausdehnen. So muss man unter anderem erklären worauf

$f_{i}(X_{k_{1}},...,X_{k_{s}(i)})$

abgebildet werden soll. Da man glücklicherweise ${\tilde {f}}_{i}$ schon definiert hat. Kann man einfach

$\phi (f_{i}(X_{k_{1}},...,X_{k_{s}(i)}))={\tilde {f}}_{i}(\phi (X_{k_{1}}),...,\phi (X_{k_{s}(i)}))$

setzen.

Sei e ein beliebiger aber im folgenden fester erweiterter Boolscher Ausdruck. Nun wollen wir dem Alphabet ein neues Funktionssymbol f hinzufügen und die zugehörige Funktion ${\tilde {f}}$ definieren. Das soll nach Möglichkeit so geschehen das für unser neu definiertes f gilt: (Gleichung 1)

$\phi (f(X_{1},...,X_{n}))=\phi (e)|\forall \phi \in P$

Ferner wollen wir zeigen dass nur diese eine Wahl von ${\tilde {f}}$ möglich ist.

Wir definieren nun ${\tilde {f}}$ für jedes $a\in H^{n}$ einzeln. Sei also $a\in H^{n}$ beliebig. Dann finden wir:

$\phi _{a}=\Psi ^{-1}(a)$

Dann definieren wir.

${\tilde {f}}(a):=\phi _{a}(e)$

Damit haben wir ${\tilde {f}}$ vollständig definiert. Als nächstes wollen wir überprüfen ob (Gleichung 1) für f gilt. Sei also $\phi \in P$ beliebig. Dann finden wir:

$b=\Psi (\phi )$

Nun rechnen wir

$\phi (f(X_{1},...,X_{n}))={\tilde {f}}(\phi (X_{1}),...,\phi (X_{s(i)}))={\tilde {f}}(b_{1},...,b_{n})={\tilde {f}}(b)=\Psi ^{-1}(b)(e)=(\Psi ^{-1}(\Psi (\phi )))(e)=\phi (e)$

Womit gezeigt ist das (Gleichung 1) erfüllt ist.

Es bleibt noch zu zeigen, dass ${\tilde {f}}$ eindeutig ist. Dazu fügen wir dem Alphabet ein Symbol g hinzu und nehmen an jemand habe eine zugerhörige Funktion ${\tilde {g}}$ definiert, die jedoch folgende Gleichung erfüllt:

$\phi (g(X_{1},...,X_{n}))=\phi (e)|\forall \phi \in P$

Wir zeigen dies für jedes $a\in H^{n}$ einzeln. Sei also $a\in H^{n}$ beliebig. Dann finden wir:

$\phi _{a}=\Psi ^{-1}(a)$

Offenbar gilt:

${\tilde {g}}(a)={\tilde {g}}(\phi _{a}(X_{1}),...,\phi _{a}(X_{s(i)}))=\phi _{a}(g(X_{1},...,X_{n}))=\phi _{a}(e)={\tilde {f}}(a)$

Damit haben wir gezeigt, dass f und g für alle Werte a aus ihrem Definitionsbereich identische Funktionswerte annehmen. Daher sind die Funktionen gleich. Damit ist die Behauptung bewiesen.