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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook