Log in

View Full Version : XOR property (MD4/5 related)

bilbo
April 18th, 2005, 04:53
Hi all,
how can we prove that:
Code:
(X and Y) or (notX and Z)
can be replaced by
Code:
(Z xor (X and (Y xor Z)))
???

Well, the "bruteforce" demonstration is obvious: we test the whole space for inputs (with SPACE 1 as well as 256 for X,Y,Z: it is enough the case one-bit)
Code:


#include <stdio.h>



#define SPACE 1



void

main(void)

{

    int X, Y, Z;



    for (X=0; X<SPACE; X++) for (Y=0; Y<SPACE; Y++) for (Z=0; Z<SPACE; Z++)

        if ((X&Y | (~X&SPACE-1)&Z) != (Z ^ (X & (Y^Z)))) {

            printf("ko: X=%d, Y=%d, Z=%d\n", X, Y, Z);

            return;

            }

    printf("ok\n";

}


but, is there some more elegant demonstration?
Thanks, bilbo
Shub-nigurrath
April 18th, 2005, 05:08
generally speaking these things are demonstrated through a truth table, that's a "bruteforcing", used to find the minimum or equivalent circuit. There are no theorems that come to my mind at the moment. And anyway all the theorems are demonstrated always using a trugh table and showing that the two circuits are equivalent at the pins..
mike
April 18th, 2005, 05:09
Quote:
[Originally Posted by Bilbo]is there some more elegant demonstration?

Yeah: notice that there aren't any carries, so showing it's true for one bit means it's true for n bits. Or is that what you meant by SPACE=1?

Anyway, A xor B = A+B; A and B = AB; A or B = A+B+AB; notA = A+1; AA=A

(X and Y) or (notX and Z)
= XY + (X+1)Z + XY(X+1)Z
= XY+XZ+Z+XYZ+XYZ
= XY+XZ+Z
= Z+X(Y+Z)
=(Z xor (X and (Y xor Z)))
naides
April 18th, 2005, 05:41
Mike:

Perhaps it is just a set of different, but equivalent conventions, but as far as I recall:

A or B = A + B

A xor B = A(notB) + (notA)B

I know chances are I am wrong. . .
bilbo
April 18th, 2005, 09:51
Got it, Mike, but...
ooh, I'm so short-sighted...

can we also elegantly demonstrate
Code:
A or B = A xor B xor AB
or is it just a matter of truth tables, as Shub-nigurrath suggested?

Thanks, bilbo
SiGiNT
April 18th, 2005, 12:40
The HTML wouldn't paste correctly, maybe this link will apply.

http://www.omnifarious.org/~eljay/info_ttable.html (http://)


SiGiNT
mike
April 18th, 2005, 16:19
Quote:
[Originally Posted by naides]Perhaps it is just a set of different, but equivalent conventions
Yes. It depends on which rig you choose. Here I'm using + to mean normal addition modulo 2.
Quote:
[Originally Posted by bilbo]can we also elegantly demonstrate A or B = A xor B xor AB

How would you write OR when all you've got is multiplication and addition mod 2? We can pretty much just take it as the definition of OR.

If you want to use + to mean OR, that's fine, but then we have to define XOR like naides suggested, and you'd be asking for an elegant demonstration of that
bilbo
April 19th, 2005, 00:32
Thanks, Mike,

I intended, for elegantly, only in terms of AND/OR (canonical XOR definition suggested by naides) and De Morgan theorems (and I know it can be done, see exercise 1 at http://www.ee.scu.edu/classes/2000fall/elen021/hwk/hw3/hw3.html).

Anyway, also your point of view (only in terms of plus/times operators) is interesting.

Best regards, bilbo
mike
April 19th, 2005, 03:30
Yes, it can be done, but the derivation is a lot longer. In fact, if elegance is inversely proportional to the length of the proof, then the most elegant proof is the truth table!

A rig is a mathematical gadget (R, 0, 1, +, *), where R is a set and 0,1,+ and * behave the way you'd normally expect: * distributes over +, 0 annihilates under multiplication and is the additive identity, 1 is the multiplicative identity, etc.

There are two 2-element rigs,
({F,T}, F, T, OR, AND) = ({0,1}, 0, 1, max, min)
and
({F,T}, F, T, XOR, AND) = ({0,1}, 0, 1, + mod 2, *)

Other rigs include the integers: ( {..., -2, -1, 0, 1, 2, 3, ...}, 0, 1, +, *)
the reals: ( Reals, 0, 1, +, *)
the nonnegative rationals: ( rationals >= 0, 0, 1, +, *)
the complex numbers, the quaternions, polynomials--in fact, any ring or field;

Here's a much stranger one: the role of zero is played by infinity, the role of one is played by zero, the role of plus is played by min, and the role of * is played by +!
Code:


(reals>=0, infinity, 0, min, +)



   distributive: a + min(c,d) = min(a+c, a+d)

   additive identity: min(infinity,a) = a

   multiplicative identity: a + 0 = a

   annihilation under multiplication: a+infinity = infinity

The right tool can make all the difference!
bilbo
April 19th, 2005, 09:43
Quote:
[Originally Posted by mike]Yes, it can be done, but the derivation is a lot longer. In fact, if elegance is inversely proportional to the length of the proof, then the most elegant proof is the truth table!

You are definitely right!
In fact, after a lot of thinking, I could elaborate the following solution...

Code:


Assumptions:

 (1) + is OR, . (or nothing) is AND, ^ is XOR

 (2) in following dissertation, A' means notA

 (3) A xor B = AB' + A'B (XOR definition "in OR,AND rig" or "a la Naides"

 (4) A+B is equals to A'B' (DeMorgan law)

Code:


Theorem:

 X xor Y xor XY = X +(or) Y

Code:


Demonstration:

 X ^ Y ^ XY = associative property

 (X ^ Y) ^ XY = XOR definition for first XOR

 (XY'+X'Y) ^ XY = XOR definition for second XOR

 (XY'+X'Y)'(XY) + (XY'+X'Y)(XY)' = DeMorgan for the two negated parenthesis

 (XY')'(X'Y)'(XY) + (XY'+X'Y)(X'+Y') = DeMorgan for the new two negated parenthesis

 (X'+Y)(X+Y')(XY) + (XY'+X'Y)(X'+Y') = resolving the first two and last two parenthesis (distributive property)

 (X'X+X'Y'+YX+YY')(XY) + (XY'X'+XY'Y'+X'YX'+X'YY') = some semplification

 (X'Y'+YX)(XY) + XY' + X'Y = 

 X'Y'XY + YXXY + XY' + X'Y =

 XY + XY' + X'Y =

 X(Y+Y') + X'Y =

 X + X'Y = distributive property of + against .

 (X+X')(X+Y) =

 1.(X+Y) =

 X + Y

Phew! This stuff is far away from elegant!

Best regards, bilbo