View Full Version : [Frage] 8.3
Mr.Anderson
19-05-2004, 15:06
Was ist das Deduktionstheorem, bzw. wo im Skript steht da was darüber???
Auf welche Klauselmenge kommts ihr? Ich komme schon hier auf einen Widerspruch, weil bsp.weise sowohl {b} als auch {!b} enthalten sind.
Herleitung eurer Klauselmenge wäre super! :verycool:
mfg Piet
Septic.exe
22-05-2004, 14:43
Das mit dem Deduktionstheorem is mir auch nicht ganz klar ....
Kugelfisch
22-05-2004, 16:43
Deduktionstheorem siehe Skript S. 71. Satz 3.27
Cassandra
22-05-2004, 17:01
Ich komm auf folgende Klauselmenge:
{{A, !B, !C}, {!B, C}, {B, !C}, {!D, C}, {D}, {!A}}
Die Herleitung kann ich vielleicht später posten, wenn ich mehr Zeit habe ;)
Veronika
22-05-2004, 18:53
Ich komm auf folgende Klauselmenge:
{{A, !B, !C}, {!B, C}, {B, !C}, {!D, C}, {D}, {!A}}
Die Herleitung kann ich vielleicht später posten, wenn ich mehr Zeit habe ;)
Gibt jetzt die Resolution aus {B, !C} und {!B,C} eigentlich gleich die leere Menge und ist das gleich die Resolutionswiderlegung?
Cassandra
22-05-2004, 19:11
Gibt jetzt die Resolution aus {B, !C} und {!B,C} eigentlich gleich die leere Menge und ist das gleich die Resolutionswiderlegung?
Nein, die Resolution würde je nachdem welche Variable du resolvierst entweder {!C, C} oder {B, !B} ergeben. Das wären beides Tautologien und somit sicher nicht nötig zur Resolutionswiderlegung.
Hier meine Lösung, bei Teil 3 bin ich mir nicht sicher, ob ich die Frage richtig verstanden hab, aber würd es so lösen (also zeigen, dass diese Klauselmenge durch keine Variablenbelegung erreichbar ist).
Ich war zu faul, es mittels Tableau oder wasauchimmer-kalkül zu machen, aber die paar logischen Implikationen sollten doch eh reichen?
lG,
Murmel
edit: ist durch die Verkleinerung ein bisschen unleserlich geworden, aber ich hoffe es geht
edit 2: hab jetzt erst das Resolutionskapitel im Skriptum entdeckt und damit Punkt 3 gecheckt, der stimmt so wie er hier steht also nicht. Der Rest sollte aber passen.
edit 3 (vielleicht sollte ich erst rechnen, und dann posten, dann gäbs nicht soviele edits, aber egal :D ) habs jetzt. Ich würd den 3er folgendermassen lösen.
Unsere Klauselmenge:
1.{!A}
2.{A, !B, !C}
3.{D}
4.{!D, C}
5.{!B, C}
6.{B, !C}
Aus 1&2 folgt:
7. {!B, !C}
Aus 3&4:
8. {C}
Aus 6&7:
9. {!C}
Aus 8&9:
10. {}
-> unerfüllbar
könnte man das ganze auch nicht mit einer Wahrheitstabelle lösen? Da hab ich dann nur 2 KNF's:
{A,!B,!C,!D} und {A,B,C,!D}
und wenn ich hier die Resolution anwende, erhalte ich zum Schluss auch die Leere Menge.
Denk schon, steht ja nicht explizit da, wie mans in die KNF bringen soll.
lG,
Murmel
@ murmel
also ich stimme dir bei deinem file beim zweiten Unterpunkt bis Zeile 7 zu. Aber ab Zeile 8 versteh ich nicht ganz, wie du aus
((!B v !C) n (B v C)) diesen Ausdruck bekommst: (B n !C)v(!B n C)
:confused:
aus
((!B v !C) n (B v C)) diesen Ausdruck bekommst: (B n !C)v(!B n C)
:confused:
hab da der Geschwindigkeit halber ein paar Schritte übersprungen:
((!B v !C) n (B v C)) ergibt
(!B n B) v (!B n C) v (!C n B) v (!C n C)
ergibt f v (!B n C) v (B n !C) v f
und (f v A) ergibt bekanntlich A, deshalb kann man die streichen
alles klar?
lG,
Murmel
*_konkreeet_*
23-05-2004, 16:41
Unsere Klauselmenge:
1.{!A}
2.{A, !B, !C}
3.{D}
4.{!D, C}
5.{!B, C}
6.{B, !C}
Aus 1&2 folgt:
7. {!B, !C}
Aus 3&4:
8. {C}
Aus 6&7:
9. {!C}
Aus 8&9:
10. {}
-> unerfüllbar
warum nimmst du nicht 5 & 7: {!B} ?
warum nimmst du nicht 5 & 7: {!B} ?
Stimmt, das wär wohl auch eine Möglichkeit, die Klauseln hier reichen aber auch für den Beweis, ich sag ja nicht, dass es die einzige Art ist, das Bsp zu lösen.
lG,
Murmel
*_konkreeet_*
23-05-2004, 16:48
ich frag nur, weil ich s nicht verstanden hab :thumb:
aso :D
naja, wie gesagt, diese Beweisführung funktioniert auch ohne diese Klausel.
lG,
Murmel
@ murmel:
danke, checks scho, brauch halt a bisi länger :p
und wie soll ich nun das Deduktionstheorem anweden. ich hab ja nur diesen einen Satz im Skriptum.
kP, war ja wie gesagt auch nicht ganz ausformuliert.
Das Deduktionstheorem hilft ja eh nur, um aus der ersten Zeile im File die zweite zu machen, also um von der logischen Konsequenz auf die Formel zu kommen.
lG,
Murmel
nautiLus
23-05-2004, 20:31
Unsere Klauselmenge:
1.{!A}
2.{A, !B, !C}
3.{D}
4.{!D, C}
5.{!B, C}
6.{B, !C}
Aus 1&2 folgt:
7. {!B, !C}
Aus 3&4:
8. {C}
Aus 6&7:
9. {!C}
Aus 8&9:
10. {}
-> unerfüllbar
Hallo, ich hab dazu mal eine Frage:
Damit ich eine entsprechende Resolutionswiderlegung gefunden habe, muss eine {} rauskommen... Klar.
Aber was muss ich alles dazu verwenden? Muss ich dazu jeden einzelne {..} aus der Klauselmenge mind. 1 mal benutzen oder kann ich auch mehrmals ein und dasselbe verwenden -> Hauptsache es kommt die leere Menge raus?
Ciao Nauti
Du musst nicht alle Klauseln verwenden, kannst jede sooft verwenden, wie du willst und brauchst nicht alle möglichen Klauseln finden (zumindest nicht, wenn es darum geht, die Unerfüllbarkeit zu beweisen, bei der Erfüllbarkeit muss man denk ich schon alles hinschreiben)
-> Hauptsache es kommt die leere Menge raus.
lG,
Murmel
nautiLus
23-05-2004, 20:48
Ok, danke dir!
Ciao Nauti
edit:
Unsere Klauselmenge:
1.{!A}
2.{A, !B, !C}
3.{D}
4.{!D, C}
5.{!B, C}
6.{B, !C}
d.h. wenn ich jetzt 5&6 nehme kommt {} heraus: bewiesen?
d.h. wenn ich jetzt 5&6 nehme kommt {} heraus: bewiesen?
Nein, weil du darfst nicht 2 oder mehr Variablen gleichzeitig nehmen, immer nur eine, siehe dazu auch den anderen Thread (ich glaub 8.4 war das), den Fehler hab ich am Anfang auch gemacht.
lG,
Murmel
nautiLus
23-05-2004, 21:14
Oh, naja beim 4 war ich noch nicht :)
Danke, jetzt ists mir klar!
Nauti
:distur:
hi, wo ist das attachment hin?? wo ist die lösung für 1. und 2. ? *panik*
ganz ruhig :)
ist eh noch da
thx, mein browser hats irgendwie nicht angezeigt :D
falsche bemerkung gelöscht.
Wie geht man an die Resolutionswiderlegung heran?
@Deduktionstheorem
das versteh ich überhaupt nicht, der karge satz im skriptum ist nicht sehr hilfreich ...
könnte sich jemand erbarmen und erklären, WAS das bedeutet (die formel lesen kann ich eh, ist halt nur sehr abstrakt ...)
bzw. wie das in zus.hang mit dem aufstellen der aussage für dieses bsp. zu betrachen ist
einfach nur das folgerungssymbol zu A hinzeichnen wird dem tutor vielleicht doch nicht reichen (mir an sich schon *g*)?
thx, maxi
Wie gesagt, ich denke, das Deduktionstheorem besagt im Grunde genommen nur, dass man von
A, B, C |= D
auf
A^B^C ) D
(Das ")" soll ein Impliziert sein)
kommt
(im Allgemeinen mit sovielen oder so wenigen Variablen auf der linken Seite, wie man will)
In Zusammenhang mit diesem Beispiel halt, wie man von Zeile 1 auf Zeile 2 kommt.
lG,
Murmel
Hallo an alle,
Wie kommt man bei der Klauselmenge auf die Ausdrücke {!B,C} , {B,!C}
Ist das die Auflösung von B Nexor C ? Nach welcher Regel löst man den Ausdruck(B=C) i.d. Formel auf?
Lg Isabella
Nach welcher Regel löst man den Ausdruck(B=C) i.d. Formel auf?
(B=C) = (B^C)v(!B^!C)
s. Skriptum S. 73
lG,
Murmel
Wie kommt man bei der Klauselmenge auf die Ausdrücke {!B,C} , {B,!C}
Ist das die Auflösung von B Nexor C ? Nach welcher Regel löst man den Ausdruck(B=C) i.d. Formel auf?
Wenn du B Nexor C in DNF-Schreibweise auflöst erhältst du: (B AND C) OR (!B AND !C).
In KNF-Schreibweise erhältst du: (B OR !C) AND (!B OR C).
Das kannst du ganz leicht erkennen, wenn du dir die Wahrheitstabelle anschaust und die DNF bzw. KNF gemäß Skriptum S.75 herleitest.
Mr. Bringer
25-05-2004, 03:12
Unsere Klauselmenge:
1.{!A}
2.{A, !B, !C}
3.{D}
4.{!D, C}
5.{!B, C}
6.{B, !C}
Aus 1&2 folgt:
7. {!B, !C}
Aus 3&4:
8. {C}
Aus 6&7:
9. {!C}
Aus 8&9:
10. {}
-> unerfüllbar
Frage : Reichts wenn man das so hinschreibt ???
Jo denk schon.
lG,
Murmel
meine Lösung........
lg
kambo
Mr. Bringer
25-05-2004, 14:05
richtiger lösungsweg?
(1) { A, !B, !C }
(2) { B, !C }
(3) { !B, C }
(4) { C, !D }
(5) { D }
(6) { !A }
aus (1)&(2)
(7) { A, !C }
aus (4)&(5)
(8) { C }
aus (7)&(8)
(9) { A }
aus (6)&(9)
(10) { }
somit !F unerfüllbar --> F ist gültig
richtiger lösungsweg? muss/soll man nicht alle Klauseln anwenden???
Superwinki
26-05-2004, 00:05
Hmm, dazu find ich auch nichts im Skriptum. Also nochmal: Muss man jetzt alle Klauseln anwenden, oder nicht??
In Beispiel 3.59 S. 91 kommt Klausel 6 ja auch nicht zum Einsatz...
meagain02
26-05-2004, 13:50
Hallo Leute,
Kann ich auch bei der Eliminierung alle Klauseln anschreiben o. lässt man die, die einen nicht weiter bringen weg?
1 {!B, !C, A}
2 { B, !C}
3 {!B,C }
4 {!D,C}
5 {!D}
6 {!A}
7 { !B, A} aus 1,2 // 7 & 8 welche aus welchen klauseln eliminiert wurde war vertauscht
8 {B} aus 2,3
9 {C} aus 4,5
10 {!B, !C} aus 1,6
11 {!C} aus 10,8
12 {} leere Klausel aus 11,10 ; damit ist die unerfüllbarkeit gezeigt
Mfg
@meagain02
ehrlich gesagt verstehe ich gaaaaaar nicht , was Du hier geschrieben hast!! Wie hast du zB. {!B, A} von 2,3 abgeleitet??
Superwinki
26-05-2004, 15:29
In dem Moment, wo man die leere Klausel herleiten kann, hat man "gewonnen". Ansonsten muss man alle möglichen Kombinationen ausprobieren (wie beim 4. Beispiel notwendig). Daher heißt es ja, dass die Resolution in endlich vielen Schritten ein Ergebnis liefert...
Wenn man auch nach allen möglichen Kombinationen keine leere Klauselmenge herleiten kann, ist die Klauselmenge gültig --> da verneint die Folge an Formeln ungültig
vBulletin® v3.7.1, Copyright ©2000-2009, Jelsoft Enterprises Ltd.