Konjunktive in Disjunktive Normalform umwandeln |
| 03.07.2011, 00:34 | Der constrainte Hans | Auf diesen Beitrag antworten » | ||
| Konjunktive in Disjunktive Normalform umwandeln Ich rätsel jetzt schon Tage über die Konvertierung zwischen DNF und KNF. Klar, die üblichen Methoden wie Wahrheitstabelle bilden oder KV-Diagramm nutzen etc. sind mir klar, aber was gibt es für weitere Techniken? Generell gibt's ja noch DeMorgan, da bin ich mir aber nicht sicher, ob das immer funktioniert. Zumindest gibt's Quellen, die sowas behaupten. Und vor allem meine Frage: Mit welchem Aufwand ist die Umwandlung möglich? Ich vermute fast, dass das ein NP-vollständiges Problem ist, bin mir aber überhaupt nicht sicher. Und dummerweise finde ich nirgends im Netz eine sinnvolle Angabe, wie das denn nun so ist, und auch mit Beispiel-Umwandlungen tut sich nicht viel. Meine Ideen: Das 3-SAT-Problem ist ja NP-vollständig und wird als KNF formuliert. Wäre es jetzt möglich, eine KNF mit weniger als dem NP-Aufwand in eine DNF zu konvertieren, hätte man ja eine effiziente Lösungsmöglichkeit gefunden, da aus der DNF die Lösungsmenge direkt ablesbar ist (ein einzelner Term = eine Lösung). |
||||
| 03.07.2011, 18:36 | Abakus | Auf diesen Beitrag antworten » | ||
| RE: Konjunktive in Disjunktive Normalform umwandeln Hallo, lassen sich die Max- und Minterme da nicht einfach ablesen? Abakus 
|
||||
| 03.07.2011, 19:58 | dc Hans | Auf diesen Beitrag antworten » | ||
Hallo, die Min- und Maxterme lassen sich bspw. aus der Wertetabelle direkt ablesen. Wenn ich jetzt allerdings nur eine bspw. KNF habe, ist es entsprechend aufwändig, eine Wertetabelle zu erstellen (exponentielles Wachstum). Daher meine Frage, ob (und wenn ja: wie) das schneller geht. Liebe Grüße Hans |
||||
| 03.07.2011, 21:41 | Abakus | Auf diesen Beitrag antworten » | ||
Wenn du eine KNF mit Maxtermen hast, liest du die der Reihe nach durch und streichst für jeden Maxterm den entsprechenden Minterm durch, die übrigbleibenden Minterme bilden dann die DNF. ZB: du hast die KNF , die aus einem einzigen Maxterm besteht. Der wird nur dann 0, wenn alle 3 Variablen Null sind. Also ist sofort klar, welcher Minterm in der DNF fehlen muss, nämlich derjenige, der die Belegung 0 0 0 zu einer 1 macht. Die DNF besteht also aus 7 Mintermen, dieser hier ist der einzige der fehlt: . Abakus
|
||||
| 03.07.2011, 22:38 | dc Hans | Auf diesen Beitrag antworten » | ||
Für jeden Maxterm den Minterm durchstreichen entspricht ungefähr dem Bilden einer Wertetabelle, d. h. exponentieller Aufwand. Und vor allem: Wie sieht es aus, wenn es keine kanonische Normalform ist, also irgendwelche Terme, nur nicht Min- und Max-? Also bspw. sowas: (x v z) ^ (x v !y) ^ (!y v !z) Wie gesagt: Die Theorie mit dem Umwandeln über Wertetabellen etc. ist nicht das Problem, mir geht's um den Zeitaufwand bzw. die praktische Umsetzung in kurzer Zeit. |
||||
| 03.07.2011, 23:27 | Abakus | Auf diesen Beitrag antworten » | ||
Was erwartest du denn für ein Verfahren? Die KNF kann ja - bei n Variablen - aus bis zu Maxtermen bestehen. Die musst du alle einlesen, um die KNF überhaupt zur Kenntnis zu nehmen. Ohne das wird es kaum gehen, und damit arbeitet das Verfahren in linearer Zeit abhängig von der Anzahl der Maxterme dann.
Hier wirst du auch alle Terme erstmal lesen müssen, denke ich. Abakus
|
||||
| Anzeige | ||||
|
|
||||
| 04.07.2011, 00:35 | dc Hans | Auf diesen Beitrag antworten » | ||
Keine Ahnung
Irgendwie könnte es ja mit DeMorgan auch funktionieren (ist mir noch nicht gelungen) oder auch was völlig anderes. Oder ich krieg eine definitive Ansage, dass das Umwandeln zwischen beiden definitiv nur mit exponentiellem Aufwand möglich ist - was ich ja zumindest vermute.Ansonsten erst mal Danke für deine Hilfe bei meinem Rätselraten
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
