n-stellige Boolsche Funktion

06.12.2005, 19:36

thx

n-stellige Boolsche Funktion

Hi,

ich habe ein kleines Problem bei einer Aufgabe, sollte eigentlich ganz einfach sein, jedoch komme ich nicht weiter. Es geht um die n-Stelligkeit einer Boolschen Funktion. Für jedes $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$ mit $\begin{eqnarray*} n \geq 1 \end{eqnarray*}$ gibt es $\begin{eqnarray*} 2^{2^{n}} \end{eqnarray*}$ verschiedene totale n-stellige Funktionen aus $\begin{eqnarray*} \{ 0,1\}^{n} \end{eqnarray*}$ nach $\begin{eqnarray*} \{ 0,1\} \end{eqnarray*}$ .
Das soll man mit vollst. Induktion beweisen.

Ind.anfang: n = 1 --> $\begin{eqnarray*} p(1) = 2^{2^{1}} = 4 \end{eqnarray*}$
Ind.vor.: Aussage gilt für $\begin{eqnarray*} p(n) = 2^{2^{n}} \end{eqnarray*}$
Ind.beh.: wenn Ind.vor. gilt, dann auch $\begin{eqnarray*} p(n+1) = 2^{2^{n+1}} \end{eqnarray*}$
Beweis:
$\begin{eqnarray*} p(n+1) = 2^{2^{n+1}} \end{eqnarray*}$
= $\begin{eqnarray*} 2^{2^2*{n}} \end{eqnarray*}$

Und hier komme ich nicht weiter. Ich muss nur noch zeigen das die Vor. erfüllt ist, aber wie bekomme ich das separat aus p(n+1) heraus, also das irgendwo $\begin{eqnarray*} )2^{2^{n}} \end{eqnarray*}$ auftaucht ?

Vielen Dank schonmal im Voraus smile

06.12.2005, 23:17

irre.flexiv

Auf diesen Beitrag antworten »

Zitat:

$\begin{eqnarray*} p(n+1) = 2^{2^{n+1}}= 2^{2^2*{n}} \end{eqnarray*}$

Falsch.

$\begin{eqnarray*} p(n+1) = 2^{2^{n+1}} = 2^{2^n + 2^n} =2^{2^n} \cdot 2^{2^n} = p(n)\cdot p(n) \end{eqnarray*}$

Tja da gehts wohl nich weiter. Es sei denn du änderst die IV in $\begin{eqnarray*} \forall 0 \leq m \leq n : p(m)=2^{2^m} \end{eqnarray*}$ .

Das ist eine sehr praktische Form der vollständigen Induktion. Siehe :
http://de.wikipedia.org/wiki/Vollst%C3%A..._Vorg.C3.A4nger
(unter Sonstige)

07.12.2005, 13:21

thx

Auf diesen Beitrag antworten »

Danke.

Ich dachte immer das mit den Potenzen wird anders umgeformt, aber da lag ich wohl völlig falsch. Wieder was gelernt smile

Neue Frage »

Antworten »

n-stellige Boolsche Funktion

Verwandte Themen