Was meint ihr, ist der 7. Skriptteil (6. Syntaxanalyse kontextfreier Sprachen) auch noch klausurrelevant? Wir haben zu dem immerhin keinen Übungszettel gehabt?

Sorry, wollte kein neues Topic eröffnen. Ich hätte da nochmal ein paar Fragen zu F1 und zwar:
Wie forme ich die folgende Formel am besten in eine KNF um? F=(A & B) v (-B & C)


V=Allquantor E=Existenzquantor - = nicht

Wenn ich folgende Formel nur in eine bereinigte Form bringen will
F= (Vx Ey P(x,g(y,f(x))) v -Q(z)) v -Vx R(x,y)
bekomme ich dann:
Vx1Ey1 P(x1,g(y1 f(x1))) v -Q(z) v -Vx2 R(x2,y) oder

r1(x)=y und damit
Vx1Ey1 P(x1,g(y1 f(x1))) v -Q(z) v -Vx2 R(x2,r1(x))
In der Definition für BPF heisst es ja, dass keine Variablen, die sowohl gebunden als auch frei vorkommen, in der Formel sein dürfen.
Die freien Variablen wären ja z und das letzte y aus F.

Wie kann ich folgende Formeln auf Gültigkeit, Kontingenz, Unerfüllbarkeit testen?
Vx P(a)
Ex(-P(x) v P(a))
P(a) ->ExP(x)
VxP(x) & -EyP(y)
VxP(x) ->ExP(x)

Danke für jede Antwort!

Wie forme ich die folgende Formel am besten in eine KNF um? F=(A & B) v (-B & C)

Script, 4-32. Schritt 0 und 1 braucht man nicht, nur Schritt 2:
(A & B) v (-B & C)
== ((A & B) v -B) & ((A & B) v C)
== ((Av-B) & (Bv-B)) & ((AvC) & (BvC))
== (Av-B) & (AvC) & (BvC)

Wenn ich folgende Formel nur in eine bereinigte Form bringen will

Du meinst bereinigte Praenexform, oder?

F= (Vx Ey P(x,g(y,f(x))) v -Q(z)) v -Vx R(x,y)
bekomme ich dann:
Vx1Ey1 P(x1,g(y1 f(x1))) v -Q(z) v -Vx2 R(x2,y)

Sieht gut aus

oder

r1(x)=y und damit
Vx1Ey1 P(x1,g(y1 f(x1))) v -Q(z) v -Vx2 R(x2,r1(x))

Wieso r1(x)=y? Verwechselst Du da was mit Skolemform?

In der Definition für BPF heisst es ja, dass keine Variablen, die sowohl gebunden als auch frei vorkommen, in der Formel sein dürfen.
Die freien Variablen wären ja z und das letzte y aus F.

richtig

<edit>So, jetzt sollte es stimmen.</edit>

Wie kann ich folgende Formeln auf Gültigkeit, Kontingenz, Unerfüllbarkeit testen?
Vx P(a)

ist aequivalent zu P(a), und P(a) laesst sich durch die Substitution sub(A) = P(a) aus der aussagenlogischen Formel A gewinnen. Da A kontingent ist, ist auch P(a) kontingent, also auch Vx P(a)

Ex(-P(x) v P(a))

== Ex(-P(x)) v P(a)
== -VxP(x) v P(a)
== VxP(x) -> P(a)
Sei A eine passende Struktur.
Wenn A(VxP(x)) = 0, dann A(VxP(x) -> P(a)) = 1.
Wenn A(VxP(x)) = 1, dann A[x/a]P(x) = 1, also P(a) = 1. Also auch A(VxP(x) -> P(a)) = 1.
Ex(-P(x) v P(a)) == VxP(x) -> P(a) ist also gueltig.

P(a) ->ExP(x)

Sei A eine passende Struktur.
Wenn A(P(a)) = 0, dann A(P(a) ->ExP(x)) = 1.
Wenn A(P(a)) = 1, dann A[x/a](P(x)) = A(P(a)) = 1, also A(ExP(x)) = 1, also A(P(a) ->ExP(x)) = 1.
P(a) ->ExP(x) ist also gueltig.

VxP(x) & -EyP(y)

== VxP(x) & Vx-P(x)
== Vx(P(x) & -P(x))
P(x) & -P(x) laesst sich durch Substitution aus der AL-Formel A & -A gewinnen, was bekanntlich eine Kontradiktion ist. Also ist P(x) & -P(x) eine Kontradiktion, also ist Vx(P(x) & -P(x)) eine Kontradiktion.

VxP(x) ->ExP(x)

Sei A eine passente Struktur.
Wenn A(VxP(x)) = 0, dann A(VxP(x) ->ExP(x)) = 1.
Wenn A(VxP(x)) = 1, dann ist fuer alle d A[x/d]P(x) = 1, also gibt es ein d, fuer das A[x/d]P(x) = 1, also A(ExP(x)) = 1. Also A(VxP(x) ->ExP(x)) = 1.
VxP(x) ->ExP(x) ist also gueltig.

ok, nochmal z. Verständniss:In der Definition für BPF heisst es ja, dass keine Variablen, die sowohl gebunden als auch frei vorkommen, in der Formel sein dürfen.

Das y kommt in der Formel als einzige Variable gebunden und frei vor.
Das heisst, dass ich das letzte y als y in der Formel so stehen lassen kann, weil das erste y ,dass an den Existenzquantor gebunden ist nummeriert wird und somit das y aus der Ursprungsformel nicht mehr gebunden als auch frei vorkommt, weil y1 nichts mehr mit y zu tun hat.
Und wenn freie Variablen nur als freie auftreten, dann kann ich sie so stehen lassen, oder?

Und wenn freie Variablen nur als freie auftreten, dann kann ich sie so stehen lassen, oder?

Ja. Eine Variable darf nur nicht gleichzeitig gebunden und frei vorkommen

Was meint ihr, ist der 7. Skriptteil (6. Syntaxanalyse kontextfreier Sprachen) auch noch klausurrelevant? Wir haben zu dem immerhin keinen Übungszettel gehabt?

Nope. [img]http://www.fb18.de/gfx/23.gif[/img]
Hat unser Prof. auch in der Vorlesung gesagt.

Hi,

ich wollte allen Schreibern von F1/2 für morgen nochmal Glück wünschen (und dabei nicht ncohmal extra 'nen neune Thread aufmachen).

Also, ich drücke euch die Daumen (sofern meine Arbeit das zuläßt)! Und seht zu, daß euch soetwas erspart bleibt:
[img]http://www.dasourcerer.net/misc/ass_lv.jpg[/img]

LOL, Danke. Und ich geh jetzt pennen…