# Boolean Functions

• Oct 5th 2011, 04:01 AM
rorosingsong
Boolean Functions
Hi I'm having trouble with this question and was hoping for a push in the right direction...
I've been given the boolean function
$f = w \oplus y \oplus xz \oplus wxz \oplus wyz \oplus wxyz$
and been asked to apply the karnaugh map method to it.
However I don't know how to get straight from that function to a Karnaugh map and I'm having trouble with the algebra in trying to get rid of the $\oplus$ signs.

I've gotten as far as
$f = (wy'\vee w'y)(x'\vee z')\vee (w'\vee y)(w\vee y')(xy) \oplus wxz \oplus wyz \oplus wxyz$
and I'm finding the rest of the algebra messy and intimidating. I don't think I'm on the right track.

I'd really appreciate some pointers, thanks in advance!
• Oct 5th 2011, 05:29 AM
emakarov
Re: Boolean Functions
As I understand, the Karnaugh map method goes from truth values to a formula, so you are not supposed to symbolically transform your formula into a DNF.

Draw a Karnaugh map 4x4 and label it as shown here. Then for each term in your sum put one mark into corresponding cells. For example, if the top of the table says xy and the columns are marked 00, 01, 11, 10, and if the left of the column says zw and the rows are marked 00, 01, 11, 10, then for the term xz you would put one mark into each of the four cells of the lower-right quarter of the table. You can use "xz" as the mark to keep track of the terms.

If there are n variables total, a term consisting of k variables corresponds to $2^{n-k}$ cells of the table. Therefore, you will have 8 + 8 + 4 + 2 + 2 + 1 = 25 marks in total. Finally, since $\oplus$ is exclusive disjunction, cells with even number of marks will have truth value F and those with odd number of marks will have T. After that, you can construct a DNF corresponding to this Karnaugh map.
• Oct 5th 2011, 06:07 AM
rorosingsong
Re: Boolean Functions
Thanks emakarov!
I really appreciate your prompt reply, but the question seems to suggest reducing the function to a DNF because it states "recall that $x \oplus y = xy' \vee x'y$ ..."

Should I apply the karnaugh map method without first going through the algebra regardless?

Thanks again,
rorosingsong (Bow)
• Oct 5th 2011, 06:18 AM
rorosingsong
Re: Boolean Functions
Also I got 27 marks... And I'm generally confused... Do I put a 1 (true) in a cell with an even number of marks and a 0 (false) in a cell with an odd number of marks?
In that case do I still put a 0 in the cells with no marks?

Cheers,
Roro
• Oct 5th 2011, 06:22 AM
emakarov
Re: Boolean Functions
First, what does the question exactly ask? The OP says "apply the Karnaugh map method," but what do you have to get in the end?

To create a Karnaugh map, one needs to know the truth table. In contrast, rewriting using logical equivalences neither uses nor gives the truth table, so I don't see how Karnaugh method is useful there.

Maybe $x \oplus y = xy' \vee x'y$ was given to remind the definition and the truth table of $\oplus$.
• Oct 5th 2011, 06:30 AM
rorosingsong
Re: Boolean Functions
The question says:
"recall that the boolean addition is defined by the rule $x \oplus y = xy' \vee x'y$. Consider the Boolean function in four variables $w, x, y z$ defined by the formula $f= w \oplus y \oplus xz \oplus wxz \oplus wyz \oplus xyz \oplus wxyz$.
Apply the the Karnaugh map method to find all simple Boolean expressions corresponding to $f$."

Thanks again for your help emakarov! (Bow)
• Oct 5th 2011, 06:44 AM
emakarov
Re: Boolean Functions
Quote:

Originally Posted by rorosingsong
Also I got 27 marks...

Well, do you agree with the following correspondence between the terms and the number of cells?

$\begin{array}{c|c}\mbox{Term} & \mbox{Number of cells (marks)}\\\hline w & 8\\y & 8\\xz & 4\\wxz & 2\\wyz & 2\\wxyz & 1\\\hline\mbox{Total} & 25\end{array}$

Quote:

Originally Posted by rorosingsong
Do I put a 1 (true) in a cell with an even number of marks and a 0 (false) in a cell with an odd number of marks?

The other way around. It's as if you make a Karnaugh map for each of the 6 terms and then add (using ⊕) the corresponding cells together. The sum 1 ⊕ 1 ⊕ ... ⊕ 1 = 1 iff the left-hand side has an odd number of 1's.

Quote:

Originally Posted by rorosingsong
In that case do I still put a 0 in the cells with no marks?

Yes because zero is an even number.
• Oct 5th 2011, 06:56 AM
rorosingsong
Re: Boolean Functions
Quote:

Originally Posted by emakarov
Well, do you agree with the following correspondence between the terms and the number of cells?

$\begin{array}{c|c}\mbox{Term} & \mbox{Number of cells (marks)}\\\hline w & 8\\y & 8\\xz & 4\\wxz & 2\\wyz & 2\\wxyz & 1\\\hline\mbox{Total} & 25\end{array}$

Ah I understand, that makes sense, however there is an additional term in the function that doesn't appear in your table $xyz$.
So with the inclusion of xyz, would it be 27 marks?

How would I go about answering this question by manipulating the function into a DNF? I'm confused because the question says to find "all simple Boolean expressions corresponding to $f$"

Thanks again. I really do appreciate your help.(Bow)
• Oct 5th 2011, 07:08 AM
emakarov
Re: Boolean Functions
Quote:

Originally Posted by rorosingsong
So with the inclusion of xyz, would it be 27 marks?

Yes.

Quote:

Originally Posted by rorosingsong
How would I go about answering this question by manipulating the function into a DNF? I'm confused because the question says to find "all simple Boolean expressions corresponding to $f$"

The concepts of "simple Boolean expressions" and which simple Boolean expressions correspond to a function are not standard. Could you give the definitions? Are simple Boolean expressions conjunctions of variables and negation of variables?
• Oct 5th 2011, 07:12 AM
rorosingsong
Re: Boolean Functions
Quote:

Originally Posted by emakarov

The concepts of "simple Boolean expressions" and which simple Boolean expressions correspond to a function are not standard. Could you give the definitions? Are simple Boolean expressions conjunctions of variables and negation of variables?

I'm sorry, I really don't know. I'm only a beginner, just started a discrete maths course this semester and I don't think we went into that much detail in the lectures... :(
• Oct 5th 2011, 07:18 AM
emakarov
Re: Boolean Functions
Well, you have to either look up the meaning of "a simple Boolean expression" in the textbook/lecture notes or ask the instructor. It is impossible to solve a problem if one does not know the definitions of all concepts involved; otherwise it is not clear what to solve.

My guess would be that simple Boolean expressions corresponding to f are conjunctions of variables and their negations that occur in the DNF of f, but this needs to be double-checked.
• Oct 6th 2011, 02:01 AM
rorosingsong
Re: Boolean Functions
Thanks for the advice emakarov, I'll be sure to check. :)