Boolean algebra: complement

  • Thread starter Bipolarity
  • Start date
  • #1
Bipolarity
775
2
Suppose that A is an n-digit binary string: [itex] a_{0}a_{1}a_{2}...a_{n} [/itex] where [itex]a_{i}[/itex] is a member of the set [itex]\{0,1\}[/itex]

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
 

Answers and Replies

  • #2
chiro
Science Advisor
4,815
134
Hey Bipolarity.

When you say binary addition, are you talking for example if you have say a number in binary that is 1010112 and another number 0001002, then is the resulting number C = A + B (where we have standard addition), but C is in binary form as well?
 
  • #3
Bipolarity
775
2
Hey Bipolarity.

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

Yup!

BiP
 
  • #4
chiro
Science Advisor
4,815
134
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.
 
  • #5
Bipolarity
775
2
The correctness of the 2-complement system is precisely what it is I am trying to prove by posting this question.

BiP
 
  • #6
chiro
Science Advisor
4,815
134
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.
 

Suggested for: Boolean algebra: complement

Replies
13
Views
3K
Replies
15
Views
810
  • Last Post
Replies
6
Views
384
  • Last Post
Replies
10
Views
1K
Replies
12
Views
3K
Replies
3
Views
1K
Replies
1
Views
926
  • Last Post
Replies
2
Views
143
Replies
8
Views
2K
Top