Aussagen über Horn-Formeln < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 00:15 Sa 15.06.2013 | | Autor: | ac1989 |
| Aufgabe 1 | Sei [mm] \theta [/mm] eine Horn-Formel und [mm] \psi [/mm] = (X [mm] \to \theta [/mm] ).
Dann ist [mm] \psi [/mm] äquivalent zu einer Horn-Formel. |
| Aufgabe 2 | Sei [mm] \theta [/mm] eine Horn-Formel und [mm] \psi [/mm] eine beliebige aussagenlogische Formel mit [mm] \theta \models \psi
[/mm]
Dann ist auch [mm] \psi [/mm] äquivalent zu einer Horn-Formel. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Also zu den obigen Aufgaben habe ich mir folgende Notizen aufgeschrieben:
zu Aufgabe 1)
Definition von Horn-Formel(aus unserem Skript):
Eine (aussagenlogische) Horn-Formel ist eine Formel [mm] \psi [/mm] = [mm] \wedge_{i} \vee_{j} Y_{ij} [/mm] in KNF, wobei [mm] (Y_{ij} [/mm] Literale darstellen) jede Disjunktion [mm] \vee_{j} Y_{ij} [/mm] höchstens ein positives Literal enthält.
Somit können 2 Fälle auftreten:
(1) [mm] \neg X_{1} \vee [/mm] ... [mm] \neg X_{k} \vee [/mm] X (1 pos. Literal)
(2) [mm] \neg X_{1} \vee [/mm] ... [mm] \neg X_{k} [/mm] (kein pos. Literal)
Also habe ich die gegebene Formel ein bisschen umgeformt:
[mm] \psi \equiv [/mm] (X [mm] \to \theta [/mm] ) [mm] \equiv (\neg [/mm] X [mm] \vee \theta)
[/mm]
da [mm] \theta [/mm] eine Horn-Formel ist, müssen wir nun an dieser Stelle eine Fallunterscheidung machen:
falls [mm] \theata [/mm] die Form (1) hat, also schon ein pos. Literal besitzt, so ist die Formel [mm] \psi [/mm] äquvialent zu einer Horn-Formel, denn nun kommt ja nur ein [mm] \neg [/mm] X zum [mm] \theta [/mm] hinzu.
falls [mm] \theta [/mm] die Form (2) hat, so passiert auch nichts. Zu neg. Literalen bekommen wir ein neues Literal hinzu.
=> somit ist die Formel [mm] \theta [/mm] äquivalent zu einer Horn-Formel
zu Aufgabe 2:
Diese Aussage hierzu habe ich mit einem Gegenbeispiel widerlegt.
meine Idee hierzu war, dass Horn-Formeln unter Schnitt abgeschlossen sind. D.h. Wenn ich zwei Modelle [mm] I_{1} [/mm] und [mm] I_{2} [/mm] habe, die mein [mm] \psi [/mm] erfüllen, dann muss auch der Schnitt [mm] I_{1} \cap I_{2} [/mm] mein [mm] \psi [/mm] erfüllen.
Also habe ich [mm] \psi [/mm] und [mm] \theta [/mm] wie folgt gewählt:
sei [mm] \theta [/mm] = [mm] \neg [/mm] Z [mm] \vee \neg [/mm] X [mm] \vee [/mm] Y (meine Horn-Formel)
und sei [mm] \psi [/mm] = [mm] \neg [/mm] Z [mm] \vee [/mm] X [mm] \vee [/mm] Y
Wähle Interpretation [mm] I_{1} [/mm] : Y [mm] \mapsto [/mm] 1 , Z [mm] \mapsto [/mm] 1 , X [mm] \mapsto [/mm] 0
[mm] I_{1} [/mm] würde mein beiden Formeln erfüllen.
Also: [mm] I_{1} \models \theta [/mm] und [mm] I_{1} \models \psi
[/mm]
Somit hätte ich die semantische Folgerungsbeziehung [mm] \theta \models \psi [/mm] sichergestellt.
nun zeige ich, dass [mm] \psi [/mm] nicht äquivalent zu einer Horn-Formel ist.
dazu gebe ich eine weitere Interpr. an:
[mm] I_{2} [/mm] : X [mm] \mapsto [/mm] 1 , Z [mm] \mapsto [/mm] 1 , Y [mm] \mapsto [/mm] 0
Es gilt auch [mm] I_{2} \models \psi.
[/mm]
Aber wenn ich den Schnitt von [mm] I_{1} [/mm] und [mm] I_{2} [/mm] bilde erhalte ich:
[mm] I_{1} \cap I_{2} [/mm] : Z [mm] \mapsto [/mm] 1 , X [mm] \mapsto [/mm] 0, Y [mm] \mapsto [/mm] 0
Wenn [mm] \psi [/mm] zu einer Horn-Formel äquivalent wäre so müsste der Schnitt auch [mm] \psi [/mm] erfüllen.
Aber der Schnitt erfüllt [mm] \psi [/mm] nicht.
Also ist [mm] \psi [/mm] nicht äquivalent zu einer Horn-Formel.
Die Aussage aus der Aufgabenstellung ist widerlegt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:08 So 16.06.2013 | | Autor: | ac1989 |
Also, ich würde gerne wissen, ob ich die Aufgaben richtig gelöst habe. Oder was man an der ganzen Sache noch ändern könnte.
mit freundlichen Grüßen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Mo 17.06.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 17:01 Mo 17.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: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:20 Di 25.06.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
