Diskussion:Konjunktive Normalform

Zum Archiv

Wie wird ein Archiv angelegt?

Automatische Archivierung

Auf dieser Seite werden Abschnitte halbmonatlich automatisch archiviert, wenn sie mit {{Erledigt|1=--~~~~}} markiert sind. Um die Diskussionsseite nicht komplett zu leeren, verbleibt mindestens ein Abschnitt.

KV-Diagramm

Will man die minimale KNF bilden, so kann man dies etwa mithilfe von Karnaugh-Venn-Diagrammen (kurz KV-Diagrammen) tun.

Das ist AFAIK falsch, weil es keinen Algorithmus gibt, um im Karnaugh-Diagramm die "richtigen" Rechtecke zu bestimmen (so dass möglichst wenige, möglichst große Rechtecke gewählt werden). --Head 12:19, 15. Okt 2004 (CEST)

Doch, das ist wahr.

Durch das KV - Diagramm erhält man die DNF bzw. KNF, es ist zwar kein eindeutige, aber eine minimale Darstellung (wenn man es richtig macht ;)

cya max

Und wie macht man es "richtig"? (Ohne sämtliche Möglichkeiten durchzuprobieren) --Head 18:25, 20. Jul 2005 (CEST)

Mit dem KV-Diagramm! :-)

Alternativ auch zu Fuß oder mit Quine-Mcklusky.

Beispiel zu Fuß:

$y={\bar {x_{2}}}x_{1}{\bar {x_{0}}}\vee {\bar {x_{2}}}x_{1}x_{0}\vee x_{2}{\bar {x_{1}}}x_{0}\vee x_{2}x_{1}x_{0}$

${\bar {x_{2}}}x_{1}{\bar {x_{0}}}\vee {\bar {x_{2}}}x_{1}x_{0}$ läßt sich zu ${\bar {x_{2}}}x_{1}$ vereinfachen.

${\bar {x_{2}}}x_{1}x_{0}\vee x_{2}x_{1}x_{0}$ läßt sich zu $x_{1}x_{0}$ vereinfachen

$x_{2}{\bar {x_{1}}}x_{0}\vee x_{2}x_{1}x_{0}$ läßt sich zu $x_{2}x_{0}$ vereinfachen

mehr vereinfachen geht nicht.

Der Min-Term lautet demzufolge: ${\bar {x_{2}}}x_{1}\vee x_{1}x_{0}\vee x_{2}x_{0}$

Mit dem KV-Diagramm lässt sich das Ganze einfach ablesen. --Arbol01 18:52, 20. Jul 2005 (CEST)

Nachtrag: Bei drei oder vier Variablen kann man die Bestimmung des Minterms noch sehr gut zu Fuß machen. Aber bei z.B. 8 Variablen wird das Ganze unübersichtlich, und KV-Diagramm bzw. Quine-Mcklusky werden unerläßlich. --Arbol01 19:03, 20. Jul 2005 (CEST)

Zweiter Nachtrag: Wir reden hier von Grundlagen der Informatik, erstes Semester. --Arbol01 19:04, 20. Jul 2005 (CEST)

hier nochmal max bin student der Informatik, 1. Semester, gerade eine klausur über dieses thema geschrieben ^^

Was soll die Aussage besagen? --Arbol01 00:18, 22. Jul 2005 (CEST)

Mein Beispiel war übrigens eine DNF und keine KNF. Aber die DNF liegt mir nun mal mehr. Ex-Student der Informatik. --Arbol01 00:20, 22. Jul 2005 (CEST)

@Arbol01:, @Head: Ich habe gerade das Verfahren von Quine und McCluskey im Artikel unter 'Bildung' erwähnt. Ist diese Diskussion damit erledigt? --Martin Thoma 10:45, 14. Nov. 2014 (CET)

Definition nicht ganz richtig

Hi

Die Definition muss um den Aspekt der Vollständigkeit erweitert werden. Eine KNF besteht aus konjunktiv verknüpften Maxtermen, also aus Termen die vollständig sind, d.h. jedes Literal in dem Maxterm muss genau einmal darin vorkommen.

Grüße síkhs

Sorry, versteh ich nicht! Was bitte ist ein Maxterm? Im Beispiel von 3-SAT sehe ich kein Literal mehrfach in einer Disjunktion? --Koethnig 16:21, 30. Dez. 2007 (CET)

Ich wollte schon schreiben, dass síkhs Unrecht hat, und dass die Definition im Artikel der üblichen entspricht. Ein paar Stichproben, z. B. [1], [2] und [3] oder auch der englische WP-Artikel scheinen das zu stützen.

Dann fing ich an, in den Unterlagen meines Informatik-studierenden Sohnes zu stöbern, und finde in Klaus Beuth: Digitaltechnik, ISBN 9783802319587, auf S. 78 eine Definition, die der síkhs'schen entspricht. In [4] wird diese enger gefasste Normalform die kanonische konjunktive Normalform genannt.

Offenbar scheiden sich die Geister. M. E. ist die in dem Artikel verwendete Definition die üblichere und kann so stehen bleiben.

@Koethnig: síkhs Beschreibung eines Maxterms ist korrekt. Beuth nennt die Maxterme Volldisjunktionen und beschreibt denselben Sachverhalt so: „Unter einer Volldisjunktion versteht man eine ODER-Verknüpfung, in der alle vorhandenen Variablen einmal vorkommen - entweder negiert oder nicht negiert.“ (a.a.O.) - Wird es damit klar?

Gruß --Mussklprozz 23:47, 30. Dez. 2007 (CET)

Hi nochmal,

wie ich sehe, ist der Artikel hier --> http://de.wikipedia.org/wiki/Disjunktive_Normalform ein wenig vollständiger, da dort die kanonische Normalform erwähnt wird :-)

Grüße síkhs

Ei, dann machen wir uns das fix zunutze und bauen es mutatis mutandis in den Artikel ein. Danke für den Hinweis! --Mussklprozz 19:48, 2. Jan. 2008 (CET)

Berechnung der KNF ohne Wahrheitstafel

Es sollte beschrieben werden, wie die KNF ohne Wahrheitstafel berechnet werden kann.

Für die DNF gibt es die Shannon-Zerlegung (kenne ich als "Entwicklungssatz von Shannon", ich glaube das ist das Gleiche). Gibt es etwas ähnliches für die DNF?

Grüße, --Martin Thoma 10:24, 14. Nov. 2014 (CET)

Ah, ich glaube folgendes Funktioniert:

1. Formel $F$ negieren: $\neg F$

2. Shannon-Zerlegung auf $\neg F$ anwenden um ${\tilde {F}}$ (in DNF) zu erhalten

3. ${\tilde {F}}$ nochmals negieren.

Grüße, --Martin Thoma 10:47, 14. Nov. 2014 (CET)