Hi all,
I have a mathematical question:

is it possible to expand this formula? :

(A + B) XOR C

I mean, like (A + B) * C = A*C + B*C ?

even if it requires indefinitude.. (and maybe with some suppositions, like "if A and B < 7F then...". etc) I will be very glad to hear any opinions.

p.s> sure I know how this operations works separately, but wanna hear a point of view of a mathematician. maybe I missed something and this thing can be solved?

Thanks!
Posted on 2005-02-19 04:08:05 by xor_eax
A XOR B XOR C

...results in the same value for a large percentage of numbers.

Posted on 2005-02-19 14:15:21 by bitRAKE
(A+B) here is A or B? or it's + ?
if it's + then One more: A,B,C are sets (many bits binary numbers) or they are logical values (i.e. E {0,1} and nothing more)?
Posted on 2005-02-19 15:03:20 by The Svin
if "+" is "add" then there are crucial differences between it and XOR, addition operation depends on the values of the numbers and XOR "seems" to depends on the actual representation of the number.

What I mean is XORing only makes sense in terms of base 2 (binary) while addition doesn't care about the base so it's unlikely that there will be a way of expanding unless as Svin suggests there are some restrictions on the values of A, B & C.

But this is just me thinking out loud, I've no real experience of this.
Posted on 2005-02-19 15:44:27 by Eóin
I think by "expansion of brackets" he means what we call in math distribution. And distribution assumes that something is distrebutive TO something other (by something I mean operation)
for example in classic arithmetics (sine Euclid) multiplication distributive to
addition (and substruction as a kind of addition) a(b+c) = ab+ac
but addition is not distributive to mult so we can not a+(bc)=(a+b)(a+c)
By the above I just want to stress importance of "what is distributive to what" the order matters.
In boolean algebra both mult (and) distributive to addition (or) and also
addition distributive to multiplication
so
A & (B | C) = (A&B) | (A&C)
and also
A | (B & C) = (A | B) & (A | C)

XOR as exclusive OR in neither distr to OR nor to AND.
It's easy to check since in canonical way XOR is simmetrical logical substruction (in terms of set theory) i.e. A xor B <=> (A&B') | (A'&B)
and after replacing A xor (B | C) with
(A&(B|C)') | (A'&(B|C))
we can see contradiction in truth table with distribution.
So in logical means it's not distributive.

My question actually realeted mostly to bitRake statement.
If A B C are logical (meaning only 1 or 0 and results of operation is also might be (limited by areg terms) only 1 or 0) and + here is addition by modula 2, then his statement is correct. Since addition modulo 2 and XOR are equvalents.
Yet if + means OR, or + means ADD and A B C are sets not boleans - then the statement is wrong.
Posted on 2005-02-19 18:42:09 by The Svin
The point here is that XOR is only applied to bits and it dosent generate a carry ;), only generate 1 output (not two like a adder).


Altought XOR can be used for make a half-adder and then a combination of half-adders come and is called a complete adder.

For example for binary:


01 XOR 01 = 00
01 + 01 = 10


A half adder will have two inputs: i1 and i2 (in bits), and two outputs: sum and carry.

The functions for the two outputs can be expressed in a lot of diferent ways :) (you know the boolean logic and the gates to be used), pheraphs some like this:

input:
i1, i2
output:
sum = i1 XOR i1
carry = i1 AND i2


( 0010 + 0001 ) equal ( 0010 XOR 0001)
( 0001 + 0001 ) not equal ( 0001 XOR 0001)


The fact is that "XOR" can only replace a "+" where the secuence of bits exclude each other in the bits set and in that way dosent generate the carry and is because of that than seem like a XOR like the first example can replace a "+", the problem is where the set bits have the same position generating a carry like te second one.

this is what you mean by "how this operations works separately" ???


is it possible to expand this formula? :

(A + B) XOR C

I mean, like (A + B) * C = A*C + B*C ?


For first point like Svin say if you take "+" like "or" seem not posible to expand (1 or 0) XOR 1 = 0, and, (1 XOR 1) or (0 XOR 1) = 1. I dont remember the expression of XOR in basic gates :S... that will clear more on.

In the second case taking the "+" like a sum, then dont know ;), but pheraphs taking the other "near" problem will show some???

Instead of:

(A + B) XOR C, take A + (B XOR C)

if you see by the () the XOR will never generate a carry and finally B XOR C can be considered like a "single unit" that dosent generate a carry or need and the computation on each bit dosent is propagated trought the others... then we can have this "single unit" called like D, then A+D is the problem to solve...

you see, in this case if we whant that A + D become in the outputs like A XOR D, then we need restriction over the values that A and D can take, if and only if (I guess ;)) A and D equal zero then A+D == A XOR D.

You can take the direct aproach and see that in the case that:

(A+B) XOR C == A XOR B XOR C

you need that A and B equal zero, that is, they mutually exclude in each position of a bit set.





hehe, and here Im complicating things (again) or expanding things to much, if you take the first definitions of the adder, the ones that define the outputs, you will conclude that for dont generate a carry (= i1 and i2) you only need i1 and i1 = 0 ;) and in that way only matter the first output (i1 XOR i2).

What you think I normally overcomplicate things :S.
Posted on 2005-02-19 19:23:55 by rea
(A+B) here is A or B? or it's + ?
if it's + then One more: A,B,C are sets (many bits binary numbers) or they are logical values (i.e. E {0,1} and nothing more)?


yes, sorry, this is my fault. I didnt want you to explain the extra things.. sorry.

A,B and C arent logical values, they are bytes (i.e. many bits binary numbers, in general, its not important, bytes,words, dwords...).

and, about distribution.. well, what I wanted to ask. In general, this question was generated from this task (I use C syntax, so "+" is ADDition, and "^" is XOR):

((A+B) ^ C - D) ^ (A+B) = E

is it possible to express A or B from this equation ?

if I'll try to express (A+B) I get this:

(A+B) = E ^ ((A+B) ^ C - D)

or this:

(A+B) = (E ^ (A+B) + D) ^ C

it confuses me :oops:

so, even if we will be able replace (A+B) by (A^B) (when we agree some suppositions..), this will not help us.., isnt it ?
Posted on 2005-02-20 05:22:34 by xor_eax
There are some rules for reduction, is called some like "..." remembering....

One of them are:
(a->b) & (b -> c) can be reduced to a->c

is called.... "inference rules" or is at less like I know them, also you can use the "boolean postulates" (If I remember well) like: a & ~a = 0, a | ~a = 1, the morgan's laws :).

The only point is that + is a operator that is boolean result not only produce only one boolean variable but two then I guess it can't be handled with such reductions ...


heer you can find ones... www.mathpath.org/proof/proof.inference.htm

The one like a U rotated 90 degrees if Im not wrong is -> or => or single implication?????
Posted on 2005-02-20 10:59:31 by rea
rea
thanx for the hint, but I know the morgan's law :)

but we cannot apply any of them to simplify this:
((A+B) ^ C - D) ^ (A+B) = E

... okay, then my question is transformed to: "is it possible to express A variable from this formula?", that is A = ...

Thanx for your time spending.
Posted on 2005-02-20 12:08:29 by xor_eax

but we cannot apply any of them to simplify this:
((A+B) ^ C - D) ^ (A+B) = E


Let's use this one (Svin's law - jocking)
(A ^ B <=> C) <=> ((A ^ C <=>B) & (B ^ C <=>A))
Thus:
((A+B) ^ C - D) ^ (A+B) = E <=>
((A+B) ^ C - D) ^ E = (A+B)
Posted on 2005-02-20 12:35:58 by The Svin

but we cannot apply any of them to simplify this:
((A+B) ^ C - D) ^ (A+B) = E


Let's use this one (Svin's law - jocking)
(A ^ B <=> C) <=> ((A ^ C <=>B) & (B ^ C <=>A))
Thus:
((A+B) ^ C - D) ^ (A+B) = E <=>
((A+B) ^ C - D) ^ E = (A+B)

"<=>" means "not equal"? so, why they're not equal? :?

ps> A,B,C and D are any numbers.
Posted on 2005-02-20 12:49:47 by xor_eax
<=>
<-> etc. means equal.
-> means implication, both side implication means equality.
if b follows a and a follows b then a equal b.
It's terms of math logic where = means algebra meaning of to be equal,
and <=> logical (limited to truth and false area) meaning
If you are confused with logic means you can just spell
((A+B) ^ C - D) ^ E = (A+B) ->
A = ((A+B) ^ C - D) ^ E - B
Is that what you want, to express "A"?
Posted on 2005-02-20 12:57:38 by The Svin
If you are confused with logic means you can just spell
((A+B) ^ C - D) ^ E = (A+B) ->
A = ((A+B) ^ C - D) ^ E - B
Is that what you want, to express "A"?


when I said above:
if I'll try to express (A+B) I get this:
(A+B) = E ^ ((A+B) ^ C - D)
or this:
(A+B) = (E ^ (A+B) + D) ^ C

I knew that from this
(A+B) = (E ^ (A+B) + D) ^ C
I can get this:
A = ((E ^ (A+B) + D) ^ C) - B

okay, but, how can I calculate A if I know B,C,D and E ?
by "express A" I meant a possibility to express A that will depend only on B,C,D and E.

and we got that A depends on A... that is where the problem... :(
Posted on 2005-02-20 13:15:00 by xor_eax
No, you can't. If you rearrange, you get:
D = C^(A+B) - E^(A+B)
For any bit that is common to C and E, the corresponding bit in A+B can't be determined.
Posted on 2005-02-20 14:51:28 by Sephiroth3
A = ((A+B) ^ C - D) ^ E - B
ok, is a the transcendental equation.
but, afaik transcendental doesnt mean unsolvable...
maybe with some suppositions we can solve it ?..
but I think my question annoys you already...
Posted on 2005-02-21 04:13:58 by xor_eax
Hi

If we take:

> ((A+B) ^ C - D) ^ (A+B) = E

Can't it be expressed as:

(M ^ N) ^ M = E

And we know that ^ doesn't care about brackets (i forget the term), so

M ^ N ^M = E

and order doesn't matter for ^ so it can be

N ^ M ^ M = E

and we know that any ^ the same = 0

so answer is just N = E

so, the original question of "can you get A + B" is impossible, right?
Posted on 2005-02-21 05:04:40 by abc123
abc123
this thing is not easy as 123,
you forgot about "- D" <- it is just what makes the trouble to express A or B. I mean, D is subtracted only after (A+B) is xored with C. We cant replace (C - D) by N...
Posted on 2005-02-21 05:53:58 by xor_eax
> you forgot about "- D" <- it is just what makes
> the trouble to express A or B. I mean, D is subtracted
> only after (A+B) is xored with C. We cant replace (C - D) by N...

Oh..........

I see.

I assumed in c with no brackets that "-" operator is evaluated before "^" operator hence my misunderstanding.
Posted on 2005-02-21 05:58:48 by abc123
xor_eax, I think I see where the confusion here is coming from.

First I'm curious where this equation came from. A = ((A+B) ^ C - D) ^ E - B is very much a prgramming thing, ie we're all used to using things like A=A+B in a program but thats not being used in the same way as in an algebra equation.

To explain, starting with A=A+B and saying I know B and want to express it in terms of B doesn't work casue A=A+B really means B=0.

In a different case you could have the line A=2A+B in a program, here at least when taking A=2A+B as an equation the A's don't disappear and we can rewrite A=-B. But that doesn't make sense in relation to the origional program, and here's why.

In the programming line A=2A+B, the A's have a different value. When we write this equation in math notation we have to distinguish the A's somehow, the easiest way is subscript ( using _ ) so the programming line A=2A+B becomes the math equation A_2 = 2A_1 + B, or if this were happening in a loop then then we'd include i's, A_(i+1) = 2A_i + B.

So you see you can only express A = ((A+B) ^ C - D) ^ E - B in terms of B, C, D & E if the value of A is the same. And if those A's are the same then as Sephiroth3 points out you can't do it anyway.

Another important thing XOR as a mathematical operator operates only on binary 0,1. Even though we can use it on 32bit regs its not really operating on a 32bit numbers, ultimatly it only operates on 0 and 1. Addition however does operate on 32bit numbers so I don't think you can mix the two in a math equation unless you limit yourself to 1 bit numbers. In which case add and sub are really xor anyway.
Posted on 2005-02-21 07:26:51 by Eóin
In the programming line A=2A+B, the A's have a different value. When we write this equation in math notation we have to distinguish the A's somehow, the easiest way is subscript ( using _ ) so the programming line A=2A+B becomes the math equation A_2 = 2A_1 + B, or if this were happening in a loop then then we'd include i's, A_(i+1) = 2A_i + B.

I understand this perfectly... But, this equation didnt come from a programming line. It came from other equation when I was calculating some thing (I didnt make a mistake, 100%). Actually it was not exactly as I posted here.. Ohh, nevermind :)
So you see you can only express A = ((A+B) ^ C - D) ^ E - B in terms of B, C, D & E if the value of A is the same. And if those A's are the same then as Sephiroth3 points out you can't do it anyway.

This is the final solve, it is impossible, that is what I wanted to know.

Thanks to all!
Posted on 2005-02-21 07:42:00 by xor_eax