Maxterms

**aeubz** · February 11th 2010, 04:49 PM

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

**Drexel28** · February 11th 2010, 05:35 PM

Originally Posted by aeubz

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

What are maxterms?

**aeubz** · February 11th 2010, 05:41 PM

Originally Posted by Drexel28

What are maxterms?

Its a sum of literals, in which each input variable appears exactly once. Boolean Algebra

**emakarov** · February 12th 2010, 02:45 AM

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.

**aeubz** · February 12th 2010, 05:28 AM

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

**emakarov** · February 12th 2010, 09:18 AM

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$

Thread: Maxterms

LinkBack

Thread Tools

Display

Maxterms

Similar Math Help Forum Discussions

Hello. Q on minterms and maxterms

Minterms and maxterms!

Search Tags