Direkt zum Inhalt

Lexikon der Mathematik: Quine-McCluskey, Methode von

Verfahren zur Berechnung der Menge der Primimplikanten einer vollständig definierten Booleschen Funktion f : {0, 1}n → {0, 1}.

Die Methode beruht auf dem Satz von Quine, der die Implikanten einer Booleschen Funktion f charakterisiert:

Ein Boolesches 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 ≤ in), die in q weder als positives noch als negatives Boolesches 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.

Lesermeinung

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos