Results 1 to 11 of 11

Math Help - boolean and KV Diagram

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    6

    boolean and KV Diagram

    Hi

    I'm new to this forum. and I would like to ask how do you make a KV Diagram to a given Boolean Algebra.
    I'm not sure how to proceed. I have an example here:

    S= !A * C * !D * !B + !A * C * D * B

    First I made this one:

    D C B A
    0 0 0 0
    0 0 0 1
    0 0 1 0
    0 0 1 1
    0 1 0 0
    0 1 0 1
    0 1 1 0
    0 1 1 1
    1 0 0 1
    1 0 1 0
    1 0 1 1
    1 1 0 0
    1 1 0 1
    1 1 1 0
    1 1 1 1

    Then I don't know how to proceed anymore. Do I have to put the S here as the equivalent. I've attached the KV Diagram

    Thanks for your help
    Attached Thumbnails Attached Thumbnails boolean and KV Diagram-kv.gif  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    nvv
    nvv is offline
    Newbie
    Joined
    Jan 2009
    Posts
    14
    Hi, tintincute.

    Could You please specify your problem(I'm not sure what is your problem)?

    But if I inderstand You:
    The KV Diagram is used to obtain minimal DNF. So, first of all, obtain values for your expression(S= !A * C * !D * !B + !A * C * D * B ), then use your diagram to obtain minimal DNF(if you understand Russian I can give a link to algorithm )

    So, if You will specify your problem I'll try to help You.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2009
    Posts
    6
    sorry about that.
    my problem is, I would like to know how will you solve values to be written in the KV Diagram
    For example, I have an expression here:

    please see attached file:

    I think that's what it's call DNF. How will I obtain the DNF here?
    thanks



    ps. sorry I don't understand Russian
    Attached Thumbnails Attached Thumbnails boolean and KV Diagram-equations.bmp  
    Follow Math Help Forum on Facebook and Google+

  4. #4
    nvv
    nvv is offline
    Newbie
    Joined
    Jan 2009
    Posts
    14
    tintincute:

    DNF(disjunctive normal form) - Disjunctive normal form - Wikipedia, the free encyclopedia

    General idea how to obtain DNF using KV Diagram:
    1)obtain values for your expression
    for example,
    a | b | avb
    0 | 0 | 0
    0 | 1 | 1
    1 | 0 | 1
    1 | 1 | 1

    about boolean operations -

    Boolean logic - Wikipedia, the free encyclopedia

    2)use KV Diagram to obtain minimal DNF

    about KV Diagram - Karnaugh map - Wikipedia, the free encyclopedia

    sorry, I won't solve your problem cause I think it will be better for to doing by yourself
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2009
    Posts
    6
    hi thanks nvv. i just don't know how to proceed. for example, if i'll set the "1-er" here I don't know how. and what's the basis.
    i would appreciate it, if you could give me an example and i'll do it by myself.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    nvv
    nvv is offline
    Newbie
    Joined
    Jan 2009
    Posts
    14
    tintincute,
    >and what's the basis
    google in help
    >if you could give me an example
    ok

    for example, we have such algebra: s=avb
    a | b | avb
    0 | 0 | 0
    0 | 1 | 1
    1 | 0 | 1
    1 | 1 | 1

    now, you must to remember, that every check on KV Diagram corresponds to ones(1) in your truth table(in my simple case there is 3 ones and 1 zero). So, next step is to fill the map:

    0 1
    1 1
    (sorry for sketchy 'image')
    How to fill the map? The answer is: we take a values from truth table(but only from col. which correspond to your expression (avb in my simple case))
    and put them in appropriate squares. I don't remember excatly, how KV Diagram 'looks' for different dimensions and I'm no sure, that it exists for some big dimensions, but for dimension size like 2,3,4 you can easily find it.

    b
    0 1
    a 1 1

    _______
    a_x1_x2_ i.e. every of this values looks like (1,*)

    b
    |1|
    |1| - i.e. every of this values looks like (*,1)

    So as You see, we have only one 0-square, which corresponds to (0, 0) vertex.

    And the last - 'glue' stage. You mast 'glue' identical values in rows and cols: in such simple case
    b
    0 1
    a 1 1

    we have two combinations

    ____
    _1_1 - where a = 1

    |1|
    |1| - where b = 1

    so min.DNF will be avb

    for such algebra : a&b

    a | b | a&b
    0 | 0 | 0
    0 | 1 | 0
    1 | 0 | 0
    1 | 1 | 1

    map will be

    b
    0 0
    a 0 1

    and we have such rows and cols:

    ____
    _0_0 - where a = 0

    |0|
    |0| - where b = 0

    so min DNF will be a'vb' where a' - inverse a

    hope this will help
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jan 2009
    Posts
    6
    thank you nvv.
    I think I know how to plot this on the KV Diagram. In your example here: my question is, how did you get the 0,1,1,1 for "avb"? did you just assigned it by yourself?

    for example, we have such algebra: s=avb
    a | b | avb
    0 | 0 | 0
    0 | 1 | 1
    1 | 0 | 1
    1 | 1 | 1

    Follow Math Help Forum on Facebook and Google+

  8. #8
    nvv
    nvv is offline
    Newbie
    Joined
    Jan 2009
    Posts
    14
    how did you get the 0,1,1,1 for "avb"
    it's a logical disjunction

    Logical disjunction - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Jan 2009
    Posts
    6
    ok but what about if you're given an expression I think you shouldn't used the logical disjunction anymore because
    like for example here
    S = !A * C * !D + !A * C * D * B

    D C B A S
    0 0 0 0 0
    0 0 0 1 0
    0 0 1 0 0
    0 0 1 1 0
    0 1 0 0 1
    0 1 0 1 0
    0 1 1 0 0
    0 1 1 1 0
    1 0 0 1 0
    1 0 1 0 0
    1 0 1 1 0
    1 1 0 0 0
    1 1 0 1 0
    1 1 1 0 1
    1 1 1 1 0

    I have 2 terms. so I only have two "1's" here. But I think this is not correct. I think it's not correct because there should be another 1 here.
    That's what I don't understand. How will you identify the output after.
    How will you know that you're output is "1" or "0"?
    I think there must be an explanation here.
    That's the point where I'm stacked now. any idea?

    thanks
    Follow Math Help Forum on Facebook and Google+

  10. #10
    nvv
    nvv is offline
    Newbie
    Joined
    Jan 2009
    Posts
    14
    tintincute, sorry, I've made a mistake: you must 'glue' only '1' values. So in your case it looks like there is no min DNF for your expression

    I have 2 terms. so I only have two "1's" here. But I think this is not correct
    no, it's correct. It's a simple situation for the complicated expressions

    I think it's not correct because there should be another 1 here
    Why do You think so?


    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Jan 2009
    Posts
    6
    what do you mean by "glue" here?
    how will you know that there is DNF or not in your expression?

    thanks
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. More Boolean
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 21st 2009, 02:17 PM
  2. Boolean Ring
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: October 18th 2009, 01:19 PM
  3. Boolean reduction
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 12th 2009, 08:08 PM
  4. Boolean Matrix of Hasse diagram.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 9th 2009, 08:59 AM
  5. Boolean product
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 30th 2009, 10:09 AM

Search Tags


/mathhelpforum @mathhelpforum