Funktionale Vollständigkeit < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:50 Di 04.06.2013 | | Autor: | ac1989 |
| Aufgabe 1 | | Es gibt eine Boolesche Funktion f : [mm] \{0,1\}^{2} \to \{0,1\} [/mm] mit f(0,0) = 0 , sodass {f} funktional vollständig ist. |
| Aufgabe 2 | | Sei f: [mm] \{0,1\}^{3} \to \{0,1\} [/mm] definiert durch f(x,y,z) = max(x,z) - min(x,y) eine Boole´sche Funktion. Dann ist [mm] \{f,0,1\} [/mm] funktional vollständig. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Zu der Aufgabe 1:
In der Vorlesung haben wir einige Systeme kennengelernt, die funktional vollständig sind. Zum Beispiel [mm] \{\wedge, \vee, \neg\}. [/mm] Ich weiß, aber auch, dass auch [mm] \{\wedge, \neg\} [/mm] oder [mm] \{\vee, \neg\} [/mm] funktional vollständig ist.
So an sich habe ich auch schon die Vorgehensweise verstanden. Man hat ein System gegeben und muss zeigen, dass man mit den gegebenen "Elementen" das UND, ODER und NEGATION darzustellen, weil wir ja wissen, dass das System bestehend aus [mm] \{\wedge, \vee, \neg\} [/mm] funktional vollständig ist.
Aber bei der Aufgabe versteh ich nicht so ganz wie ich mit der Funktion f, genauer f(0,0) = 0, umgehen soll. Solche Aufgabentypen sehe ich zum ersten Mal. Kann mir jmd. sagen, wie man an diese Aufgabenstellung denn herangehen muss?
Zu der Aufgabe 2:
Bei dieser Aufgabenstellnung weiß ich auch nicht wie ich das Problem angehen muss bzw. wie ich genau vorgehen muss.
In unserem Skript haben min und max wie folgt definiert:
Sei I eine aussagenlogische Interpretation und [mm] \alpha [/mm] und [mm] \beta [/mm] aussagenlogische Formeln. Jede zu [mm] \alpha [/mm] und [mm] \beta [/mm] passende Interpretation definiert einen Wahrheitswert [mm] [\alpha]^{I} \in \{0,1\} [/mm] und [mm] [\beta]^{I} \in \{0,1\}.
[/mm]
Also:
[mm] [\alpha \wedge \beta]^{I} [/mm] = [mm] min([\alpha]^{I},[\beta]^{I})
[/mm]
und
[mm] [\alpha \vee \beta]^{I} [/mm] = [mm] max([\alpha]^{I},[\beta]^{I})
[/mm]
heißt das jetzt, dass das max mein [mm] \vee [/mm] darstellt und dass das min mein [mm] \wedge [/mm] ?
auch hier wäre ich über einen Tipp oder Ansatz, wie man am besten vorzugehen hat, sehr erfreut.
Die Lösungen hierzu würde ich dann selber erarbeiten und anschließend hochladen.
ich bedanke mich schon mal für die Tipps, Ideen und Ansätze im Voraus
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 02:51 Mi 05.06.2013 | | Autor: | tobit09 |
Hallo ac1989 und herzlich ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") !
> Es gibt eine Boolesche Funktion f : [mm]\{0,1\}^{2} \to \{0,1\}[/mm]
> mit f(0,0) = 0 , sodass {f} funktional vollständig ist.
Überprüfe bitte die Aufgabenstellung. So ist die Aussage falsch.
Heißt es vielleicht "keine" statt "eine"? Oder $f(0,1)=0$? oder $f(0,0)=1$?
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:27 Do 06.06.2013 | | Autor: | ac1989 |
Also ich habe die Aufgabe überprüft und konnte keinen Fehler feststellen. Ich habe also die Aufgabenstellung korrekt abgetippt.
gruß
ac1989
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:39 Do 06.06.2013 | | Autor: | ac1989 |
hallo tobit09,
ich bins nochmal. Also ich hab die Aufgabenstellung zwar richtig abgetippt, aber ich muss erwähnen, dass diese Aufgaben Wahr- oder Falschaussagen sind. Das heißt, dass ich begründen soll, ob die Aussage wahr oder falsch ist.
Und genau da wusste ich nicht so ganz ich wie da vorgehen soll.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:01 Mi 05.06.2013 | | Autor: | meili |
Hallo,
> Es gibt eine Boolesche Funktion f : [mm]\{0,1\}^{2} \to \{0,1\}[/mm]
> mit f(0,0) = 0 , sodass {f} funktional vollständig ist.
> Sei f: [mm]\{0,1\}^{3} \to \{0,1\}[/mm] definiert durch f(x,y,z) =
> max(x,z) - min(x,y) eine Boole´sche Funktion. Dann ist
> [mm]\{f,0,1\}[/mm] funktional vollständig.
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
> Zu der Aufgabe 1:
> In der Vorlesung haben wir einige Systeme kennengelernt,
> die funktional vollständig sind. Zum Beispiel [mm]\{\wedge, \vee, \neg\}.[/mm]
> Ich weiß, aber auch, dass auch [mm]\{\wedge, \neg\}[/mm] oder
> [mm]\{\vee, \neg\}[/mm] funktional vollständig ist.
>
> So an sich habe ich auch schon die Vorgehensweise
> verstanden. Man hat ein System gegeben und muss zeigen,
> dass man mit den gegebenen "Elementen" das UND, ODER und
> NEGATION darzustellen, weil wir ja wissen, dass das System
> bestehend aus [mm]\{\wedge, \vee, \neg\}[/mm] funktional
> vollständig ist.
> Aber bei der Aufgabe versteh ich nicht so ganz wie ich mit
> der Funktion f, genauer f(0,0) = 0, umgehen soll. Solche
> Aufgabentypen sehe ich zum ersten Mal. Kann mir jmd. sagen,
> wie man an diese Aufgabenstellung denn herangehen muss?
f ist in dieser Aufgabe eine 2-stellige Boolsche Funktion.
Davon gibt es 16 verschiedene Funktionen.
Mit f(0,0) = 0 ist ein Funktionswert festgelegt. Es bleiben noch 8 Möglichkeiten
für verschiedene Funktionen. Ist eine davon als Basisfunktion geeignet?
Siehe dazu auch Mitteilung von tobit09.
>
>
> Zu der Aufgabe 2:
> Bei dieser Aufgabenstellnung weiß ich auch nicht wie ich
> das Problem angehen muss bzw. wie ich genau vorgehen muss.
> In unserem Skript haben min und max wie folgt definiert:
>
> Sei I eine aussagenlogische Interpretation und [mm]\alpha[/mm] und
> [mm]\beta[/mm] aussagenlogische Formeln. Jede zu [mm]\alpha[/mm] und [mm]\beta[/mm]
> passende Interpretation definiert einen Wahrheitswert
> [mm][\alpha]^{I} \in \{0,1\}[/mm] und [mm][\beta]^{I} \in \{0,1\}.[/mm]
>
> Also:
> [mm][\alpha \wedge \beta]^{I}[/mm] = [mm]min([\alpha]^{I},[\beta]^{I})[/mm]
> und
> [mm][\alpha \vee \beta]^{I}[/mm] = [mm]max([\alpha]^{I},[\beta]^{I})[/mm]
>
> heißt das jetzt, dass das max mein [mm]\vee[/mm] darstellt und dass
> das min mein [mm]\wedge[/mm] ?
Ja. Du kannst auch das Minimum und das Maximum der Zahlen 0 und 1
nehmen. Es ergibt genau AND und OR.
Wenn Du aber mit Zahlen rechnest, geht das mit dem Minus ( - ) auch besser.
>
> auch hier wäre ich über einen Tipp oder Ansatz, wie man
> am besten vorzugehen hat, sehr erfreut.
> Die Lösungen hierzu würde ich dann selber erarbeiten und
> anschließend hochladen.
>
>
>
> ich bedanke mich schon mal für die Tipps, Ideen und
> Ansätze im Voraus
Gruß
meili
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:31 Do 06.06.2013 | | Autor: | ac1989 |
Also ich bin jetzt zu folgendem Schluss gekommen:
zu der Aufgabe 1:
so wie ich das jetzt verstanden habe, kann ich mit der Funktion f wohl nur die 0 darstellen.
Aber wenn ich nur die 0 darstellen kann, so ist das System nicht funktional vollständig.
zu der Aufgabe 2:
wenn ich nun mit min und max nur die Disjunktion [mm] \vee [/mm] und Konjunktion [mm] \wedge [/mm] darstellen kann, so ist dieses System ja auch nicht funktional vollständig, da die Negation fehlt.
Ist das so korrekt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:54 Fr 07.06.2013 | | Autor: | meili |
Hallo,
> Also ich bin jetzt zu folgendem Schluss gekommen:
>
> zu der Aufgabe 1:
> so wie ich das jetzt verstanden habe, kann ich mit der
> Funktion f wohl nur die 0 darstellen.
Nein, f kann auch andere Werte annehmen.
Nur f(0,0) = 0.
> Aber wenn ich nur die 0 darstellen kann, so ist das System
> nicht funktional vollständig.
Das ist zu kurz geschlossen.
>
> zu der Aufgabe 2:
>
> wenn ich nun mit min und max nur die Disjunktion [mm]\vee[/mm] und
> Konjunktion [mm]\wedge[/mm] darstellen kann, so ist dieses System ja
> auch nicht funktional vollständig, da die Negation fehlt.
Es wurde eine dreistellige Funktion f definiert. Stimmt diese mit einer
bekannten dreistelligen Boolschen Funktion überein?
Gefragt ist ob {f,0,1} vollständig ist.
>
> Ist das so korrekt?
Nein.
Gruß
meili
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:34 So 09.06.2013 | | Autor: | ac1989 |
Also zu der Aufgabe 1:
Wenn die Funktion f auch andere Werte annehmen kann, wieso schreiben wir dann bzw. wieso steht dann in der aufgabe nur f(0,0)=0 ?
und zu der Aufgabe2:
hier habe ich folgendes aufgeschrieben:
1.) Darstellung der Negation:
Seien x,y,z jeweils mit 1 belegt, dann folgt
[mm] \neg [/mm] x [mm] \equiv [/mm] f(1,1,1)
Denn [mm] \neg [/mm] 1 [mm] \equiv [/mm] max(1,1) - min(1,1) [mm] \equiv [/mm] 1-1 [mm] \equiv [/mm] 0.
Sei nun x mit 0 belegt. y,z seien unverändert. Dann gilt auch [mm] \neg [/mm] x [mm] \equiv [/mm] f(0,1,1)
Denn:
[mm] \neg [/mm] 0 [mm] \equiv [/mm] max(0,1) - min(0,1) [mm] \equiv [/mm] 1-0 [mm] \equiv [/mm] 1
=> somit folgt daraus, dass die Negation darstellbar ist.
2) Nun zur Darstellung der Disjunktion und Konjunktion
Aber es reicht ja, wenn ich nur eins davon darstellen kann.
Ich habe mich für die Disjunktion entschieden. Dazu habe ich die Wahrheitstabelle für die Disjunktion aufgestellt, um eben alle Kombinationen durchzugehen, da wir es ja mit einer Äquivalenz zu tun haben:
Sei y mit 0 belegt und fix.
Sei x=0, z=0:
x [mm] \vee [/mm] z [mm] \equiv [/mm] max(0,0) - min(0,0) [mm] \equiv [/mm] 0-0 [mm] \equiv [/mm] 0
Sei x=0, z=1:
x [mm] \vee [/mm] z [mm] \equiv [/mm] max(0,1) - min(0,0) [mm] \equiv [/mm] 1-0 [mm] \equiv [/mm] 1
Sei x=1, z=0:
x [mm] \vee [/mm] z [mm] \equiv [/mm] max(1,0) - min(1,0) [mm] \equiv [/mm] 1-0 [mm] \equiv [/mm] 1
Sei x=0, z=0:
x [mm] \vee [/mm] z [mm] \equiv [/mm] max(0,0) - min(0,0) [mm] \equiv [/mm] 0-0 [mm] \equiv [/mm] 0
=> alle Kombinationen sind erfüllt. Also ist auch die Disjunkiton darstellbar
Ich weiß, dass ein System bestehend aus Negation und Disjunktion funktional vollständig ist.
Also ist das System {f,0,1} fkt. vollständig.
Ist das richtig so ?
bei Aufgabe 1 weiß ich aber immer noch nicht so ganz wie ich vorgehen soll.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:03 So 09.06.2013 | | Autor: | meili |
Hallo,
> Also zu der Aufgabe 1:
> Wenn die Funktion f auch andere Werte annehmen kann, wieso
> schreiben wir dann bzw. wieso steht dann in der aufgabe nur
> f(0,0)=0 ?
Damit sind die in Frage kommenden zweistelligen Boolschen Funktionen
eingeschränkt, es bleiben aber noch einige, verschiedene Funktionen übrig.
Vergleiche ![[]](/images/popup.gif) Tabelle zweistelliger Boolscher Funktionen.
Die Frage ist, ob diese Einschränkung genügt, die Frage der Aufgabe 1
zu beantworten.
Oder andest ausgedrückt:
Gilt für eine Funktion [mm] $f_0, \ldots [/mm] , [mm] f_7$ [/mm] aus der Tabelle,
[mm] $\{f_i\}$ [/mm] ist funktional vollständig?
>
>
> und zu der Aufgabe2:
> hier habe ich folgendes aufgeschrieben:
>
> 1.) Darstellung der Negation:
> Seien x,y,z jeweils mit 1 belegt, dann folgt
>
> [mm]\neg[/mm] x [mm]\equiv[/mm] f(1,1,1)
>
> Denn [mm]\neg[/mm] 1 [mm]\equiv[/mm] max(1,1) - min(1,1) [mm]\equiv[/mm] 1-1 [mm]\equiv[/mm] 0.
>
> Sei nun x mit 0 belegt. y,z seien unverändert. Dann gilt
> auch [mm]\neg[/mm] x [mm]\equiv[/mm] f(0,1,1)
> Denn:
> [mm]\neg[/mm] 0 [mm]\equiv[/mm] max(0,1) - min(0,1) [mm]\equiv[/mm] 1-0 [mm]\equiv[/mm] 1
>
> => somit folgt daraus, dass die Negation darstellbar ist.
>
> 2) Nun zur Darstellung der Disjunktion und Konjunktion
> Aber es reicht ja, wenn ich nur eins davon darstellen
> kann.
> Ich habe mich für die Disjunktion entschieden. Dazu habe
> ich die Wahrheitstabelle für die Disjunktion aufgestellt,
> um eben alle Kombinationen durchzugehen, da wir es ja mit
> einer Äquivalenz zu tun haben:
>
> Sei y mit 0 belegt und fix.
> Sei x=0, z=0:
> x [mm]\vee[/mm] z [mm]\equiv[/mm] max(0,0) - min(0,0) [mm]\equiv[/mm] 0-0 [mm]\equiv[/mm] 0
>
> Sei x=0, z=1:
> x [mm]\vee[/mm] z [mm]\equiv[/mm] max(0,1) - min(0,0) [mm]\equiv[/mm] 1-0 [mm]\equiv[/mm] 1
>
> Sei x=1, z=0:
> x [mm]\vee[/mm] z [mm]\equiv[/mm] max(1,0) - min(1,0) [mm]\equiv[/mm] 1-0 [mm]\equiv[/mm] 1
>
> Sei x=0, z=0:
> x [mm]\vee[/mm] z [mm]\equiv[/mm] max(0,0) - min(0,0) [mm]\equiv[/mm] 0-0 [mm]\equiv[/mm] 0
>
>
> => alle Kombinationen sind erfüllt. Also ist auch die
> Disjunkiton darstellbar
>
> Ich weiß, dass ein System bestehend aus Negation und
> Disjunktion funktional vollständig ist.
> Also ist das System {f,0,1} fkt. vollständig.
>
> Ist das richtig so ?
![[ok]](/images/smileys/ok.gif "[ok]")
>
>
> bei Aufgabe 1 weiß ich aber immer noch nicht so ganz wie
> ich vorgehen soll.
>
Gruß
meili
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 22:47 Fr 14.06.2013 | | Autor: | ac1989 |
sry, dass es so lange gedauert hat. Aber diese Seite war für eine Weile nicht erreichbar. Inzwischen konnte ich allerdings über die 1.Aufgabe weiter nachdenken.
also so wie ich das jetzt verstanden habe, schaue ich mir die anderen Funktionen [mm] f_{i} [/mm] an, um die Darstellbarkeit von bekannten funktionalen Systemen darzustellen. So wie ich es bei der Aufgabe 2 gemacht habe.
Wenn ich mir die "Tabelle zweistelliger Funktionen" anschaue, die du als Link angegeben hast, dann sehe ich ja, dass ich die Disjunktion mit [mm] f_{1} [/mm] und die Konjunktion mit [mm] f_{7} [/mm] darstellen kann.
und wenn ich mit der Information f(0,0)=0 aus der Aufgabenstellung die Negation darstelle, so müsste doch {f} funktional vollständig sein, oder?
ist das jetzt richtig so?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:34 Fr 21.06.2013 | | Autor: | ac1989 |
| Aufgabe | | Siehe Fragen/Aufgaben, die ich oben gestellt habe. |
also, da ich immer noch an meinen Fragen interessiert bin, wollte ich nochmal eine Frage stellen, damit meine Fragen wieder in die Liste der offenen Fragen kommen.
Ich hoffe, dass ich dieses Mal mehr Glück haben werde.
gruß,
ac
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:24 So 23.06.2013 | | Autor: | meili |
Hallo,
> sry, dass es so lange gedauert hat. Aber diese Seite war
> für eine Weile nicht erreichbar. Inzwischen konnte ich
> allerdings über die 1.Aufgabe weiter nachdenken.
>
> also so wie ich das jetzt verstanden habe, schaue ich mir
> die anderen Funktionen [mm]f_{i}[/mm] an, um die Darstellbarkeit von
> bekannten funktionalen Systemen darzustellen. So wie ich es
> bei der Aufgabe 2 gemacht habe.
>
> Wenn ich mir die "Tabelle zweistelliger Funktionen"
> anschaue, die du als Link angegeben hast, dann sehe ich ja,
> dass ich die Disjunktion mit [mm]f_{1}[/mm] und die Konjunktion mit
> [mm]f_{7}[/mm] darstellen kann.
>
> und wenn ich mit der Information f(0,0)=0 aus der
> Aufgabenstellung die Negation darstelle, so müsste doch
> {f} funktional vollständig sein, oder?
Für die Negation gilt f(0,0) = 1.
Deshalb hast Du die Negation nicht zur Verfügung.
Ich weis leider nicht, ob es mit einer Funktion [mm] $f_0$ [/mm] bis [mm] $f_7$ [/mm] geht.
Mit [mm] $f_{14}$ [/mm] (NAND) würde es gehen, aber auch hier gilt [mm] $f_{14}(0,0) [/mm] = 1$,
scheidet also aus.
>
>
> ist das jetzt richtig so?
Gruß
meili
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:15 So 23.06.2013 | | Autor: | ac1989 |
okay, vielen Dank. Ich denke, ich weiß jetzt wie ich an solche Aufgaben herangehen muss. Vielen Dank.
gruß
|
|
|
|
