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 $\displaystyle x$ is a variable and $\displaystyle b=0$ or $\displaystyle b=1$, let $\displaystyle x^b$ denote $\displaystyle x$ when $\displaystyle b=1$ and $\displaystyle -x$ (the negation of $\displaystyle x$) when $\displaystyle b=0$.

Suppose $\displaystyle f(b_1,\dots,b_n)=0$ where $\displaystyle b_i=0$ or $\displaystyle b_i=1$. Then the maxterm $\displaystyle x_1^{-b_1}+\dots+x_n^{-b_n}$ in included into the CNF of $\displaystyle f$. E.g., if $\displaystyle f(0,1,0)=0$ then the maxterm $\displaystyle t_{010}=x_1+(-x_2)+x_3$ is in the CNF. Indeed, $\displaystyle t_{010}=0$ if $\displaystyle x_1=0$, $\displaystyle x_2=1$ and $\displaystyle x_3=0$; on all other values of $\displaystyle x_1,x_2,x_3$ this maxterm is 1. Therefore, $\displaystyle 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 $\displaystyle f=t_1\cdot\;\dots\;\cdot t_m=t_1'\cdot\;\dots\;\cdot t_k'=g$ where $\displaystyle t_i$ and $\displaystyle t_j'$ are maxterms. ($\displaystyle \cdot$ means conjunction). Then $\displaystyle f(b_1,\dots,b_n)=0$ implies thta there exist $\displaystyle 1\le i\le m$ such that $\displaystyle t_i(b_1,\dots,b_n)=0$. This means $\displaystyle t_i=x_1^{-b_1}+\dots+x_n^{-b_n}$ because every $\displaystyle x_j$ ($\displaystyle 1\le j\le n$) appears in $\displaystyle t_i$ and every member of disjunction must be false. Since the CNF's of $\displaystyle f$ and $\displaystyle g$ are the same, $\displaystyle t_i$ is one of $\displaystyle t_j'$ and therefore $\displaystyle g(b_1,\dots,b_n)$ is also 0. Similarly, $\displaystyle g(b_1,\dots,b_n)=0$ implies $\displaystyle f(b_1,\dots,b_n)=0$