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

Truth table

A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...

. The general circuit minimization problem is believed to be intractable, but there are effective heuristics such as Karnaugh map

Karnaugh map

The Karnaugh map , Maurice Karnaugh's 1953 refinement of Edward Veitch's 1952 Veitch diagram, is a method to simplify Boolean algebra expressions...

s and the Quine–McCluskey algorithm

Quine–McCluskey algorithm

The Quine–McCluskey algorithm is a method used for minimization of boolean functions which was developed by W.V. Quine and Edward J. McCluskey...

 that facilitate the process.

Purpose

The problem with having a complicated circuit

Electronic circuit

An electronic circuit is composed of individual electronic components, such as resistors, transistors, capacitors, inductors and diodes, connected by conductive wires or traces through which electric current can flow...

 (i.e. one with many elements, such as logical gates

Logic gate

A logic gate is an idealized or physical device implementing a Boolean function, that is, it performs a logical operation on one or more logic inputs and produces a single logic output. Depending on the context, the term may refer to an ideal logic gate, one that has for instance zero rise time and...

) is that each element takes up physical space in its implementation and costs time and money to produce in itself.

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.
Consider the circuit used to represent . 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

Inverter (logic gate)

In digital logic, an inverter or NOT gate is a logic gate which implements logical negation. The truth table is shown on the right.This represents perfect switching behavior, which is the defining assumption in Digital electronics. In practice, actual devices have electrical characteristics that...

, two AND gate

AND gate

The AND gate is a basic digital logic gate that implements logical conjunction - it behaves according to the truth table to the right. A HIGH output results only if both the inputs to the AND gate are HIGH . If neither or only one input to the AND gate is HIGH, a LOW output results...

s, and an OR gate

OR gate

The OR gate is a digital logic gate that implements logical disjunction - it behaves according to the truth table to the right. A HIGH output results if one or both the inputs to the gate are HIGH . If neither input is HIGH, a LOW output results...

.

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 . In terms of logical gates, inequality simply means an XOR gate

XOR gate

The XOR gate is a digital logic gate that implements an exclusive or; that is, a true output results if one, and only one, of the inputs to the gate is true . If both inputs are false or both are true , a false output results. Its behavior is summarized in the truth table shown on the right...

 (exclusive or). Therefore, . Then the two circuits shown below are equivalent:



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

Truth table

A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...

.

See also

• Binary decision diagram
  Binary decision diagram
  In the field of computer science, a binary decision diagram or branching program, like a negation normal form or a propositional directed acyclic graph , is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed...
  
  
• Espresso heuristic logic minimizer
  Espresso heuristic logic minimizer
  The Espresso logic minimizer is a computer program using heuristic and specific algorithms for efficiently reducing the complexity of digital electronic gate circuits. Espresso was developed at IBM by Robert Brayton. Rudell later published the variant Espresso-MV in 1986 under the title...
  
  
• Karnaugh map
  Karnaugh map
  The Karnaugh map , Maurice Karnaugh's 1953 refinement of Edward Veitch's 1952 Veitch diagram, is a method to simplify Boolean algebra expressions...
  
  
• Prime implicant
• Circuit complexity
  Circuit complexity
  In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them....
  
  
• Function composition
  Function composition
  In mathematics, function composition is the application of one function to the results of another. For instance, the functions and can be composed by computing the output of g when it has an argument of f instead of x...
  
  
• Function decomposition

Further reading

• De Micheli, Giovanni. Synthesis and Optimization of Digital Circuits. McGraw-Hill, 1994, Part III, Logic-Level Syntesis and Optimization
• Zvi Kohavi, Niraj K. Jha. Switching and Finite Automata Theory. 3rd ed. Cambridge University Press. 2009. ISBN 9780521857482, chapters 4–6