Results 1 to 12 of 12

Math Help - Boolean Functions

  1. #1
    Junior Member
    Joined
    Mar 2011
    Posts
    36

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2011
    Posts
    36

    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Mar 2011
    Posts
    36

    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Mar 2011
    Posts
    36

    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!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: Boolean Functions

    Quote Originally Posted by rorosingsong View Post
    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 View Post
    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 View Post
    In that case do I still put a 0 in the cells with no marks?
    Yes because zero is an even number.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Mar 2011
    Posts
    36

    Re: Boolean Functions

    Quote Originally Posted by emakarov View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: Boolean Functions

    Quote Originally Posted by rorosingsong View Post
    So with the inclusion of xyz, would it be 27 marks?
    Yes.

    Quote Originally Posted by rorosingsong View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Mar 2011
    Posts
    36

    Re: Boolean Functions

    Quote Originally Posted by emakarov View Post

    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...
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Mar 2011
    Posts
    36

    Re: Boolean Functions

    Thanks for the advice emakarov, I'll be sure to check.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Boolean function?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 22nd 2011, 03:09 PM
  2. More Boolean
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 21st 2009, 02:17 PM
  3. How to reduce algebraic degree of Boolean Functions?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 3rd 2009, 04:07 AM
  4. Boolean Algebra
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 19th 2009, 11:51 AM
  5. boolean algebra
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 19th 2009, 09:01 AM

Search Tags


/mathhelpforum @mathhelpforum