Boolesche Funktion < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:35 Mi 12.11.2014 | | Autor: | Steffi88 |
| Aufgabe | Sei f : {0,1}² → {0,1} eine zweistellige, Boolesche Funktion. Die Menge der über f explizit definierten, einstelligen Booleschen Funktionen EXP(1)(f) ist induktiv wie folgt definiert:
• Die Funktion g(x) := f(x, x) (x = 0,1) ist in [mm] EXP^{(1)}(f).
[/mm]
• Sind [mm] t_{0}, t_{1} [/mm] ∈ [mm] EXP^{(1)}(f), [/mm] so auch die Funktionen [mm] h_{0}(x) [/mm] := [mm] f(t_{0}(x), [/mm] x), [mm] h_{1}(x) [/mm] := f(x, [mm] t_{1}(x)) [/mm] und [mm] h_{2}(x) [/mm] := [mm] f(t_{0}(x), t_{1}(x)) [/mm] (x = 0,1).
Zeigen Sie:
(a) Die Mengen {NOR} und {NAND} sind Basen der Booleschen Funktionen.
(b) Die Menge {∨} ist keine Basis der Booleschen Funktionen. (2 Punkte)
Anleitung: Zeigen Sie durch Induktion nach dem Aufbau von t ∈ [mm] EXP^{(1)}(f∨), [/mm] dass t(x) = x |
Hallo zusammen,
das ist eine Aufgabe auf einem Übungsblatt und ich verstehe absolut die Aufgabe nicht. Bisher die erste Aufgabe dieser Art und ich verstehe nicht was hier genau die Boolsche Funktion ist. Anfange müsste man ja ggf mit einer Wertetabelle und zeigen das die beiden Mengen {NOR} und {NAND} dort drin enthalten sind? Bei der b) ist wahrscheinlich das "oder" gemeint, ansonsten kenne ich keine Menge {v}... Könnte mir vielleicht jemand einen stups geben wie ich hier anfange? Ich muss herausfinden was genau die Definition der Funktion bedeutet damit ich eine Tabelle aufstellen kann... :/
Danke schonmal für eure Hilfe!!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:48 Do 13.11.2014 | | Autor: | Steffi88 |
schade das mir hier keiner Helfen kann :/ verstehe einfach nicht die Funktion bzw. wie man damit umgehen muss und was es genau bedeutet...
> • Die Funktion g(x) := f(x, x) (x = 0,1) ist in
> [mm]EXP^{(1)}(f).[/mm]
>
> • Sind [mm]t_{0}, t_{1}[/mm] ∈ [mm]EXP^{(1)}(f),[/mm] so auch die
> Funktionen [mm]h_{0}(x)[/mm] := [mm]f(t_{0}(x),[/mm] x), [mm]h_{1}(x)[/mm] := f(x,
> [mm]t_{1}(x))[/mm] und [mm]h_{2}(x)[/mm] := [mm]f(t_{0}(x), t_{1}(x))[/mm] (x = 0,1).
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:23 Do 13.11.2014 | | Autor: | meili |
Hallo Steffi88,
> schade das mir hier keiner Helfen kann :/ verstehe einfach
> nicht die Funktion bzw. wie man damit umgehen muss und was
> es genau bedeutet...
>
> > • Die Funktion g(x) := f(x, x) (x = 0,1) ist in
> > [mm]EXP^{(1)}(f).[/mm]
> >
> > • Sind [mm]t_{0}, t_{1}[/mm] ∈ [mm]EXP^{(1)}(f),[/mm] so auch die
> > Funktionen [mm]h_{0}(x)[/mm] := [mm]f(t_{0}(x),[/mm] x), [mm]h_{1}(x)[/mm] := f(x,
> > [mm]t_{1}(x))[/mm] und [mm]h_{2}(x)[/mm] := [mm]f(t_{0}(x), t_{1}(x))[/mm] (x = 0,1).
>
Beispiel: Sei f Implikation, [mm] $f(x_1,x_2) [/mm] = [mm] \overline{x_1} [/mm] + [mm] x_2 [/mm] = [mm] x_1 \to x_2$.
[/mm]
So ist g(x):= f(x,x) = [mm] $\overline{x} [/mm] + x$
Also
g(0) = f(0,0) = 1 + 0 = 1,
g(1) = f(1,1) = 0 + 1 = 1
[mm] $h_0(x) [/mm] = f(g(x),x)$ mit
[mm] $h_0(0) [/mm] = f(g(0),0) = f(1,0) = 0 + 0 = 0$,
[mm] $h_0(1) [/mm] = f(g(1),1) = f(1,1) = 0 +1 =1$
[mm] $h_1(x) [/mm] = f(x,g(x))$ mit
[mm] $h_1(0) [/mm] = f(0,g(0)) = f(0,1) = 1 + 1 = 1$,
[mm] $h_1(1) [/mm] = f(1,g(1)) = f(1,1) = 0 +1 = 1$
usw.
$g(x), [mm] h_0(x), h_1(x)$ [/mm] und alle weiteren Funktionen, die durch die
Kombination entstehen, können alle in die Definiton im 2. Punkt oben
eingesetzt werden.
Aber z.B. $g [mm] \equiv h_1$ [/mm] (vergl. Werte)
Gruß
meili
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:46 Do 13.11.2014 | | Autor: | meili |
Hallo Steffi88,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Sei f : {0,1}² → {0,1} eine zweistellige, Boolesche
> Funktion. Die Menge der über f explizit definierten,
> einstelligen Booleschen Funktionen EXP(1)(f) ist induktiv
> wie folgt definiert:
>
> • Die Funktion g(x) := f(x, x) (x = 0,1) ist in
> [mm]EXP^{(1)}(f).[/mm]
>
> • Sind [mm]t_{0}, t_{1}[/mm] ∈ [mm]EXP^{(1)}(f),[/mm] so auch die
> Funktionen [mm]h_{0}(x)[/mm] := [mm]f(t_{0}(x),[/mm] x), [mm]h_{1}(x)[/mm] := f(x,
> [mm]t_{1}(x))[/mm] und [mm]h_{2}(x)[/mm] := [mm]f(t_{0}(x), t_{1}(x))[/mm] (x = 0,1).
>
> Zeigen Sie:
> (a) Die Mengen {NOR} und {NAND} sind Basen der Booleschen
> Funktionen.
>
> (b) Die Menge {∨} ist keine Basis der Booleschen
> Funktionen. (2 Punkte)
> Anleitung: Zeigen Sie durch Induktion nach dem Aufbau von
> t ∈ [mm]EXP^{(1)}(f∨),[/mm] dass t(x) = x
>
>
> Hallo zusammen,
>
> das ist eine Aufgabe auf einem Übungsblatt und ich
> verstehe absolut die Aufgabe nicht. Bisher die erste
> Aufgabe dieser Art und ich verstehe nicht was hier genau
> die Boolsche Funktion ist. Anfange müsste man ja ggf mit
So wie $f: [mm] \{0,1\} \times \{0,1\} \to \{0,1\}$ [/mm] in der Aufgabe definiert ist,
ist damit einfach eine beliebige zweistellige, Boolsche Funktion gemeint.
(gilt also für jede der 16 zweistelligen, Boolschen Funktionen) Vergl. ![[]](/images/popup.gif) Tabelle
Mit [mm] $EXP^{(1)}(f)$ [/mm] wird definiert wie man aus der zweistelligen,
Boolschen Funktion f eine Menge einstelliger, Boolscher Funktionen
erhalten kann.
(Vergl. Tabelle einstelliger, Boolscher Funktionen)
> einer Wertetabelle und zeigen das die beiden Mengen {NOR}
> und {NAND} dort drin enthalten sind? Bei der b) ist
Bei a) soll gezeigt werden, dass NOR oder NAND ausreicht, um alle Boolsche
Funktionen darstellen zu können.
(Siehe Grund- und Basisfunktionen und Vollständige Logiksysteme)
Das soll aber induktiv über [mm] $EXP^{(1)}(f)$ [/mm] mit z.B. $f [mm] \equiv$ [/mm] NOR
gezeigt werden.
> wahrscheinlich das "oder" gemeint, ansonsten kenne ich
> keine Menge {v}... Könnte mir vielleicht jemand einen
Ja, bei b) soll gezeigt werden, dass [mm] $\{\vee\}$ [/mm] (logisches oder) keine Basis ist;
damit also nicht alle Boolsche Funktionen dargestellt werden können.
> stups geben wie ich hier anfange? Ich muss herausfinden was
> genau die Definition der Funktion bedeutet damit ich eine
> Tabelle aufstellen kann... :/
>
> Danke schonmal für eure Hilfe!!
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
Gruß
meili
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Do 13.11.2014 | | Autor: | Steffi88 |
meili du bist ein Schatz!!! Hatte einfach nur die Frage nicht verstanden :D
vielen vielen dank!!
|
|
|
|
