Cancellation of Join in Boolean Algebra
Jump to navigation
Jump to search
Theorem
Let $\struct {S, \vee, \wedge, \neg}$ be a Boolean algebra.
Let $a, b, c \in S$, and suppose that:
\(\ds a \vee c\) | \(=\) | \(\ds b \vee c\) | ||||||||||||
\(\ds a \vee \neg c\) | \(=\) | \(\ds b \vee \neg c\) |
Then $a = b$.
Proof
\(\ds a\) | \(=\) | \(\ds a \vee \bot\) | Boolean Algebra Axiom $(\text {BA}_1 3)$: Identity Elements: $\bot$ is the identity for $\vee$ | |||||||||||
\(\ds \) | \(=\) | \(\ds a \vee \paren {c \wedge \neg c}\) | Boolean Algebra Axiom $(\text {BA}_1 4)$: Complements | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {a \vee c} \wedge \paren {a \vee \neg c}\) | Boolean Algebra Axiom $(\text {BA}_1 2)$: Distributivity: $\vee$ distributes over $\wedge$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {b \vee c} \wedge \paren {b \vee \neg c}\) | by hypothesis | |||||||||||
\(\ds \) | \(=\) | \(\ds b \vee \paren {c \wedge \neg c}\) | Boolean Algebra Axiom $(\text {BA}_1 2)$: Distributivity: $\vee$ distributes over $\wedge$ | |||||||||||
\(\ds \) | \(=\) | \(\ds b \vee \bot\) | Boolean Algebra Axiom $(\text {BA}_1 4)$: Complements | |||||||||||
\(\ds \) | \(=\) | \(\ds b\) | Boolean Algebra Axiom $(\text {BA}_1 3)$: Identity Elements: $\bot$ is the identity for $\vee$ |
Hence the result.
$\blacksquare$