# Basic Boolean Algebra Proof: Validity of the Cancellation Law?

• XcKyle93
In summary: Thanks for pointing that out!In summary, it has been proven that in a Boolean algebra, the cancellation law does not hold as there exist values x, y, and z such that xy = xz but y does not equal z. This can be demonstrated through a counterexample or by considering the postulates of a Boolean algebra, which do not allow for the cancellation of elements without an inverse.
XcKyle93

## Homework Statement

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.

## Homework Equations

The 6 postulates of a Boolean Algebra

## 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.

Welcome to PF, XcKyle93!

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).

On one line you have:

XcKyle93 said:
show that, for every x, y, and z in a Boolean algebra, xy = xz does not imply y = z.

But on the other:
XcKyle93 said:
Suppose that for a Boolean algebra, x = 0, y = 1, z = 0. Then, xy = yz becomes:
0*1 = 1*0
0 = 0

Surely you meant to plug in values to "xy = xz"?

Whoops, my bad. I did mean xy = xz, and 0 * 1 = 0 * 0, 0 = 0. That was a bad typo.

Your proof is correct. To prove that the cancellation law does not hold in a Boolean algebra, you can use the postulates of a Boolean algebra and the counterexample you have provided. Another way to prove this is by using a truth table, where you can show that there exist values of x, y, and z that make xy = xz true, but y ≠ z. This also demonstrates that the cancellation law does not hold in a Boolean algebra.

## 1. What is the Cancellation Law in Boolean Algebra?

The Cancellation Law states that in Boolean algebra, if two terms are being ANDed and one term is the inverse of the other, then the result will always be 0. Similarly, if two terms are being ORed and one term is the inverse of the other, then the result will always be 1.

## 2. How is the Cancellation Law used in Boolean Algebra proofs?

The Cancellation Law is used to simplify Boolean expressions and make proofs more efficient. It is especially useful in proving the validity of certain Boolean identities and laws.

## 3. What is the process for proving the validity of the Cancellation Law?

The process involves setting up the Boolean expression and applying the Cancellation Law to simplify it. Then, using the basic properties and laws of Boolean algebra, the expression is further simplified until it is reduced to a single term or a known identity.

## 4. Can the Cancellation Law be applied to any Boolean expression?

No, the Cancellation Law can only be applied when two terms are being ANDed or ORed and one term is the inverse of the other. Additionally, the terms must not contain any variables or variables that cancel out.

## 5. What is the significance of the Cancellation Law in Boolean algebra?

The Cancellation Law is an important tool in Boolean algebra as it allows for the simplification of expressions and proofs. It also helps in understanding the properties and behaviors of Boolean expressions and can be used to solve logic problems in computer science and digital electronics.

• Engineering and Comp Sci Homework Help
Replies
5
Views
5K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K
• Engineering and Comp Sci Homework Help
Replies
15
Views
3K
• Engineering and Comp Sci Homework Help
Replies
9
Views
3K
• Engineering and Comp Sci Homework Help
Replies
2
Views
4K
• Engineering and Comp Sci Homework Help
Replies
6
Views
16K
• Engineering and Comp Sci Homework Help
Replies
1
Views
5K
• Engineering and Comp Sci Homework Help
Replies
4
Views
2K
• Calculus and Beyond Homework Help
Replies
2
Views
832
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K