# Boolean Algebra - proof without associativity?

I would like to prove the following:

$(x\cdot y) + (\overline{x} + \overline{y}) = 1$

without the Associativity Property. I can't seem to do this algebraically (without truth tables).

$$(x\cdot y) + (\overline x + \overline y) = (x\cdot y)+ (\overline{x\cdot y}) = 1$$

We simply make use of Demorgan's Law, and the identity $p + \overline p = 1$.

• I was using the statement as part of a proof for DeMorgan's actually--is there some way to prove it without this? May 11 '15 at 22:38
• You can easily do a case analysis. Four cases to consider May 11 '15 at 22:40

So I cannot use Associative:

$X + (Y + Z) = (X + Y) + Z = (X + Z) + Y = X + Y + Z$

$(x\cdot y) + (\overline{x} + \overline{y})$

Expand minimized terms using complement

$(x\cdot y) + (\overline{x} \cdot (\overline{y} + y) + \overline{y} \cdot (\overline{x} + x))$

$(x\cdot y) + (\overline{x}\cdot\overline{y} + \overline{x}\cdot y + \overline{y} \cdot \overline{x} + \overline{y}\cdot x)$

Remove duplicates with Idempotent.

$(x\cdot y) + (\overline{x}\cdot\overline{y} + \overline{x}\cdot y + \overline{y}\cdot x)$

Extract common terms with Redundancy and Complement.

$x \cdot (y + \overline{y}) + \overline{x} \cdot (\overline{y} + y)$

I may of used Associative by removing brackets. Complement again.

$x + \overline{x}$

$1$

A lot easier using deMorgan's.

Laws and Theorems of Boolean Algebra

First note that \begin{align*} x + (\overline x + \overline y) &= 1\cdot (x + (\overline x + \overline y)) \\ &= (x + \overline x)\cdot (x + (\overline x + \overline y)) \\ &= x + (\overline x\cdot (\overline x + \overline y)) \\ &= x + ((\overline x + 0)\cdot (\overline x + \overline y)) \\ &= x + (\overline x + (0\cdot \overline y)) \\ &= x + (\overline x + 0) \\ &= x + \overline x \\ &= 1 \end{align*} Similarly, $$y + (\overline y + \overline x) = 1$$ So \begin{align*} (x\cdot y) + (\overline x + \overline y) &= (x + (\overline x + \overline y))\cdot (y + (\overline x + \overline y)) \\ &= (x + (\overline x + \overline y))\cdot (y + (\overline y + \overline x)) \\ &= 1\cdot 1 \\ &= 1 \end{align*}

This uses distributivity and the properties of $0$ and $1$, but not associativity and not De Morgan. (I also used the commutativity of $+$, but it's not essential.)