I was wrong.
3 inputs would also give a high output.

 

How about now that it is one circuit instead of cascaded gates?

How about what?

It's the functional behavior that counts and, more to the point for this thread, what the definition is of the functional behavior of a multi-input XOR gate. Your FET-level drawing is nothing more than the tree implementation of three two-input XOR gates showing a raw 12-transistor implementation of each XOR gate. You could also draw it as one big direct CMOS implementation of the logic. Same functionality. You could also show it as an implementation using NOT, OR, and AND gates to directly mirror a basic Boolean expression. Same functionality (although a horrendously exploded transistor count and propagation delay).

But so what?

Does theory over rule the truth table?

Meaningless question. Where'd your truth table come from? It either came from the treed implementation, in which case you are using a topology to define the function, or it came from something else that defined the functionality. Either way, it is just one of several possible, reasonable definitions. There are others that have different truth tables that can also be defended as being reasonable.

But, again, while it is interesting to discuss the various possible ways that a multi-input XOR gate MIGHT have been defined, we can't escape the fact that, from a practical standpoint, we need to work with the way it actually WAS defined, regardless of whether or not we might believe it was arbitrary, capricious, or just plain wrong.

Personally, I think defining it as having the same functionality as cascaded two-input XOR gates has the strongest underpinnings from a Boolean algebraic standpoint. I've already shown that this is functionally equivalent to a treed topology. That it is also functionally equivalent to an odd parity detector is useful, but entirely coincidental.

 

the XOR operation is not fundamental to Boolean algebra to begin with.

I guess it can't be done then.

 

I guess it can't be done then.

I don't know what you are trying to say here.

Boolean algebra defines three operations, unary-NOT, binary-OR, and binary-AND. These are defined via explicit truth table. All of the Boolean identities follow directly from this. As a result, those identities can only involve those three operations.

We can certainly define other functions and we can give names to those functions. In fact, all sixteen possible binary functions have names. One of those is XOR, which is defined either by its truth table or by the Boolean expression

XOR(A, B) = (A(B')) + ((A')B)

But this does not make it a Boolean operator (despite the common and useful treatment of it as being one) and, more to the point, this definition says nothing about what a multi-input XOR function is. So we have to decide, somewhat arbitrarily, what that definition is going to be.

From the standpoint of keeping the definition clean from a Boolean algebraic standpoint, it is useful if we can extend the definition inductively, namely, given the definition for N inputs, define it for N+1 inputs. The cleanest way of doing this is:

XOR(A, B, C) = XOR(XOR(A, B), C)

Or

for N>2: XOR(N-inputs) = XOR(XOR(first N-1 inputs), last input)

At this point, all we need is the definition for a 2-input XOR gate (which we already have) and we are set.

Note that we could blindly apply this to all of the 2-input functions, even the non-symmetric ones, but in many cases the results are nonsensical, or at least non-intuitive. For instance, we could define a multi-input NAND gate this way, but the result would NOT be consistent with the semantics that NAND is NOT-of-the-AND. Hence, while we could define it this way, we don't. As a result, a multi-input NAND gate CANNOT be made by cascading or treeing a bunch of NAND gates. The same holds for the multi-input NOR gate. Interestingly, it DOES hold for the multi-input XNOR gate (which is best understood as NOT-of-the-XOR as opposed to Exclusive-NOR -- XNOR was chosen over NXOR purely because XNOR is naturally pronounceable as "ex-nor" while NXOR has no such easy pronunciation).

 

Hi again,

The more i read about this the more i am starting to become convinced that it is not that the multi input XOR gate has an ambiguous definition, it is that the multi input XOR gate has *NO* valid definition. That is, NONE of the implementations we had discussed so far are valid because there is no valid definition for a multi input XOR gate. Consider the following.

The 2 in AND gate can be cascaded to form a 3 in AND gate, and the 2 in OR gate can be cascaded to form a 3 in OR gate. But who said we have to cascade gates in order to form a multi input gate of that logical type?

The mathematical formulas for a 3 in AND and OR gate can be written:
D=A*B*C
D=A+B+C

but who said we have to write them that way? For the OR gate for example we can write:
D=(A+B)+C
D=A+(B+C)
D=B+(A+C)

and likewise for the AND gate.

Now as soon as we turn to other gates, we get a change in functionality. If we stick two 2 in NAND gates together we get:
D=((A*B)'*C)'
or:
D=((A'+B')*C)'
or:
D=A*B+C'

which if i did that right results in a combination of logic, not an extension of the original logic. In other words, we end up with a CIRCUIT, and a CIRCUIT does not have such a strict definition.

This means that i believe that although it is up to the manufacturer to call their product just about anything they want to, it doesnt make it a fact that it is somehow a basic element of logic.

Thus when we combine gates of any kind in a cascade of any kind we are forming a circuit, not another basic logic element. So we should be calling that three input XOR gate a "three input parity generator" and the equality detector i mentioned earlier just that, "an equality detector". It is better that neither implementation be called an XOR gate of any kind.

This result is the only way to clear up any possible ambiguity.

Comments welcome.

 

That's basically what I have been saying over and over.

Having said that, we still have to live in the real world and in the real world the professional digital logic community has long since come to a very widely established consensus that a multi-input XOR gate is defined to be one that is functionally equivalent to a cascade of two-input XOR gates. We can shout from the rooftops all day long that they shouldn't do this and should instead call such a circuit an "N-input odd-parity generator" (and notice that calling it a "three input parity generator" isn't sufficient because it could be an odd-parity generator or an even-parity generator) but that doesn't change the fact that when we see an XOR gate in a schematic that has more than two inputs, we need to be able to know (at least with a pretty high likelihood of being correct) what that component does.

Now, in the designs that WE document, it would definitely be a good idea to be explicit about what we mean so that WE remove any potential ambiguity from our designs.

 

As far as fundamental logic goes, you could say that there is a two terminal NOT gate, and a three terminal AND gate, and that all other logic is made from these.

 

As far as fundamental logic goes, you could say that there is a two terminal NOT gate, and a three terminal AND gate, and that all other logic is made from these.

And how is that at all relevant to the discussion of what a multi-input XOR gate is defined as?

Fundamentally, the three Boolean logic operations are NOT, OR, and AND.

You can implement an AND gate using just NOT and OR gates.

You can implement an OR gate using just NOT and AND gates.

More to the point, you can implement ALL Boolean logic function using only NAND gates. Or using only NOR gates.

In actual circuits, you implement an AND gate by following a NAND gate with a NOT gate and you implement an OR gate using a NOR gate followed by a NOT gate. This is because transistors are inherently inverting (at least BJT and FET) and so it takes fewer transistors (and stages) to implement either a NAND or a NOR gate than to implement an AND or an OR gate.

But NONE of this is in any way relevant to the question of what the "proper" definition of a multi-input XOR gate is (or ought to be).

 

because there is no definition. as you stated, all logic can be defined using nand gates. and so anything beyond that is completely user-defined. regardless of a device manufacturing methods.

 

defining xor with nand suddenly becomes elegant. or and nor become superfluous. fundamental definitions, such as or, where proposed to simplify simple logic circuits. as soon as logic goes past the first level of complexity, from a nand to an xor, fundamental definitions become mute. I could define a not gate as a 1 input nand gate. that is, if all inputs are high (1 input in this case), then the output is low. ultimately, fundamental logic should have only one type of gate - nor or and, but not both ?

 

I have the answer

From previous discussion, it is clear that there is only one basic logic unit, NAND (or NOR).

So why is XOR different ?

Because you can make an XOR from NAND, but not a NAND from XOR.

The underlying difference is that NAND has one unique outcome from many possible inputs.

XOR has many outcomes from many inputs.

Shabam

 

so anything beyond that is completely user-defined.

How so?

 

The 74LVC1G386DCKRG4 and its variants, are described by manufacturers as a 3 input xor gate', but isn't a 'one hot' device.

 

Long, long, ago, somebody defined a nand gate as a multi-input, single output port that followed this definition:

If all inputs are high, the output will be low. This follows common sense and logic:

If I turn the gas on, and light it, I'm having Goulash tonight.

But an equally valid definition is:

If one input is high, and the other is low, then the output will be high.

If I turn the gas on, and refrain from lighting it, I really shouldn't be allowed to play with gas.

Ultimately, a logic unit has ONE outcome from MANY incomes.

It follows our very human way of thinking.

We define our complex world by taking TWO things at a time, and making it ONE coherent thing.

We then take two of these things and coerce these.

What is important when defining logic is that it acts like a funnel, bringing multiple ideas into one, which can be further funneled.

 

because there is no definition. as you stated, all logic can be defined using nand gates. and so anything beyond that is completely user-defined. regardless of a device manufacturing methods.

No, everything beyond that (whatever "that" is) is not user defined. Just because all logic can be implemented using two-input NAND gates does not mean that the user gets to define what a two-input AND gate is, or a two-input XOR gate, for that matter. It does not let them define what a multi-input AND or OR gate is. These are all very well defined and those definitions are universally agreed upon.

Manufacturing methods are irrelevant. The discussion is about the functional definition of a multi-input XOR gate.

 

a nand gate as a multi-input, ...

Tough for a NAND gate to be a single-input device,

If all inputs are high, the output will be low. This follows common sense and logic:

...

But an equally valid definition is:

If one input is high, and the other is low, then the output will be high.

You don't think the two are the same?

The fact that one logic algorithm can be expressed differently probably doesn't mean one can define them arbitrarily.

End of the day, if the same input generates the same output for two differently-looking (logic) algorithms, they are the same.

 

View attachment 91802
defining xor with nand suddenly becomes elegant. or and nor become superfluous. fundamental definitions, such as or, where proposed to simplify simple logic circuits. as soon as logic goes past the first level of complexity, from a nand to an xor, fundamental definitions become mute. I could define a not gate as a 1 input nand gate. that is, if all inputs are high (1 input in this case), then the output is low. ultimately, fundamental logic should have only one type of gate - nor or and, but not both ?

A four-NAND implementation of a 2-input XOR gate is normally done as follows:



You pretty clearly do not grasp the concept of fundamental Boolean logic and, more to the point, the distinction between function definitions and implementation.

If you want to design all of your logic using just two-input NAND gates, by all means go ahead. Your NOT gate will take twice the area and be half as fast as mine. Your NOR gate will take four times the area and only be one-third as fast as mine. Whose designs do you think are going to win?

 

I have the answer

From previous discussion, it is clear that there is only one basic logic unit, NAND (or NOR).

So why is XOR different ?

Because you can make an XOR from NAND, but not a NAND from XOR.

The underlying difference is that NAND has one unique outcome from many possible inputs.

XOR has many outcomes from many inputs.

Shabam

????

Babble.

 

Long, long, ago, somebody defined a nand gate as a multi-input, single output port that followed this definition:

If all inputs are high, the output will be low. This follows common sense and logic:

If I turn the gas on, and light it, I'm having Goulash tonight.

But an equally valid definition is:

If one input is high, and the other is low, then the output will be high.

If I turn the gas on, and refrain from lighting it, I really shouldn't be allowed to play with gas.

Ultimately, a logic unit has ONE outcome from MANY incomes.

It follows our very human way of thinking.

We define our complex world by taking TWO things at a time, and making it ONE coherent thing.

We then take two of these things and coerce these.

What is important when defining logic is that it acts like a funnel, bringing multiple ideas into one, which can be further funneled.

Can you provide a reference for this history that you are claiming?

This is not difficult to grasp.

Boolean logic is defined by three basic operations -- NOT, OR, and AND. The first is a unary operator and the latter two are binary. ALL other logic functions are ultimately defined in terms of these three basic operations. The NAND is shorthand for NOT-AND, which is, as the name implies, the NOT of the AND of two inputs. It's behavior for more than two inputs follows not from any fundamental definition of NAND, but directly from the notion that NOT-AND can be applied to a multi-input AND and the functional behavior of a multi-input AND follows naturally from the definition of a two-input AND applied to Boolean expressions in which more than two inputs are ANDed together.

 

no. they are defined by not and either or or and. not both. and, although you are right on both fronts, manufacturing, and pure logic, are distinct. so are we talking die real-estate, or logic philosophy.
user-defined means: at any point in pure logic one goes past the most basic definition of a 2-i/p, 1-o/p gate, one is defining that logic himself.