Ws2016 Probeklausur Aufgabe 4

Bachelor Grundlagen der Logik in der Informatik
1

kann jemand kurz überprüfen!!!

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Ws2016 Probeklausur Aufgabe 4
an der Schritte 6 zu skolem-form die [color=orange]die organge Teile muss ich bei beide z auch verschiede bennen?(S(x, z) ∧ S(z, x))) [/color]

  1. ∀x((∀y(R(x, y)) ∨ ∃y(R(y, x))) → ∃z(S(x, z) ∧ S(z, x)))
  2. ∀x(-(∀y(R(x, y)) ∨ ∃y(R(y, x))) ∨ ∃z(S(x, z) ∧ S(z, x)))
  3. ∀x((∃y-(R(x, y)) ∧ ∀y-(R(y, x))) ∨ ∃z(S(x, z) ∧ S(z, x)))
    Umbenennung der gebund. Variablen → d.h wir haben 2 unterschied. y ( y und y2)
  4. ∀x((∃y-(R(x, y)) ∧ ∀y2-(R(y2, x))) ∨ ∃z(S(x, z) ∧ S(z, x)))
    [color=crimson]5. Pränexe-Form
    ∀x∃z∃y∀y2     [/color] [color=blue]
    (-(R(x, y)) ∧ -(R(y2, x))) ∨ (S(x, z) ∧ S(z, x)))
    [/color]
    [color=crimson]6.skolem-Form
    ∀x∀y2    [/color]
    (-R(x,f(x)) ∧ -(R(y2, x)))∨ (S(x, h1(x)) ∧ S(h2(x), x)))
    an der Stelle muss ich die beide z auch verschiede variable angeben oder kann ich
    so
    s(x, h1(x))∧ S(h1(x), x)))
3

Wenn es dieselbe Variable ist, dann musst du auch dieselbe Skolemfunktion benutzen.
Dieselbe meint sogar gleichnamig, wenn man sich in der pränexen Normalform befindet.

Denn der zweite Fall kann in der pränexen NF nicht mehr auftreten.

  • ∃y (R(y) ^ S(y)). Beide y repräsentieren dieselbe Variable.
  • ∃y (R(y)) v ∃y∀x(T(y, x)). Beide y repräsentieren verschiedene/unabhängige Variablen.

Warum man tatsächlich dieselbe Skolemfunktion nehmen muss:

Wenn ∀x∃a(R(x) ^ (S(a, x) v S(x, a))) gültig wäre, wäre dann auch ∀x∃b∃c(R(x) ^ (S(b, x) v S(x, c))) gültig? Anders gesagt: Sei M ein Modell. Da die erste Formel per Annahne gültig ist, ist sie in M erfüllt. Ist die zweite dann auch erfüllt?
Ja, die zweite wäre auch erfüllt.
Wenn jedoch die zweite Formel in M erfüllt wäre, wäre es dann auch die erste? Nein, nicht zwingend.

Daher sind beide Formeln auch nicht erfüllbarkeitsäquivalent!
Wie würden die Skolemformen der beiden aussehen? Die zweite Formel ist genau das, was du machen wolltest durch Einführen verschiedener Skolemfunktionen. Dieser Schritt ist also illegitim.

4

das heisst , ich soll (S(x, h1(x)) ∧ S(h2(x), x))) durch Einführen verschiedener Skolemfunktionen so schreiben!

5

danke

6

Nein, richtig wäre (S(x, h1(x)) ∧ S(h1(x), x)).

7

erste Satz Wenn es dieselbe Variable ist, dann musst du auch dieselbe Skolemfunktion benutzen. , hast du gemeint, S(x, z) ∧ S(z, x)) hat selbe x und z, deshalb sollte es gleiche Skolemfunktion haben, weil die beise in selber Funktion darinen?

8

Dass das ‘x’ auch als Argument auftaucht, ist irrelevant. Auch dass beide Male das Prädikat S verwendet wird, ist irrelevant. Es geht nur darum, dass beide ‘z’ von demselben Existenz-Quantor eingefangen werden.
Wenn es hieße ‘\forall x \exists z \forall y ((S(z) ^ T(x)) v R(x, y, z))’, müsste du es nach Eliminieren vom Existenzquantor über z so schreiben: ‘\forall x, y ((S(g(x)) ^ T(x)) v R(x, y, g(x)))’.

9

So ist endliche Loesungsweg zur Probeklausur Ws2016 A4

  1. ∀x((∀y(R(x, y)) ∨ ∃y(R(y, x))) → ∃z(S(x, z) ∧ S(z, x)))
  2. ∀x(-(∀y(R(x, y)) ∨ ∃y(R(y, x))) ∨ ∃z(S(x, z) ∧ S(z, x)))
  3. ∀x((∃y-(R(x, y)) ∧ ∀y-(R(y, x))) ∨ ∃z(S(x, z) ∧ S(z, x)))
    Umbenennung der gebund. Variablen → d.h wir haben 2 unterschied. y ( y und y2)
  4. ∀x((∃y-(R(x, y)) ∧ ∀y2-(R(y2, x))) ∨ ∃z(S(x, z) ∧ S(z, x)))
  5. Pränexe-Form
    ∀x∃z∃y∀y2
    (-(R(x, y)) ∧ -(R(y2, x))) ∨ (S(x, z) ∧ S(z, x)))

[color=crimson] 6.skolem-Form
∀x∀y2 [/color]

  (-R(x,f(x)) ∧ -(R(y2, x))) ∨     (S(x, h1(x)) ∧ S(h1(x), x)))
                                                             an der Stelle muss man selbe soklem Funktion benuzten

7. CNF-Form
(-R(x,f(x)) ∨ S(x, h1(x))) ∧ (-R(y2,x) ∨ S(x, h1(x))) ∧ (-R(x,f(x)) ∨ S(h1(x), x)) ∧ (-R(y2,x) ∨ S(h2, x))

10

[quote=Marcel[Inf]]
Dass das ‘x’ auch als Argument auftaucht, ist irrelevant. Auch dass beide Male das Prädikat S verwendet wird, ist irrelevant. Es geht nur darum, dass beide ‘z’ von demselben Existenz-Quantor eingefangen werden.
Wenn es hieße ‘\forall x \exists z \forall y ((S(z) ^ T(x)) v R(x, y, z))’, müsste du es nach Eliminieren vom Existenzquantor über z so schreiben: ‘\forall x, y ((S(g(x)) ^ T(x)) v R(x, y, g(x)))’.
[/quote]

deine Erklaerung habe ich schon verstanden, nach Skirpt habe noch folgende Problem und Gedanken:

aus deiner Beispiel: ∀x.∃z.∀y ((S(z) ∧ T(x)) v R(x, y, z))
skolem-form bei dir ist: ∀x.∀y ((S(z) ∧ T(x)) v R(x, y, g(x))) warum kann z nicht als g(x,y)
laut der Skirpt, habe ich so verstanden, ∀x.∃z.∀y da ∃z vorne nur ∀x., deshalb kann nur die R(x,y,g(x)) als die Skolem-form von (R(x,y,z)
es muss doch die Reihungfolge betrachen, wenn man streng an der Regel beachten

habe ich folge Beispiel 1:

[b] ∀x.∃z.(P(x,z)v Q(z)) [/b]

skolem-form: ∀x (P(x,f(x))v Q(f(x)))richtig?

beispiel 2: aufagbe35 (1) aus der https://formal.iti.kit.edu/~beckert/teaching/Logik-SS06/loesung_blatt10.pdf

∃y.∀x.∃z.(-p(x,y)v q(z,z))
meine Umbennung:skolem-form: ∀x.(-p(x,h(x))v q(f(x),f(x))
in der PDF-Datei: die Loesung steht :∀x.(-p(x,a)v q(f(x),f(x)), [color=darkviolet] ich nehme an, da ∃y. vorne keine Quanto mehr, deshalb haben die eine variable a genommen
[/color]

11

[quote=Marcel[Inf]]
Wenn es dieselbe Variable ist, dann musst du auch dieselbe Skolemfunktion benutzen.
Dieselbe meint sogar gleichnamig, wenn man sich in der pränexen Normalform befindet.

Denn der zweite Fall kann in der pränexen NF nicht mehr auftreten.

  • ∃y (R(y) ^ S(y)). Beide y repräsentieren dieselbe Variable.
  • ∃y (R(y)) v ∃y∀x(T(y, x)). Beide y repräsentieren verschiedene/unabhängige Variablen.

Warum man tatsächlich dieselbe Skolemfunktion nehmen muss:

Wenn ∀x∃a(R(x) ^ (S(a, x) v S(x, a))) gültig wäre, wäre dann auch ∀x∃b∃c(R(x) ^ (S(b, x) v S(x, c))) gültig? Anders gesagt: Sei M ein Modell. Da die erste Formel per Annahne gültig ist, ist sie in M erfüllt. Ist die zweite dann auch erfüllt?
Ja, die zweite wäre auch erfüllt.
Wenn jedoch die zweite Formel in M erfüllt wäre, wäre es dann auch die erste? Nein, nicht zwingend.

Daher sind beide Formeln auch nicht erfüllbarkeitsäquivalent!
Wie würden die Skolemformen der beiden aussehen? Die zweite Formel ist genau das, was du machen wolltest durch Einführen verschiedener Skolemfunktionen. Dieser Schritt ist also illegitim.
[/quote]

und ich habe den Uebungsleiter gerade gefragt,
in unsere Fall , ist v und ∧ muessen wir unterscheiden!!!
aus Probeklausur ∀x ∃z S(x, z) ∧ S(z, x))
zur Skolem-form : muss z verschiede nenen, da [color=orange]∧ als Verbindungssymbol[/color]

beispiel :∃x.(x=0 [color=crimson]v x nicht= 0)[/color] v ist oder
∃x.x=0 v ∃x.x nicht= 0 das gilt : kann die beide gleiche Fkt nemhem

aber ∃x.(x=0 [color=crimson]∧ x nicht= 0) [/color] muss verschiede FKt nehmen

deshalb in der Probeklausur : ∀x∃z (S(x, z) ∧ S(z, x)))
skolem-form ist :∀x (S(x, h1(x)) ∧ S(z,h2( x))))

in der Ws2016 richtige Klausur teilaufgabe: ∀x∃z (P(x,z) v Q(z)
skolem-form ist: ∀x (P(x,f(x)) v Q(f(x))

12

[quote=momo8]habe ich folge Beispiel 1:

[b] ∀x.∃z.(P(x,z)v Q(z)) [/b]

skolem-form: ∀x (P(x,f(x))v Q(f(x)))richtig?

beispiel 2: aufagbe35 (1) aus der https://formal.iti.kit.edu/~beckert/teaching/Logik-SS06/loesung_blatt10.pdf

∃y.∀x.∃z.(-p(x,y)v q(z,z))
meine Umbennung:skolem-form: ∀x.(-p(x,h(x))v q(f(x),f(x))
in der PDF-Datei: die Loesung steht :∀x.(-p(x,a)v q(f(x),f(x)), [color=darkviolet] ich nehme an, da ∃y. vorne keine Quanto mehr, deshalb haben die eine variable a genommen
[/color]
[/quote]

Beispiel 1: Richtig.
Beispiel 2: Vor ∃y gibt es keinen Allquantor, also ist die Auswahl von y „von nichts abhängig“ => Skolemfunktion bekommt kein Argument. Die Skolemfunktion kann man sich auch als Auswahlfunktion des Zeugen y vorstellen. Wäre davor noch ein Allquantor, sagen wir ∀w, dann muss dieser Zeuge ggf. in Abhängigkeit von w ausgesucht werden.

Das stimmt!

13

[quote=Marcel[Inf]]

[quote=momo8]habe ich folge Beispiel 1:

[b] ∀x.∃z.(P(x,z)v Q(z)) [/b]

skolem-form: ∀x (P(x,f(x))v Q(f(x)))richtig?

beispiel 2: aufagbe35 (1) aus der https://formal.iti.kit.edu/~beckert/teaching/Logik-SS06/loesung_blatt10.pdf

∃y.∀x.∃z.(-p(x,y)v q(z,z))
meine Umbennung:skolem-form: ∀x.(-p(x,h(x))v q(f(x),f(x))
in der PDF-Datei: die Loesung steht :∀x.(-p(x,a)v q(f(x),f(x)), [color=darkviolet] ich nehme an, da ∃y. vorne keine Quanto mehr, deshalb haben die eine variable a genommen
[/color]
[/quote]

Beispiel 1: Richtig.
Beispiel 2: Vor ∃y gibt es keinen Allquantor, also ist die Auswahl von y „von nichts abhängig“ => Skolemfunktion bekommt kein Argument. Die Skolemfunktion kann man sich auch als Auswahlfunktion des Zeugen y vorstellen. Wäre davor noch ein Allquantor, sagen wir ∀w, dann muss dieser Zeuge ggf. in Abhängigkeit von w ausgesucht werden.

Das stimmt!
[/quote]
Du hast Recht, :blush: :blush: ich habe irgendwie falsch verstanden!! die ∧ v sind mit dem Formel nichts zu tun. es soll gleiche Fktsname angeben!!!