boolsche funktionen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:09 Fr 14.04.2006 | | Autor: | AriR |
| Aufgabe | | Beweisen sie, dass es genau 16 zweistellige boolsche funktionen gibt. |
(frage zuvor nicht gestellt)
hey leute, weiß nicht genau wie ich die aufgabe angehen soll.
da die funktion 2stellig ist gibt es insgesammt pro funktion immer 4 kombinationen aus der Startmenge (hoffe das ist so richtig formuliert, ansonsten könnt ihr das gerne berichitgen)
ja da es 4 kombinationen gibt, muss man zeigen das es 16 4er-lösungstupel gibt (auch hier ist die formulierung sicher wieder falsch, hoffe ihr wisst was gemeint ist)
wie kann ich denn jetzt genau zeigen, dass es genau 16 sind? ich weiß gar nicht genau wie man die aufgabe angehen soll, obwohl es rein intutiv ganz klar ist.
danke im voraus :) gruß an alle..
|
|
| |
|
Hi AriR,
das ist eigentlich ganz einfach zu zeigen, deine weiterführenden Überlegungen führen aber eher auf eine falsche Fährte.
Wie du schon richtig bemerkt hast, sind aufgrund der 2 Parameter insgesamt [mm] $2^2$, [/mm] also 4 mögliche Eingaben gegeben.
Die einzelnen Funktionen können sich somit nur in der Weise unterscheiden, wie sich sich für jeden einzelnen Wert verhalten.
Es gibt also [mm] $2^{2^{2}} [/mm] = [mm] 2^4 [/mm] = 16$ mögliche 2-stellige Boole'sche Funktionen. (Übrigens: [mm] $2^{2^{n}} \not= 4^n$. $2^{2^{n}}$ [/mm] lässt sich nicht weiter vereinfachen.)
Preisfrage: Mit diesen Überlegungen sollte es nicht schwer sein, die Anzahl der verschiedenen n-stelligen Boole'schen Funktionen herauszufinden. Kriegst du das hin?
Übrigens kann man diese ganzen (2-stelligen) Funktionen auch folgendermaßen in einer Tabelle eintragen:
[mm]\begin{matrix}
Eingabe & f_0 & f_1 & f_2 & \cdots & f_{14} & f_{15}\\
00 & 0 & 0 & 0 & \cdots & 1 & 1 \\
01 & 0 & 0 & 0 & \cdots & 1 & 1 \\
10 & 0 & 0 & 1 & \cdots & 1 & 1 \\
11 & 0 & 1 & 0 & \cdots & 0 & 1 \\
\end{matrix}[/mm]
Die meisten dieser Funktionen haben Namen. Beispielsweise ist [mm] $f_0$ [/mm] die konstante 0, [mm] $f_1$ [/mm] das logische UND, [mm] $f_6$ [/mm] das logische Exklusiv-Oder (XOR), usw..
Viele Grüße,
Michael
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:01 Fr 14.04.2006 | | Autor: | AriR |
leider verstehe ich nicht ganz den schritt wie man auf [mm] 2^2^2 [/mm] kommt :(
ich hab meine überlegung gerade etwas fortgesetzt und bin auf folgendes gekommen:
also eigentlich sind alle möglichen 4er-Tuper gesucht, die als komponenten 0 und 1 haben. Diese kann man alle darstellen, durch alle möglichen kombinationen von addition der 4 einheitsvektoren des [mm] \IR^4. [/mm] Man such also sozusagen die Kardinalität der Potenzmenge einer 4-elementigen menge welches [mm] 4^2=16 [/mm] ist.
Ich glaube der gedankengang ist deinem ähnlich.
zu der aufgabe mit den n-stelligen funktionen:
es sind ingsammt [mm] 2^n [/mm] eingaben möglich, als ist die Potenmenge einer [mm] 2^n [/mm] elementigen menge geuscht welches wiederum [mm] 2^2^n [/mm] ist oder?
danke vielmals :) Ari
|
|
|
| |
|
Hi Ari,
du hast es verstanden! 
Eine Boole'sche Funktion kann man auch als Element der Potenzmenge der Eingabewerte sehen: Und zwar sind es dann die Eingaben, die zu einer 1 im Funktionswert führen. Damit wäre [mm] $f_0 [/mm] = [mm] \{\}$, $f_1 [/mm] = [mm] \{11\}$, $f_6 [/mm] = [mm] \{10, 01\}$, $f_{15} [/mm] = [mm] \{00, 01, 10, 11\}$ [/mm] usw..
Wobei die Eingabemenge natürlich [mm] $2^n$ [/mm] Elemente (00, 01, 10, 11) hat. Daher hat die Potenzmenge eben [mm] $2^{(2^{n})}$ [/mm] Elemente - nämlich die Funktionen.
Alles klar?
Viele Grüße,
Michael
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:01 Fr 14.04.2006 | | Autor: | AriR |
also den hintergrund sage ich mal, habe ich wohl verstanden, nur die formale begründung leider überhaupt nicht :(
|
|
|
| |
|
Hi Ari,
dann versuch ichs jetzt nochmal in anderen Worten und mit Verständnisfragen zwischendrin.
Ok, erste Frage: Was unterscheidet denn 2 n-stellige Boole'sche Funktionen voneinander?
Viele Grüße,
Michael
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:36 Fr 14.04.2006 | | Autor: | AriR |
1.) entweder nichts, dann sind diese identisch
2.)sie reagieren für die gleichen eingabe wert anders, also der funktionswert gleicher eingabeparameter wird auf einen andern boolschenwert abgebildet.
war das gemeint? =)
|
|
|
| |
|
Genau!
Und nun:
1. Wie viele verschiedene "Gesamteingabewerte" kann man mit n binären Eingabewerten erzeugen? (Ich hoffe, du verstehst was gemeint ist)
2. Wenn man x verschiedene Eingaben hat, wie viele unterschiedliche binäre Funktionen können dann bestimmt werden? (Vielleicht mal induktiv zeigen - fang mit x=0 und 2 Funktionen (Konstant 0 und Konstant 1) an)
Gruss,
Michael
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:52 Sa 15.04.2006 | | Autor: | AriR |
also zu 1) sind das [mm] 2^n [/mm] wenn ich die frage verstehe.
zu 2) bei der verstehe ich die frage leider nicht so ganz. wenn man 0 eingabe werte hat, warum hat man dann 2 funktionen?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:08 Sa 15.04.2006 | | Autor: | felixf |
Hallo AriR!
> also zu 1) sind das [mm]2^n[/mm] wenn ich die frage verstehe.
Genau.
> zu 2) bei der verstehe ich die frage leider nicht so ganz.
> wenn man 0 eingabe werte hat, warum hat man dann 2
> funktionen?
Du hast die zwei konstanten Funktionen [mm] $f_0$ [/mm] und [mm] $f_1$, [/mm] wobei [mm] $f_0$ [/mm] immer den Wert $0$ und [mm] $f_1$ [/mm] immer den Wert $1$ zurueckliefern. Auch wenn sie gar keine Argumente bekommen
Wenn du ein Argument hast, hast du vier Funktionen: Die zwei Konstanten [mm] $f_0$ [/mm] und [mm] $f_1$, [/mm] die Identitaet $x [mm] \mapsto [/mm] x$ und die Negation $x [mm] \mapsto \neg [/mm] x$.
Noch etwas zum Zusammenhang Potenzmenge [mm] $\leftrightarrow$ Anzahl Funktionen: Wenn du eine Funktion $f : A \to \{ 0, 1 \}$ hast, dann ist die Funktion durch die Menge $\{ x \in A \mid f(x) = 0 \}$ eindeutig bestimmt: Also gibt es genauso viele Funktionen $A \to \{ 0, 1 \}$, wie es Teilmengen von $A$ gibt, also genau $2^{|A|}$. Und $|A|$ ist hier gerade $2^n$...
LG Felix
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:30 Sa 15.04.2006 | | Autor: | AriR |
jo nochmals vielen dank an euch zwei
@felixf: hast du vielleicht den satz mit beweis, für die eindeutigkeit einer boolschen funtkion, wenn man ihre eingabeparamter kennt, die auf die 0 abgebildet werden (Wenn ich das richtig verstanden habe) ?
danke ari =)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:55 Sa 15.04.2006 | | Autor: | felixf |
Hallo Ari!
> @felixf: hast du vielleicht den satz mit beweis, für die
> eindeutigkeit einer boolschen funtkion, wenn man ihre
> eingabeparamter kennt, die auf die 0 abgebildet werden
> (Wenn ich das richtig verstanden habe) ?
Da gibt es keinen wirklichen Satz zu, das ist eine Aussage, deren Richtigkeit man sich leicht ueberlegen kann. Als Tipp: Eine Funktion $f : A [mm] \to \{ 0, 1\}$ [/mm] kann nur die Werte $0$ und $1$ annehmen. Wenn sie fuer $x [mm] \in [/mm] A$ also nicht den Wert $0$ annimmt, dann muss $f(x) = 1$ sein. Also ist die Funktion durch die Menge [mm] $\{ x \in A \mid f(x) = 0 \}$ [/mm] schon eindeutig bestimmt, da du damit die Funktionswerte fuer alle $x [mm] \in [/mm] A$ kennst!
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:16 Sa 15.04.2006 | | Autor: | AriR |
ahh danke ich glaube ich habe es jetzt..
Man nimmt aus A alle Teilmengen, und überlegt sich einfach, dass diese Teilmengen aus A auf die 0 abgebildet werden, der rest auf die 1. Und halt wieviele Teilmengen möglich sind, soviele Funktionen sind auch möglich oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:25 Sa 15.04.2006 | | Autor: | felixf |
Hallo Ari!
> ahh danke ich glaube ich habe es jetzt..
>
> Man nimmt aus A alle Teilmengen, und überlegt sich einfach,
> dass diese Teilmengen aus A auf die 0 abgebildet werden,
> der rest auf die 1. Und halt wieviele Teilmengen möglich
> sind, soviele Funktionen sind auch möglich oder?
Exakt
Eine andere Moeglichkeit ist auch noch: Wenn du alle Funktionen $f : A [mm] \to [/mm] B$ suchst mit $A$ und $B$ endlich, dann hast du ja fuer jedes $a [mm] \in [/mm] A$ genau $|B|$ Moeglichkeiten, dieses abzubilden. Damit hast du [mm] $|B|^{|A|}$ [/mm] Moeglichkeiten fuer Funktionen $f : A [mm] \to [/mm] B$, da du die Funktionswerte von einer FUnktion $f : A [mm] \to [/mm] B$ fuer jedes $a [mm] \in [/mm] A$ beliebig aus $B$ (also unabhaengig von den restlichen $a' [mm] \in [/mm] A$) waehlen kannst.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:18 Sa 15.04.2006 | | Autor: | AriR |
Diese kniffeligen dinger machen voll spaß +g+
ich glaube ich hab das jetzt auch verstanden :)
man hat zB 10 Elmente in A und 20 in B
dann habe ich für das erste element 20 möglichkeiten für abbildung
für das 2. aus A wieder 20 ..... und für das 10 wieder 20möglichkeiten also insgesammt 20^10 möglichkeiten oder?
|
|
|
| |
|
Hi Ari,
schön dass dir sowas Spass macht
Zu deinen Überlegungen: genau richtig!
Frohe Ostern und noch nen schönen Tag an alle!
Gruss,
Michael
|
|
|
|
