boolean-logicboolean-expressiondigital-logickarnaugh-map

sum of minterm vs product of maxterm


Given the following Boolean expression of F(A,B,C): F(A,B,C) = A' + B + C' Which of the following statements is/are true about the above expression?

(i) It is an SOP expression (ii) It is a POS expression (iii) It is a sum-of-minterms expression (iv) It is a product-of-maxterms expression

The model answer for this question is i),ii) and iv)

My question is why is iii) not one of the answers? i drew the K-map and found out that its possible to derive such a sum-of-minters expression


Solution

  • A cluster of literals in a boolean expression forms a minterm or a maxterm only, if there are all literals (variables of the given function or their negation) included in it.

    A minterm is a product of all literals of a function, a maxterm is a sum of all literals of a function.

    In a K-map a minterm or a maxterm marks out only one cell. In a truth table a maxterm or a minterm matches only one row.

    The following truth-table corresponds to the given function:

     index | a | b | c || f(a,b,c) | term matching the row/K-map cell
    -------|---|---|---||----------|----------------------------------
       0   | 0 | 0 | 0 ||     1    | minterm: m0 = (¬a⋅¬b⋅¬c)
       1   | 0 | 0 | 1 ||     1    | minterm: m1 = (¬a⋅¬b⋅c)
       2   | 0 | 1 | 0 ||     1    | minterm: m2 = (¬a⋅b⋅¬c)
       3   | 0 | 1 | 1 ||     1    | minterm: m3 = (¬a⋅b⋅c)
    -------|---|---|---||----------|----------------------------------
       4   | 1 | 0 | 0 ||     1    | minterm: m4 = (a⋅¬b⋅¬c)
       5   | 1 | 0 | 1 ||     0    | MAXTERM: M5 = (¬a + b + ¬c)
       6   | 1 | 1 | 0 ||     1    | minterm: m6 = (a⋅b⋅¬c)
       7   | 1 | 1 | 1 ||     1    | minterm: m7 = (a⋅b⋅c)
    

    There is only one maxterm present in the truth table (and your K-map) and the only maxterm determining the function's output as logical 0. It is a valid product-of-maxterms expression, even if there is only one. It is also the same boolean expression as the original one, so that is a valid product-of-maxterms expression too.

    However, this is not a valid sum of minterms, because there is none:

    f(a,b,c) = ∏(5) = M5 = (¬a + b + ¬c)
    

    For the original expression to be also the sum of minterms, it would need to mark out every single true/one cell in your K-map separately like this:

    f(a,b,c) = ∑(0,1,2,3,4,6,7) = m0 + m1 + m2 + m3 + m4 + m6 + m7 =
             = (¬a⋅¬b⋅¬c)+(¬a⋅¬b⋅c)+(¬a⋅b⋅¬c)+(¬a⋅b⋅c)+(a⋅¬b⋅¬c)+(a⋅b⋅¬c)+(a⋅b⋅c)
    

    As you can see, even if these two boolean expressions are equivalent to each other, the original one (on the left side of the equation) is not written as the sum-of-minterms expression (on the right side of the equation).

    (¬a+b+¬c) = (¬a⋅¬b⋅¬c)+(¬a⋅¬b⋅c)+(¬a⋅b⋅¬c)+(¬a⋅b⋅c)+(a⋅¬b⋅¬c)+(a⋅b⋅¬c)+(a⋅b⋅c)
    

    Just any product is not a minterm, so the original expression could be in the form of both the product of sum and the sum of products, but not the valid sum-of-minterms.

    f(a,b,c) = (¬a + b + ¬c) = (¬a) + (b) + (¬c)
    

    In the picture (created using latex) you can see the expression – it is the same in it's minimal DNF and minimal CNF – and the sum of minterms equivalent to it.

    K-maps with equivalent expressions.