Re: building boolean gates

Bernd Schneider wrote:

No, I havent translated any text from German to English. In fact, I am not
into electronics but a colleague of me has called these gates linear and
And and Or non-linear gates. I think the idea is that the output of a
linear gate is 1 with probability 1/2 whereas the output of a non-linear
gate may differ (in case of an AND gate the probability that the output
takes the value is indeed only 1/4). Following this definition the gates
that I have specified are also linear and that let me hope that I can build
them from only linear basic gates.

The Fredkin gate is what you call a "linear gate", because for each of the
three outputs the probability is 1/2 that it is 1. It is universal, so your
functions can be implemented with linear gates, only.

For your first function:

u s e w
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

the logic function looks like this: w = (e AND u) OR ((NOT e) AND s)
It is not possible to implement it with XOR and NOT, only.

To prove this, you have to show that it is not possible to implement your
function with XORs, 1 and 0, only (because NOT p = 1 XOR p). First we prove
that it is impossible to implement half of your function, with s=0, which
is a selector for just one bit (an AND gate)

u e w
0 0 0
0 1 0
1 0 0
1 1 1

To prove it, we have to show that any number of XOR gates, connected in any
valid combination, does not produce an AND gate. Lets start with 0 XOR
gates. The possible values for w are u, e, 1 and 0.

With one XOR gate:

1 (u and e not used, fixed input 1 and 0)
0 (u and e not used, fixed input 0 and 0)
u xor e
u (=u xor 0)
e (=e xor 0)
not u (= u xor 1)
not e (= e xor 1)

Adding one more XOR gate, the output of the previous gate, u, e, 0 and 1
can be used for both inputs. u, e, 0 and 1 are outputs of the previouse
gate, too, so there are 49 combinations to test:

1 xor 1 = 0
0 xor 1 = 1
(u xor e) xor 1 = not(u xor e)
u xor 1 = not u
e xor 1 = not e
(not u) xor 1 = u
(not e) xor 1 = e

1 xor 0 = 1
0 xor 0 = 0
(u xor e) xor 0 = u xor e
u xor 0 = u
e xor 0 = e
(not u) xor 0 = not u
(not e) xor 0 = not e

1 xor (u xor e) = not(u xor e)
0 xor (u xor e) = u xor e
(u xor e) xor (u xor e) = 0
u xor (u xor e) = e
e xor (u xor e) = u
(not u) xor (u xor e) = not e
(not e) xor (u xor e) = not u

1 xor u = not u
0 xor u = u
(u xor e) xor u = e
u xor u = 0
e xor u = u xor e
(not u) xor u = 1
(not e) xor u = not(u xor e)

1 xor e = not e
0 xor e = e
(u xor e) xor e = u
u xor e = u xor e
e xor e = 0
(not u) xor e = not(u xor e)
(not e) xor e = 1

1 xor (not u) = u
0 xor (not u) = not u
(u xor e) xor (not u) = not e
u xor (not u) = 1
e xor (not u) = not(u xor e)
(not u) xor (not u) = 0
(not e) xor (not u) = u xor e

1 xor (not e) = e
0 xor (not e) = not e
(u xor e) xor (not e) = not u
u xor (not e) = not(u xor e)
e xor (not e) = 1
(not u) xor (not e) = u xor e
(not e) xor (not e) = 0

This shows that only the expression not(u xor e) is new. Now we calculate
the result of any combination of the new 8 expressions. All combinations
with the first 7 expressions are already tested, so we have to test only
the 7 combinations with the new one:

1 xor not(u xor e) = u xor e
0 xor not(u xor e) = not(u xor e)
(u xor e) xor not(u xor e) = 1
u xor not(u xor e) = not e
e xor not(u xor e) = not u
(not u) xor not(u xor e) = e
(not e) xor not(u xor e) = u

This shows that there is no new result, which means it doesn't matter how
many XOR gates you add, there are only 8 possible logic functions with XOR
gates:

1
0
u xor e
u
e
not u
not e
not(u xor e)

No function is the AND gate, so it is not possible to create an AND gate
with XOR gates.

This means that for your function with 3 inputs and s=0 it is not possible
to build it with NOT and XOR, only. This means it is not possible to build
your whole function, because no matter what you feed to s, you can't build
at least half of your logic table with XOR and NOT, only, so the full logic
is not possible, too.

--
Frank Buss, fb@xxxxxxxxxxxxx
http://www.frank-buss.de, http://www.it4-systems.de
.

Relevant Pages

  • Re: using of 2-to-4-line Decoder
    ... > Hi peaple, ... > I have a logic function: ... > F= A XOR C ...
    (comp.arch.embedded)
  • Re: Stupid 4024 freq divider question (shaft encoder resolution)
    ... square represents an amplifier and a hysteresis sign a threshold. ... As for a three or more input XOR gate, FAIK the number of inputs is not ... One American style ...
    (sci.electronics.design)
  • Re: building boolean gates
    ... I am trying to build the following two linear gates from basic boolean gates (XOR, NOT, AND, OR): ... Enable gate with the following truth table where u,s,e are the inputs and w is the output ... Both gadgets look pretty linear to me, so I hope this is somehow possible. ...
    (sci.electronics.design)
  • Re: building boolean gates
    ... gates (XOR, NOT, AND, OR): ... Enable gate with the following truth table where u,s,e are the inputs ... OR) together with the u signal and the second gadget should not involve t ...
    (sci.electronics.design)
  • Re: building boolean gates
    ... I am trying to build the following two linear gates from basic boolean ... gates (XOR, NOT, AND, OR): ... Enable gate with the following truth table where u,s,e are the inputs ... Both gadgets look pretty linear to me, so I hope this is somehow possible. ...
    (sci.electronics.design)
Quantcast