0
$\begingroup$

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:

enter image description here

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?

$\endgroup$
3
  • 1
    $\begingroup$ My bet is on $f > 0$ ... the trick will be to prove that that one is 'maximal' using a proof by induction. $\endgroup$
    – Bram28
    Commented Dec 2, 2019 at 15:09
  • $\begingroup$ 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? $\endgroup$
    – Elahe
    Commented Dec 2, 2019 at 15:15
  • 1
    $\begingroup$ OK, I added a proof by induction $\endgroup$
    – Bram28
    Commented Dec 2, 2019 at 18:18

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .