Funktionen & Kominatorik < Sonstiges < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich habe Probleme bei 2 Aufgaben bei einen Übunsgsblatt
-Aufgabe1:
Sei f eine Funktion auf einer endlichen Menge A. Zeigen Sie ,dass folgende Eigenschaften von f gleichwertig sind:
(i) f ist bijektiv
(ii) f ist injektiv,
(iii) f ist surjektiv.
Bei dieser Aufgabe versteche ich nicht ganz, was man machen soll, weil (i),(ii) und (iii) doch nicht gleichwertig sind. Soll ich einen Widerspruchsbeweis machen oder sind die vielleicht doch gleichwertig . Aber eine Funktion muss doch nicht gleich surjektiv sein, wenn sie injektiv ist. (Aber wenn sie bijektiv ist, dann sit sie ja surj. & inj. ).
??????
kann mir da jemand helfen?
Dann hab ich noch Probleme bei einer anderen Aufgabe:
-Aufgabe 3:
Eine n-stellige boolesche Funktion ist eine Funktion von {0, [mm] 1}^{n} [/mm] nach {0, 1}. Eine n-stellige
boolesche Funktion f heißt symmetrisch, falls der Funktionswert von f nur von der Anzahl
der Einsen in der Eingabe abh¨angt. D.h. haben x, [mm] y\in [/mm] {0, [mm] 1}^{n} [/mm] die gleiche Anzahl von Einsen,
dann gilt f(x) = f(y). Zum Beispiel ist die 2-stellige und-Funktion symmetrisch.
a) Wieviele Elemente enthält {0, [mm] 1}^{n}?
[/mm]
b) Wieviele Eingaben aus {0, [mm] 1}^{n} [/mm] haben k Einsen, für 0 [mm] \le [/mm] k [mm] \le [/mm] n?
c) Wieviele n-stellige boolesche Funktionen gibt es?
d) Wieviele symmetrische n-stellige boolesche Funktionen gibt es?
Meine Lösungen:
a) ist [mm] 2^{n} [/mm]
b) [mm] k\approx [/mm] log n , wobei der 2-log verwendet wird und das Ergebnis aufgerundet wird
[mm] c) z=2^{2^n} [/mm] boolsche Funktionen ( zwei hoch zwei hoch n)
Da habe ich Probleme bei der d.
Ich vermute , dass es die Hälfte ist also z/2. stimmt das?
Ich würde mich freuen, wenn mir jemand bei den beiden Aufgaben helfen könnte.
Gruß Peter
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:02 Sa 04.12.2004 | | Autor: | Marc |
Hallo nightburner!
> -Aufgabe1:
> Sei f eine Funktion auf einer endlichen Menge A. Zeigen
> Sie ,dass folgende Eigenschaften von f gleichwertig sind:
> (i) f ist bijektiv
> (ii) f ist injektiv,
> (iii) f ist surjektiv.
>
> Bei dieser Aufgabe versteche ich nicht ganz, was man machen
> soll, weil (i),(ii) und (iii) doch nicht gleichwertig sind.
> Soll ich einen Widerspruchsbeweis machen oder sind die
> vielleicht doch gleichwertig . Aber eine Funktion muss doch
> nicht gleich surjektiv sein, wenn sie injektiv ist. (Aber
> wenn sie bijektiv ist, dann sit sie ja surj. & inj. ).
> ??????
> kann mir da jemand helfen?
Im allgemeinen sind die Aussagen auch nicht gleichwertig, das entscheidene ist hier die Einschränkung "auf einer endlichen Menge A".
Ich denke, das reicht schon als Tipp, denn die Gleichwertigkeit ist ziemlich offensichtlich 
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:08 Sa 04.12.2004 | | Autor: | Marc |
Hallo Nightburner,
> Dann hab ich noch Probleme bei einer anderen Aufgabe:
Neue Fragen bitte in einen neuen Thread (das nächste Mal )
> -Aufgabe 3:
> Eine n-stellige boolesche Funktion ist eine Funktion von
> [mm] $\{0, 1\}^{n}$ [/mm] nach {0, 1}. Eine n-stellige
> boolesche Funktion f heißt symmetrisch, falls der
> Funktionswert von f nur von der Anzahl
> der Einsen in der Eingabe abh¨angt. D.h. haben x, [mm]y\in[/mm]
> [mm] $\{0, 1\}^{n}$ [/mm] die gleiche Anzahl von Einsen,
> dann gilt f(x) = f(y). Zum Beispiel ist die 2-stellige
> und-Funktion symmetrisch.
> a) Wieviele Elemente enthält [mm] $\{0, 1\}^{n}$?
[/mm]
> b) Wieviele Eingaben aus [mm] $\{0, 1\}^{n}$ [/mm] haben k Einsen, für 0
> [mm]\le[/mm] k [mm]\le[/mm] n?
> c) Wieviele n-stellige boolesche Funktionen gibt es?
> d) Wieviele symmetrische n-stellige boolesche Funktionen
> gibt es?
>
>
> Meine Lösungen:
> a) ist [mm]2^{n}[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
> b) [mm]k\approx[/mm] log n , wobei der 2-log verwendet wird und das
> Ergebnis aufgerundet wird
Hier ist --denke ich-- der genaue Wert gemeint, in Abhängigkeit eines vorgegebenen k.
> [mm]c) z=2^{2^n}[/mm] boolsche Funktionen ( zwei hoch zwei hoch
> n)
> Da habe ich Probleme bei der d.
>
> Ich vermute , dass es die Hälfte ist also z/2. stimmt
> das?
Der Funktionswert hängt nur von der Anzahl der Einsen in der Eingabe ab.
Es gibt n+1 verschiedenen solche Anzahlen, nämlich 0,1,...,n.
Jeder dieser Anzahlen kann nun eine 0 oder 1 zugeordnet werden, also gibt es wie viele symmetrische boolesche Funktionen?
Viele Grüße,
Marc
|
|
|
| |
|
Hallo,
bei Aufgabe 1 sind die Aussagen dann gleichwertig, weil es sich um eine Funktion auf eine endliche Menge handelt, d.h. dass jeder Punkt wird erreicht wird und zwar nur einmal. also ist die Funktion injektiv &surjektiv, deswegen auch bijektiv?
stimmt die Erklärung?
und bei der 3 d) kommt [mm] 2^{n} [/mm] raus oder?
danke für deine Hilfe
Gruß Peter
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:22 Sa 04.12.2004 | | Autor: | Marc |
Hallo Peter,
> bei Aufgabe 1 sind die Aussagen dann gleichwertig, weil es
> sich um eine Funktion auf eine endliche Menge handelt, d.h.
> dass jeder Punkt wird erreicht wird und zwar nur einmal.
> also ist die Funktion injektiv &surjektiv, deswegen auch
> bijektiv?
> stimmt die Erklärung?
Welche Erklärung? Ich erkenne keine Kausalkette, sondern nur Vermengung von Voraussetzungen und Behauptungen.
> und bei der 3 d) kommt [mm]2^{n}[/mm] raus oder?
![[notok]](/images/smileys/notok.gif "[notok]") , es gibt n+1 verschiedene Eingaben, denen jeweilse unabhängig voneinander der Wert 0 oder 1 zugeordnet werden kann.
Also gibt es [mm] $2^{n+1}$ [/mm] Funktionen.
Was ist mit 3b?
Viele Grüße,
Marc
|
|
|
| |
|
Hallo,
bei der 3 b) kommt dann [mm] 2^{n} [/mm] über k raus. (hofentlich stimmts)
könntest du die Anwort zu der Aufgabe 3 d) besser erleutern?
ich verstehe nicht, warum man für eine symetrische n-stellige boolsche Funktion n+1 verschiedene Eingaben gibt!
ach, wie soll ich die 1 beweisen.
mit einen Beispiel oder mit den Definitionen von surjekitv un d injektiv -> bij.
weil ich finde dass die Aufgabe 1 sehr allgemein formuliert ist. und ich weiss nicht wie ich dort anfangen soll.
danke
gruß peter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:42 So 05.12.2004 | | Autor: | Marc |
Hallo Nightburner!
Fragen an die Gemeinschaft bitte in einen Frageartikel schreiben
Fragearktikel erlangen eher die Aufmerksamkeit eines "Antwortwilligen", da wir spezielle Übersichten (Übersicht 1, Übersicht 2) für offene Fragen anbieten (und ausserdem die Markierung durch ein rotes Quadrat recht auffällig ist).
Mitteilungs- und Antwortartikel werden dagegen leicht übersehen.
> bei der 3 b) kommt dann [mm]2^{n}[/mm] über k raus. (hofentlich
> stimmts)
Das kann nicht stimmen.
Es gibt doch maximal [mm] 2^n [/mm] Eingaben, das hast du doch in a) selbst ausgerechnet.
Wie können dann [mm] ${2^n \choose k}$ [/mm] davon nur eine bestimmte Eingenschaft erfüllen? [mm] ${2^n \choose k}$ [/mm] ist doch im allgemeinen größer als [mm] $2^n$.
[/mm]
> könntest du die Anwort zu der Aufgabe 3 d) besser
> erleutern?
> ich verstehe nicht, warum man für eine symetrische
> n-stellige boolsche Funktion n+1 verschiedene Eingaben
> gibt!
Eine symmetrische Funktion ist durch die Funktionswerte folgender n+1 Eingabe eindeutig bestimmt:
[mm] $(0,0,\ldots,0)\in\{0,1\}^n$ [/mm] (0 Einsen)
[mm] $(0,0,\ldots,1)\in\{0,1\}^n$ [/mm] (1 Eins)
[mm] $\vdots$
[/mm]
[mm] $(1,1,\ldots,1)\in\{0,1\}^n$ [/mm] (n Einsen)
(Die übrigen der insgesamt [mm] $2^n$ [/mm] Eingaben enthalten ja eine bestimmte Anzahl Einsen, und haben einen identischen Funktionswert).
Für diese n+1 Eingaben kann der Funktionswert aber frei festgelegt werden, für jeden haben wir 2 Möglichkeiten: 0 oder 1.
Insgesamt gibt es so [mm] $2^{n+1}$ [/mm] symmetrische Funktionen.
> ach, wie soll ich die 1 beweisen.
> mit einen Beispiel
> oder mit den Definitionen von surjekitv
> un d injektiv -> bij.
> weil ich finde dass die Aufgabe 1 sehr allgemein
> formuliert ist. und ich weiss nicht wie ich dort anfangen
> soll.
Ich würde hier nur zeigen:
i) injektiv [mm] $\Rightarrow$ [/mm] surjektiv
ii) surjektiv [mm] $\Rightarrow$ [/mm] injektiv
(Die Bijektivität ergibt sich dann jeweils automatisch, bzw. kann alternativ vorausgesetzt werden.)
Ich führe mal ii) vor, versuche i) doch mal alleine.
Sei $|A|=n$
Angenommen, f ist nicht injektiv. Dann existieren [mm] $a_1,a_2\in [/mm] A$ mit [mm] $f(a_1)=f(a_2)$. [/mm] Das bedeutet aber doch --da f eine Funktion ist-- dass [mm] $|f(A)|\le [/mm] n-1$ ist, denn die übrigen n-2 Elemente aus A können auf maximal n-2 Elemente abgebildet werden.
Also gibt es ein Element [mm] $a\in A\setminus [/mm] f(A)$, was bedeutet, dass f nicht surjetiv ist.
Schöner könnte man diesen Beweis übrigens per Induktion führen.
Viele Grüße,
Marc
|
|
|
| |
|
ok,
die Aufgaben sind mir jetzt klar.
Gruß Peter
|
|
|
|
