verschachtelung von funktionen < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:52 Mi 04.01.2006 | | Autor: | JoergL |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
hallo,
alle höherstelligen Booleschen Funktionen (n>2) kann man ja durch
zweistellige Boolesche Funktionen ausdrücken:
z.b. für n=4
F(w, x, y, z) = f1( f2( f3(w, x), y), z)
welchen Term kann man für allgemeines n schreiben?
hoffe Jemand weiß Rat,
Jöerg
|
|
| |
|
Hallo Joerg,
die Anzahl der Boole'schen Funktionen [mm] f\colon \{0,1\}^n\to\{0,1\} [/mm] ist
[mm] 2^{2^n}. [/mm] Bei einer verschachtelten Darstellung der Art, wie Du sie beschreibst, bei der
also jede Variable nur einmal als Argument einer zweist. Fkt. verwendet wird,
benutzt Du jeweils hoechstens n-1 zweistellige Funktionen. Mal angenommen, Du erlaubst
noch Permuationen der Variablen, kommst Du so nur auf
fakultaet (n) [mm] \cdot 4^{n-1} \approx 2^{const. \cdot n\cdot \log n} [/mm] Funktionen, was
zuwenig ist.
Erlaubst Du jedoch, dass Variablen mehrfach als Argumente verwandt werden,
so kannst Du fuer bel. [mm] f\colon\{0,1\}^n\to\{0,1\} [/mm] schreiben:
[mm] f(x_1,\ldots x_n) [/mm] = [mm] \bigvee_{a\in\{0,1\}^n,f(a)=1} x^a
[/mm]
mit
[mm] x^a [/mm] = [mm] x_1^{a_1}\wedge\ldots \wedge x_n^{a_n}
[/mm]
und [mm] x_j^{a_j} [/mm] = [mm] x_j [/mm] falls [mm] a_j=1, \neg x_j [/mm] falls [mm] a_j=0
[/mm]
Dann kannst Du die Und-Terme verschachtelt schreiben und
das [mm] \bigvee [/mm] auch.
Bei Deiner ''Normalform'' fuer n=4 schau doch mal, ob es auch fuer
f(w,x,y,z)= [mm] (w\wedge y)\vee (x\wedge [/mm] z) klappt.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 04:23 Do 05.01.2006 | | Autor: | JoergL |
hallo,
danke schonmal für die antwort,
ich schreibe zur zeit eine arbeit in der ich noch keine Normalform auch keine binären Operationen definiert habe.
Ich suche lediglich einen allgemeinen term, der darauf hinweist das die
Verschachtelung von von von binären funktionen für jede Schaltfunktion möglich ist in der form F(a, b, c,......) = f(f(f(f(........)) .
Gibt es eine Algebraische Schreibweise?
danke,
Joerg
|
|
|
| |
|
Hallo nochmal,
wie schon geschrieben, gibt es - aus Kardinalitaetsgruenden - nicht fuer jede n-stellige
Boole'sche Funktion [mm] f\colon\{0,1\}^n\to\{0,1\} [/mm] eine Darstellung
[mm] f(x_1,\ldots [/mm] , [mm] x_n)= f_1(x_1,f_2(x_2,\ldots f_{n-1}(x_{n-1},x_n)\ldots [/mm] )
(sogar nur ''fuer einen verschwindend kleinen Teil - ein Gruss an alle Freunde der
Asymptotik  ).
Viele Gruesse,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:46 Do 05.01.2006 | | Autor: | JoergL |
hallo,
vielen dank für die erläuterungen.
in meinem Lehrscript zur Schaltalgebra, steht;
"Alle höherwertigen Booleschen Funktionen (n>2) können durch Verknüpfungen
zweistelliger Boolescher Funktionen aufgebaut werden."
,eben durch diese Verschachtelung. In der Praxis der Schaltalgebra wird es
ja auch so gemacht.
Ist diese Behauptung jetzt falsch. bzw. hab ich was falsch formuliert, oder existiert wirklich ein funktionsterm der für beliebige n anwendbar ist und alle fälle einschliesst?
Gruß
Joerg
|
|
|
| |
|
Hallo Joerg nochmal,
wie geschrieben, wenn Du erlaubst, dass Variablen in mehreren 2-stell. Fkt. als Argumente
vorkommen, existiert sowas immer - siehe meine erste Antwort, aber wenn Du - wie man es bei Deiner Aufgabenformulierung vermuten koennte, jede Variable nur einmal
als Argument nehmen willst, klappt es im allgemeinen nicht.
Gruss,
Mathias
|
|
|
|
