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

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):

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.

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

Originally Posted by lamentofking
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.

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

Originally Posted by emakarov
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.

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

Originally Posted by lamentofking
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.

Originally Posted by lamentofking
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'.

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

Originally Posted by emakarov
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'.

6. ## 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.

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

Originally Posted by emakarov
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 ?