Results 1 to 7 of 7

Math Help - Find minimum AND-OR expression using a Karnaugh Map?

  1. #1
    Junior Member
    Joined
    Apr 2013
    From
    USA
    Posts
    69
    Thanks
    1

    Find minimum AND-OR expression using a Karnaugh Map?

    Use a Karnaugh Map to find the minimum AND-OR expression for x(a,b,c):

    Find minimum AND-OR expression using a Karnaugh Map?-kmap.png

    For part a the answer is: x(a, b, c) = ac + b'c'

    How do I get that answer? I know from the problem that x=1 at rows 0, 4, 5, and 7 of the respective truth table (which is not given), however I thought x can only equal 1 if a, b, and c are all 1 by the definition of AND? I'm just confused how truth tables work for inputs I suppose.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: Find minimum AND-OR expression using a Karnaugh Map?

    Quote Originally Posted by lamentofking View Post
    I know from the problem that x=1 at rows 0, 4, 5, and 7 of the respective truth table (which is not given), however I thought x can only equal 1 if a, b, and c are all 1 by the definition of AND?
    That would be true if x(a, b, c) = a AND b AND c, but nobody said that x has this form.

    Any function with a finite number of inputs can be specified by explicitly listing outputs corresponding to those inputs. This is what a truth table does. The notation $\Sigma(0,4,5,7)$ specifies a function that equals 1 for the following values of inputs: $a=0,b=0,c=0$; $a=1,b=0,c=0$; $a=1,b=0,c=1$; $a=1,b=1,c=1$. The values of inputs occur in rows 0, 4, 5 and 7 of the truth table if rows are counted from 0. Note also that the values of inputs: 000, 100, 101 and 111, are 0, 4, 5 and 7 in binary. For other inputs x(a,b,c) = 0 by definition.

    Describing how to use Karnaugh maps is beyond the scope of this post. You can read about it, for example, in Wikipedia. There is also an online Karnaugh map generator here.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2013
    From
    USA
    Posts
    69
    Thanks
    1

    Re: Find minimum AND-OR expression using a Karnaugh Map?

    Quote Originally Posted by emakarov View Post
    That would be true if x(a, b, c) = a AND b AND c, but nobody said that x has this form.

    Any function with a finite number of inputs can be specified by explicitly listing outputs corresponding to those inputs. This is what a truth table does. The notation $\Sigma(0,4,5,7)$ specifies a function that equals 1 for the following values of inputs: $a=0,b=0,c=0$; $a=1,b=0,c=0$; $a=1,b=0,c=1$; $a=1,b=1,c=1$. The values of inputs occur in rows 0, 4, 5 and 7 of the truth table if rows are counted from 0. Note also that the values of inputs: 000, 100, 101 and 111, are 0, 4, 5 and 7 in binary. For other inputs x(a,b,c) = 0 by definition.

    Describing how to use Karnaugh maps is beyond the scope of this post. You can read about it, for example, in Wikipedia. There is also an online Karnaugh map generator here.
    Is there more than one answer in reducing the AND-OR expression? Because when I did it I got ac + b'c' + ab' . My adjacent terms were a'b'c' and ab'c', ab'c' and ab'c, ab'c and abc.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: Find minimum AND-OR expression using a Karnaugh Map?

    Quote Originally Posted by lamentofking View Post
    Is there more than one answer in reducing the AND-OR expression?
    Yes, but usually one expression is shorter than the rest. I am not sure right now whether the minimal expression is unique. Also there are different ways to measure the size of an expression: total number of symbols, the number of logical operations, the number of variables and so on.

    Quote Originally Posted by lamentofking View Post
    Because when I did it I got ac + b'c' + ab'.
    Note that having ab' does not add anything to the function. All four outputs of 1 are already given by ac + b'c'.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Apr 2013
    From
    USA
    Posts
    69
    Thanks
    1

    Re: Find minimum AND-OR expression using a Karnaugh Map?

    Quote Originally Posted by emakarov View Post
    Yes, but usually one expression is shorter than the rest. I am not sure right now whether the minimal expression is unique. Also there are different ways to measure the size of an expression: total number of symbols, the number of logical operations, the number of variables and so on.

    Note that having ab' does not add anything to the function. All four outputs of 1 are already given by ac + b'c'.
    Just to make sure this is a correct way of doing this...

    The way I learned it was that after finding the adjacent terms I got this: ac + b’c’ + ab’ so in order to find minimal expression, I looked at the expression and crossed out each letter that showed up at least twice in the expression. Kind of like counting pairs. If a total pair (xy) has been crossed out then it won't be a part of the final expression. So in this example I start left to right and look at ac. Is 'a' repeated anywhere else in the expression? Yes in ab' so I cross all the a's out. Then I look at c. c is not repeated anywhere else so it stays. So now I know that the factor ac will be in the final expression. b' is repeated so I cross all of them out. I can stop at this point because ab' has been totally eliminated so the final expression will be ac + b'c'.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: Find minimum AND-OR expression using a Karnaugh Map?

    I am not familiar with the algorithm you described, which starts with writing adjacent terms and proceeds by crossing out pairs. I just try to break the cells of the Karnaugh map marked with 1 into rectangular groups of 2^k cells (k = 1, 2, ...). The idea is to select rectangles as large as possible because they correspond to terms with fewer variables. Rectangles can overlap. Then for each rectangle I write the corresponding term.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Apr 2013
    From
    USA
    Posts
    69
    Thanks
    1

    Re: Find minimum AND-OR expression using a Karnaugh Map?

    Quote Originally Posted by emakarov View Post
    I am not familiar with the algorithm you described, which starts with writing adjacent terms and proceeds by crossing out pairs. I just try to break the cells of the Karnaugh map marked with 1 into rectangular groups of 2^k cells (k = 1, 2, ...). The idea is to select rectangles as large as possible because they correspond to terms with fewer variables. Rectangles can overlap. Then for each rectangle I write the corresponding term.
    Well what I'm doing is effectively writing the inputs (which in this case are: aíbící + abící + abíc + abc) and grouping together the terms that differ by one term (eg. a'b'c' and ab'c') and then keeping the common factors (b'c') for my answer. That's how I got ac + b'c' + ab' . The algorithm was just one I stumbled on accidentally. It could be a coincidence that it works. Well lets see then: is the answer for 31b: a'b + bc ?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: March 27th 2011, 04:34 AM
  2. karnaugh map II
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 30th 2010, 02:57 AM
  3. Replies: 3
    Last Post: July 13th 2010, 07:12 PM
  4. Minimum Sum-Of-Products Expression
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 13th 2009, 11:12 AM
  5. Minimum value of trigonometric expression?
    Posted in the Calculus Forum
    Replies: 10
    Last Post: September 6th 2008, 09:51 AM

Search Tags


/mathhelpforum @mathhelpforum