Circuit minimization for Boolean functions

In Boolean algebra, circuit minimization is the problem of obtaining the smallest logic circuit (Boolean formula) that represents a given Boolean function or truth table. The unbounded circuit minimization problem was long-conjectured to be $\Sigma_2^P$-complete, a result finally proved in 2008,^[1] but there are effective heuristics such as Karnaugh maps and the Quine–McCluskey algorithm that facilitate the process.

Purpose

The problem with having a complicated circuit (i.e. one with many elements, such as logical gates) is that each element takes up physical space in its implementation and costs time and money to produce in itself. Circuit minimization may be one form of logic optimization used to reduce the area of complex logic in integrated circuits.

Example

While there are many ways to minimize a circuit, this is an example that minimizes (or simplifies) a boolean function. Note that the boolean function carried out by the circuit is directly related to the algebraic expression from which the function is implemented.^[2] Consider the circuit used to represent $(A \wedge \bar{B}) \vee (\bar{A} \wedge B)$. It is evident that two negations, two conjunctions, and a disjunction are used in this statement. This means that to build the circuit one would need two inverters, two AND gates, and an OR gate.

We can simplify (minimize) the circuit by applying logical identities or using intuition. Since the example states that A is true when B is false or the other way around, we can conclude that this simply means $A \neq B$. In terms of logical gates, inequality simply means an XOR gate (exclusive or). Therefore, $(A \wedge \bar{B}) \vee (\bar{A} \wedge B) \iff A \neq B$. Then the two circuits shown below are equivalent:

You can additionally check the correctness of the result using a truth table.

See also

• Binary decision diagram
• Espresso heuristic logic minimizer
• Karnaugh map
• Petrick's method
• Prime implicant
• Circuit complexity
• Function composition
• Function decomposition
• Gate underutilization

References

1. Buchfuhrer, D.; Umans, C. (2011). "The complexity of Boolean formula minimization". Journal of Computer and System Sciences 77: 142. doi:10.1016/j.jcss.2010.06.011. This is an extended version of the conference paper Buchfuhrer, D.; Umans, C. (2008). "The Complexity of Boolean Formula Minimization". Automata, Languages and Programming. Lecture Notes in Computer Science 5125. p. 24. doi:10.1007/978-3-540-70575-8_3. ISBN 978-3-540-70574-1.
2. M. Mano, C. Kime. "Logic and Computer Design Fundamentals" (Fourth Edition). Pg 54

Further reading

• De Micheli, Giovanni. Synthesis and Optimization of Digital Circuits. McGraw-Hill, 1994, Part III, Logic-Level Synthesis and Optimization
• Zvi Kohavi, Niraj K. Jha. Switching and Finite Automata Theory. 3rd ed. Cambridge University Press. 2009. ISBN 978-0-521-85748-2, chapters 4–6
• Knuth, Donald E. (2010). "chapter 7.1.2: Boolean Evaluation". The Art of Computer Programming 4A. Addison-Wesley. pp. 96–133. ISBN 0-201-03804-8.
• Multi-level minimization part I, partII: CMU lectures slides by Rob A. Rutenbar