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!

Basic Boolean Algebra Proof: Validity of the Cancellation Law?

  1. Feb 16, 2012 #1
    1. The problem statement, all variables and given/known data

    Prove that in a Boolean algebra the cancellation law does not hold; that is, show that, for every x, y, and z in a Boolean algebra, xy = xz does not imply y = z.

    2. Relevant equations
    The 6 postulates of a Boolean Algebra


    3. The attempt at a solution
    I am uncertain as to whether or not what I have done is a valid proof. Plus, is there a way to do this using solely the postulates? That's what I initially tried to do, but I drew a blank. I honestly needed a hint for the below.

    Suppose that for a Boolean algebra, x = 0, y = 1, z = 0. Then, xy = yz becomes:
    0*1 = 1*0
    0 = 0
    Thus, xy = yz does not imply that y = z, and the cancellation law of multiplication does not hold for a Boolean Algebra.
     
  2. jcsd
  3. Feb 18, 2012 #2

    I like Serena

    User Avatar
    Homework Helper

    Welcome to PF, XcKyle93! :smile:

    You have just completed the proof.
    It's a proof by counterexample.
    If you can find an example in which a proposition does not hold, that is enough to proof it false.

    To do it by the postulates, you need to consider what left cancellation means.
    What you actually do, is multiply the left with the inverse of x.
    However, in a boolean algebra not every element has an inverse, so cancellation is not allowed.

    Note that "cancellation" is not an axiom, but a proposition.
    It (only) follows if every element has an inverse (which is not the case here).
     
  4. Feb 18, 2012 #3
    On one line you have:


    But on the other:
    Surely you meant to plug in values to "xy = xz"?
     
  5. Feb 19, 2012 #4
    Whoops, my bad. I did mean xy = xz, and 0 * 1 = 0 * 0, 0 = 0. That was a bad typo.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Basic Boolean Algebra Proof: Validity of the Cancellation Law?
Loading...