1. ## Maxterms

Why every function can be written as a unique product of maxterms??

2. Originally Posted by aeubz
Why every function can be written as a unique product of maxterms??
What are maxterms?

3. Originally Posted by Drexel28
What are maxterms?
Its a sum of literals, in which each input variable appears exactly once. Boolean Algebra

4. That's because each maxterm corresponds to one and only one tuple of values of the function's arguments. E.g., if a function f(x1, x2, x3) has three arguments, then the triple <x1, x2, x3> can have 8 values, from <0, 0, 0> to <1, 1, 1>. Each maxterm is true on one and only one of those 8 values.

Therefore, the sum-of-maxterms representation of a function f(x1, ..., xn) includes precisely those maxterms that correspond to values of <x1, ..., xn> where f(x1, ..., xn) = true.

Please post here if this explanation is unclear or if you need a more formal proof.

5. Originally Posted by emakarov
That's because each maxterm corresponds to one and only one tuple of values of the function's arguments. E.g., if a function f(x1, x2, x3) has three arguments, then the triple <x1, x2, x3> can have 8 values, from <0, 0, 0> to <1, 1, 1>. Each maxterm is true on one and only one of those 8 values.

Therefore, the sum-of-maxterms representation of a function f(x1, ..., xn) includes precisely those maxterms that correspond to values of <x1, ..., xn> where f(x1, ..., xn) = true.

Please post here if this explanation is unclear or if you need a more formal proof.
A proof would be helpful

6. I am sorry, I thought you were talking about disjunctive normal form (DNF), not conjunctive normal form (CNF).

In CNF every maxterm corresponds to a line in the truth table where the function is false. First, for notation, suppose 0 means false and 1 means true. Next, if $x$ is a variable and $b=0$ or $b=1$, let $x^b$ denote $x$ when $b=1$ and $-x$ (the negation of $x$) when $b=0$.

Suppose $f(b_1,\dots,b_n)=0$ where $b_i=0$ or $b_i=1$. Then the maxterm $x_1^{-b_1}+\dots+x_n^{-b_n}$ in included into the CNF of $f$. E.g., if $f(0,1,0)=0$ then the maxterm $t_{010}=x_1+(-x_2)+x_3$ is in the CNF. Indeed, $t_{010}=0$ if $x_1=0$, $x_2=1$ and $x_3=0$; on all other values of $x_1,x_2,x_3$ this maxterm is 1. Therefore, $t_{010}$ forces the whole conjunction to be false on 0,1,0 and is true (i.e., does not force anything) on other values.

From this it should be clear how to construct a CNF.

As for uniqueness, suppose $f=t_1\cdot\;\dots\;\cdot t_m=t_1'\cdot\;\dots\;\cdot t_k'=g$ where $t_i$ and $t_j'$ are maxterms. ( $\cdot$ means conjunction). Then $f(b_1,\dots,b_n)=0$ implies thta there exist $1\le i\le m$ such that $t_i(b_1,\dots,b_n)=0$. This means $t_i=x_1^{-b_1}+\dots+x_n^{-b_n}$ because every $x_j$ ( $1\le j\le n$) appears in $t_i$ and every member of disjunction must be false. Since the CNF's of $f$ and $g$ are the same, $t_i$ is one of $t_j'$ and therefore $g(b_1,\dots,b_n)$ is also 0. Similarly, $g(b_1,\dots,b_n)=0$ implies $f(b_1,\dots,b_n)=0$