Boolean Algebra: Proving A'''' = A Using Complement and Binary Addition

[Bipolarity]

Suppose that A is an n-digit binary string: a_{0}a_{1}a_{2}...a_{n} where a_{i} is a member of the set \{0,1\}

Now define the following sequence of operations:

1) Complement each digit in A to get a binary string A'
2) A'' = A' + 1 (here + is taken to mean binary addition rather than the boolean OR)
3) Complement each digit in A'' to get a new binary string A'''
4) A'''' = A''' + 1 (here + is taken to mean binary addition rather than the boolean OR)

Prove that for all A, A'''' = A

I appreciate all the help.

BiP

 

[chiro]

Hey Bipolarity.

When you say binary addition, are you talking for example if you have say a number in binary that is 101011₂ and another number 000100₂, then is the resulting number C = A + B (where we have standard addition), but C is in binary form as well?

 

[Bipolarity]

Hey Bipolarity.

When you say binary addition, are you talking for example if you have say a number in binary that is 101011₂ and another number 000100₂, then is the resulting number C = A + B (where we have standard addition), but C is in binary form as well?

Yup!

BiP

 

[chiro]

One suggestion I have is to use the 2-complement system (add an extra bit that is a signed bit) and use the fact that if you want to invert a number, you simply invert the bits and add 1.

When it's done this way you can resort to normal arithmetic methods instead of a binary method.

You will have to take into account this adding of 1 in your inversions so that you retain the nature of the process, but again using the two's complement form will make it a lot easier.

 

[Bipolarity]

The correctness of the 2-complement system is precisely what it is I am trying to prove by posting this question.

BiP

 

[chiro]

Ohh ok, well my suggestion would be kind of circular then.

I guess the suggestion would be to just resort to the definition of addition. Basically if you are adding something then you have a carry bit and a placement bit.

Personally I think the easiest way is to recall that if you take one number in binary form say X, and you add another number where all its bits are inverted, you will get all 1's.

Now this relates to your problem by considering how you can get an expression for complementing X + 1 (where the 1 is just something with all 1's), but this is actually not too hard because you know that if you have n 1's, you can simply re-write this has a 1 with n 0's minus 1. and doing addition on this is easy because you will be adding something with a bunch of zeroes.

Now let's say you do the above: you have a number A (and take its complement) and you had 2^(n+1) - 1. It would be nice to have a way to numerically know what A^c represents numerically as opposed to bitwise.

Basically if we complement something we know that it's complement plus the origin has all 1's which means that A + A^c = 2^(n+1) - 1 where n is the number of digits in your string.

This means that A^c = 2^(n+1) - 1 - A for any A.

So you have gone from a bitwise to a completely numerical form for your A and when this is done you simply resort to algebra rather than binary bitwise operations.

I'll wait for your response, but this is going to be basically plugging in that definition a few times and seeing how it all cancels and simplifies.