1
$\begingroup$

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

$\endgroup$
0
2
$\begingroup$

$$(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$.

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

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.