Boolean Algebra (Simplification?)

Discussion in 'Math' started by kazafz, Jun 11, 2008.

  1. kazafz

    Thread Starter New Member

    Jun 11, 2008
    1
    0
    Hello there guys, hows everyone doing?

    I currently got this question from my nephew asking me how to simplify a Boolean Algebra but I don't know how to, so I was just wondering if anyone could lend me a hand?

    The Boolean Algebra is:

    W = S . (p + r) . (q + r)

    I thought about simpliying it but I only know how to simplify Sum-Of-Products expression and not Products-Of-Sums....so please, can anyone teach me so I can teach my nephew?

    EDIT: I think I phrased the question wrong because there is also a table.

    p q r S W=S . (p + r) . (q + r)
    1 1 1 0 0
    1 1 0 1 1
    1 0 1 0 0
    1 0 0 1 0
    0 1 1 0 0
    0 1 0 1 0
    0 0 1 0 0
    0 0 0 0 0

    So what the question was asking was:

    Develop a Boolean expression W in its simplest form.

    So what I did was I found the row of inputs which gave the output (W) as "1" (The row that is bolded), then I put it in the Boolean form:

    pqr's = W

    then I'm stuck because I don't know how to simplify is using Boolean Algebra.
     
    Last edited: Jun 11, 2008
  2. RiJoRI

    Well-Known Member

    Aug 15, 2007
    536
    26
    Simplify "W = S . (p + r) . (q + r)"

    First, I'd replace the dot with a star:
    W = S * (p + r)*(q + r)

    And toss in a few parens:
    W = S *( (p + r)*(q + r) )

    Then the problem looks a lot like regular algebra. Can you take it from there? You may wish to run a truth table for p, q, and r to verify the simplified form is the same as the "complexified" form.

    --Rich
     
  3. Mark44

    Well-Known Member

    Nov 26, 2007
    626
    1
    It looks to me like the table is missing some rows--eight of them, to be exact. If you have four Boolean variables (p, q, r, and S), you need 16 rows to capture all of the possible combinations of true and false.

    On the other hand, you said that this table is part of the information that was given in the problem. If that's the case, from the table, the only time W is true is when p, q, and S are true, and r is false. W is false otherwise, at least from the information in the table.
     
  4. iamspook

    Member

    Aug 6, 2008
    27
    0
    There are two simple rules for boolean algebra.
    "NOT NOT does NOUGHT"
    and
    "Break a line - change the sign"

    So

    A.B which means 'A' AND 'B'

    can be written with TWO nots (negations - normally a line above but I'll have to use parentheses and exclamation marks:

    !!(A.B) = A.B


    "Break the line change the sign: The "AND" goes to OR ( a plus sign )

    !(!A+!B) = A.B

    A and B are any statements which evaluate to TRUE/FALSE.

    So to demonstrate:

    If A = "all cats have four legs"
    and
    B = "All four legged animals are goats"

    NOT(NOT("all cats have four legs")) OR NOT("All four legged animals are goats"))

    is the same as

    "all cats have four legs" AND "All four legged animals are goats"

    Which is clearly an expression which evaluates to FALSE

    VIZ:

    NOT("all cats have four legs") = "NO cats have four legs" = FALSE
    and
    NOT("All four legged animals are goats") = "Not only goats have four legs" = TRUE

    BUT,
    NOT ( "NO cats have four legs" OR "Not only goats have four legs" ) =
    NOT ( FALSE OR TRUE ) =
    NOT ( TRUE ) =
    FALSE


    The thing just above also used a simplification that

    (FALSE OR TRUE) = TRUE which is like

    ( "Whatever" OR TRUE ) = TRUE
    Using different notation:
    ( A + 1 ) = 1

    What about ( FALSE OR "whatever" ) ? This is just "Whatever"
    Using different notation:
    (0 + A) = A

    but note (Where the . means AND)

    (0.A) = 0
    also
    (1.A) = A

    Which is the negation of the previously discussed.

    Since NOT NOT doesn't change anything, then

    !!(0.A) = !(!0+!A) = !(1+!A)

    Using these rules you can simplify boolean expressions.
     
  5. Ratch

    New Member

    Mar 20, 2007
    1,068
    3
    kazafz,

    You mean a Boolean expression, don't you?

    The notation you chose is clumsy and clunky, so I will clean it up. Also, I will use the same case. w = s(p+r)(q+r).

    That is coming up.

    The table is incomplete and disorganized by not being sequential. We will find the terms by using Boolean algebra on the expression instead of your table.

    Then let's get started.

    w = s(p+r)(q+r) = (ps+rs)(q+r)=pqs+prs+qrs+rs = pq(r+r')s+p(q+q')rs+(p+p')qrs+(p+p')rs

    = pqrs+pqr's+pqrs+pq'rs+pqrs+p'qrs+prs+p'rs
    = pqrs+pqr's+pqrs+pq'rs+pqrs+p'qrs+p(q+q')rs+p'(q+q')rs
    = pqrs+pqr's+pqrs+pq'rs+pqrs+p'qrs+pqrs+pq'rs+p'qrs+p'q'rs

    Notice how I expanded out the expression above. Now we get rid of the duplicate terms.

    =pqrs+pqr's+pq'rs+p'qrs+p'q'rs

    The terms represent the values 3,7,11,13,15. Notice your incomplete table only caught value 13.

    Now using a Karnaugh map, or my favorite way, the Quine-McCluskey tabulation method, we get a simplification to a sum of products (SOP) of w = pqs+rs

    Now let's go above and beyond and find the product of sums (POS) solution. The complement of w, represented by w' are the missing values of w, specifically 0,1,2,4,5,6,8,9,10,12,14 . Again using a K-map, or the QM method, we get w' = q'r'+p'r'+s' . Then using DeMorgan's theorem, we get w = (q+r)(p+r)s , which is what we started out with.

    Ratch
     
    Last edited: Sep 2, 2008
  6. Ratch

    New Member

    Mar 20, 2007
    1,068
    3
    iamspook,

    There are many simple rules for Boolean algebra.

    Ratch
     
  7. RiJoRI

    Well-Known Member

    Aug 15, 2007
    536
    26
    Ratch --
    What's the Quinn-McCluskey method? Tried Googling and came up only with people referring to it.

    --Rich
     
  8. Ratch

    New Member

    Mar 20, 2007
    1,068
    3
    RiJoRI,

    My bad fat finger. Try to find Quine-McCluskey. I guess Google is not big on fuzzy logic.

    Although it is my favorite method to reduce Boolean expressions, I realize and acknowledge that it is not for everyone. It takes lots of practice to become good at it. Once you do, however, you can function anywhere without a K-map. Also it shows all the prime implicants which you might miss on a K-map, especially on a 5 or 6 variable one. It systematically finds all the different ways some logical expressions can be expressed by deleting and introducing a term or two. And finally, it does not rely on pattern recognition, which is a bear for 6 or higher variable expressions on a K-map, if you can even find such a K-map. Finally, since it is a tabulation method, it is easy to program.

    The disadvantages are that it is tedious, prone to "dumb" mistakes, and usually takes longer, especially for a beginner.

    Ratch
     
Loading...