2
$\begingroup$

Recently, when I self-learnt Discrete Mathematics and Its Applications 8th by Kenneth Rosen, it says in 12.4 Minimization of Circuits which uses the Karnaugh Map or the Quine-McCluskey method:

Minimizing a Boolean function makes it possible to construct a circuit for this function that uses the fewest gates and fewest inputs to the AND gates and OR gates in the circuit, among all circuits for the Boolean expression we are minimizing.

So I set the goal function to optimize and get the smallest value $f(x)=N_1(x)\cdot N_2(x)$ where $x$ is the target Boolean expression and $N_1(x)$ is the gate number and $N_2(x)$ is the input number in the minimized circuit although this target function seems to not be used explicitly by any references.


I have already known that the Karnaugh Map won't always "generate the circuit with the minimum inputs and minimum gates" as QA_1 says which has $f(x)=(5+1)\cdot 4$ for the Karnaugh Map (4 AND gates and 1 OR gates. Here I assume the gate can have multiple inputs) and $f(x)=(4+1)\cdot 4$ for the Quine-McCluskey method. The problems of the Karnaugh Map in this example is that it doesn't have all prime implicants but the Quine-McCluskey method has all terms being prime implicants.

QA_1 links to QA_2 (I tried search for the reference book of QA_2 based on its quote but failed) which cares about the fact that "the Quine-McCluskey method" will have only prime implicants left and the comment shows Adjacency and Idempotence are enough which can get Absorption. This is used in the construction process of the Quine-McCluskey method which will only have prime implicants at last.

Q:

Does the Quine-McCluskey method minimize $f(x)$ since it has only prime implicants?

$\endgroup$
8
  • $\begingroup$ Both algorithms find prime implicants, therefore my question is related: cs.stackexchange.com/q/76922/71879 Basically, I asked if a minimum CNF can contain non-prime implicants. or if prime implicants can be longer than any original clause. A lack of answers suggests it's an open problem and therefore your question also would be open... $\endgroup$
    – rus9384
    Commented Feb 12 at 8:22
  • 1
    $\begingroup$ And if you allow the circuit to have depth over 2, then trivially this algorithm won't always produce the smallest circuits. $\endgroup$
    – rus9384
    Commented Feb 12 at 9:20
  • $\begingroup$ @rus9384 Thanks for replies. Re to the 1st comment: 1. You are right. If "a minimum CNF can contain non-prime implicants", then "the Quine-McCluskey method" won't minimize. So my question can be reduced to yours. Hope someone can make these 2 questions closed. 2. BTW, "the Karnaugh Map" may not find all prime implicants in some cases as the question says. $\endgroup$
    – An5Drama
    Commented Feb 13 at 3:11
  • $\begingroup$ Re to the 2nd comment: Here you may define the goal function as the number of 2-ary gates (implied in your question post "smallest amount of literal occurences") which will cause depth greater than 2 while the question assumes using gates with multiple inputs. Both are fine since I didn't find one quantification formula defining the size of the circuit when having one corresponding logical formula. Do you know some references showing one quantification formula? $\endgroup$
    – An5Drama
    Commented Feb 13 at 3:12
  • 1
    $\begingroup$ Basically, the minimal formula that uses only AND, OR and NOT gates for $x\oplus y\oplus z$ is $(x\land(yz\lor\overline y\overline z))\lor(\overline x\land(\overline yz\lor y\overline z))$ which uses 9 fanin-2 gates. Whereas smallest CNF or DNF uses 11 gates. And Quine-McCluskey algorithm generates only DNFs or CNFs. $\endgroup$
    – rus9384
    Commented Feb 13 at 10:49

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.