Something I discovered doing logic

[vin300]

I haven't known about a law that says so. Step 1: using two numbers in any format: binary, octa, hexa, do an AND operation. Step 2: Perform OR operation on the same numbers. Step 3: Add the results of step 1 and 2 numerically. The result comes out to be the same as the sum of original numbers.

 

[Stephen Tashi]

Give an example to explain what you mean by performing an "AND" and an "OR" operation on two numbers. Show an example in ordinary base 10 representation.

 

[Erland]

Hmm I wonder if "X and Y" simply means min(X,Y) and "X or Y" means max(X,Y), when applied to numbers. If so, what vin300 has discovered is just that min(X,Y)+max(X,Y)=X+Y, which is easy to see.

 

[h6ss]

I haven't known about a law that says so. Step 1: using two numbers in any format: binary, octa, hexa, do an AND operation. Step 2: Perform OR operation on the same numbers. Step 3: Add the results of step 1 and 2 numerically. The result comes out to be the same as the sum of original numbers.

What you "discovered" is that P&Q added to P|Q is equal to P+Q, right?

Here's a short explanation of what's really happening. Using the bitwise operator "&" for the logical operator "AND" and the bitwise operator "|" for the logical operator "OR", evaluating the expression P&Q basically creates a binary number with "1" at each position where both numbers have a "1" and puts zeros elsewhere; the expression P|Q does the same thing but puts a "1" at each position where at least one of the two numbers has a "1" and also puts zeros elsewhere. So when you add both expressions P|Q and P&Q, you're basically adding P and Q and the remainders, which gives you P+Q. This works under binary arithmetic since the only possible operations we have for addition are:

• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 0 = 1
• 1 + 1 = 0, and carry 1 to the next more significant bit, i.e. in this direction ←

In other words, when you evaluate P&Q or P|Q, every position where P and Q both had zeros will remain zero; likewise, every position where at least P or Q or both had "1" will remain the same. Since in the last case one event is included in the other, this assures you under the arithmetic rules we agreed on that adding P&Q and P|Q is equivalent to add P and Q.

Here is an example with P=5 and Q=6:

Expression     Result     Binary Description
P              5          00000101
Q              6          00000110
P & Q          4          00000101 & 00000110 = 00000100
P | Q          7          00000101 | 00000110 = 00000111

When you add P&Q and P|Q, you have:

      1
  00000100 = P & Q
+ 00000111 = P | Q
----------
  00001011 = (P & Q) + (P | Q)

And when you add P and Q, you have:

      1
  00000101 = P
+ 00000110 = Q
----------
  00001011 = P + Q

We can see that both expressions are equal. Of course the mathematical representation of bitwise operations can get messier depending of what we're using, e.g. if P and Q are not positive and/or integers, but that's the general procedure used to handle these operations, and basically every programming language that I know of does that.