Is there a unique minimal expression for every boolean function?

Question

Is there a unique minimal expression for every boolean function?

I've heard that there are some boolean expressions for which the minimal form is not unique. What are the characteristics of this kind of functions?

Answer 1

No, the minimal expression is not necessarily unique.

Example:

A*!B + B*!C + !A*C

!B*C + !A*B +A*!C

The difference between both expressions becomes clearer when looking at their Karnaugh maps (created using the LaTex package karnaugh-map):

The six minterms can be covered by three implicants in two alternative ways.

Both expressions represent the same function and are minimal in the sense that they have the minimum number of implicants when expressed in Disjunctive Normal Form (DNF). Depending on the expression, there might be many different ways to select the minterms/implicants which represent the expression.

However, "minimal expression" might refer to other properties like number of operations or nesting depth of the expression.

Functions with a unique minimal DNF can be expressed solely by "essential prime implicants". None of their implicants is "non essential" and can be removed without changing the function.