Given a truth table for a truth function that takes n inputs and produces a single output (true or false), what is the fastest way to find the simplest combination of logic gates that will output the given truth table?
A few rules for specificity:
- Any binary truth function may be used as a logic gate. In other words, AND, OR, XOR, NOR, and NAND are all valid logic gates, but a binary truth function like AND(NOT(A), B) also counts as a single logic gate when determining the simplicity or complexity of a solution.
- The "simplest" solution is the one which uses the fewest logic gates
- The output of a logic gate may either be the output, or it may be an input to exactly one other logic gate.
Primary inputs themselves may go to more than one logic gate; it is only the output of a logic gate that may only be used once. I am most concerned with the minimal circuit necessary for the binary multiplication of two numbers. Do we know of a minimal circuit for multiplication? If so is there an efficient algorithm to construct the minimal circuit?