Results 1 to 6 of 6

Thread: Maxterms

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    61

    Maxterms

    Why every function can be written as a unique product of maxterms??
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    22
    Quote Originally Posted by aeubz View Post
    Why every function can be written as a unique product of maxterms??
    What are maxterms?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2008
    Posts
    61
    Quote Originally Posted by Drexel28 View Post
    What are maxterms?
    Its a sum of literals, in which each input variable appears exactly once. Boolean Algebra
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2008
    Posts
    61
    Quote Originally Posted by emakarov View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    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$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Hello. Q on minterms and maxterms
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 21st 2008, 10:43 AM
  2. Minterms and maxterms!
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: Oct 21st 2008, 04:35 AM

Search Tags


/mathhelpforum @mathhelpforum