It seems that Karnaugh maps and Quine–McCluskey algorithm are used to minimize the general number of gates to represent some truth table (boolean function) with $n$ inputs (usually small $n$) and one output.

My problem is different from the problems the above techniques solve in two aspects:

  1. Need to consider 2-output-bit rather than 1
  2. Can use AND, NOT, XOR and need to minimize number of AND where the number of XOR and NOT gates do not matter.

The functions I'm working on have 4 input bits. My question is whether there is a way to determine the minimum number of AND gates for realizing certain function.

  • \$\begingroup\$ So, what is your question? \$\endgroup\$ – Andy aka May 22 '17 at 14:40
  • \$\begingroup\$ I edited in the question \$\endgroup\$ – Bush May 22 '17 at 15:50
  • \$\begingroup\$ There is likely no established algorithm for this, because "number of AND gates" is not a relevant cost metric in any real-world technology I'm aware of. If you have a homework question that's asking you to do this for some particular truth table, you just need to be clever. \$\endgroup\$ – The Photon May 22 '17 at 15:56
  • \$\begingroup\$ Minimizing multiple output logic is a real-world problem, so you may find some ways to do that in the literature. The main idea would be finding common factors in the equations for two outputs, and not calculating those terms twice. \$\endgroup\$ – The Photon May 22 '17 at 15:57
  • \$\begingroup\$ Sounds like an academic use of en.wikipedia.org/wiki/De_Morgan%27s_laws exchanging nand for nor \$\endgroup\$ – sstobbe May 22 '17 at 19:37

Your Answer


Browse other questions tagged or ask your own question.