www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
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:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
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


^ Seitenanfang ^
www.vorhilfe.de