building boolean gates

"Bernd Schneider" schrieb im Newsbeitrag news:g6esau$74l$ snipped-for-privacy@aioe.org...

Hello Bernd,

To be honest, this definition of "linear" together with digital logic is nonsense. Please ask your friend for a web-link. I am really interested to see who uses this definition.

Best regards, Helmut

You can build any logic function out of XOR gates. Since you have defined the XOR as a linear gate, use it.

hi I think its a simple misunderstanding with linear and non.. a gate will always make a change in state, from Vcc to gnd or like , It will never act like a linear device.

But it is so that Nor ,not ,nand inverts the signal and and ,or do not invert signals. So you have inverting and non inverting gates .

alex

No, not with XORs. You can with all NANDs or all NORs, but not with all XORs.

Whoever told you that should not be used as a reference in the future.

The terms min-term and max-term were in use at one time, and although they serve little purpose at least they make sense. Calling a gate linear just because its output is true 50% of the time doesn't make sense.

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.

hsa.googlegroups.com:

=3D1

You could think of the Kmap as a way to create the Boolean equation, then massage the equation to get what gates you want to use.