Vorbereitung Klausur Logik

Junior Schreiberling

Tuesday, August 31st 2010, 12:29pm

Hi,

zur Zeit wiederhole ich ein paar Sachen für die Klausur Freitag und wollt mal was zur Übung 3 Aufgabe 2 fragen:

Die erste Klausel von Phi lautet p2 <-> (nicht) p4
Diese Biimplikation lässt sich auflösen in zwei Implikationen: (p2 -> (nicht) p4) UND ((nicht) p4 -> p2)

Laut Skript ist eine Implikation wie folgt aufzulösen:

p1 -> p2 = (nicht) p1 ODER p2

Wenn ich diese Regel auf die oben genannte Klausel anwende, dann erhalte ich ((nicht) p2 ODER (nicht) p4) UND (p2 ODER p4). Dieses Ergebnis deckt sich aber nicht mit der Musterlösung. Das Ergebnis dort lautet:

((nicht) p2 ODER p4) UND (p2 ODER (nicht) p4). Nur mit diesem Ergebnis funktioniert die Resolution, kann mir da mal jemand bitte auf die Sprünge helfen?

Danke schonmal!

Go to the top of the page

FSW16

Trainee

Posts: 119

Date of registration: Jun 25th 2008

Location: Hildesheim

2

Tuesday, August 31st 2010, 1:41pm

Das hast du soweit richtig aufgelöst nur musst du
(p2 oder p4) und ((nicht) p2 oder (nicht) p4)
in DNF umformen und dann kommst du auf das Ergebnis in der Lösung. Denn zuerst brauchst du die komplette DNF-Form um dann die Morgansche Regel anzuwenden um die KNF-Form für nicht phi zu erhalten.

Ich hoffe es ist verständlich.

Edit: Sorry KNF und DNF zuerst vertauscht gehabt. Ist nun aber alles korrigiert.

This post has been edited 5 times, last edit by "FSW16" (Aug 31st 2010, 2:24pm)

Go to the top of the page

fragenfrager

Junior Schreiberling

Posts: 189

3

Tuesday, August 31st 2010, 2:05pm

Hi,

danke dir schonmal herzlich für deine Antwort!

Quoted from "FSW16"

nur musst du p2 oder p4 und (nicht) p2 oder (nicht) p4 in KNF umformen und dann kommst du auf das Ergebnis in der Lösung.

Also die Ableitungsschritte sind ja so:
(p2 <-> (nicht) p4)
(p2 -> (nicht p4)) UND ((nicht p4) -> p2)
((nicht p2) ODER (nicht p4)) UND (p4 ODER p2))

Und die letzte Zeile ist doch bereits KNF? KNF ist doch die "Ver-UND-ung" von "Ver-ODER-ungen", also die Konjunktion von Disjunktions-Klauseln...

Die Reihenfolge bei der Resolution (eine von zwei Möglichkeiten) ist doch, (nicht) Phi in KNF zu bringen. Also ist die Reihenfolge so:
1) Phi in DNF umwandeln
2) (nicht) Phi bilden (ergibt sehr schnell eine KNF)
3) Resolutionsableitungen durchführen

Go to the top of the page

FSW16

Trainee

Posts: 119

Date of registration: Jun 25th 2008

Location: Hildesheim

4

Tuesday, August 31st 2010, 2:18pm

Ich hatte vorhin ausversehen DNF und KNF verwechselt, deswegen war das ein bisschen irreführend, aber nun:

((nicht p2) ODER (nicht p4)) UND (p4 ODER p2))
ist KNF wie du ja selber sagst und wie du auch gesagt hast brauchst du aber zuerst die DNF-Form also musst du sie noch umwandeln und dann kriegst du folgende DNF-Form:

((nicht) p2 UND p4) ODER ((nicht) p4 UND p2)

und das wird dann wieder in Phi eingesetzt
und dann wird (nicht) phi gebildet
und dadurch wird aus:

((nicht) p2 UND p4) ODER ((nicht) p4 UND p2) (negieren)=> ( p2 ODER (nicht p4)) UND (p4 ODER (nicht p2))

Edit: Ist es nun klar? Weil wenn nicht, dann könnte ich es auch nochmal ganz ausführlich machen, aber nur wenn es noch unklar ist, da ich gerade GThI lerne.

This post has been edited 1 times, last edit by "FSW16" (Aug 31st 2010, 2:32pm)

Go to the top of the page

FSW16

Trainee

Posts: 119

Date of registration: Jun 25th 2008

Location: Hildesheim

5

Tuesday, August 31st 2010, 2:56pm

Komplette Ableitung:
1.(p2 <-> (nicht) p4)
2.(p2 -> (nicht p4)) UND ((nicht p4) -> p2)
3.((nicht p2) ODER (nicht p4)) UND (p4 ODER p2)) = KNF-Form
4.((nicht) p2 UND p4) ODER ((nicht) p4 UND p2) = DNF-Form, das steht auch in der Lösung bei Phi

und dann wird erst (nicht) Phi gebildet:
1a.nicht( ((nicht) p2 UND p4) ODER ((nicht) p4 UND p2) )
2a.(p2 ODER (nicht p4)) UND (p4 ODER (nicht p2)) = gesuchte KNF-Form von (nicht) Phi, das steht auch in der Lösung

Go to the top of the page

fragenfrager

Junior Schreiberling

Posts: 189

6

Tuesday, August 31st 2010, 3:14pm

Total nett, dass du mir hier so hilfst, danke dir!

Ich glaub, ich mache irgendwo einen Fehler. Ich schreibe dir mal meine Ableitungen rein, vielleicht siehst du ja, wo ich den Fehler mache:

Sei die umzuformende Klausel $\psi$ der Formel $\phi$ .
$\psi := ( p2 \to \neg p4) \wedge ( \neg p4 \to p2)$
$\eq ( \neg p2 \vee \neg p4) \wedge (\neg \neg p4 \vee p2)$
$\eq ( \neg p2 \vee \neg p4) \wedge (p4 \vee p2) =: \psi$ in KNF. Das jetzt in DNF umformen:

$\eq \neg ( \neg p2 \vee \neg p4) \vee \neg(p4 \vee p2)$
$\eq ( p2 \wedge p4) \vee ( \neg p4 \wedge \neg p2) =: \psi$ in DNF.

Dies ist also meine in DNF umgeformte Klausel, die ich wieder in $\phi$ einsetzen.

$\phi$ wird jetzt negiert ( $\neg \phi$ ) und man erhält unter Anwendung von deMorgan ( $\neg \phi$ ) in KNF. DeMorgan auf die oben hergeleitete Klausel $\psi$ in DNF angewendet ergibt:

$\eq \neg (( p2 \wedge p4) \vee ( \neg p4 \wedge \neg p2))$
$\eq \neg (p2 \wedge p4) \wedge \neg ( \neg p4 \wedge \neg p2)$
$\eq (\neg p2 \vee \neg p4) \wedge ( p4 \vee p2) := \neg \psi$ in KNF.

Auf diese Formel ( ( $\neg \phi$ ) in KNF) kann jetzt der Resolutionsalgorithmus angewendet werden.

Ich komm einfach nicht auf die Lösung $(\neg p2 \vee p4) \wedge ( \neg p4 \vee p2)$ , weil in den Klammern jeweils nur zwei nicht-negierte, oder zwei negierte Literale stehen. Da hilft ja auch kein Umwandeln in DNF oder KNF...

Go to the top of the page

fragenfrager

Junior Schreiberling

Posts: 189

7

Tuesday, August 31st 2010, 3:19pm

Hab ich so lange für das Texen gebraucht, dass dein Posting zuerst kam

Quoted from "FSW16"

3.((nicht p2) ODER (nicht p4)) UND (p4 ODER p2)) = KNF-Form
4.((nicht) p2 UND p4) ODER ((nicht) p4 UND p2) = DNF-Form, das steht auch in der Lösung bei Phi

Von 3. auf 4. scheint mir aber nicht äquivalent...

Muss es nich so gehen?

$(\neg p2 \vee \neg p4) \wedge (p4 \vee p2)$ . Diese KNF negieren für die Umwandlung in DNF:
$\eq \neg ((\neg p2 \vee \neg p4) \wedge (p4 \vee p2))$
$\eq (p2 \wedge p4) \vee (\neg p4 \wedge \neg p2))$

This post has been edited 2 times, last edit by "fragenfrager" (Aug 31st 2010, 3:20pm)

Go to the top of the page

FSW16

Trainee

Posts: 119

Date of registration: Jun 25th 2008

Location: Hildesheim

8

Tuesday, August 31st 2010, 3:33pm

Ne du darfst ja nicht einfach etwas einmal negieren, denn sonst erhälst du ja die negierte Version der Formel.
Um KNF in DNF umzuwandeln kannst du einfach die Klammer miteinander "multiplizieren":
((nicht p2) ODER (nicht p4)) UND (p4 ODER p2))
wird dann genaugesehen zu:
((nicht) p2 UND p2) ODER ((nicht) p2 UND p4) ODER ((nicht) p4 UND p4) ODER ((nicht) p4 UND p2))
und ((nicht) p2 UND p2) und ((nicht) p4 UND p4) kannst du weglassen (da sie so oder so "0" ergeben)
und dann bleibt nur noch:
((nicht) p2 UND p4) ODER ((nicht) p4 UND p2) über.

Es gibt auch noch andere Methoden KNF in DNF umzuwandeln aber einmal negiern darfst aufjedenfall nicht, da du eben sonst nicht mehr eine äquivalente Formel zur Ursprünglichen Formel hast.

MFG

Go to the top of the page

fragenfrager

Junior Schreiberling

Posts: 189

9

Tuesday, August 31st 2010, 3:46pm

Quoted from "FSW16"

Es gibt auch noch andere Methoden KNF in DNF umzuwandeln aber einmal negiern darfst aufjedenfall nicht, da du eben sonst nicht mehr eine äquivalente Formel zur Ursprünglichen Formel hast.

MFG

Hm, so macht das wirklich SInn mit dem "Ausmultiplizieren". Blättere gerade im Skript rum und suche mal, wo diese oder andere Methoden genannt werden. Klar, einmal Negieren verändert die Formel, hab ich übersehen. Und dabei dachte ich, lediglich DeMorgan angewendet zu haben...

Danke dir vielmals!

Go to the top of the page

kyo_udon

Praktikant

Posts: 10

Date of registration: Sep 16th 2009

10

Tuesday, August 31st 2010, 5:05pm

welche Hilftsmittel sind in der Klausur erlaubt?

Go to the top of the page

fragenfrager

Junior Schreiberling

Posts: 189

11

Wednesday, September 1st 2010, 2:32pm

Ein beidseitig beschriebenes A4-Blatt

War wer beim Repetitorium? Wurde außer DPLL noch etwas genaueres zu gesagt, wo noch Schwerpunkte liegen (könnten)?

Go to the top of the page

Ryoga`

Trainee

Posts: 51

Date of registration: Oct 15th 2008

Location: Sarstedt

12

Wednesday, September 1st 2010, 6:43pm

Notiert habe ich folgendes im Repi:

Klausurschwerpunkte
- Resolutionswiderlegung (Davis-Putnam-Algorithmus/DPLL)
- Hornformeln (erkennen/umformen/(DNF/KNF/Pränixe NF)
- Formalisieren (siehe aufgabe 5 aus Probeklausur)

This post has been edited 1 times, last edit by "Ryoga`" (Sep 1st 2010, 6:43pm)

Go to the top of the page

Georg

Praktikant

Posts: 8

Date of registration: Oct 3rd 2008

13

Thursday, September 2nd 2010, 5:38pm

Ableitungsbaum und generell Mitschrift in Logik

In der 3. Übung, 1. Aufgabe heißt es, man solle einen Ableitungsbaum für die Formel aufzeichnen.

Im Skript habe ich nur die Zeile gefunden, dass man Formeln auch als Ableitungsbäume darstellen kann - klasse

Was genau will man da von mir sehen?

Hat generell jemand eine Mitschrift der Logik-Übungen, die er mir mailen (oder hochladen und hier verlinken) könnte? (Bevor ich noch viele weitere Fragen hier rein poste...)

Wäre klasse. Danke schon mal.

Go to the top of the page

fragenfrager

Junior Schreiberling

Posts: 189

14

Thursday, September 2nd 2010, 6:19pm

Bei dieser Übung, nach der du fragst, habe ich eine Notiz zu einer Bemerkung von Thorsten Kluge gemacht, wonach solche Ableitungen (sub( $\phi$ )) in der Klausur nicht abgefragt werden. Zur Mitschrift: Ganz ehrlich, bis auf die paar Zusatzbemerkungen, die ich mir notiert habe, konnte ich keinen Unterschied zur online gestellten Musterlösung entdecken (was ich persönlich sehr schade finde, aber was will man machen...). Kann aber durchaus sein, dass manch anderer mehr notiert hat...

Beim Baum musst du dir das so vorstellen: Guck im Skript die Reihenfolge bei den Bindungen an und dann schreib in die Wurzel das Symbol, welches in der jeweiligen Formel am stärksten bindet. Beispiel: $(a \vee b) \to (c \vee d)$ . Hier bindet $\to$ am stärksten und kommt in die Wurzel, als linkes Kind kommt $\vee$ mit zwei Blättern "a" und "b". Rechter Teilbaum analog...

Und mit "Zusatzbemerkungen" meine ich: Ich habe mir Notizen gemacht, was Thorsten explizit als klausurrelevant hervorgehoben hat. Das steht aber auch schon alles in einem Posting oben, also auch da leider kein Mehrwert...

Go to the top of the page

FSW16

Trainee

Posts: 119

Date of registration: Jun 25th 2008

Location: Hildesheim

15

Thursday, September 2nd 2010, 6:27pm

Wie sieht es mit dem Sequenzenkalkül aus? Ist das Klausurrelevant? Also muss ich damit was ableiten können oder kommt sowas definitiv nicht dran?

MfG

Go to the top of the page

Georg

Praktikant

Posts: 8

Date of registration: Oct 3rd 2008

16

Thursday, September 2nd 2010, 6:58pm

danke dir fragenfrager, so habe ich mir das mit dem Ableitungsbaum auch vorgestellt, war mir aber plötzlich nicht mehr sicher. In sofern durchaus Mehrwert für mich, auch wenn es unwahrscheinlich ist, das sowas in der Klausur drankommt.

Go to the top of the page

FSW16

Trainee

Posts: 119

Date of registration: Jun 25th 2008

Location: Hildesheim

17

Friday, September 3rd 2010, 12:52pm

Was habt ihr bei der Aufgabe 5b der heutigen Klausur rausbekommen?
erfüllbar, aber nicht allgemeingültig?

MfG

This post has been edited 1 times, last edit by "FSW16" (Sep 3rd 2010, 3:53pm)

Go to the top of the page

Schokoholic

Fritz

Posts: 2,518

Date of registration: Oct 4th 2006

Location: Hannover

Occupation: Haarspaltung

18

Friday, September 3rd 2010, 4:09pm

Quoted from "FSW16"

Wie sieht es mit dem Sequenzenkalkül aus? Ist das Klausurrelevant? Also muss ich damit was ableiten können oder kommt sowas definitiv nicht dran?

Der Sinn einer Klausur ist doch, dass der gesamte Vorlesungsstoff geprüft werden kann. Wenn jemand "Schwerpunkte" vorgibt, heißt das nicht, dass der Rest nicht dran kommt! Sonst bräuchte man ihn in der Vorlesung ja garnicht behandeln, wenn es nicht wichtig genug wäre, um es zu prüfen. Nur so als ganz allgemeiner Tip.