0 Daumen
490 Aufrufe

Monotone Boolesche Funktionen


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

 

Eine Lösung wäre gut. Eine Lösung mit einer Erklärung dazu wäre aber sehr viel hilfreicher!

 

Vielen Dank im Vorraus!

Gefragt von
Hast du eine Definition für "monotone Boolesche Funktion" und für "Signatur"?
Gerade gefunden. Hier ist das Skript der FU Berlin mit teilweisen Definitionen dazu: http://www.inf.fu-berlin.de/lehre/WS10/mafi1/u3.pdf

1 Antwort

0 Daumen

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.

Beantwortet von 6,8 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...