vollständige junktorensysteme < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:23 Di 16.01.2007 | | Autor: | AriR |
| Aufgabe | zeigen sie, dass [mm] \{\vee;\wedge\} [/mm] nicht vollständig ist.
|
Hey,
ich hab diese folgendermaßen versucht zu zeigen:
mann kann zB nicht [mm] \neg(a \wedge [/mm] b) darstellen, da dies für a=b=w (w:=true) den wert f (f:=false) liefert, man jedoch mit [mm] \wedge [/mm] und [mm] \vee [/mm] nie den wert f erhält, wenn man a=b=w beliebig oft miteinander verknüpft, da w [mm] \wedge [/mm] w = w und w [mm] \vee [/mm] w = w
kann man das so einfach sagen?
Gruß Ari
|
|
| |
|
Moin Ari,
jou, so ist es, die via [mm] \wedge,\vee [/mm] gebildeten Terme definieren sogenannte monotone Funktionen
[mm] f\colon\{0,1\}^n\to\{0,1\}, [/mm] die alle die Eigenschaft [mm] f(1,\ldots [/mm] , 1)=1 haben, was man zB formal durch strukturelle
Induktion nach der Formellänge beweisen kann
(Ind. Anfang: [mm] f(x_1,\ldots [/mm] , [mm] x_n)=x_j,
[/mm]
Ind. Schritt: Gelte es für [mm] g_1,g_2\colon\{0,1\}^n\to\{0,1\}, [/mm] dann ist zu zeigen, daß
[mm] f_1(x_1,\ldots [/mm] , [mm] x_n)=g_1(x_1,\ldots [/mm] , [mm] x_n)\wedge g_2(x_1,\ldots [/mm] , [mm] x_n)
[/mm]
und
[mm] f_2(x_1,\ldots [/mm] , [mm] x_n)=g_1(x_1,\ldots [/mm] , [mm] x_n)\vee g_2(x_1,\ldots [/mm] , [mm] x_n)
[/mm]
auch diese Eigenschaft haben.
Das schaffst Du dann schon ordentlich aufzuschreiben, gelle ?
Nur mal so: Woher in NRW kommst Du denn ? - Ist ja legitim zu fragen, wenn
Du hier schon solch eine Rundumbetreuung bekommst.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:18 Di 16.01.2007 | | Autor: | AriR |
ach klar kannst du das fragen :D
ich komme aus gronau und studiere in münster diplom informatik mit nebenfach mathematik
wenn du noch mehr fragen hast, dann tu dir keinen zwang an
Gruß Ari
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:51 Di 16.01.2007 | | Autor: | AriR |
ich hab mal versucht das so aufzuschreiben:
Beh: [mm] f(x_1,...,x_n)=1 [/mm] für [mm] x_i=1 [/mm] und alle [mm] f:\{0;1\}^n\to\{0;1\}
[/mm]
Bew: durch Induktion über den aufbau von f.
IA: sei f 2stellig also n=2
dann gilt [mm] f(x_1,x_2)=x_1\wedge x_2 [/mm] oder [mm] f(x_1,x_2)=x_1\vee x_2
[/mm]
und in beiden fällen ergibt [mm] f(x_1,x_2)=1 [/mm] für [mm] x_1,x_2=1
[/mm]
IV: bla bla bla +g+
IS: Sei f n+1-stellig. oBda alle komponenten werden in dem Term benutzt. Dann ist [mm] f(x_1,...,x_{n+1})= g(x_1,...,x_n)\vee x_{n+1} [/mm] oder [mm] f(x_1,...,x_{n+1})= g(x_1,...,x_n)\wedge x_{n+1}
[/mm]
[mm] g(x_1,...,x_n) [/mm] ist 1 laut IV für [mm] x_1,...,x_n [/mm] und somit f auch wieder in beiden fällen 1 für [mm] x_{n+1}=1
[/mm]
qed.
würde der beweis ca so aussehen? sind glaub ich par formale fehler drin :(
|
|
|
| |
|
Moin Ari,
geht leider so nicht, da Du dann so Formeln wie
[mm] (x_1\wegde x_2)\vee (x_3\wedge x_4)
[/mm]
in Deinem Induktionsbeweis nicht mit abdeckst.
Mach es durch Induktion nach Formellänge/Aufbau der Formel, also Formeltiefe, dann geht es auch.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 09:17 Mi 17.01.2007 | | Autor: | AriR |
ich versuchs mal:
Bew: durch Induktion des Aufbaus von f
IA: Ist [mm] f(x_1,...,x_n)=x_j [/mm] für [mm] 1\le j\le [/mm] n, dann ist f immer 1 für [mm] x_i=1
[/mm]
IV:...
IS: Sei [mm] f(x_1,...,x_n)=g(x_1,...,x_n)\wedge h(x_1,...,x_n) [/mm] oder [mm] f(x_1,...,x_n)=g(x_1,...,x_n)\vee h(x_1,...,x_n)
[/mm]
dann sind für [mm] x_i=1 [/mm] g und h beide 1 laut IV und somit f wieder in beiden fällen 1.
qed.
meintest du dsa ca so? wenn ja, ist das formale auch richtig? Ich glaube im Induktionsschritt passt da was nicht mit dem g und h. Es wird nicht wirklich klar, das damit funktionen aus der IV gemeint sind oder?
Gruß Ari
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:20 Mo 22.01.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:28 Mi 17.01.2007 | | Autor: | AriR |
ich muss euhc leider enttäuschen, bin ein junge +g+
bin im 3.semester und mein name ist einfach Ari :)
ist keine abkürzung wie die meisten denken.
achja und zu der eigentlich aufgabe. man soll ja zeigen, dass das junktorensystem nicht vollständig ist, und wenn nicht negation konjungtion und disjunktion zeigen könnte, dann wäre es ja vollständig
|
|
|
|
![[cap]](/images/smileys/cap.gif "[cap]"){kind=small}
![[breakdance]](/images/smileys/breakdance.gif "[breakdance]"){kind=small}
![[bussi]](/images/smileys/bussi.gif "[bussi]"){kind=small}
![[huepf]](/images/smileys/huepf.gif "[huepf]"){kind=small}
![[aetsch]](/images/smileys/aetsch.gif "[aetsch]"){kind=small}
