Is it Possible 4 input XOR gate ? why ?

analogdude

Joined Jul 14, 2015
14
This is not really what I have been saying.

The reason that these gates are fundamental is that from the four combinations of input 00, 01, 10 and 11, there is only ONE unique output, either 0, 0, 0, 1 for AND, or 0, 1, 1, 1 for OR.
XOR is not fundamental because it has two outcomes for four combinations of input, 0, 1, 1, 0 in this case.
You could put it that way, or say that AND and OR will allow (the input) current to pass through the load, in all but one input combination.
As in diode/resistor gates. An XOR would do so for two of those input states.
 

WBahn

Joined Mar 31, 2012
29,976
This is not really what I have been saying.
He's not saying that it is -- just as you have gone off on a path that has nothing to do with the original question, so has he. This happens in threads when the TS doesn't keep the wanderings in check.

I think that theoretically, all logic circuits can be made from NOT gates and AND gates, or NOT gates and OR gates, because each is a fundamental logic unit.
For instance, take an AND (or OR) gate with TWO inputs and ONE output, and a NOT gate with ONE input and ONE output (a two input NOT gate is nonsensical).
The reason that these gates are fundamental is that from the four combinations of input 00, 01, 10 and 11, there is only ONE unique output, either 0, 0, 0, 1 for AND, or 0, 1, 1, 1 for OR.
XOR is not fundamental because it has two outcomes for four combinations of input, 0, 1, 1, 0 in this case.
You have yet to say what is so special about a gate being "fundamental", so at this point that is merely just a word that you have chosen to describe this condition. You could just as easily call just gates "lonely".

What is so special about these "fundamental" gates that makes them worthy of being put in a special class?

How many "fundamental" two-input gates are there? There are eight. Here they are:

A|B|#1|#2|#3|#4|#5|#6|#7|#8
0|0|0|0|0|1|1|1|1|0
0|1|0|0|1|0|1|1|0|1
1|0|0|1|0|0|1|0|1|1
1|1|1|0|0|0|0|1|1|1

In order for there to be any point in categorizing gates based on whether they have one unique output, you need to show that there is some property that ALL such gates have that NO other gates have (beyond the trivial property that they all have one unique output). So, what is that property. Otherwise it is just blather.

Now, a THREE input AND (or OR) gate also has ONE unique outcome from EIGHT combinations of input.
Says who? You've said before that if you don't like something that you are free to redefine it however you want.

That is, 1 for an input 111, and a 0 for all other inputs 000, 001, 010, 011, 100, 101 and 110 (in binary notation, and inputs A, B and C are in any order).
The reason that a THREE input AND gate seems to be a logical extension of a TWO input AND gate is that:
1/ It still has one unique output, and:
2/ It still follows our basic concept of an AND function.
Point #1 is irrelevant.
Point #2 is convenient and coincidental, but not relevant to the definition. Remember that the actual function is not even called AND, it is "logical conjunction". That we use the term "AND" to describe it is purely because it coincidentally happens to match how we usually use that word in everyday verbal logic.

The behavior of a three-input AND gate comes directly from Boolean algebra.

Y(A,B,C) = A & B & C

This is a 3-input AND function (by definition).

By Boolean algebra and the definition of the binary operators being left associative, this is the same as

Y(A,B,C) = (A & B) & C

This directly defines a 3-input AND in terms of the binary & operator defined by the algebra.

I would't say it was FUNDAMENTAL though, because it can be made from two, TWO input AND gates.
Now you are contradicting yourself. You keep making this big deal about how AND and OR gates are somehow "fundamental" because they truth table has one unique output, but now you have another gate that obeys that same definition and yet it is for some reason not "fundamental". So, once again, what in your world makes a gate "fundamental" and why is that important, interesting, or useful?

You seem to be saying that it isn't "fundamental" because it can be made from other gates (namely two 2-input AND gates). Okay, so then why is a 2-input AND gate "fundamental" given that IT can be made from two 2-input NAND gates?

What makes AND and OR and NOT useful, is that each in combination can describe the four unique outcomes of a TWO input gate.
That is, for TWO inputs of 00, 01, 10, 11, in any order: OR gives 0, 1, 1, 1: AND gives 0, 0, 0, 1: NOR gives 1, 0, 0, 0: NAND gives 1, 0, 0, 0.
What about the other four? I've asked you about this previously and you just responded with a sad face and the proceeded to ignore it.

This makes it intuitive when designing simple logic. And there will always be a place in circuit design where a handful of gates will do a better job than a Micro Control Unit or a Large Scale Integration (LSI) Gate Array.
Complete non sequitur -- how does this claim follow in any way from the prattle that came before it?

Now, we can choose, If We Like, to reduce this combination of OR, AND, NOR and NAND down to a SINGLE FUNDAMENTAL UNIT, say, for instance, a NAND gate, because, ultimately, all other logic can be made from this, including an XOR gate.
You cannot make a NAND gate for XOR gates (and if someone can, I would be interested to know).
So? Now you are saying that "fundamental" means that we can use it to implement all other logic. We already have a word for that -- it is called a "universal gate". But you say that AND and OR are "fundamental", they that are NOT universal gates and you cannot implement all other logic with them alone. So, once again, just what do you mean when you claim a gate is "fundamental"? You are all over the map.

There are SIX two-input logic gates that are universal. NAND and NOR are simply two of them. They just happen to be the other two of the six that are also symmetric.

Practically though, and correct me if I'm wrong, but don't manufactures of LSI devices in some cases use ONLY NAND gates on there silicon real-estate. N-channel MOSFET's are faster than P-channel (because the current mechanism uses electron flow rather than hole flow), they are simpler to populate using current methods, resistors are made from them, they inherently follow NAND and NOT in there optimal circuit configuration, and because ONLY NAND's are used, complexity is minimized.
Consider yourself corrected because you are wrong.

Why would an IC designer use a NAND gate to make an inverter? Twice the silicon, half the speed.

Why would an IC designer use NAND gates to make a NOR gate? Four times the silicon, one-third the speed.

I've been designing ICs for two decades and would never consider using NAND gates as the only element in my standard cell library.

To sum up:
Yes, it is useful to have a universal definition of NOT, OR, AND and XOR, but
No, you cannot intuitively scale XOR to three or more inputs like AND and OR.
This was established long before you joined the thread. But nothing that you have added has really done anything to establish this conclusion independently.

I hope I have confused the thread:eek:
I suspected that this has been your primary goal for quite some time.
 

peter taylor

Joined Apr 1, 2013
106
OK

An 2-i/p XOR gate is precisely defined as having one outcome half of the time, and a different outcome the other half of the time.

Intuitively, if one input AND the other input are different, then the output will be true, which KIND of makes it exclusive AND.

Then I would imagine that a three input XOR's output would be true if one, OR the other, OR the other input is different from the other two.
AND, I would imagine that a three input XOR's output would be true if one, AND the other, AND the other input is different from the other two.

I might go and lie down now :oops:
 

WBahn

Joined Mar 31, 2012
29,976
OK

An 2-i/p XOR gate is precisely defined as having one outcome half of the time, and a different outcome the other half of the time.
That's not at all a precise definition of a 2-input XOR gate. By this "precise" definition, ALL of the following are two input XOR gates:

A|B|XOR|XOR|XOR|XOR|XOR|XOR
0|0|0|0|0|1|1|1
0|1|0|1|1|0|0|1
1|0|1|0|1|0|1|0
1|1|1|1|0|1|0|0

So, according to your "precise" definition, we have six different logic functions that all qualify as being a 2-input XOR gate.

Intuitively, if one input AND the other input are different, then the output will be true, which KIND of makes it exclusive AND.
This is just babble.

Then I would imagine that a three input XOR's output would be true if one, OR the other, OR the other input is different from the other two.
More babble.

Unless all of the inputs are true or all of the inputs are false, you are guaranteed that one of the inputs will be different than the other two.

AND, I would imagine that a three input XOR's output would be true if one, AND the other, AND the other input is different from the other two.
More babble.

I might go and lie down now :oops:
Sounds like a good idea. Revisit things once you sober up.
 

peter taylor

Joined Apr 1, 2013
106
OK, the original, question was: Can you have a 4-input XOR gate.

Yes you can, but is it still an XOR gate.

I gather nobody has really defined a 4-input XOR gate, and if they have, GREAT.

What I have been saying is that the IEEE can define a gate because it is intuitive.

A 2, 3 or 100 input AND gate, and 2,3 or 27 input OR gate intuitively remain AND and OR gates.

BECAUSE THEY ARE FUNDAMENTAL.

Do this with an XOR gate and see where you get.

I don't think I am confusing the issue, and I don't think I am full of babble.

I think I am getting to the crux of the question, by defining what one would consider as BASIC and UNCHANGING and scale-able, so that a AND and an OR can have more than 2 inputs and maintain their basic, function, while an XOR can't.

I don't think I'm the one having a problem here.

So, yes, you can have a 4-input XOR gate, and yes, the IEEE can define this a particular way, but this becomes arbitrary depending on its one of many configurations.

A 2-input XOR can be universally defined, a 4-input XOR gate cannot.

I'm going to a different thread :p
 

WBahn

Joined Mar 31, 2012
29,976
I think I am getting to the crux of the question, by defining what one would consider as BASIC and UNCHANGING and scale-able, so that a AND and an OR can have more than 2 inputs and maintain their basic, function, while an XOR can't.
Did you even bother reading, say, Post #2 in this thread?

I'm going to a different thread :p
Promise?
 

MrAl

Joined Jun 17, 2014
11,389
Hi,

I like the idea of looking at the AND and OR gates as having only one output that is unique among the others, for what it is worth.

Side notes:

As for the one inverter problem i posed, i cant remember the full details and cant find any notes from the past that would have contained more info so i'll have to drop it.

As for the two inverter problem, what struck me is we usually throw three invert gates at that to invert all three inputs, but it can be done with just two inverters. This probably fits more into the category of designing circuits with limited resources rather than about XOR gates with multiple inputs, so i'll drop it unless anyone is still interested. In fact, maybe i'll start another thread so it doesnt muddy this swamp of a thread up any more (chuckle) :)
 

analogdude

Joined Jul 14, 2015
14
I don't think it's useful to define gates by their unique output. In the case of AND, that output is 1. Being unique, there can't be another, and all of the input states have been exhausted. Then, by use of the 'other' unique output, 0, the same gate becomes OR.
 

WBahn

Joined Mar 31, 2012
29,976
I don't think it's useful to define gates by their unique output. In the case of AND, that output is 1. Being unique, there can't be another, and all of the input states have been exhausted. Then, by use of the 'other' unique output, 0, the same gate becomes OR.
While I agree in that I don't see the usefulness of categorizing gates by whether they have a unique output, I don't follow the rest of what you are saying. By "unique", Peter clearly meant that only one of the possible input combinations produces a particular output and all other input combinations produce the other. If that unique output is a 1, then there are four gates that have that behavior: NOR, Converse nonimplication, Material nonimplication, and AND. If that unique output is a 0, then there are four gates that have that behavior: NAND, Material implication, Converse Implication, and OR.
 

analogdude

Joined Jul 14, 2015
14
While I agree in that I don't see the usefulness of categorizing gates by whether they have a unique output, I don't follow the rest of what you are saying. By "unique", Peter clearly meant that only one of the possible input combinations produces a particular output and all other input combinations produce the other. If that unique output is a 1, then there are four gates that have that behavior: NOR, Converse nonimplication, Material nonimplication, and AND. If that unique output is a 0, then there are four gates that have that behavior: NAND, Material implication, Converse Implication, and OR.
Yes, only one of the four unique entries in the AND truth table, produces the output 1. How many uniques does one need?
The appeal to a 'unique output' is tautological.

As for classification, one must accept that 'unique output' can represent two different states, so again, more 'uniques' than one. On the other hand, OR, NOR AND and NAND have in common, than expansion does not change behaviour, but the XOR does.
 
Last edited:

peter taylor

Joined Apr 1, 2013
106
A 2 input AND gate:
If the first input is true, and the second input is true, then the output is true.
A 2 input OR gate:
If the first input is true, or the second input is true, then the output is true.
A 2 input XOR gate:
If the first input is different from the second input, then the output is true.

A 3 input AND gate:
If the first input is true, and the second input is true, and the third input is true, then the output is true.
A 3 input OR gate:
If the first input is true, or the second input is true, or the third input is true, then the output is true.
A 3 input XOR gate:
If the first input is different from the second and third inputs, or the second input is different from the first and third inputs, or the third input is different from the first and second inputs, then the output is true.

Hang on a second, how can all three inputs be different ?
:cool:
 

peter taylor

Joined Apr 1, 2013
106
The three D's of engineering: Define, Define, Define.
Q: Can you have a 4 input XOR gate ?
A: Only if we can have a 3 input XOR gate.

So lets try to define a 3 input XOR gate from a 2 input XOR gate.

A 2 input XOR gate:
If the first input is different from the second input, then the output is true.
Alternatively, if all inputs are different, then the output is true.

A 3 input XOR gate:
If all inputs are different, then the output is true.
Since each input can only have 2 states, it is impossible for all three inputs to be different.

We cannot have a 3 input XOR, therefore, we cannot have a 4 input XOR gate.

The definition of a gate is 'something that directs flow to a single point'.
 

WBahn

Joined Mar 31, 2012
29,976
If you start with a non-extensible definition then it is not surprising that you are unable to extend it.

Solution: Start with an extensible definition.

A 2-input XOR gate:
If the number of inputs that are HI is odd, then the output is true.

A 3-input XOR gate:
If the number of inputs that are HI is odd, then the output is true.

A 4-input XOR gate:
If the number of inputs that are HI is odd, then the output is true.

As has been repeatedly stated, there are MANY ways to describe the behavior of a 2-input XOR gate. Some of them are extensible and some of them aren't. Of the ones that are extensible, they aren't all in agreement with each other. None-the-less, a long-standing general consensus has been reached that

\(
Y \; = \; A \; \oplus \; B \; \oplus \; C \; \oplus \; D
Y \; = \( \( \( \; A \; \oplus \; B \) \; \oplus \; C \) \; \oplus \; D \)
\)
 

peter taylor

Joined Apr 1, 2013
106
Extensible: able to be extended.

Can you put brackets around terms x and y, thus (x)(y), and expect it to equal (xy).

In pure mathematics, yes.
 

peter taylor

Joined Apr 1, 2013
106
I am speaking in terms of matrix multiplication, where matrix A multiplied by matrix B, does not mean the same as B x A.

But man, now I have to go back and prove that.

It's 3:30 in the morning, and I've got better things to do.
 

WBahn

Joined Mar 31, 2012
29,976
Extensible: able to be extended.

Can you put brackets around terms x and y, thus (x)(y), and expect it to equal (xy).

In pure mathematics, yes.
You have to define which operator is used when no operator is given. In normal math it is defined to be multiplication. In Boolean algebra, if it is allowed at all (some practitioners don't allow it and require the operators to appear explicitly) then it is the AND operation.

So

(x)(y) = (x) AND (y)
(xy) = (x AND y)

They what you are really asking is whether
(x)(y) = (x) AND (y)

Since the parens on the left side don't group anything we have (x) = x and (y) = y, hence
(x)(y) = x AND y
(x)(y) = xy

And since we can always put parens around the entire expression without changing anything, we have

(x)(y) = (xy)
 
Top