DNF zu KNF Nötig für Klauselform?

[Aventuri (Gast)]

Hallo Forum!

ich weiß, morgen ist Weinachten ^^ aber das lässt mich momentna nicht 
los.
Ich habe hier eine Übungsaufgabe in der ich eine Formel in Klauselform 
bringen soll. Ist ja eigentlich recht banal, wenn sie in KNF wäre:

Wie in Beispiel 1:
http://de.wikipedia.org/wiki/Klausel-Normalform


Allerdings ist meine Formel in DNF.
Jetzt frage ich mich, wie ich einfach eine Formel von DNF in KNF bringen 
kann (und ob das überhaupt nötig ist?)

Weiß das jemand?

Frohes Weinachtsfest :-) !

[Falk S. (falkschilling)]

Aventuri schrieb:
> Allerdings ist meine Formel in DNF.
> Jetzt frage ich mich, wie ich einfach eine Formel von DNF in KNF bringen
> kann (und ob das überhaupt nötig ist?)

Wahrheitswertabellen oder Umformungsregeln (DeMorgan und Co.) verwenden. 
Und vorher versuchen, zu vereinfachen soweit möglich (Quine/McCluskey).

Frohe Weihnachten!

[Davis (Gast)]

Aventuri schrieb:

> ich weiß, morgen ist Weinachten ^^ aber das lässt mich momentna nicht
> los.

Weihnachten ist übermorgen.

[Aventuri (Gast)]

@FALK

Danke für die rasche Antwort.

Eine Klauselform lässt sich nicht aus einer Formel in DNF bilden?

[Bushmaster (Gast)]

DNF ist disjunktive Normalenform

KNF ist konjunktive Normalenform

Schreib die Wahrheitstaballe mit der DNF auf.

Dann muss man die Product of Sums erstellen.

Das heisst man muss die Literale, wo z=0 ist, betrachten. Diese muss man 
für jede Zeile invertiert ODER-Verknüpfen und jede dieser Summen aus 
jeder Zeile UND-Verknüpfen.

[Bushmaster (Gast)]

Wundere mich aber, dass Du bei der sehr abstrakten Klauselform 
angekommen bist, ohne die einfachen und grundlegenden Dinge verstanden 
zu haben.

[Logikfuzzi (Gast)]

Auf Anhieb fallen mir folgende Dinge zu dem Post ein:

- DeMorgan
- blöd rumrechnen
- Um Himmels Willen keine Wahrheitstabellen, ab 4 Literalen erkennt man 
daraus nicht wirklich viel
- OBDDs
- KV-Diagramme, gibt dir sogar die minimale KNF bzw. DNF
- Tseitin Transformation
- charakteristische Funktion aufstellen, um dann wieder blöd 
rumzurechnen

[Aventuri (Gast)]

Hallo, vielen Dank schonmal.

hab mir das Grundwissen jetzt nochmal angeeignet. Komme aber bei einem 
Punkt nicht weiter.

Angenommen in meinem KNF kommt u.a folgende Disjunktion  (~B v B). Wenn 
ich die die KNF Formel in Klauselform bringen muss, lasse ich diese 
Disjunktion dann weg ? Weil {~B , B} als Klauselform würde ja nicht viel 
Sinn machen oder?

Danke !