Question

Show that a Boolean function can be represented as a Boolean product of maxterms. This representation is called the product-of-sums expansion or conjunctive normal form of the function. (Hint: Include one maxterm in this product for each combination of the variables where the function has the value 0.)

Short answer

Yes, the Boolean sum is represented as a Boolean product.

Step-by-step solution

Definition.

The complements of an elements\(\overline {\bf{0}} {\bf{ = 1}}\)and\(\overline {\bf{1}} {\bf{ = 0}}\).

The Boolean sum + or OR is 1 if either term is 1.

The Boolean product (.) or AND is 1 if both term are 1.

Show the Boolean function can be represented as a Boolean product.

The Boolean sum is \({{\bf{y}}_{\bf{1}}}{\bf{ + }}{{\bf{y}}_{\bf{2}}}{\bf{ + }}....{\bf{ + }}{{\bf{y}}_{\bf{n}}}\) where \({{\bf{y}}_{\bf{i}}}{\bf{ = }}{{\bf{x}}_{\bf{i}}}\) or \({{\bf{y}}_{\bf{i}}}{\bf{ = }}\overline {{{\bf{x}}_{\bf{i}}}} \), has the value 0 for exactly one combination of the values of the variables, namely, when \({{\bf{x}}_{\bf{i}}}{\bf{ = }}0\) if \({{\bf{y}}_{\bf{i}}}{\bf{ = }}{{\bf{x}}_{\bf{i}}}\) and \({{\bf{x}}_{\bf{i}}}{\bf{ = 1}}\)if\({{\bf{y}}_{\bf{i}}}{\bf{ = }}\overline {{{\bf{x}}_{\bf{i}}}} \). This Boolean sum is called a maxterm.

For each combination of the values of the variables for which the Boolean function F is 0.

The Boolean product of maxterms is 0 if and only if at least one of the maxterm is 0. Thus, the Boolean function F can be represented as a Boolean product of the maxterm.

Therefore, the Boolean sum is represented as Boolean products.