1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Using Boolean Algebra to Prove Equations

  1. Nov 5, 2011 #1
    1. The problem statement, all variables and given/known data

    There should be lines of some values to imply the "Not" form of them, however to make it easier, i'll just use the ¬ Symbol

    (a) Let x, y be elements of a Boolean algebra. Prove from the axioms that (x · y) + x = x.

    (b) Prove from the axioms of Boolean algebra that x · ¬( y · ¬x + ¬y ) = (x + x) · (y + 0). You can use DeMorgan’s and other identities we already derived in class.

    (c) In the proof of completeness of Boolean algebra, we showed how to convert every formula to its “canonical DNF”: a normal form corresponding to the DNF obtained from the truth table without any simplifications.
    Describe the normal form for the formula ¬( y · ¬x + ¬y )


    2. Relevant equations

    x + y = y + x
    x · y = y · x
    (x + y) + z = x + (y + z)
    (x · y) · z = x · (y · z)
    x · (y + z) = x · y + x · z
    x + y · z = (x + y) · (x + z)
    x + 0 = x
    x · 1 = x
    x + ¬x = 1
    x · ¬x = 0
    0 ≠ 1

    3. The attempt at a solution

    Part a, i don't even know how to start it. There doesn't seem to be anything i can do to it.

    Part b, i have an attempt for
    x * ¬(y * ¬x + ¬y) = (x + x) * (y + 0)
    x * (¬y + x * y) = (x + x) * (y + 0)
    x * (¬y + y * y + x) = (x + x) * (y + 0)
    x * (1 * y + x) = (x + x) * (y + 0)
    x * (x + 1) * (y + 1) = (x + x) * (y + 0)
    x * x + x * 1 * (y + 1) = (x + x) * (y + 0)
    0 + x * (y + 1) = (x + x) * (y + 0)
    0 + (x * y) + (x * 1) = (x + x) * (y + 0)
    0 + (x * y) + (x) = (x + x) * (y + 0)

    but i get here and get stuck.

    and part c, much like part a, i don't even know how to start it.
     
  2. jcsd
  3. Nov 8, 2011 #2

    ehild

    User Avatar
    Homework Helper
    Gold Member

    a) You did not include into the relevant equations but you certainly know that x+1=1.
    There are two more axioms: 1*x=x and the distributive law: a*(b+c)=a*b+a*c.
    Write y*x+x in the form y*x+1*x, apply the reverse of the distributive law, (factor out x) ...

    b)

    ¬(y * ¬x + ¬y) ≠(¬y + x * y).

    The correct application of de Morgan rule is :

    ¬((y * ¬x) + ¬y) =¬(y * ¬x)*y=(¬y+x)*y=....

    c)Set up the truth table of the expression. Collect what product of x and y result 1 and add them. For example, if you get 1 when x= 0 and y =1 and also when x=1 and y = 1, then the canonical form is ¬x*y + x*y.

    ehild
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Using Boolean Algebra to Prove Equations
  1. Boolean algebra (Replies: 1)

  2. Boolean Algebra (Replies: 7)

  3. Boolean Algebra prove (Replies: 8)

Loading...