Fachrat Informatik - Forum

Quoted from "Kanubis"

[...]
A2 DP Algo, Resolutionswiederlegung
[...]
Ich beginne mit x2

Das wäre ein böser Fehler, die Heuristik ist x1<x2<x3<x4, musst also mit x1 beginnen.

Hallo,

was ich im moment vom Sommersemester 2011 habe ist die probeklausur aber nicht die Klausur selbst.ich wäre sehr dankbar wenn mir jemand die Klausur vom letzten Jahr schicken würde!

Danke im voraus.

und ich hab noch eine frage im bezug auf die probeklausur 2011 von logik.Aufgabe 5 verstehe iwie nicht so ganz gut !! hat jemand vlt einen lösungsvorschlag??

ich habe eine frage zu aufgabe-3 (Rep. 25.09.2011)

und zwar bei dem schritt fuer q2

wir haben in diesem schritt unsere klauselmenge {k2, k4, k7, k8, k9, k10}

laut der tafel haben wir: k7,k8 und k9,k8 genommen!
muesste man da nicht noch k7,k9 auch zusammen nehmen? wenn nicht, dann warum? und wenn ja, warum wurde das an der tafel nicht gemacht?

Ich weiß jetzt zwar nicht, welchen Inhalt die von dir genannten Klauseln haben, aber wenn sich K8 mit K7 und K9 kombinieren läßt, dann kommt in K7 und K9 das gleiche Literal vor, das in K8 in negierter Form steht. Um Klauseln kombinieren zu können, muß eine Variable in einer positiv und in der anderen Klausel negiert vorkommen.

@Mehrad: Schau mal in Stud.IP bei den Dateien der Logik-Vorlesung!

Vielen Dank.
ich habs einfach übersehen!!

Hallo Leute,
ich sitz grad nochmal an Aufgabenblatt 3 Aufgabe 3. Ich hab ein Problem mit dem Ausdruck (p2 <-> !p4). Das wäre ja, wenn man die Bi-Implikation eliminiert (p2 -> !p4) OR (!p4 -> p2). Dann eliminiert man noch die Implikationen und kommt zu (!p2 OR !p4) AND (p4 OR p2). Das passt dann aber im weiteren Verlauf nicht mehr zur Musterlösung. Hat das mal jemand nachgerechnet, oder sieht hier jemand meinen Fehler?

( ! soll die Negation darstellen)

LG
Florian

Quoted from "sos1981"

Das wäre ja, wenn man die Bi-Implikation eliminiert (p2 -> !p4) OR (!p4 -> p2)

(p2 -> !p4) AND (!p4 -> p2)

Stimmt, hab ich hier auch so stehen. Das Problem sind die Variablen in den Termen. Die lauten nämlich laut Musterlösung: (p2 OR !p4) AND (!p2 OR p4). ich komme (bevor die ganze Formel negiert werden soll) auf (!p2 OR !p4) AND (p2 OR p4)...

Auf die Form in der Musterlösung kommt man durch "Ausmultiplizieren" : (a OR b) AND c = (a AND c) OR (b AND c), c muss ja keine einzelne Variable sein.

(p2 OR !p4) AND (!p2 OR p4) steht doch in der Musterlösung erst nach dem Negieren

AHHHH... ich hab meinen Fehler gefunden.... danke!!!!!!!!!!!!!

weiß wer ob der mitzubringende zettel auch bedruckt sein darf?

In der Nachricht im StudIP von Thorsten Kluge steht:

Quoted

Als zusätzliches Hilfsmittel ist ein Blatt Papier (DIN A4) mit beliebiger (beidseitiger)
Beschriftung (von Hand geschrieben oder bedruckt) erlaubt.

Weiß jemand zufällig (ich meine es wurde während der Klausur nichts darüber gesagt), wann mit den Ergebnissen zu rechnen sei?

(btw: warum steht der Thread eigentlich unter "Mathematik" - laut dem Regelstudienplan ist das aus den "Grundlagen der Informatik")

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

2a) Naja halt Hornformel bestimmen. Wichtig war glaube ich, dass man die Implikationen derart umformt, dass auf der rechten Seite keine negierten Variablen standen.
2b) Da die 2. Klausel raus geschmissen wurde, ging der Horn-Algo nichtmal in die While Schleife über. Die Belegung nach Zeile 2 des Algos war erfüllend.

3a) wahr
3b) wahr
3c) falsch

4a) Es existiert a Es existiert b Es existiert c (a != b und a != c und b != c)
4b) Für alle a,b,c,d,e,f,g,h ((E(a,b) und E(c,d) und E(e,f) impliziert nicht E(g,h)) und (g=a impliziert h!=b) und (g=c impliziert h!=d) und (g=e impliziert h!=f))
//Eventuell fehlt hier etwas um zu sagen, dass die 3 Kanten unterschiedlich sein sollen.
4c) 4b verbietet mehr als 3 Kanten, also kann keine 4er Clique(6 Kanten) entstehen

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

Joa, hab ich größtenteils genauso. Bis auf 2 Dinge:

Quoted from "MaxKoch"

4c) 4b verbietet mehr als 3 Kanten, also kann keine 4er Clique(6 Kanten) entstehen

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

zu 4c) "höchstens 3 Kanten => keine 4er Clique" stimmt schon, aber für die Äquivalenz müsste dann auch gelten "keine 4er Clique => höchstens 3 Kanten", was allerdings nicht so ist

zu 5c) Das kommt darauf an, wie das '<=' - Zeichen vom Modell interpretiert wird. Als Allrelation in der für alle x und y gilt (x <= y), müsste die Formel eigentlich wahr werden, wenn ich mich nicht irre. Demnach wäre sie also erfüllbar

Bei 4c versteh ich deinen Einwand nicht. Mit "höchstens 3 Kanten => keine 4er Clique" stimmen wir überein. Aber meiner Meinung nach ist damit der 3. Punkt voll mit abgedeckt, auch wenn man die Umkehrung natürlich nicht schließen kann.

Naja, gesucht ist eine Formel die genau dann von einem Graphen erfüllt wird, wenn dieser keine 4er Clique besitzt. Wenn du nun die Formel aus b) dafür nimmst, müsste gelten, dass eben diese Formel von einem Graphen genau dann erfüllt wird, wenn dieser keine 4er Clique hat. Das bedeutet, dass sowohl "keine 4er Clique => höchstens 3 Kanten" als auch "höchstens 3 Kanten => keine 4er Clique" gelten muss

Oder versteh ich dich falsch?