Is it possible to represent the logic AND operation using only
NOT and XOR operations?  For instance, I know that the AND operation
can be expressed using only OR and NOT operators:

AB = !(!A + !B)

However, is it possible to represent AND using XOR and NOT operators?
     I've spent the past few hours trying to do so, thinking that it
must be possible.  However, the longer I worked with it, the more I
realized just how symmetrical XOR is in nearly every respect.  This is
what makes the whole ordeal tricky.  I've searched the internet, and
looked in a textbook that I have, but haven't been able to find any
such representation of the AND operation.  I slowly began to wonder if
it's even possible.  Does anyone know for sure?
     Thanks for your time.

     Is it possible to represent the logic AND operation using only
NOT and XOR operations?  For instance, I know that the AND operation
can be expressed using only OR and NOT operators:

AB = !(!A + !B)

However, is it possible to represent AND using XOR and NOT operators?
     I've spent the past few hours trying to do so, thinking that it
must be possible.  However, the longer I worked with it, the more I
realized just how symmetrical XOR is in nearly every respect.  This is
what makes the whole ordeal tricky.  I've searched the internet, and
looked in a textbook that I have, but haven't been able to find any
such representation of the AND operation.  I slowly began to wonder if
it's even possible.  Does anyone know for sure?
     Thanks for your time.

Is it possible to represent the logic AND operation using only
NOT and XOR operations? For instance, I know that the AND operation
can be expressed using only OR and NOT operators:

AB = !(!A + !B)

~(p & q) <-> (~p v ~q)

However, is it possible to represent AND using XOR and NOT operators?

On Tue, 22 Apr 2008, Steven wrote:

Is it possible to represent the logic AND operation using only
NOT and XOR operations? For instance, I know that the AND operation
can be expressed using only OR and NOT operators:

AB = !(!A + !B)

~(p & q) <-> (~p v ~q)

However, is it possible to represent AND using XOR and NOT operators?

(p & ~q) xv (~p & q) xv (p & q) <-> (p v q)

Dang, that's wrong.

Steven schrieb:

Is it possible to represent the logic AND operation using only
NOT and XOR operations? For instance, I know that the AND operation
can be expressed using only OR and NOT operators:

AB = !(!A + !B)

However, is it possible to represent AND using XOR and NOT operators?
I've spent the past few hours trying to do so, thinking that it
must be possible. However, the longer I worked with it, the more I
realized just how symmetrical XOR is in nearly every respect. This is
what makes the whole ordeal tricky. I've searched the internet, and
looked in a textbook that I have, but haven't been able to find any
such representation of the AND operation. I slowly began to wonder if
it's even possible. Does anyone know for sure?
Thanks for your time.

Observe xor is commutative and associate,
so any expression involving + (xor), 1, 0 and
variables can be brought into the form:

a1*x1 + .. + an*xn + b*1 + c*0

(Just count the variables/constants in the
expression tree, a*x is short hand for
a-times x+..+x)

Now further observe:

(2*n+1) * x = x
(2*n) * x = 0

So an expression over the variables x, y, will
reduce to one of the following:

0
1
x
x + 1
y
y + 1
y + x
y + x + 1

All of them not being the and. Q.E.D.

P.S.: Similar tricks applicable if the set
of base operations is arbitrarly given??

Is it possible to represent the logic AND operation using only
NOT and XOR operations? For instance, I know that the AND operation
can be expressed using only OR and NOT operators:

AB = !(!A + !B)

However, is it possible to represent AND using XOR and NOT operators?
I've spent the past few hours trying to do so, thinking that it
must be possible. However, the longer I worked with it, the more I
realized just how symmetrical XOR is in nearly every respect. This is
what makes the whole ordeal tricky. I've searched the internet, and
looked in a textbook that I have, but haven't been able to find any
such representation of the AND operation. I slowly began to wonder if
it's even possible. Does anyone know for sure?
Thanks for your time.

On Apr 22, 9:36 pm, Steven <evanss...@yahoo.com> wrote:
Is it possible to represent the logic AND operation using only
NOT and XOR operations? For instance, I know that the AND operation
can be expressed using only OR and NOT operators:

AB = !(!A + !B)

However, is it possible to represent AND using XOR and NOT operators?
I've spent the past few hours trying to do so, thinking that it
must be possible. However, the longer I worked with it, the more I
realized just how symmetrical XOR is in nearly every respect. This is
what makes the whole ordeal tricky. I've searched the internet, and
looked in a textbook that I have, but haven't been able to find any
such representation of the AND operation. I slowly began to wonder if
it's even possible. Does anyone know for sure?
Thanks for your time.

The set {~,xor} is inadequate. The set {~,<->} is also inadequate and
for the same reason.
You've already put your finger on the reason. You might prove the
inadequacy of either of
these sets by demonstrating that conjunction (your example) cannot be
expressed by any
combination of ~ and xor (or <-> if you like).

You might find it surprising that the set {->,xor} is adequate.
The key is to note that xor is just the denial of material
equivalence.

Marshall schrieb:

P.S.: Similar tricks applicable if the set
of base operations is arbitrarly given??

How similar is similar enough?

Of the 16 possible binary functions over {0, 1},
2 are commutative but not associative, 2 are
associative and not commutative, 6 are both,
and 6 are neither.

Marshall

Similar in the sense that the size of tree
can be reduced. Every binary function:

f: B x B -> B (B={0,1})

Can be viewed as two unary functions:

g0: B -> B, (g0(x)=f(0,x))
g1: B -> B, (g1(x)=f(1,x))

If g0(0)=1, and g0(1)=0, we can write for
the orbit of g0, orbit(g0)={01}.

The orbit of these functions is always finite,
and has one of the following forms:

0{1}

{0} {1}

{01}

1{0}

So maybe tree depth 4 is upper bound?

P.S.: Similar tricks applicable if the set
of base operations is arbitrarly given??

How similar is similar enough?

Of the 16 possible binary functions over {0, 1},
2 are commutative but not associative, 2 are
associative and not commutative, 6 are both,
and 6 are neither.


Marshall

(A xor B)  =/=  ~(A -> B) for A = 0 (false) and B = 1 (true).

I'm sure you just misspoke.

On Apr 23, 3:01 pm, herbzet <herb...@gmail.com> wrote:

(A xor B) =/= ~(A -> B) for A = 0 (false) and B = 1 (true).

I'm sure you just misspoke.


Misspoke?
I'd say it's a bit closer to the truth to say that you just misread.
But thanks anyway for your attention.