Konjunktive / Disjunktive Normalform
-
Hallo zusammen,
kann mir jemand den praktischen Nutzen der konjunktiven und der disjunktiven Normalform sagen? Was bringt es mir, einen logischen Term in eine dieser Normalformen umzuwandeln?
Vielen Dank
lg, freakC++
-
freakC++ schrieb:
kann mir jemand den praktischen Nutzen der konjunktiven und der disjunktiven Normalform sagen? Was bringt es mir, einen logischen Term in eine dieser Normalformen umzuwandeln?
Mir bringt es Übersicht.
Bei (A∧B∧C)∨(B∧-C)∨D
sehe ich gleich die erlaubten Belegungen.
(Fragezeichen sei Platzhalter für beliebigen Wert)
111?
?10?
???1Und eine Schaltung dafür zu basteln geht auch wunderbar geradlinig. So ohne Nachdenken zu müssen. Und sie ist hübsch begrenzt auf drei Ebenen (falls ich Gatter mit viel genugen Eingängen habe), da kann ich mich auf die Schaltgeschwindigkeit verlassen.
-
Mann kann die Formeln brauchen für das Erfüllbarkeitsproblem und für das Tautologieproblem. Wenn ich gerade nicht falsch überlege:
KNF:
Mit der KNF Formel kann man effizent entscheiden, ob eine Formel eine Tautologie ist. Eine KNF Formel ist Tautologie genau dann, wenn jede Klausel Tautologie ist.DNF:
Das Erfüllbarkeitsproblem für DNF kann effizient berechnet werden. Eien DNF-Formel ist erfüllbar genau dann, wenn mindestens eine der Klauseln erfüllbar ist.(Bin mir jetzt nicht 100% sicher, ob das stimmt. Ich weiss es nicht mehr auswendig und kann sein, das ich gerade etwas falsch überlegt habe. Falls ja, korrigiert mich bitte).
Wenn man eine Wahrheitstabelle gegeben hat, kann man sehr einfach logische Formeln aus der Tabelle herleiten.
Für alle Zeilen, die am Ende "True" ergeben, kann man die Teilformeln als DNF schreiben.
Für alle Zeilen, die am Ende "False" ergeben, kann man die Teilformeln als KNF schreiben.Hat viele Anwendungen. Ich habs z.B. mal in der Digitaltechnik gebraucht.
Die Resolution basiert auf der KNF-Form.
Hornformeln basieren auf der KNF.
-
volkard schrieb:
Und sie ist hübsch begrenzt auf drei Ebenen (falls ich Gatter mit viel genugen Eingängen habe), da kann ich mich auf die Schaltgeschwindigkeit verlassen.
Warum?
-
freakC++ schrieb:
volkard schrieb:
Und sie ist hübsch begrenzt auf drei Ebenen (falls ich Gatter mit viel genugen Eingängen habe), da kann ich mich auf die Schaltgeschwindigkeit verlassen.
Warum?
Die Einzelterme haben keine Abhängigkeiten zueinander. Also können sie gleichzeitig/auf der gleichen Ebene ausgewertet werden. Die zweite Ebene ist dann einfach das Verunden/Verodern aller dieser Einzelergebnisse. Drei Ebenen sind es dann wohl je nachdem ob man die Eingänge noch negieren muss.
-
Es gibt auch noch (mindestens) einen weiteren, sehr praktischen Aspekt. Bei manchen Problemen bekommt man wirklich große SAT-Formeln, und möchte wissen ob diese erfüllbar sind. Es gibt einige Spezialprogramme, sogenannte SAT-solver, die sowas können (und zwar oft erstaunlich schnell), die meisten von denen fressen aber nur Formeln in KNF, man muß seine Formel also erst umwandeln.
-
Ok, danke! Ich habe mich gefragt, wie ich eine DNF in einer KNF umwandle. Ich dachte zuerst daran, einfach eine Wahrheitstabelle zu erstellen und dann für die Zeilen, die 0 ergeben, eine Disjunktion zu erstellen, um sie danach konjunnktiv zu verknüpfen. Geht das denn auch, wenn der Term bereits in einer DNF ist. Durch Zufall ist mir aufgefallen, dass ich durch Umformen auch die KNF erhalte. Ich nehme mal den Term aus meinem anderen Thread:
Ich habe den Teil rechts neben dem ODER durch D substituiert:
Nun wende ich das Distributivgesetz an und resubstituiere danach. Dann kann ich nochmals zweimal das Distributivgesetz anwenden und ich erhalte einen viel längeren Term, der aber das Muster einer KNF hat. Ist dieses Vorgehen hier ein Zufall oder funktioniert das immer? Substituieren, "ausmultiplizieren" und resubstituieren?
Vielen Dank
lg, freakC++
-
Ja, durch anwenden des Distributivgesetzes lässt sich jede DNF in eine KNF und umgekehrt umformen. Wozu Du da noch substituierst ist mir schleierhaft. (Soll das übersichtlicher sein? Mich verwirrts nur...)
-
Für mich ist das übersichtlicher und es kommen weniger Fehler rein.
-
bevor ein eigenes Unterforum speziell für deine Übungsaufgaben eröffnet werden muß, ein Buchtip für dich zu Ostern:
Sauer/Krupstedt, Informatik für Ingenieure (Teubner-Studienskripten), Teubner, 1985.
Da steht wunderbar anschaulich mit sehr vielen Beispielen Grundlegendes über Boole'sche Algebra, Codierung, Informationstheorie, Schaltnetze und -Werke inkl Flipflops, Automaten u.v.a.