The Quine–McCluskey algorithm (or the method of prime implicants) is a method used for minimization of boolean functions which was developed by W.V. Quine and Edward J. McCluskey. It is functionally identical to Karnaugh mapping, but the tabular form makes it more efficient for use in computer algorithms, and it also gives a deterministic way to check that the minimal form of a Boolean function has been reached. It is sometimes referred to as the tabulation method.

PropertyValue
dbpprop:abstract
  • The Quine–McCluskey algorithm (or the method of prime implicants) is a method used for minimization of boolean functions which was developed by W.V. Quine and Edward J. McCluskey. It is functionally identical to Karnaugh mapping, but the tabular form makes it more efficient for use in computer algorithms, and it also gives a deterministic way to check that the minimal form of a Boolean function has been reached. It is sometimes referred to as the tabulation method. The method involves two steps: Finding all prime implicants of the function. Use those prime implicants in a prime implicant chart to find the essential prime implicants of the function, as well as other prime implicants that are necessary to cover the function.
  • Das Verfahren nach Quine und McCluskey ist eine Methode, um Boolesche Funktionen zu minimieren. Der Kern des Verfahrens wurde bereits von Quine vollständig beschrieben. Die Verfeinerungen von McCluskey betreffen im wesentlichen die praktische algorithmische Durchführbarkeit. Die Minimierung ist u. a. deshalb wichtig, weil dadurch die hardwaretechnische Realisierung einfacher und daher kostengünstiger wird. Der Vorteil dieses Verfahrens ist, dass es sich verhältnismäßig leicht in ein Computerprogramm fassen und so mittels eines Computers ausführen lässt. Das Verfahren benötigt im schlechtesten Fall exponentielle Laufzeit, um eine minimale Lösung zu finden. Das Verfahren findet immer eine minimale Lösung, es ist jedoch möglich, dass es noch andere (gleichwertige) Lösungen gibt, die nicht gefunden werden. Da das zugrunde liegende Problem NP-vollständig ist, und unter der Annahme, dass P ≠ NP gilt, gibt es kein in diesem Sinne effizientes Verfahren. Das Verfahren bezieht sich zunächst nur auf Funktionsdarstellungen in kanonischer disjunktiver Normalform (KDNF). Ausdrücke in konjunktiver Normalform (KNF) lassen sich jedoch ohne weiteres über die Verneinung der betrachteten Funktion zunächst in eine DNF umwandeln, dann wie unten beschrieben minimieren und schließlich durch erneute Verneinung in eine KNF zurücktransformieren.
  • El Algoritmo Quine–McCluskey es un método de simplificación de funciones booleanas desarrollado por Willard Van Orman Quine y Edward J. McCluskey. Es funcionalmente idéntico a la utilización del mapa de Karnaugh, pero su forma tabular lo hace más eficiente para su implementación en lenguajes computacionales, y provee un método determinístico de conseguir la mínima expresión de una función booleana.
  • La méthode de Quine-McCluskey est un algorithme systématique permettant de simplifier une fonction logique quelconque de plusieurs variables
  • Il metodo di Quine-McCluskey (o metodo degli implicanti primi) è un algoritmo sviluppato da Willard Van Orman Quine ed Edward McCluskey che viene utilizzato nelle reti combinatorie a due livelli di logica per la minimizzazione di una funzione booleana di n variabili. Il metodo è funzionalmente identico alla mappa di Karnaugh, ma la sua forma tabellare lo rende più efficiente per essere realizzato al computer; inoltre fornisce anche un modo deterministico per testare la minimizzazione di una funzione booleana. Il metodo consiste in due passi: Identificare tutti gli implicanti primi della funzione. Riportare gli implicanti primi trovati in una tabella per ricavare gli implicanti primi essenziali della funzione.
  • クワイン・マクラスキー法（—ほう; Quine-McCluskey algorithm/略:QM法）はブール関数を簡単化するための方法である。カルノー図と同様の目的で使われるが、コンピュータによる自動化に適しており、またブール関数が最簡形かどうか決定的に求めることができる。W・V・クワインが提案し、E・J・マクラスキーが発展させた方法なのでこの名がある。 クワイン・マクラスキー法は3段階からなる。 関数の主項をすべて求める 求めた主項を表にまとめ、必須項を求める 最簡形を求める
  • Metoda Quine'a-McCluskeya to sposób minimalizacji funkcji boolowskich. Daje rezultaty identyczne do metody tablic Karnaugh, ale w przeciwieństwie do niej, dużo łatwiej daje się zaimplementować na komputerze.
  • Метод Куайна — Мак-Класки — табличный метод минимизации булевых функций, предложенный Уиллардом Куайном и усовершенствованный Эдвардом Мак-Класки. Представляет собой попытку избавиться от недостатков метода Куайна.
  • Quine-McCluskey 算法是最小化布尔函数的一种方法。它在功能上等同于卡诺图，但是它的表格形式使它更有效的用做计算机算法，并且它还给出了检查布尔函数是否达到了最小化形式的确定性方法。 方法涉及两步： 找到这个函数的所有素蕴涵项。 使用这些素蕴涵项（implicant）来找到这个函数的本质素蕴涵项，对覆盖这个函数是必须的其他素蕴涵项也同样要使用。
dbpprop:hasPhotoCollection
dbpprop:reference
rdfs:comment
  • The Quine–McCluskey algorithm (or the method of prime implicants) is a method used for minimization of boolean functions which was developed by W.V. Quine and Edward J. McCluskey. It is functionally identical to Karnaugh mapping, but the tabular form makes it more efficient for use in computer algorithms, and it also gives a deterministic way to check that the minimal form of a Boolean function has been reached. It is sometimes referred to as the tabulation method.
  • Das Verfahren nach Quine und McCluskey ist eine Methode, um Boolesche Funktionen zu minimieren. Der Kern des Verfahrens wurde bereits von Quine vollständig beschrieben. Die Verfeinerungen von McCluskey betreffen im wesentlichen die praktische algorithmische Durchführbarkeit. Die Minimierung ist u. a. deshalb wichtig, weil dadurch die hardwaretechnische Realisierung einfacher und daher kostengünstiger wird.
  • El Algoritmo Quine–McCluskey es un método de simplificación de funciones booleanas desarrollado por Willard Van Orman Quine y Edward J. McCluskey. Es funcionalmente idéntico a la utilización del mapa de Karnaugh, pero su forma tabular lo hace más eficiente para su implementación en lenguajes computacionales, y provee un método determinístico de conseguir la mínima expresión de una función booleana.
  • La méthode de Quine-McCluskey est un algorithme systématique permettant de simplifier une fonction logique quelconque de plusieurs variables
  • Il metodo di Quine-McCluskey (o metodo degli implicanti primi) è un algoritmo sviluppato da Willard Van Orman Quine ed Edward McCluskey che viene utilizzato nelle reti combinatorie a due livelli di logica per la minimizzazione di una funzione booleana di n variabili.
  • Metoda Quine'a-McCluskeya to sposób minimalizacji funkcji boolowskich. Daje rezultaty identyczne do metody tablic Karnaugh, ale w przeciwieństwie do niej, dużo łatwiej daje się zaimplementować na komputerze.
  • Метод Куайна — Мак-Класки — табличный метод минимизации булевых функций, предложенный Уиллардом Куайном и усовершенствованный Эдвардом Мак-Класки. Представляет собой попытку избавиться от недостатков метода Куайна.
  • Quine-McCluskey 算法是最小化布尔函数的一种方法。它在功能上等同于卡诺图，但是它的表格形式使它更有效的用做计算机算法，并且它还给出了检查布尔函数是否达到了最小化形式的确定性方法。 方法涉及两步： 找到这个函数的所有素蕴涵项。 使用这些素蕴涵项（implicant）来找到这个函数的本质素蕴涵项，对覆盖这个函数是必须的其他素蕴涵项也同样要使用。
rdfs:label
  • Quine–McCluskey algorithm
  • Verfahren nach Quine und McCluskey
  • Algoritmo Quine–McCluskey
  • Méthode de Quine-Mc Cluskey
  • Metodo di Quine-McCluskey
  • クワイン・マクラスキー法
  • Metoda Quine'a-McCluskeya
  • Метод Куайна — Мак-Класки
  • Quine-McCluskey算法
owl:sameAs
skos:subject
foaf:page
is dbpprop:disambiguates of
is dbpprop:redirect of