3

The proof should be built of the following postulates, for a Boolean Algebra:

P1. The operations (+) and (·) are commutative.

P2. There exist in B distinct identity elements 0 and 1 relative to the operations (+) and (·), respectively.

P3. Each operation is distributive over the other.

P4. For every a in B there exists an element a′ in B such that $a + a′ = 1$ and $aa′ = 0$

More importantly, what is the reasoning for each step?

All I've managed is to go down different paths hoping to eventually see some clues (which hasn't worked) but this can't be an efficient way to approach this

Edit: Please see my attempts in attached photo attempt

Jay M
  • 277
  • What methods of simplification are you allowed to use? In addition, how is equality defined in your course? If you can write a Karnaugh map then that would be the easier way to solve the problem, as it can make the answer clear without a clear definition of equality. – user400188 May 19 '20 at 05:14
  • 1
    @user400188 sorry, I should have been clearer!. I've edited the question to include the postulates given for a Boolean Algebra. Ideally the proof should use them since this question is supposed to solidify one's understanding of those postulates and how they apply to any Boolean Algebra – Jay M May 19 '20 at 05:25
  • I am still a bit confused about equality. Is it the case that $a=b$ in this question corresponds to $a\iff b$? That is $a=b$ is the same as $ab+a'b'$? If this is the case, then the best way to approach this problem would be to expand the equalities so that they correspond to there definitions, then conjoin them and simplify until you get $a=b$. – user400188 May 19 '20 at 05:28
  • @Jay M it would be helpful for us to understand the question, if you could also post your attempts – Ethan May 19 '20 at 05:42
  • 2
    I have just added my attempts in a photo – Jay M May 19 '20 at 06:28

1 Answers1

5

I think what you are looking for is:

If $ a + x = b+x $ then $$\begin{align} (a+x)x' &= (b+x)x' \\ ax' +xx' &= bx' + xx' & \text{operator } \cdot \text{ is distributive} \\ ax' &= bx' & \text{because }xx' = 0 \end{align}$$ Similarly, using $a+x' = b+x'$ you obtain $ax = bx$, so that $$\begin{align} ax'+ax &= bx'+bx \\ a(x'+x) &= b(x'+x) & \text{operator } \cdot \text{ is distributive} \\ a\cdot 1 &= b \cdot 1 &x+x' = 1\\ a &= b&1 \text{ is an identity} \end{align}$$

It seems you have not stated the operators are associative nor that the inverse is unique. I suspect that limits the steps you can take.

WA Don
  • 4,488
  • How do you know that multiplying the equations by two constants is allowed? – user400188 May 19 '20 at 06:56
  • 1
    @user400188 If $a=b$, then $ac=bc$; otherwise product would not be an operation. – amrsa May 19 '20 at 07:05
  • What I mean by my first comment is, the original question is to prove that $a+x=b+x$ and $a+x'=b+x'$ imply that $a=b$. If you multiply both equations by a constant, what you have really proved is instead: $(a+x=b+x)\cdot x'$ and $(a+x'=b+x')\cdot x$ imply that $a=b$. – user400188 May 19 '20 at 07:22