Boolean Algebra Simplification

Discussion in 'Homework Help' started by chetgnegy91, Sep 17, 2010.

  1. chetgnegy91

    Thread Starter New Member

    Sep 17, 2010
    10
    0
    Design a circuit with output f and input x0,x1,y0,y1. Let X = x1x0 and Y=y1y0 each having four possibilities (00,01,10,11) corresponding to the numbers 0,1,2,3 respectively. The output should be one when X=Y, otherwise it should be 0.
    Synthesize the simplest possible product-of-sums expression for f.

    truth table:
    x0 x1 y0 y1 | f
    --------------|-
    0 0 0 0 | 1
    0 0 0 1 | 0
    0 0 1 0 | 0
    0 0 1 1 | 0
    0 1 0 0 | 0
    0 1 0 1 | 1
    0 1 1 0 | 0
    0 1 1 1 | 0
    1 0 0 0 | 0
    1 0 0 1 | 0
    1 0 1 0 | 1
    1 0 1 1 | 0
    1 1 0 0 | 0
    1 1 0 1 | 0
    1 1 1 0 | 0
    1 1 1 1 | 1

    I made a product of sums using the maxterms.
    !=not
    (x0 + x1 + y0 + !y1)(x0 + x1 + !y0 + y1)(x0 + x1 + !y0 + !y1)(x0 + !x1 + y0 + !y1)(x0 + !x1 + !y0 + y1)(x0 + !x1 + !y0 + !y1)(!x0 + x1 + y0 + y1)(!x0 + x1 + y0 + !y1)(!x0 + x1 + !y0 + !y1)(!x0 + !x1 + y0 + y1)(!x0 + !x1 + y0 + !y1)(!x0 + !x1 + !y0 + y1)

    Ok....
    The trouble is the simplification.
    To combine the first two terms: (x0 + x1 + y0 + !y1)(x0 + x1 + !y0 + y1)
    I get: (x0 +x1+y0y1 + !y0!y1)
    A correct product of sums form cannot have any product terms like this, right?

    Also
    (x0 + x1 + y0 + !y1)(x0 + x1 + !y0 + y1)(x0 + x1 + !y0 + !y1)
    ==>(x0 + x1 + y0 + !y1)(x0 + x1 + !y0 + !y1)(x0 + x1 + !y0 + y1)(x0 + x1 + !y0 + !y1) (duplicate the last term)

    can be simplified to
    (x0 + x1 + !y1)(x0+x1+!y0)
    and then to
    (x0 +1x)

    this alone (without the other terms) violates the truth table for the last entry (1111)

    Am I making a mistake somewhere or can this not be simplified?
    Thanks in advance for any help!
     
  2. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    The answer can be simplified into a product of four terms, with 2 terms each. Why don't you try using a carnot map, and simplify the zeros? Do you know how?

    It can get troublesome if you go through expression simplification.
     
  3. chetgnegy91

    Thread Starter New Member

    Sep 17, 2010
    10
    0
    I do not know how. I'm sure I could figure it out, but the problem asks me to use algebraic simplification. I tried using the minterms and demorgan's theorem to get the POS, I got an answer, but it was four products with 4 terms each.

    Is what I have in quotes a mistake?
     
  4. chetgnegy91

    Thread Starter New Member

    Sep 17, 2010
    10
    0
    I tried the Karnaugh map and I got (x0x1+y0y1)(!x0!x1+y0y1)(x0x1+!y0!y1)(!x0!x1+!y0!y1).

    I'm pretty sure this is not considered POS form though because x0x1 is a product itself....
     
  5. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    Ok, let's start with the sensible way to do the problem, which is the carnot map. The map as it should be is below:
    k-map.png
    As you can see, in order to get the Product of Sums form, we begin with the F', by simplifying all the zeros. The quadruplets we choose to simplify are the positions (numbering starts from 0): (2,3,7,8), (8,9,12,13), (1,3,9,11) and (4,6,12,14). These give the following expression:
    F'=A'C+AC'+B'D+BD'
    which in turn gives:
    F=(F')'=(A+C')(A'+C)(B+D')(B'+D).
    In my opinion this is simple enough.

    I don't understand why the exercise would demand that you do simplifications by hand. But even so, play smart and follow the same path that the Carnot map did: Form the F' as a sum of products (the zoroes, that is), simplify them and then turn them into product of sums, using deMorgan's theorem.
     
    chetgnegy91 likes this.
  6. chetgnegy91

    Thread Starter New Member

    Sep 17, 2010
    10
    0
    That is very clear, thank you. We are only two weeks into the class, that's why we aren't doing k-maps. You have been a lot of help.
     
  7. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    Glad to hear so. Good luck with your classes.
     
Loading...