# Maximum number of prime impliacants for conditional statements in a Karnaugh map with n variables?

I'm looking to find the maximum number of prime implicants for a conditional statement in a Karnaugh map with n variables.

Example: A is a variable with a domain of {0, 1, ..., 15} and I have a condition A > 5. Here I will have the following map:

So the boolean expression would be A + CB which contains 2 prime implicants. If I change my condition to A > 10, clearly the boolean expression will be different.

My question is: what is the maximum number of prime implicants for any other constants?

• My bet is on $f > 0$ ... the trick will be to prove that that one is 'maximal' using a proof by induction. Commented Dec 2, 2019 at 15:09
• I also think it is `f > 0' but I'm looking for proof. Can you tell me more about how to prove it by induction? Commented Dec 2, 2019 at 15:15
• OK, I added a proof by induction Commented Dec 2, 2019 at 18:18

I'll prove by induction that for any $$n \geq 2$$, you need $$n$$ implicants for the function $$f(x_1, x_2 , ... x_n) = \sum_{i=1}^n 2^{(i-1)} \cdot{x_i} > 0$$

(which I'll simply refer to as $$f(x_1, x_2 , ... x_n) > 0$$)

and that all other functions with $$n$$ variables require fewer than $$n$$ implicants.

Base: $$n=2$$

We have just $$3$$ possible functions to consider:

It is clear that $$f > 0$$ requires $$2$$ implicants: $$x_1$$ and $$x_2$$ (or, as a boolean expression: $$x_1+x_2$$)

$$f>1$$ is a single implicant: $$x_2$$

$$f > 2$$ is a single implicant $$x_1 x_2$$

Step: Assume that for some $$k > 2$$, you need $$k$$ implicants for the function $$f(x_1, x_2 , ... x_k) > 0$$

and that all other functions with $$k$$ variables require fewer than $$k$$ implicants.

Now let's consider all possible functions with $$k+1$$ variables.

First, consider any function $$f(x_1, x_2 , ..., x_k, x_{k+1}) > c$$ with $$c \geq 1$$. To cover this function, we can use a single implicant $$x_{k+1}$$ to cover all values from $$2^k$$ to $$2^{k+1}-1$$. Now define, relative to $$f$$, the function $$g(x_1, x_2 , ..., x_k) = f(x_1, x_2 , ..., x_k, 0)$$. The function $$g$$ has $$k$$ variables, and so by inductive hypothesis you need less than $$k$$ implicants to cover it. However, this means that those implicants covers the values $$c+1$$ through $$2^k-1$$ for the $$f$$ fu8nction, and that means that we can cover the original $$f$$ using those less than $$k$$ implicants, plus the single implicant $$x_{k+1}$$, meaning that we can cover $$f$$ with less than $$k+1$$ implicants.

Second, consider $$f(x_1, x_2 , ..., x_k, x_{k+1}) > 0$$

This function can be covered by $$x_1+x_2+...+x_{k+1}$$, i.e. by $$k+1$$ implicants, and it is clear that in fact these are all essential prime implicants: for any $$i$$, there is no way to express $$x_i$$ in terms of the other variables. So, $$k+1$$ implicants is the minimum.