matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenDiskrete Mathematikboolsche funktionen
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Diskrete Mathematik" - boolsche funktionen
boolsche funktionen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

boolsche funktionen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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..

        
Bezug
boolsche funktionen: Antwort
Status: (Antwort) fertig Status 
Datum: 15:36 Fr 14.04.2006
Autor: sirprize

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

Bezug
                
Bezug
boolsche funktionen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                        
Bezug
boolsche funktionen: Antwort
Status: (Antwort) fertig Status 
Datum: 16:45 Fr 14.04.2006
Autor: sirprize

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

Bezug
                                
Bezug
boolsche funktionen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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 :(

Bezug
                                        
Bezug
boolsche funktionen: Antwort
Status: (Antwort) fertig Status 
Datum: 17:26 Fr 14.04.2006
Autor: sirprize

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


Bezug
                                                
Bezug
boolsche funktionen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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? =)

Bezug
                                                        
Bezug
boolsche funktionen: Antwort
Status: (Antwort) fertig Status 
Datum: 19:25 Fr 14.04.2006
Autor: sirprize

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

Bezug
                                                                
Bezug
boolsche funktionen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                                                                        
Bezug
boolsche funktionen: Antwort
Status: (Antwort) fertig Status 
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]

Bezug
                                                                                
Bezug
boolsche funktionen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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 =)

Bezug
                                                                                        
Bezug
boolsche funktionen: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                                                                                                
Bezug
boolsche funktionen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                                                                                                        
Bezug
boolsche funktionen: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                                                                                                                
Bezug
boolsche funktionen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                                                                                                                        
Bezug
boolsche funktionen: Antwort
Status: (Antwort) fertig Status 
Datum: 19:42 So 16.04.2006
Autor: sirprize

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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


Alle Foren
Status vor 2h 53m 4. fred97
MaßTheo/Sigma-Algebra = P(X)
Status vor 1d 4h 13m 8. Gonozal_IX
MaßTheo/Beweis Sigma-Algebra
Status vor 2d 6. hohohaha1234
USons/Größtmöglichstes Produkt
Status vor 2d 2. matux MR Agent
Mathematica/parametrischen Plot
Status vor 2d 3. Gonozal_IX
UAuslg/Log. Äquivl. vs. log. Schluss
^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]