Es geht um
funktionale Vollständigkeit. Hier ist das Aufgabenblatt:
http://www.informatik.uni-hamburg.de/WSV/teaching/vorlesungen/FGI1SoSe07/aufg04.pdfIch habe trotz des Hinweises darunter keine Idee -
- Muss man das mit vollständiger Induktion lösen?
- Wenn ja, wie fange ich an?
Würde bei der Aufgabe beim ersten Blick auf strukturelle Induktion Tippen.
In der Aufgabe sollst du einfach zeigen: dass man nicht alle logischen Verknüpfungen mit der Menge J ausdrücken kann. Z.B. die Menge {NAND} ist funktional Vollständig.
Im Hinweis steht ja eigentlich schon wie du vorgehen solltest.
1. Finde eine Belegung , die für alle Formeln die mit den Junktoren aus J aufgebaut sind, den
gleichen Wahrheitswert liefert. Versuch dies mal über die Induktion.
2. Schaue dir dann den Wahrheitswert von not A unter dieser Belegung an.
strukturelle induktion würd ich auch sagen. beim schritt muss du nur noch die <-> und negation beweisen. <-> kann man ja mit den vorgegebenen junktoren darstellen. also….;-)
strukturelle induktion würd ich auch sagen. beim schritt muss du nur noch die <-> und negation beweisen. <-> kann man ja mit den vorgegebenen junktoren darstellen. also….;-)
Huch? Also die Aussage für die Negation zu beweisen, dürfte nicht gehen [28]
Oder was meinst du genau?
Schreib dir mal die Wahrheitswerttabelle für A,B, A=>B, A v B, A ^ B auf. Mir ist da sofort was interessantes aufgefallen.
Das kann ja jeder:
A | B | (A -> B) | (A v B) | (A & B)
–+–+———+——–+——–
1 | 1 | 1 | 1 | 1
1 | 0 | 0 | 1 | 0
0 | 1 | 1 | 1 | 0
0 | 0 | 1 | 0 | 0
Zeilenweise verUNDet wie verODERt gibt das eine Tautologie …
… meinst du das?
Anm.: Der Server merkt sich die Passwort-Fehleingaben leider über mehrere Tage, vielleicht Wochen, vielleicht ewig … nach 3mal bist du ein Viertelstündchen draußen. Ich kann mich gerade nicht anmelden wegen einmaliger Passwort-Fehleingabe. fmeyer
Hätte bei struktureller Induktion gesagt, dass ich damit über den Formelaufbau der Formeln mit den Junktoren aus J , zeige , dass unter einer bestimmten Belegung immer der gleiche Wahrheitswert für alle Formeln rauskommt.
Dann hätte eine atomare Formel auch diesen Wahrheitswert und die Negation von dieser hätte einen Umgekehrten unter dieser Belegung…
Liege ich mit dem Ansatz richtig oder was meint ihr? bin mir noch unsicher…
Anm.: könnte auch sein, dass FB18-Passwort-Fehleingaben im Cookie gespeichert werden und man nur den rapidforum-Cookie löschen muss.
-.-
Die Schwierigkeit mit den drei Operatoren =>, v, & etwas zu verNICHTen sehe ich auch in der Tabelle. Aber ich versehe nicht, wie ich mit der Aufforderung:
"Finden Sie eine geeignete Belegung A, die für alle G elem. H denselben Wahrheitswert b liefert, kurz:
Für alle G elem. H gilt A(G) = b;"
umgehen soll.
H ist ja eine riesige (vermutlich unendliche) Menge, denn sie enthält wirklich alle nur denkbaren aussagenlogischen Formeln mit Außnahme derer, die die anderen Junktoren enthalten. Dadurch fällt einiges weg, aber das ist immer noch zuviel für mich, denn ich soll nun diese riesige Menge mit einer Belegung abgleichen, so dass alle Formeln herausgefiltert werden, bei denen derselbe Wahrheitswert herauskommt, die Menge nenne ich dann G - oder wie?.
Die strukturelle Induktion ist in den Folien beschrieben: 2-[29] und 2-[35] bis 2-[37].
http://www.informatik.uni-hamburg.de/WSV/teaching/vorlesungen/FGI1SoSe07/Syntax_1.pdfOder anders herum gefragt - wie formuliere ich treffsicher, dass bei den Formeln mit obigen Junktoren immer das gleiche herauskommt?
Weiss nicht ob es richtig ist , sitze auch shcon die ganze zeit bei der Aufgabe:
H ist doch die Menge aller Formeln , die als Junktoren HÖCHSTENS =>, ^, v besitzen.
Also können doch in H nur Formeln sein, die entweder Atomare Formeln sind z.B F
oder Formeln der Form (H o G) o element {=>, ^, v}.
Nun kann man doch anhand der Wahrheitstabelle sehen, dass unter der Belegung A
für die gilt: A ( atomarer Formel ) = 1 , auch für alle anderen Formeln G element H gilt:
A(G)= 1. Das wäre dann eine Behauptung , die man per Induktion beweisen kann…
Erstmal fällt mir gerade auf, dass man mit einer atomaren Formel vollkommen auskommt. Also nochmal Wahrheitswerte für A, A => A, A v A, A ^ A angucken :-)
Ich kenn die Folien nicht, keine Lust sie rauszusuchen.
Strukturelle Induktion:
* Fang mit was trivialem an. "A" ist trivial und in H drin. Du weisst nun: A \in H
* Diesen Schritt immer wieder ausführen: Du kennst endlich viele Formeln in H. Jede mögliche Kombination aus zwei (schon bekannten) Formeln verbindest du nun einmal mit jedem der Junktoren. Diese neuen Formeln dürfen erst benutzt werden, wenn du alle Möglichkeiten durch hast und mit diesem Schritt von vorne beginnst.
Auf diese Weise erhältst du in endlicher Zeit jede endliche Formel in H. Manche doppelt, ist hier aber nicht relevant. Welchen Wert hat A? Welchen Wert müssen alle Formeln haben, die du im zweiten Schritt jeweils generierst?
Wie es sich nun mit unendlichen Formeln verhält weiß ich nicht. Mit der Induktion kriegt man leider nur endliche Formeln. Vermutlich darfst du aber davon ausgehen, dass H nur aus unendlich vielen endlichen Formeln besteht.
