Zeigen Sie durch Terminduktion, dass jede Formel über der Signatur {0,1, ˄, ˅} monoton ist.

Question

Zeigen Sie mit Terminduktion, dass jede Formel über der Signatur {0,1, ˄, ˅} eine monotone Boolesche Funktion ist.

Definition der monoton booleschen Funktion:

1) Auf der Menge \( n \) -Tupel \( \left(b_{1}, \ldots, b_{n}\right) \in \mathbb{B}^{n} \) führen wir eine Ordnungsrelation \( \preceq \) ein: \( \left(b_{1}, \ldots, b_{n}\right) \preceq\left(c_{1}, \ldots, c_{n}\right) \quad \) genau dann, wenn \( b_{i} \leq c_{i} \) für alle \( i=1, \ldots, n, \) wobei sich das \( \leq \) von den Zahlen auf die Wahrheitswerte überträgt.

2) Man nennt eine Boolesche Funktion \( f: \mathbb{B}^{n} \longrightarrow \mathbb{B} \) monoton, wenn für zwei beliebige Tupel aus der Bedingung \( \left(b_{1}, \ldots, b_{n}\right) \preceq\left(c_{1}, \ldots, c_{n}\right) \) folgt, dass \( f\left(b_{1}, \ldots, b_{n}\right) \leq \) \( f\left(c_{1}, \ldots, c_{n}\right) \)

Quelle FU Berlin: http://www.inf.fu-berlin.de/lehre/WS10/mafi1/u3.pdf

Eine Lösung mit einer Erklärung wäre hilfreich.

Answer 1

Hast Du das Beweisprinzip der Terminduktion verstanden? Hier gibt es eine ausführliche Erklärung: http://www.mathematik.tu-darmstadt.de/~haller/Skripten/M2InfSkript16.pdf (S. 129).

Die Aufgabe wurde hier auch schon mal von StrgAltEntf gelöst:

Der komplette Induktionsschritt:

Sei \( \phi(x_1,...,x_n,x_{n+1}) \) monoton.

Zeige:

$$ \phi(x_1,...,x_n,x_{n+1}) = (x_{n+1}\wedge\phi(x_1,...,x_n,1)) \vee \phi(x_1,...,x_n,0) $$ (*)

Mit der IV, angewendet auf $$ \psi_0(x_1,...,x_n)=\phi(x_1,...,x_n,0) $$ und $$ \psi_1(x_1,...,x_n)=\phi(x_1,...,x_n,1) $$ sind wir dann fertig.

Beachte hierbei, dass \( \psi_0(x_1,...,x_n) \) und \( \psi_1(x_1,...,x_n) \) ebenfalls monoton sind.

Um (*) zu zeigen, beachte, dass

$$ \phi(x_1,...,x_n,x_{n+1})=(x_{n+1}\wedge\phi(x_1,...,x_n,1)) \vee (-x_{n+1}\wedge\phi(x_1,...,x_n,0)) $$ (**)

Fall 1: $$ x_{n+1} = 0 $$

Dann ist wegen (**) \( \phi(x_1,...,x_n,x_{n+1})=\phi(x_1,...,x_n,0)=(x_{n+1}\wedge\phi(x_1,...,x_n,1)) \vee \phi(x_1,...,x_n,0) \), also gilt (*).

Fall 2: $$ x_{n+1} = 1x_{n+1} = 1 $$ $$ x_{n+1} = 1 $$

Dann ist wegen (**) $$ \phi(x_1,...,x_n,x_{n+1})=\phi(x_1,...,x_n,1) $$

Zeige nun, dass

$$ \phi(x_1,...,x_n,1)= \phi(x_1,...,x_n,1)\vee\phi(x_1,...,x_n,0) $$ (***).

Dann gilt nämlich (*), und wir sind fertig.

(***) folgt aber aus der Monotonie von \( \phi \):

$$ \phi(x_1,...,x_n,1)=\phi(x_1,...,x_n,1)\vee \phi(x_1,...,x_n,1) \geq \phi(x_1,...,x_n,1)\vee\phi(x_1,...,x_n,0)\geq \phi(x_1,...,x_n,1) $$

Bei Bedarf gerne nachfragen.