Results 1 to 6 of 6

Math Help - 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
    21
    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,559
    Thanks
    785
    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,559
    Thanks
    785
    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
    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: October 21st 2008, 11:43 AM
  2. Minterms and maxterms!
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: October 21st 2008, 05:35 AM

Search Tags


/mathhelpforum @mathhelpforum