Fachrat Informatik - Forum

Wenn ich ihn richtig verstanden habe, alles nicht-elektronische aka Skript, Übungen, alte Klausuren, Mitschriften, etc. Keine Taschenrechner, Handys, Laptops usw

zustimm

letzt jahr war das so ,dies jahr glaube ich auch so.viel erfolg für alle !

Ich habe mal zwei Fragen:

1.)
Blatt 2, Aufgabe 2)
(nA1 AND nA2 AND nA3) OR (A1 AND nA2 AND A3) ist DNF
{{A1,nA2},{nA2},{A1,nA3},{nA2,nA3},{nA1,A2,A3}} ist KNF

warum? Wie geht die Umformung.

2.)
Blatt 7, Aufgabe 2a)
Man soll ein Modell angeben. Wie kommt man auf das Modell? Ist das einfach "geraten"? Wenn ich das Modell überprüfe, ist es ganz einfach und man sieht, dass es passt. Aber selbst eines erstellen macht mir doch Probleme.

Danke schonmal

Quoted

Original von root
2.)
Blatt 7, Aufgabe 2a)
Man soll ein Modell angeben. Wie kommt man auf das Modell? Ist das einfach "geraten"? Wenn ich das Modell überprüfe, ist es ganz einfach und man sieht, dass es passt. Aber selbst eines erstellen macht mir doch Probleme.

Erstmal: je simpler, desto besser

In der Regel kann man ein Model sehr schnell finden, wenn man sich den Aufbau der Klauseln anschaut. Nehmen wir mal Blatt 8, Aufgabe 1a als Beispiel.

Die beiden negierten Klauseln (1 u. 3) unterscheiden sich auf den ersten Blick doch ganz deutlich von den anderen, dass als zweites Argument von P das Funktionssymbol f steht. Also sucht man sich eine Interpretation von P und f, so dass P in diesen Klauseln den Wert 0 erhält. Naheliegend ist doch, f(yadda) = 1 und P(a,b,c) = {b != 1} zu setzen. Dann braucht man nur noch in den beiden anderen Klauseln dafür zu sorgen, dass das zweite Argument von P jeweils gültig ist - bspw g(yadda) = 2, A(c) = 1272.
Fertig.

Ähnliches für Blatt 7, Aufgabe 2a
Klauseln 1 u. 3 charakterisieren sich durch das Funktionssymbol f an zweiter Stelle in P. Also wieder P(a,b,c) = {b != 1}, f(yadda) = 1 gesetzt. Jetzt gilt es nur noch g(x7) und x4 ungleich 1 zu setzen und schon ist man fertig - bspw A(x4) = 2 (da freie Variable), g(yadda) = 239712.

Quoted

Original von root
Blatt 2, Aufgabe 2)
(nA1 AND nA2 AND nA3) OR (A1 AND nA2 AND A3) ist DNF
{{A1,nA2},{nA2},{A1,nA3},{nA2,nA3},{nA1,A2,A3}} ist KNF

warum? Wie geht die Umformung.

Erst negieren:

(A1 OR A2 OR A3) AND (!A1 OR A2 OR !A3)

Dann "ausmultiplizieren":

(A1 AND !A1) OR (A1 AND A2) OR (A1 AND !A3)
OR (A2 AND !A1) OR (A2 AND A2) OR (A2 AND !A3)
OR (A3 AND !A1) OR (A3 AND A2) OR (A3 AND !A3)

Dann vereinfachen:

(A1 AND A2) OR (A1 AND !A3)
OR (A2 AND !A1) OR A2 OR (A2 AND !A3)
OR (A3 AND !A1) OR (A3 AND A2)

Dann wieder negieren:

(!A1 OR !A2) AND (!A1 OR A3)
AND (!A2 OR A1) AND !A2 AND (!A2 OR A3)
AND (!A3 OR A1) AND (!A3 OR !A2)

Das kann man nochmal vereinfachen ... (da !A2 sowieso erfüllt sein muß)

(!A1 OR A3) AND !A2 AND (!A3 OR A1)

(Vergleicht man dieses Ergebnis mit der Ausgangsformel sieht man, daß man da auch einfacher hätte drauf kommen können, indem man !A2 "ausklammert". Der hier beschriebene Weg klappt jedoch immer.)


Alternativ kann man sich auch eine Wertetabelle für die Negation der Ausgangsformel aufstellen und aus den Zeilen dann die KNF bauen.

Quoted

2.)
Blatt 7, Aufgabe 2a)
Man soll ein Modell angeben. Wie kommt man auf das Modell? Ist das einfach "geraten"? Wenn ich das Modell überprüfe, ist es ganz einfach und man sieht, dass es passt. Aber selbst eines erstellen macht mir doch Probleme.

Wenn Du mir verrätst, wo ich die Aufgabe finde, schaue ich mir das gerne mal an.

Danke schonmal Euch beiden.

@Dude: hört sich wieder leicht an, wenn ich es lese. Ich hoffe, ich schaffe es in der Klausur dann auch.

@Joachim: Schade, ich dachte, es gäbe einen schnelleren Weg. Aber ok, so verstehe ich es wenigstens.

http://www-ifm.math.uni-hannover.de/~hol…06/ueblog7l.pdf

Allerdings hat Dude die Aufgabe oben schon erklärt. Damit komme ich (glaub ich) klar.

So, da habe ich doch glatt die nächste Frage:

Es geht um Resolution in der Prädikatenlogik.
Wie man resolviert, ist mir klar.
Aber wie kommt man auf die Ersetzungen?

http://www-ifm.math.uni-hannover.de/~hol…06/ueblog9l.pdf

Auf diesem Blatt ist es die Aufgabe 1 a und b.
Bei a) substituiert man z.B. [x7/h(c,c,c,e)]
Kann man eigentlich substituieren was man will, oder gibt es da feste Regeln für?

Genauso Aufgabe 2. Ich erkenne da kein Schema.

Und nochmal 'ne kurze Frage:

Habe gerade eine alte Klausur gerechnet.
Man soll zeigen, dass A ein Modell von F ist.

F = forall(x1)ex(x2) (P(x1,x2) AND P(t0,t1))

Dann waren noch t0 und t1 gegeben.
x1 und x2 habe ich durch k und n ersetzt.
t0 und t1 ausgerechnet. Dann kommt am Ende folgendes raus:

k < n AND 2k^2 + 8n < n^2 + 2k

Nach obiger Formel müsste jetzt ja gelten:

Für alle k existiert mindestens ein n.

Aber wie ist jetzt genau die Lösung, bzw. wie gebe ich die an? Und ist A ein Modell von F?

Quoted

Original von root
So, da habe ich doch glatt die nächste Frage:

Es geht um Resolution in der Prädikatenlogik.
Wie man resolviert, ist mir klar.
Aber wie kommt man auf die Ersetzungen?

http://www-ifm.math.uni-hannover.de/~hol…06/ueblog9l.pdf

Auf diesem Blatt ist es die Aufgabe 1 a und b.

Ich erkläre am besten mal anhand von Aufgabe 1a, worum es bei dieser Art von Aufgaben überhaupt geht. Vielleicht hast Du die Zusammenhänge zwar schon verstanden, aber sicher ist sicher. :) Ich finde, daß gerade solche Aufgaben gleich viel leichter werden, wenn man weiß, was man da eigentlich tut.

Wir starten mit einer Formel der Prädikatenlogik und wollen herausfinden, ob es eine Möglichkeit gibt, diese Formel wahr werden zu lassen; und zwar durch eine geeignete Interpretation der Symble und durch passende Belegung der freien Variablen mit Werten.

Die Formel ist
[img]http://mimetex.selke.info/?\forall{}x_1\Biggl(\exists{}x_3\neg{}P\bigl(x_1,f(x_3),x_5\bigr)\\\hspace{40}\wedge\hspace{20}\neg\exists{}x_4\neg\forall{}x_1P\bigl(x_1,f(x_4),x_6\bigr)\\\hspace{40}\wedge\hspace{20}\neg\exists{}x_2\forall{}x_1\Bigl(P\bigl(x_1,f(x_1),x_2\bigr)\hspace{15}\vee\hspace{15}\exists{}x_1\neg\forall{}x_2P\bigl(f(x_1),x_4,x_2\bigr)\Bigr)\Biggr).[/img]

Zunächst benennen wir alle Variablen um, so daß keine voneinander verschiedenen Variablen denselben Namen tragen:

[img]http://mimetex.selke.info/?\forall{}x_1\Biggl(\exists{}x_3\neg{}P\bigl(x_1,f(x_3),x_5\bigr)\\\hspace{40}\wedge\hspace{20}\neg\exists{}x_4\neg\forall{}x_7P\bigl(x_7,f(x_4),x_6\bigr)\\\hspace{40}\wedge\hspace{20}\neg\exists{}x_2\forall{}x_8\Bigl(P\bigl(x_8,f(x_8),x_2\bigr)\hspace{15}\vee\hspace{15}\exists{}x_9\neg\forall{}x_{10}P\bigl(f(x_9),x_{11},x_{10}\bigr)\Bigr)\Biggr).[/img]

Nun ziehen wir die Negationen nach innen:

[img]http://mimetex.selke.info/?\forall{}x_1\Biggl(\exists{}x_3\neg{}P\bigl(x_1,f(x_3),x_5\bigr)\\\hspace{40}\wedge\hspace{20}\forall{}x_4\forall{}x_7P\bigl(x_7,f(x_4),x_6\bigr)\\\hspace{40}\wedge\hspace{20}\forall{}x_2\exists{}x_8\Bigl(\neg{}P\bigl(x_8,f(x_8),x_2\bigr)\hspace{15}\wedge\hspace{15}\forall{}x_9\forall{}x_{10}P\bigl(f(x_9),x_{11},x_{10}\bigr)\Bigr)\Biggr).[/img]

Sollte die Formel erfüllbar sein, so läßt sich jede existentiell quantifizierte Variable als eine Funktion der abhängigen all-quantifizierten Variablen angeben. Wir nehmen daher einfach mal an, die Formel sei erfüllbar und führen das dann zum Widerspruch. Wir erhalten also:

[img]http://mimetex.selke.info/?\forall{}x_1\Biggl(\neg{}P\Bigl(x_1,f\bigl(h(x_1)\bigr),x_5\Bigr)\\\hspace{40}\wedge\hspace{20}\forall{}x_4\forall{}x_7P\bigl(x_7,f(x_4),x_6\bigr)\\\hspace{40}\wedge\hspace{20}\forall{}x_2\biggl(\neg{}P\Bigl(q(x_1,x_2),f\bigl(q(x_1,x_2)\bigr),x_2\Bigr)\hspace{15}\wedge\hspace{15}\forall{}x_9\forall{}x_{10}P\bigl(f(x_9),x_{11},x_{10}\bigr)\biggr)\Biggr).[/img]

Das ganze sortieren wir nun ein wenig um (wegen der Umbenennungen von oben geht das problemlos):

[img]http://mimetex.selke.info/?\forall{}x_1\forall{}x_4\forall{}x_7\forall{}x_2\forall{}x_9\forall{}x_{10}\\\hspace{10}\Biggl(\neg{}P\Bigl(x_1,f\bigl(h(x_1)\bigr),x_5\Bigr)\hspace{10}\wedge\hspace{10}P\bigl(x_7,f(x_4),x_6\bigr)\hspace{10}\wedge\hspace{10}\neg{}P\Bigl(q(x_1,x_2),f\bigl(q(x_1,x_2)\bigr),x_2\Bigr)\hspace{10}\wedge\hspace{10}P\bigl(f(x_9),x_{11},x_{10}\bigr)\Biggr).[/img]

Wir wir sehen erhält die Formel drei freie Variablen: x_5, x_6 und x_10. Ist die Formel erfüllbar so gibt es Werte a, b, und c für diese Variablen, so daß die obige Formel wahr ist. Wir nehmen also mal an, daß es solche Werte gibt und die Formel dann wahr ist:

[img]http://mimetex.selke.info/?\forall{}x_1\forall{}x_4\forall{}x_7\forall{}x_2\forall{}x_9\forall{}x_{10}\\\hspace{10}\Biggl(\neg{}P\Bigl(x_1,f\bigl(h(x_1)\bigr),a\Bigr)\hspace{10}\wedge\hspace{10}P\bigl(x_7,f(x_4),b\bigr)\hspace{10}\wedge\hspace{10}\neg{}P\Bigl(q(x_1,x_2),f\bigl(q(x_1,x_2)\bigr),x_2\Bigr)\hspace{10}\wedge\hspace{10}P\bigl(f(x_9),c,x_{10}\bigr)\Biggr).[/img]

Um zu zeigen, daß diese Formel nicht wahr ist (und damit die Ursprungsformel unerfüllbar), reicht es also aus, für die all-quantifizierten Variablen Werte zu finden, so daß sich ein Widerspruch ergibt. Dies läßt sich für jede Klausel getrennt machen, da ja jede Klausel für alle Werte erfüllt sind, die man für die Variablen einsetzt.

Ein solcher Widerspruch kann sich in unserem Fall nur ergeben, wenn zwei der Konjunktionsglieder gleich sind, wobei eines negiert vorkommt und das andere nicht.

Um dies zu erreichen können wir 1/2, 1/4, 2/3 oder 3/4 kombinieren. 1/2 scheidet aus, weil a und b verschieden sind (zumindest haben wir das oben angenommen). 1/4 scheidet auch aus, weil c und f(...) verschieden sind. 3/4 scheidet ebenso aus, da q und f verschieden sind. Hier hat unsere Einsetzstrategie also keine Erfolg.

Bleibt also noch 2/3. Hier haben wir Erfolg, indem wir
x_2 durch b, (damit sind die dritten Komponenten identisch)
x_1 durch b, (oder eine andere beliebige Konstante)
x_7 durch q(b, b) und (damit sind die ersten Komponenten identisch)
x_4 durch q(b, b) (damit sind die zweiten Komponenten identisch)
ersetzen. Für x_1 und x_2 können wir dann irgendwelche Konstanten wählen und somit aus 2 und 3 (mit diesen Ersetzungen) die leere Klausel resolvieren. Die Formel ist also falsch.

Damit ist die obige Formel unerfüllbar. Denn sonst hätten wir keine Ersetzung finden können, die einen Widerspruch erzeugt.

Anmerkung: Auch wenn in beiden Klausel dieselben Variablen vorkommen würden (das ist in dieser Aufgabe nicht der Fall), können wir sie jeweils durch verschiedene Ausdrücke ersetzen, da (wie gesagt) jede Klausel für alle Variablenwerte erfüllt ist (denn die Formel ist nach unserer Annahme wahr).

Quoted

Original von root
Man soll zeigen, dass A ein Modell von F ist.

F = forall(x1)ex(x2) (P(x1,x2) AND P(t0,t1))

Dann waren noch t0 und t1 gegeben.
x1 und x2 habe ich durch k und n ersetzt.

Genau. Damit überträgst Du die Formel in die "Interpretationsebene", die durch A definiert wird. k und n sind dan (vermute ich) natürliche (oder ganze) Zahlen.

Quoted

t0 und t1 ausgerechnet. Dann kommt am Ende folgendes raus:

k < n AND 2k^2 + 8n < n^2 + 2k

Da fehlen noch die Quantoren. Die kannst Du durch Text ersetzen. Mit der Interpretation A lautet die obige Formel also:

"Für alle (natürlichen?) Zahlen k gibt es eine Zahl n, so daß k < n und 2k^2 + 8n < n^2 + 2k gelten."

Und diese Aussage mußt Du nun auf ihren Wahrheitswert hin untersuchen.

Quoted

Nach obiger Formel müsste jetzt ja gelten:

Für alle k existiert mindestens ein n.

Ja.

Quoted

Aber wie ist jetzt genau die Lösung, bzw. wie gebe ich die an?

Entweder zeigst Du, daß diese Aussage wahr ist, indem Du eine Vorschrift angibst, die zu jedem k ein passende n konstruierst, oder Du gibst ein Gegenbeispiel an indem Du einen konkreten Wert für k annimst und zeigst, daß mit diesem Wert die Aussage für alle n falsch ist.[/quote]

Quoted

Und ist A ein Modell von F?

A ist genau dann ein Modell von F, wenn F unter der Interpretation A wahr ist.