2
$\begingroup$

I understand that in terms of minterms,

F (Boolean Function) = Sum of Products and thus will yield true when either of the products is true.

But I am unable to develop any intuition for maxterms,

F(Boolean Function) = Product of Sums (of maxterms).

Is F = Product of sums just a different way of representing F = Sum of Products?

If yes, is it possible to prove that using the duality principle?

$\endgroup$
3
$\begingroup$

Indeed, maxterm is the concept dual to minterm. As you mention, $$ f(x) = \bigvee_{y\colon f(y)=1} \text{"$x=y$"} = \bigvee_{y\colon f(y)=1} \bigwedge_{i=1}^n \text{"$x_i=y_i$"}. $$ Here $\vee$ is OR (your addition), $\wedge$ is ADD (your multiplication), the input is $x = x_1,\ldots,x_n$, and "$x_i=y_i$" is either $x_i$ (if $y_i$ is True) or $\bar{x}_i$ (if $y_i$ is False).

Similarly, we have $$ f(x) = \bigwedge_{y\colon f(y)=0} \text{"$x \neq y$"} = \bigwedge_{y\colon f(y)=0} \bigvee_{i=1}^n \text{"$x_i \neq y_i$"}. $$ This time "$x_i\neq y_i$" is $x_i$ if $y_i$ is False, and $\bar{x}_i$ if $y_i$ is True.


When the function is monotone, we can improve on the first representation: $$ f(x) = \bigvee_{\text{$y$ minterm}} \text{"$x \geq y$"} = \bigvee_{\text{$y$ minterm}} \bigwedge_{i\colon y_i=1} x_i. $$ Here "$x \geq y$" means $x_i \geq y_i$ for all $i$, and a minterm is a satisfying assignment of $f$ which is minimal in the sense that changing any 1 to 0 changes it to an unsatisfying assignment.

We can define maxterms analogously – maximal unsatisfying assignments, and then $$ f(x) = \bigwedge_{\text{$y$ maxterm}} \text{"not $x \leq y$"} = \bigwedge_{\text{$y$ maxterm}} \bigvee_{i\colon y_i=0} x_i. $$

$\endgroup$
  • $\begingroup$ Is maxterm the complement of a minterm or not? $\endgroup$ – Archer Sep 27 '18 at 8:02
  • 1
    $\begingroup$ No, it’s the dual concept to minterm. $\endgroup$ – Yuval Filmus Sep 27 '18 at 13:42

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.