Pretty much the title. We were learning about Karnaugh maps in class today and they didn't really mention why it has to be a power of 2. A quick google search basically confirmed that it needs to be a power of 2 but I couldn't find the reason why anywhere.
Asked
Active
Viewed 65 times
1 Answers
0
Well, it depends on your definition of an implicant. Ussually an implicant of a boolean function $f(x_1, \dots, x_n)$ is defined as the conjunction $K$ (or a product term) with the property $K \to f \equiv 1$. Every conjuction corresponds to the face of a boolean cube, which is the set of all boolean vectors satisfying $K$. More formally, the face $F_K$ corresponding to an implicant $K$ is defined to be $\{a \in \{0, 1\}^n \mid K(a) = 1\}$. If $K = x_{i_1}\dots x_{i_k}\bar{x}_{j_1} \dots \bar{x}_{j_m}$ then $$F_K = \{a \in \{0, 1\}^n \mid a_{i_1} = \dots = a_{i_k} = 1, a_{j_1} = \dots = a_{j_m} = 0\}.$$ The cardinality of such a set is $2^{n - (k + m)}$ since $k+m$ coordinates $i_1, \dots, i_k, j_1, \dots, j_m$ are fixed and you have $2$ possibilities ($a_t \in \{0, 1\}$) for other $n-(k+m)$ coordinates with $t \notin \{i_1, \dots, i_k, j_1, \dots, j_m\}$.
Random Jack
- 2,906