Lexikon der Mathematik: Quine-McCluskey, Methode von
Verfahren zur Berechnung der Menge der Primimplikanten einer vollständig definierten Booleschen Funktionf : {0, 1}
Die Methode beruht auf dem Satz von Quine, der die Implikanten einer Booleschen Funktion f charakterisiert:
EinBoolesches Monom q ∈ 𝔄n (Boolescher Ausdruck) ist genau dann ein Implikant von f, wenn entweder q ein Minterm von f ist, oder
\begin{eqnarray}\begin{array}{cc}q\cdot {x}_{i} & und & q\cdot \overline{{x}_{i}}\end{array}\end{eqnarray}
Implikanten von f sind für eine Variable xi (1 ≤ i ≤ n), die in q weder als positives noch als negativesBoolesches Literal vorkommt.
Die Methode von Quine-McCluskey startet mit der Menge aller Minterme der Booleschen Funktion f, für die die Primimplikanten bestimmt werden sollen, und kürzt gemäß dem zweiten Punkt der angegebenen Charakterisierung diese Implikanten zu kleineren Implikanten. Die Implikanten, die nicht verkürzt werden können, sind die Primimplikanten von f.
Die Methode von Quine-McCluskey ist eine Spezialisierung der Methode des iterierten Konsensus.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.