[Math] What’s the maximum number of minterms in the minimal form of all Boolean functions of $n$ variables

boolean-algebralogicpropositional-calculus

Suppose we have $n$ Boolean variables. This means that there are $2^n$ distinct values for these $n$ variables. Hence, there are $2^{2^n}$ distinct Boolean functions of $n$ variables. Each of these functions can be expressed as a sum of minterms, in minimal form. I want to find out what's the maximum number of minterms for all the Boolean functions of $n$ variables.

For example, for one Boolean variable we can have four distinct functions:

  • $f_1(x) = 0$
  • $f_2(x) = 1$
  • $f_3(x) = x$
  • $f_4(x) = \neg x$

Hence, the maximum number of minterms is one.

Similarly, for two Boolean variables we can have sixteen distinct functions:

  • $f_1(x, y) = 0$
  • $f_2(x, y) = 1$
  • $f_3(x, y) = x$
  • $f_4(x, y) = y$
  • $f_5(x, y) = \neg x$
  • $f_6(x, y) = \neg y$
  • $f_7(x, y) = x \wedge y$
  • $f_8(x, y) = x \vee y$
  • $f_9(x, y) = \neg x \wedge y$
  • $f_{10}(x, y) = \neg x \vee y$
  • $f_{11}(x, y) = x \wedge \neg y$
  • $f_{12}(x, y) = x \vee \neg y$
  • $f_{13}(x, y) = \neg x \wedge \neg y$
  • $f_{14}(x, y) = \neg x \vee \neg y$
  • $f_{15}(x, y) = (\neg x \wedge y) \vee (x \wedge \neg y)$
  • $f_{16}(x, y) = (\neg x \wedge \neg y) \vee (x \wedge y)$

Hence, the maximum number of minterms is two.

So, in general what's the maximum number of minterms in the minimal form of all Boolean functions of $n$ variables? I have a feeling that for $n$ variables, the answer is always $n$ minterms. However, that's just a hypothesis. I don't know how to actually prove or disprove it.

Best Answer

The $n$-ary Boolean function with the largest minimal DNF representation is the modulo-2 sum of all inputs (which can also be viewed as the iterated exclusive or of all inputs).

There are $2^{n-1}$ ones in the truth table, and no term can cover more than a sincle one of them, so you need $2^{n-1}$ terms.

If you want minterms (as defined in your link), specifically, then the constant function $1$ will need even more, namely $2^n$ minterms. Since a minterm must, by definition, use all variables, the representations you list for two-variable functions are not all minterm-based.

Related Question