Fachrat Informatik - Forum

ich hab 4c) so gelöst: die Formel aus der Übung für die k-Clique und k durch 4 ersetzt. Dann das Teil noch negiert und das müsste es eigentlich gewesen sein....

Vielleicht kapier ich es auch einfach nicht oder falsch. Der Graph soll keine 4er Clique enthalten. Das ist (aus meiner Sicht) durch die Bedingung mit den Kanten gegeben.

Quoted from "MaxKoch"

Wie fandet ihr die Klausur?

Meine Lösungen, so wie ich sie noch im Kopf habe(Können falsch sein, ohne Gewähr):
1a) Im 4. Durchlauf der DP-Algo Schleife, also bei p4, kam die leere Klausel raus
1b) Hab ich eine Teilmenge gefunden, die (hoffentlich) nicht erfüllbar war => nicht minimal unerfüllbar

(...)

5)
phi1 allgemeingültig
phi1 und phi2 erfüllbar, vielleicht allgemeingültig
phi1 und phi2 und phi3 unerfüllbar, weil phi3 ein minimales Element beschreibt, das in phi2 ausgeschlossen wird => Widerspruch

Zwei drei Fragen/ Anmerkungen.

Angenommen ich bin bei p3 und in den Klauseln stünde K1={p3, !p3, p4} und K2={!p3} was kommt dann raus?
Zu 1B) wie lautete die Fragestellung dort genau?

Zu 5B) Ist es nicht so, dass die ersten x und y mit den beiden zweiten nichts zu tun haben? Also dass A und E Quantoren sich nur bis zu der and Verknüpfung auswirken? Denn dann, möchte ich meinen, wäre die Formel allgemeingültig.
Zu 5c) Die Gesammtformel ist in meinen Augen erfüllbar, aber nicht allgmeingürlig gewesen. Wenn ich das in 5B richtig verstanden habe, entstand kein Widerspruch.

Quoted from "Sergey"

Zwei drei Fragen/ Anmerkungen.

Angenommen ich bin bei p3 und in den Klauseln stünde K1={p3, !p3, p4} und K2={!p3} was kommt dann raus?
Zu 1B) wie lautete die Fragestellung dort genau?

Zu 5B) Ist es nicht so, dass die ersten x und y mit den beiden zweiten nichts zu tun haben? Also dass A und E Quantoren sich nur bis zu der and Verknüpfung auswirken? Denn dann, möchte ich meinen, wäre die Formel allgemeingültig.
Zu 5c) Die Gesammtformel ist in meinen Augen erfüllbar, aber nicht allgmeingürlig gewesen. Wenn ich das in 5B richtig verstanden habe, entstand kein Widerspruch.

In diesem Fall - glaube ich - zählt K1 sowohl zu den Klauseln, in denen p3 positive vorkommt, sowie zu denen in denen es negativ vorkommt. Sprich man muss sie in beide Mengen, C und D im DP Algo, berücksichtigen. Wobei sich die Frage ergibt, ob man K1 dann auch mit sich selbst resolieren muss. Weiß ich nicht. Hab ich nicht gemacht.

Sicher beziehen die x und y sich nur auf die Quantoren, die sie umgeben, aber trotzdem schreibt die zweite Formel vor, dass es für jedes x ein kleineres y gibt, wohingegen die dritte Formel ein minimales Element beschreibt. Zusammen ergeben sie keinen Sinn.

Quoted from "MaxKoch"

(...)

Wobei sich die Frage ergibt, ob man K1 dann auch mit sich selbst resolieren muss. Weiß ich nicht. Hab ich nicht gemacht.

Sicher beziehen die x und y sich nur auf die Quantoren, die sie umgeben, aber trotzdem schreibt die zweite Formel vor, dass es für jedes x ein kleineres y gibt, wohingegen die dritte Formel ein minimales Element beschreibt. Zusammen ergeben sie keinen Sinn.

Ich habe es gemacht, habe aber keine Ahnung ob es richtig war. Ich meine, dass so was in den Übungen nicht dran kam oder?

Lautete die 2. Fomel nicht folgendermaßen:

∀x∃y x<=y and ∀y∃x x<=y ?
In pränexer Normalform wäre es dann doch
∀x∃y∀u∃v x<=y and v<=u oder?

Das bedeutet doch, dass für alle x ein y gibt, sodass dieses y größer oder gleich x ist, sowie im zweiten Teil, dass es für alle u ein v gibt, sodass dieses v entweder kleiner oder gleich u ist.
Angenommen es gäbe das kleinste Element. So ist ∀x∃y x<=y davon nicht betroffen, da auch für das kleinste Element einen y gibt, das größer oder gleich dem x ist.
Bei ∀u∃v v<=u ist es danna uch kein Problem, da selbst wenn u bereits das kleinste Element ist, so gibt es einen v (das kleinste Element selbst) sodass v=u und die Formel erfüllt ist.

Bzw. " (...)dass es für jedes x ein kleineres y gibt" ist doch eben falsch, da es "(...)dass es für jedes x ein kleineres oder gleichgroßes y gibt" heißen müsste.

Oder bin ich auf einem völlig falschem Dampfer gerade?

Ich hab die Formeln leider nicht mehr im Kopf..... will jetzt auch nicht zu viele Vermutung anstellen...... warten wir lieber einfach aufs Ergebnis

Ihr vergesst dabei, dass das '<=' - Zeichen hier bloß ein Symbol für eine zweistellige Relation ist, ohne konkrete Bedeutung. Wie das Symbol interpretiert wird und auch die Trägermenge aus der die Variablen entstammen, wird erst im Modell festgelegt.

Man kann also das '<=' in einem Modell genausogut als Kantenrelation auffassen und die Variablen als Knoten. Die Frage ist halt, ob es überhaupt ein Modell gibt, in dem die Formel wahr wird und wenn ja, ob sie in allen Modellen wahr wird.

Nimmt man sich zB ein Modell in dem überhaupt keine Werte miteinander in der '<=' Relation stehen, wird die 2. Formel falsch, sie kann also nicht allgemeingültig sein. Interpretiert man das <= wie gewöhnlich als kleinergleich und die Menge entsprechend den natürlichen Zahlen wird die Formel allerdings wahr, also ist sie erfüllbar. Und wiegesagt, wenn in dem Modell alle Werte miteinander in <= Relation stehen wird auch die 3. Formel wahr.

Es ging in der Aufgabe aber um eine partielle Ordnung, da ist das <= mehr als einfach nur eine zweistellige Relation.

Echt, war das vorausgesetzt? Hm dann hab ich das wohl überlesen ~~

Ok sorry, in dem Kontext ist mein Post oben natürlich Quatsch. Vermutlich richtig wäre dann wohl: a) allgemeingültig b) allgemeingültig (da partielle Ordnungen reflexiv sind) und c) erfüllbar (zB mit den natürlichen Zahlen und gewohnter <= Interpretation)

(hatten wir partielle Ordnungen in der Vorlesung eigentlich jemals definiert?)

weiß jemand, wie viel % man haben muss, um zu bestehen?

Hallo,

im QIS sind nun die Noten zur Logik Klausur zu finden, wann genau die Einsicht stattfindet wird nächste Woche bekannt gegeben.

Notenspiegel:

das ist ja mal ein richtig guter Schnitt.. 2,6 bzw. 2,8 wenn ich mich nicht verrechnet habe...
Wieder eine Mathe-Klausur weniger

wann und wo ist eigentlich die einsicht?

Quoted from "infboy"

wann und wo ist eigentlich die einsicht?

Willst du vielleicht auch den Notenspiegel wissen?

Hallo,

die Einsicht der Logik Klausur wird am Dienstag den 27 September zwischen 14 und 16 Uhr im Institut (Raum 224) stattfinden.

Die Noten der heutigen Logik Klausur sind nun im QIS zu finden. Ein Notenspiegel werde ich aufgrund der Teilnehmerzahlen nicht veröffentlichen.
Die Einsicht ist Montag den 27.02.12 um 14 Uhr in Raum 219 (Appelstrasse 4).