2
$\begingroup$

A Boolean function $F(X_1, X_2, X_3, X_4, X_5, X_6)$ of six variables is defined as $F = 1$, when three or more input variables are at logic 1. otherwise 0. How many essential prime implicants does F have?


How to visualize this problem. A Six Variable k-map is very difficult to manage. Any hints?

$\endgroup$
  • $\begingroup$ see Majority $\endgroup$ – lox May 3 at 15:20
1
$\begingroup$

Hints

Here are two independent hints.

  • Try an easier case such as exercise 1 or exercise 2 below.
  • Can you find one implicant? Can you expand that implicant to a prime implicant? Can you find more?

Answer

$X_1X_2X_3$ is an implicant since $F$ becomes 1 when $X_1, X_2, X_3$ are 1.

Since none of $X_1X_2$, $X_1X_3$ and $X_2X_3$ is an implicant, $X_1X_2X_3$ is a prime implicant.

Similarly, all $X_iX_jX_k$ are prime implicant where triple $i,j,k$ are different from each other. There are $\binom 63 = 20$ of them.


Can there be other prime implicant? No. Here is how to see it. Suppose $A_1A_2\cdots A_m$ is a prime implicant, where each $A_i$ is one of $X_1, \cdots, X_6, \overline X_1, \cdots, \overline X_6$.

  1. None of $A_i$s is $\overline X_1, \cdots, \overline X_6$. Otherwise, we can remove them to get a larger implicant.
  2. The number of $A_i$s that are one of $X_1, \cdots, X_6$ must be at least 3. Otherwise, $F$ can become 1 when only those $X_i$s are 1, i.e., less than 3 of input variables are 1.
  3. The number of $A_i$s that are one of $X_1, \cdots, X_6$ must be at most 3. Otherwise, we can select $A_{i_1},A_{i_2},A_{i_3}$ that are $X_1, \cdots, X_6$. $F$ can be expanded to the implicant $A_{i_1}A_{i_2}A_{i_3}$

An essential prime implicant is an prime implicant that covers an output of the function that no combination of other prime implicants is able to cover. Based on symmetry, we should expect that every prime implicant is an essential prime implicant, which is indeed the case. Can you find the output that is covered only by $X_1X_2X_3$?

In summary, there are 20 essential prime implicants of $F$, which are $X_1X_2X_3,X_1X_2X_4,X_1X_2X_5,X_1X_2X_6,X_1X_3X_4,X_1X_3X_5,X_1X_3X_6,X_1X_4X_5,X_1X_4X_6,X_1X_5X_6,$
$X_2X_3X_4,X_2X_3X_5,X_2X_3X_6,X_2X_4X_5,X_2X_4X_6,X_2X_5X_6,$
$X_3X_4X_5,X_3X_4X_6,X_3X_5X_6,$
$X_4X_5X_6$.
It is not necessary to draw or visualize the Karnaugh map.

Exercises

Exercise 1. A Boolean function $B(X_1, X_2)$ of two variables is defined as $B = 1$, when one or more input variables are at logic 1. Otherwise 0. How many essential prime implicants does B have?

Exercise 2. A Boolean function $C(X_1, X_2, X_3)$ of three variables is defined as $C = 1$, when two or more input variables are at logic 1. Otherwise 0. How many essential prime implicants does C have?

Exercise 3. A Boolean function $F_2(X_1, X_2, X_3, X_4, X_5, X_6)$ of six variables is defined as $F_2 = 1$, when two or more input variables are at logic 1. Otherwise 0. How many essential prime implicants does $F_2$ have?

Exercise 4. A Boolean function $P(X_1, X_2, X_3, X_4, X_5, X_6)$ of six variables is defined as $P = 1$, when one or more input variables among $X_1,X_2,X_3$ are at logic 1 and one or more input variables among $X_4,X_5,X_6$ are at logic 1. Otherwise 0. How many essential prime implicants does $P$ have?

$\endgroup$
1
$\begingroup$

An implicant of $F$ is a partial assignment to the variables of $F$ which guarantees that $F$ is satisfied. A prime implicant is a minimal implicant, that is, an implicant that is no longer an implicant if we remove any single variable.

Let us start by finding all the implicants of $F$. Let $\alpha$ be any partial assignment to the variables of $F$, and suppose that $\alpha$ assigns $k$ variables to true. We can complete $\alpha$ to an assignment by assigning the rest of the variables to false, in which case we get an assignment containing $k$ true variables. Hence $\alpha$ can only be an implicant if $k \geq 3$. Conversely, it is not hard to check that if $\alpha$ assigns at least 3 variables to true then it is an implicant of $F$.

When is an implicant a prime implicant? It must be a partial assignment with at least 3 true variables, such that if we remove any single variable, there are at most 2 true variables. Can you figure out how all such implicants look like? Give it a try.

As an aside, your function is monotone, and so its prime implicants are also known as minterms. Minterms have a special structure – they cannot be arbitrary partial assignments. I'll let you figure out the special property that minterms have.

$\endgroup$
  • $\begingroup$ As per my understanding I think all such prime implicants must have at most 3 true values. eg. $X_2=1,X_4=1,X_6=1$ all others $X_i = 0$. correct me if I am wrong. $\endgroup$ – Vineet May 4 at 16:07
  • $\begingroup$ Implicants are partial assignments. They also need to imply your function. $\endgroup$ – Yuval Filmus May 4 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.