Question

In Exercises 35–42, use the laws in Definition \(1\) to show that the stated properties hold in every Boolean algebra.

Show that in a Boolean algebra, every element \({\bf{x}}\)has a unique complement \({\bf{\bar x}}\) such that \({\bf{x}} \vee {\bf{\bar x = }}1\) and \({\bf{x}} \wedge {\bf{\bar x = }}0\).

Short answer

The component of \(x\) is unique

Step-by-step solution

Definition

The complement of an element: \(\bar 0 = 1\) and \(\bar 1 = 0\)

The Boolean sum \( + \) or \(OR\) is \(1\) if either term is \(1\)

The Boolean product or \(AND\) is \(1\) if both terms are \(1\)

Identity laws

\(\begin{array}{c}x \vee 0 = x\\x \wedge 1 = x\end{array}\)

Complement laws

\(x \vee \bar x = 1\)

\(x \wedge \bar x = 0\)

Commutative laws

\(x \vee y = y \vee x\)

\(x \wedge y = y \wedge x\)

Distributive laws

\(x \vee \left( {y \wedge z} \right) = \left( {x \vee y} \right) \wedge \left( {x \vee z} \right)\)

\(x \wedge \left( {y \vee z} \right) = \left( {x \wedge y} \right) \vee \left( {x \wedge z} \right)\)

Using the identity, complement and commutative laws

To proof: The complement of \(x\) is unique.

PROOF

Let \(y\) be the complement of \(x\) (thus \(x \vee y = 1\) and \(x \wedge y = 0\)).

Using the Identity, complement, distributive and commutative laws

\(\begin{eqnarray}y{\bf{ }} &=& y \wedge 1\\ &=& y \wedge \left( {x \vee \bar x} \right)\\ &=& \left( {y \wedge x} \right) \vee \left( {y \wedge \bar x} \right)\\ &=& \left( {x \wedge y} \right) \vee \left( {y \wedge \bar x} \right)\end{eqnarray}\)

\(\begin{eqnarray} &=& 0 \vee \left( {y \wedge \bar x} \right)\\ &=& y \wedge \bar x\\ &=& \left( {y \wedge \bar x} \right) \vee 0\\ &=& \left( {y \wedge \bar x} \right) \vee \left( {x \wedge \bar x} \right)\end{eqnarray}\)

\(\begin{eqnarray} &=& \left( {\bar x \wedge y} \right) \vee \left( {\bar x \wedge x} \right)\\ &=& \bar x \wedge \left( {y \vee x} \right)\\ &=& \bar x \wedge \left( {x \vee y} \right)\\ &=& \bar x \wedge 1\\ &=& \bar x\end{eqnarray}\)

Therefore, this is to note that \(y = \bar x\) and thus \(\bar x\) (the complement of \(x\) ) is unique.