Frage zu negierter KNF (AL)

Erich
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 17. Okt 2010 13:29

Frage zu negierter KNF (AL)

Beitrag von Erich » 1. Sep 2011 13:55

Seien C und D Klauseln.

Nun habe ich eine Formel in der Form !(C && D).

Wie soll ich so etwas in eine für das Resolutionskalkül brauchbare Form bringen?

fscheepy
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 153
Registriert: 14. Dez 2009 21:17

Re: Frage zu negierter KNF (AL)

Beitrag von fscheepy » 1. Sep 2011 13:59

Ein solcher Fall ist mir bisher noch nicht untergekommen, normalerweise kann man da so weit "kürzen/ausmultiplizieren", dass eine KNF herauskommt. Hast du mal ein Beispiel aus einer konkreten Aufgabe?

eintopf
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 25. Aug 2011 17:41

Re: Frage zu negierter KNF (AL)

Beitrag von eintopf » 1. Sep 2011 14:07

Eine brutale Methode wäre einfach die Wertetabele zu der Formel !(C && D) aufzustellen und dann daraus KNF zu bilden.

Erich
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 17. Okt 2010 13:29

Re: Frage zu negierter KNF (AL)

Beitrag von Erich » 1. Sep 2011 14:11

FgdI2-Klausur WS 07/08.

wir müssen

1.) phi := (q && r) || !( p || q || r)

2.) !psi, wobei psi := (!p && ( r -> q)) || (p && q && r))

in KNF bringen, wobei bei phi das Problem die ODER-Verknüpfung in der Mitte ist:

( a || b) == !(!a && !b), und nach dem ich bei phi habe ich dann !( (!q || !r) && ( p || q || r) )

ich halte mich eigentlich strikt an die regeln, wo ist also der Fehler?

fscheepy
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 153
Registriert: 14. Dez 2009 21:17

Re: Frage zu negierter KNF (AL)

Beitrag von fscheepy » 1. Sep 2011 14:31

eintopf hat geschrieben:Eine brutale Methode wäre einfach die Wertetabele zu der Formel !(C && D) aufzustellen und dann daraus KNF zu bilden.
Wie erstellt man aus einer Wertetabelle denn die KNF? Lässt sich daraus nicht nur die DNF ablesen? Ist die Klauselform denn überhaupt das gleiche wie eine KNF, nur in Mengenschreibweise?
Erich hat geschrieben:FgdI2-Klausur WS 07/08.

wir müssen

1.) phi := (q && r) || !( p || q || r)

2.) !psi, wobei psi := (!p && ( r -> q)) || (p && q && r))

in KNF bringen, wobei bei phi das Problem die ODER-Verknüpfung in der Mitte ist:

( a || b) == !(!a && !b), und nach dem ich bei phi habe ich dann !( (!q || !r) && ( p || q || r) )

ich halte mich eigentlich strikt an die regeln, wo ist also der Fehler?
Kannst du statt && vielleicht ^ verwenden und außerdem statt || lieber v? Das ist besser lesbar:

1.) phi := (q ^ r) v !( p v q v r)

2.) !psi, wobei psi := (!p ^ ( r -> q)) v (p ^ q ^ r))

Dann kannst du phi schreiben als

(q ^ r) v (!p ^ !q ^ !r)

und jetzt das Distributivgesetz anwenden

(q ^ r ^ !p) v (q ^ r ^ !q) v (q ^ r ^ !r)

hierbei sind die letzten beiden Glieder je stets falsch, also bleibt übrig

q ^ r ^ !p

was sowohl in KNF als auch in DNF ist. Die Frage bleibt offen, was genau eine Klauselform ist? Die Klauselform hätte ich geschrieben als:

{{q},{r},{!p}}

aber keine Ahnung, wonach genau gefragt war...ich hoffe nur, ich habe keines der Gesetze falsch angewendet :|
Zuletzt geändert von fscheepy am 1. Sep 2011 15:11, insgesamt 1-mal geändert.

Erich
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 17. Okt 2010 13:29

Re: Frage zu negierter KNF (AL)

Beitrag von Erich » 1. Sep 2011 14:50

gut danke^^ aber wie siehts jetzt mit psi aus? Ich steh total aufm Schlauch :?

Edit:

Achso, und wenn ein Minterm also automatich KNF und DNF zugleich ist, kann man selbiges also auch über Maxterme sagen?

sprich: C von (p v q v r) = {p, q, r}?

fscheepy
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 153
Registriert: 14. Dez 2009 21:17

Re: Frage zu negierter KNF (AL)

Beitrag von fscheepy » 1. Sep 2011 15:20

2.) !psi, wobei psi := (!p ^ ( r -> q)) v (p ^ q ^ r))
hier hatte ich einen Fehler drinnen, habs schon editiert :o

!psi : = !((!p ^ ( r -> q)) v (p ^ q ^ r))

umformen zu

!((!p ^ ( !r v q)) v (p ^ q ^ r))

Negation reinziehen:

(p v ( r ^ !q)) ^ (!p v !q v !r)

Distributivgesetz

((p v r) ^ ( p v !q)) ^ (!p v !q v !r)

Klammer entfernen

(p v r) ^ ( p v !q) ^ (!p v !q v !r)

da haben wir also schon unsere KNF und die Klauselform müsste sein

{{p, r}, {p, !q}, {!p, !q, !r}}

Anzumerken bleibt, dass ich bisher nicht von offizieller Seite weiß, ob das wirklich der richtige Lösungsweg bzw. die (formal) richtige Lösung ist. Hab das aber alles nach bestem Wissen und Gewissen bearbeitet :D

@Edit: was ist ein Minterm/Maxterm? :oops: Literale, die nur mit Konjunktionen bzw. nur mit Disjunktionen verknüpft sind? Die sind meiner Meinung nach sowohl in DNF als auch KNF (war bei einem Übungsblatt auch im Miniquiz).

Antworten

Zurück zu „Archiv“