4
\$\begingroup\$

Wikipedia says that it is a idealized or physical device that implements the Boolean function.

By this definition I tend to think every digital circuits (say a counter or encoder) as a logic gate.

But it also says that "Logic circuits include such devices as multiplexers, registers, arithmetic logic units (ALUs), and computer memory, all the way up through complete microprocessors, which may contain more than 100 million gates". So according to this every complex digital circuit is not an logic gate but they are made up of logic gates.

Then I confused by the definition of logic gates. If multiplexer is not a logic gate then I tend to think XOR gate also not as logic gate. Can anyone explain this?

\$\endgroup\$
11
  • 3
    \$\begingroup\$ What did searching this site reveal? Does electronics.stackexchange.com/questions/117459/… help? \$\endgroup\$
    – Huisman
    Commented Dec 11, 2019 at 13:23
  • 1
    \$\begingroup\$ "Logic gates" are electric implementations of the most elementary logic functions (OR, AND and NOT). In essence, they are electrically-controlled switches connected in parallel or in series (a typical example of this structure are MOS and CMOS gates). These elementary building blocks can be combine to form more sophisticated logic circuits like decoders, multiplexes, etc. \$\endgroup\$ Commented Dec 11, 2019 at 13:29
  • 7
    \$\begingroup\$ I just read this mess of comments and answers. Let me ask a deciding question. Suppose I made a NAND gate from a multiplexor or a complex system of multiplexors? Would this still be "a logic gate?" Or not? If not, why not? I think the context matters and there are no bright lines. Worse, the common usage of the term in a specific context today might not be the same as in the most similar context 40 years ago. Be wary of bright line definitions. What about a bunch of relays making up a logic gate? Or cams and gears? \$\endgroup\$
    – jonk
    Commented Dec 11, 2019 at 14:24
  • 6
    \$\begingroup\$ We definitely need a gate keeper \$\endgroup\$
    – Huisman
    Commented Dec 11, 2019 at 14:45
  • 1
    \$\begingroup\$ Not "the boolean function" -- rather "a boolean function" An equation is much more than a mathematical operator. \$\endgroup\$ Commented Dec 11, 2019 at 15:41

10 Answers 10

22
\$\begingroup\$

You can define the term "logic gate" to be whatever you want, and no one will force you to change your mind. Each person is free to define the term as best suits their needs.

As a CMOS VLSI designer I tend to think of NAND, NOR, inverters, and transmission gates as being the set of "gates". To me, an XOR is usually a multi-gate circuit. When a manufacturer talks about the number of "gates" in some product they usually mean the number of equivalent 2-input NAND gates.

To George Boole, the AND, OR, and NOT operators were the most primitive logical operators so it would make sense that a person could define the AND, OR, and NOT gates to be the only true "gates".

\$\endgroup\$
4
  • 9
    \$\begingroup\$ "Each person is free to define the term as best suits their needs." I think it would make more sense to use a definition that is commonly understood. \$\endgroup\$
    – Huisman
    Commented Dec 11, 2019 at 13:34
  • 7
    \$\begingroup\$ @Huisman Yes, communication in engineering works best when we agree on common definitions of terms. But in this case there is no standard definition of the term "logic gate" (as is made clear by the answers) so in reality a person could use that term to mean anything. So, anyone using that term in formal engineering practice needs to define it before using it. \$\endgroup\$ Commented Dec 11, 2019 at 13:38
  • \$\begingroup\$ NOR, inverters, and transmission gates can also be built from NAND gates, so really you can think of the NAND gate as the only "gate". You can do the same with the NOR gate, since both are functionally complete and therefore serve as "universal gates". \$\endgroup\$ Commented Dec 12, 2019 at 15:45
  • 1
    \$\begingroup\$ @probably_someone: Transmission gates are a bit different from "logic gates". Further, many practical devices also require a concept of a gate whose propagation delay is guaranteed to be within a certain range. \$\endgroup\$
    – supercat
    Commented Dec 13, 2019 at 0:06
20
\$\begingroup\$

Wikipedia says that it is a idealized or physical device that implements the Boolean function.

The mistake you make is assuming that the converse is true.

Something that may implement a Boolean function is not necessarily a logic gate.

Basic logic gates: -

enter image description here

Some would say that a buffer is not a logic gate (leaving 7).

Also, because you have (probably) seen an XOR implemented by three basic logic gates does not mean that this excludes it from being a basic logic gate.

Following a discussion about what is or what isn't a logic gate I've drawn this picture to help (or hinder): -

enter image description here

Clearly an output that remains at 0 or 1 for any combination of inputs is not to be regarded as a "useful" basic logic gate so this leaves 0010 and 0100 (and their respective inverted forms) as possible unnamed Boolean identities. Any ideas for a name anyone? Do they need to be named?

Should they to be regarded as genuine basic logic gates?

Maybe not because input A and input B are processed differently. For the 0010 output, it is created by A & !B. For 0100 it is B & !A. Maybe that is what makes it an "unrecognized" basic logic gate.

\$\endgroup\$
17
  • 1
    \$\begingroup\$ In your first paragraph, it sounds like you're saying, "You are assuming that anything that implements a Boolean function is not necessarily a logic gate." Maybe it would be a good idea to change "In other words" to "As a matter of fact" (and "reverse" to "converse")? \$\endgroup\$ Commented Dec 11, 2019 at 14:02
  • 2
    \$\begingroup\$ A logic function can be implemented as in a typical FPGA. For a typical 2-input function a 4-bit memory memory is used as a logic cell (or as part of a larger logic cell that may very well be a larger memory). The 4-bits are set to produce any one of the possible logic function truth table for the two inputs. One stage does it all - you do not need three separate stages to produce the XOR function! \$\endgroup\$ Commented Dec 11, 2019 at 14:17
  • 8
    \$\begingroup\$ Regarding naming only — 1101 and 1011 are well known in logic as the material conditional or "implies". \$\endgroup\$
    – Kevin Reid
    Commented Dec 11, 2019 at 14:55
  • 2
    \$\begingroup\$ Note for anyone else who thinks "well there must be a fundamental basis set you can reduce that table to and call those the only true logic gates" like I did: yes you can, but all you need is either NAND gates or NOR gates, so that would be overly restrictive en.wikipedia.org/wiki/Functional_completeness \$\endgroup\$
    – llama
    Commented Dec 11, 2019 at 22:31
  • 2
    \$\begingroup\$ Regarding naming only — 0010 and 0100 are the noncommutative bit-clear (BCL) operations, where a 1 in the argument forces a 0 into the corresponding bit position of the arguend. 0010 is B BCL A, that is, use 1's in B to clear bits in A. Similarly 0100 is B BCL A. -- As a computer instruction, BCL is useful when clearing and setting flag bits from the same mask. \$\endgroup\$ Commented Dec 12, 2019 at 7:22
7
\$\begingroup\$

Suppose for a second that all those things are indeed "logic gates". Would it still be a useful term? Or would it be uselessly vague because it is too broad and all-encompassing? And what would you now use to refer to AND, OR, NAND, NOR, XOR, and NOT gates as a group?

This reminds me of something I read recently about tensors. All vectors and matrices are technically special cases of tensors, but no one refers to vectors or matrices as tensors because it's not useful or communicative to do so. So whenever someone says tensor, they almost always mean a tensor that is not a matrix or vector. If they were referring to a vector or matrix, they would just call it that instead.

In the end, it's about communication. The components are what they are, regardless of what you decide to label them or how you decide to classify them. What matters is how useful your classification or labels are.

So, I ask you, is it useful to refer all logic circuits as logic gates? Perhaps we already have another way to refer to all logic circuits? Maybe it is staring us in the face. Could the term perhaps be "logic circuits"? That seems to work. So now, we are left needing term to refer to the simplest logic circuits (like AND, OR, NOT) as a group, because that would be useful to have. "Logic gate" seems like a good candidate, no?

\$\endgroup\$
1
  • \$\begingroup\$ I think it would be useful to have a term for all logic circuits whose behavior could be modeled by a feedback-free network of NAND gates, each of whose input may delay rising and falling edges by an arbitrary amount of time from zero up to a specified limit. Many logic devices can be modeled in this fashion, many others cannot, and useful things can be said about the former that cannot be said about the latter. \$\endgroup\$
    – supercat
    Commented Dec 12, 2019 at 17:36
2
\$\begingroup\$

Digital electronics relies on the actions of just seven types of logic gates, called AND, OR, NAND (Not AND), NOR (Not OR), XOR (Exclusive OR) XNOR (Exclusive NOR) and NOT.

See http://www.learnabout-electronics.org/Digital/dig21.php.

The other devices you mention (multiplexers, registers, CPUs) are built up (i.e. a combination) from these logic gates, so the they have multiple logic gates.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ The NAND, NOR, XOR, and XNOR can be built from "multiple (basic) logic gates". Why are these considered "basic logic gates" but other combinations of multiple basic logic gates are not themselves basic logic gates? In other words, who decided that XOR and XNOR should be in the list? \$\endgroup\$ Commented Dec 11, 2019 at 13:43
  • \$\begingroup\$ I slightly changed the text but your question still applies; I add the link and also am not sure why they consider it this way. \$\endgroup\$ Commented Dec 11, 2019 at 13:54
2
\$\begingroup\$

TL;DR

Logic gate : A logic primitive provided by an analog designer as part of a library of logic primitive circuits that implement a select set of Boolean functions.


One way of looking at this is by breaking down the term and considering what the phrase "logic gate" suggests in the context of classical digital design where the term originated (classical meaning before computers did the work for us). The phrase is composed of two words, 'logic' and 'gate'. Let's analyze them separately.

I think it's clear that we associate a Boolean function with the term 'logic' here. A Boolean function may be expressed as F(x1, x2, x3,....,xn), where x1, x2,...etc are the inputs to the function. Conceivably, n can be an arbitrarily large number. But, actually writing down these functions for anything more than 4 inputs is tedious and unwieldy. But more, logic designers had techniques like Karnaugh maps to analyze and design logic functions that met their needs, and these techniques were only really useful up to 4 variables and maybe 5 if you really had to.

The upshot of this is that the phrase "Boolean function" has the association of only having a few inputs, even though theoretically, a Boolean function can have an arbitrary number of inputs.

Now, let's examine the term 'gate' in the same context. The idea of a gate is something that conditionally allows something to pass or not. When designing a large set of logic, it's helpful to have mental abstractions that subdivide the complexity into smaller units of understanding. The concept of a gate is one of these abstractions.

The idea is that we have a digital signal that we either want to pass or stop based on a condition. So, we wish to choose a Boolean function that implements the gate according to our specified conditions. An example of a basic gating function would be a 2 input AND, say with inputs A and B and output Q. In this case, we could mentally pick A to be the gating signal and B as the pass through signal. The gating could be expressed, "If A is high, then pass B to Q. If A is low, then block B from Q."

Some of these logic functions have the property that they will invert the passing signal though the gate. A design technique of using bubbles in the schematic to represent inversions was used to design and manipulate these inversions using De Morgan transformations of gates. In short, an AND could be converted to an OR with bubbles on it's inputs and outputs and other conversions like this. This was extremely useful for simplifying larger logic functions and making them robust against hazards. (The term 'hazard' has a special meaning for cases where a change in the logical inputs of a function don't change the logical output, but physical implementations of logic may cause a glitch in the output as the circuit stabilizes on the correct value.)

Thus, the term 'logic gate' may be used to describe a Boolean function that implements gating.

Now, to design a logical function with transistors (or whatever) is a lot of work. And perhaps ironically, it is a job for someone who has more analog design expertise than digital expertise. Thus, there is a natural division of labor between those who design logical primitives and those who use those logical primitives. So, there is a natural question for the overworked analog designer who is supposed to design these logic primitives: which Boolean functions should be implemented? They all can't be, so which subset should be chosen? What properties should this subset have? For start, the logic designer should be able to implement every logic function possible by composing the primitive functions. But more, they should be functions that are conceptually useful for the human designer to use.

With these types of design questions and practices in mind, it seems that the term 'logic gate' got assigned to describe the logic primitives that an analog designer provides to a logic designer as a library of circuits that implement Boolean functions.

Since these olden times, there has been more automation in designing logic gates and also in using them. Therefore, the number and kind of logic primitives in these libraries has gotten far away from the concept of logic gating. However, pragmatic considerations still encourage having a limited subset of logic primitives used by computers to build digital logic, though that set of logic functions is variable and larger than a human designer would know what to do with.

All this discussion necessarily precludes the logical structures that are better built using gates (see, I'm using the terminology). For example, an encoder is built using gates because it is the expertise of digital designers to build encoders, and it's not the expertise of analog designers to build such a thing, unless you propose building the encoder out of straight transistors. That would be overly-complex to say the least.

However, a MUX is small enough to be conceivably built using the available technology, and indeed, I can testify that MUX primitives are a part of some libraries I've used. Though, in my experience the computer tends to favor composing complex gates to build multiplexing functions instead of using MUX primitives. So, they seem to be there more for human consumption.

Now, you asked specifically about the XOR function. I have seen this implemented in logic libraries, and I consider this a gate. Now, it might be hard to think of this as implementing a literal gating function. However, it can be looked at as a conditional inverter. If one input is high, the other input gets inverted, and if low, then it's not inverted. That isn't the only way to think of the XOR function, but the logic doesn't care. Conceptualization is a human business.

Moreover, the XOR function is generally efficiently implemented using transistors, even more than if implemented using other gates. Therefore, it's a very useful logic primitive to have.

\$\endgroup\$
1
\$\begingroup\$

Wikipedia says that it is a idealized or physical device that implements the Boolean function.

It says "a" Boolean function.

By this definition I tend to think every digital circuits (say a counter or encoder) as a logic gate.

No, it later clarifies that by "Boolean function", it means "performs a logical operation on one or more binary inputs and produces a single binary output." So anything with an output of more than one bit would, by their definition, not be a logic gate. Since a memory of only one bit would be of very limited utility, memory chips are generally an example of something that does not satisfy their definition of a logic gate.

But it also says that "Logic circuits include such devices as multiplexers, registers, arithmetic logic units (ALUs), and computer memory, all the way up through complete microprocessors, which may contain more than 100 million gates". So according to this every complex digital circuit is not an logic gate but they are made up of logic gates.

It does not at all say that every complex digital circuit is not an logic gate. It would be somewhat reasonable to infer that not every complex digital circuit is a logic gate, but that is very different from "every complex digital circuit is not an logic gate".

\$\endgroup\$
1
\$\begingroup\$

You may find the following heuristic useful: A logic device is a gate if it is at the bottom of the abstraction hierarchy. I.e: If you can implement the behavior of a logic device in terms of a purely logical circuit built from simpler logic devices, it is not a gate. If the device is so simple that implementing the behavior of the device requires you to abandon the logic abstraction and deal directly with a physical implementation, then it is a gate.

[naturally there are some ambiguities here, where a device may be a gate from one implementation perspective and not a gate from another]

\$\endgroup\$
0
\$\begingroup\$

A logic gate:

  • Is a gate, that is an element with one or more inputs, and an output which can have only two states (like a gate can be open or closed). The simplest electronic gate is the thyristor* (SCR) which name comes from thura and transistor. Thura means gate in ancient Greek.

  • Has its output based on a logical operation performed on its input(s). A logical operation is one which is based on Boolean algebra.

Logic gates are combinatorial devices by essence. Their output is determined only on the values of their inputs. The output value doesn't depend on their previous states (they are not sequential).

Anything having these criteria is a gate, a relay is a gate. Modern logical gates are realized using digital electronics technologies such as CMOS.

Memories are gates, though they are programmable gates. The inputs are the address bits, the outputs the data bits (which is determined by programing). There are other devices, more generally related to a lookup table, like encoders (e.g. decimal to binary encoder) which are gates.

However, gates can be elementary (the commonly understood definition) or made of multiple elementary gates.

  • Any combination of elementary gates is itself a gate.
  • Elementary gates are those performing the elementary Boolean operations: Not, And, Or. By extension they include the same operators combined with a Not gate on the inputs or the output: Nand, Nor, XOr, etc.

A CPU is not a gate, as its state is not solely determined by its inputs. For example, if the inputs have some values giving some output values, and the CPU is reset, the output values will change, regardless of inputs. CPU contains internal programs (microcode or firmware) which are executed to determine the outputs on a sequential basis. The fact there is a clock signal is an indication the device may not be based on combinatorial logic.


*: "A thyristor is not a proportional device like a transistor. In other words, a thyristor can only be fully on or off, while a transistor can lie in between on and off states." Source.

\$\endgroup\$
2
  • \$\begingroup\$ Can you cite any authority or reference for your definitions of a gate, or is this just your personal observation? \$\endgroup\$ Commented Dec 13, 2019 at 16:00
  • \$\begingroup\$ @ElliotAlderson: I'm using "gate" as in thyristor gate, a switching function, that is the output is based on the value of the gate current, and can have only two states, open or closed. Some would say the thyristor is a buffer function. \$\endgroup\$
    – mins
    Commented Dec 13, 2019 at 16:24
-2
\$\begingroup\$

"Logic gates" are electric implementations of the most elementary logic functions (OR, AND and NOT). In essence, they are electrically-controlled switches connected in parallel or in series (a typical example of this structure are MOS and CMOS gates). Diodes, BJT, MOSFET, etc. can serve as such controlled switches. In some logic families (diode logic and TTL), only parallel connection (OR) is possible since diode switches and base-emitter junctions cannot be connected in series. The reason for that is diodes are two-terminal switching elements, in which the input and output are not separated (they are the same). As a result, series connected diode switches cannot be driven by grounded input voltage sources.

To solve this problem, diode AND gates are constructed in the same manner as OR diode gates - by parallel connected diode switches. However, to obtain AND instead OR function according to De Morgan's laws, the input and output logical variables are inverted:

Y = NOT (NOT (X1) OR NOT (X2)) = NOT (NOT (X1 AND X2)) = X1 AND X2, where X1 and X2 are the two input logical variables; Y is the output variable.

Therefore, the diode AND logic gate is a modified diode OR logic gate: the diode AND gate is actually a diode OR gate with inverted inputs and output.

Diode AND logic gate made from OR gate.png

(4 - X1, 5 - X2, 2 - +VCC, 1 - Y = X1.X2)

To realize the basic idea, the diodes are reverse connected and forward biased by an additional voltage source +V (a power supply) through the pull-up resistor R1. The input voltage sources are connected in opposite direction to the supplying voltage source (traveling along the loop +V - R1 - D - Vin). To invert the output voltage and to get a grounded output, the complementary voltage drop (+V - VR1) between the output and ground is taken as an output instead the floating voltage drop VR1 across the resistor.

The same trick is used in the TTL input part where the base-emitter junctions of the multiple-emitter transistor act as the diodes of the diode logic gate above.

\$\endgroup\$
1
  • \$\begingroup\$ Where do you get the idea that only the most basic ones count as logic gates? That's a valid definition, sure, but it's not the one most people use in my experience. \$\endgroup\$
    – Hearth
    Commented Dec 12, 2019 at 16:25
-2
\$\begingroup\$

I'll propose a simple definition: If you can write a truth table for it, then it's a logic gate.

Things that are logic gates then: OR/AND/NOT gates, as used in everything, not least engineering texts. Combinations of those gates to make a 100 input, 20 output super-device would still be a logic gate.

That means that a microprocessor, multiplexer, register, ALU etc are all NOT "logic gates". Even a 2-input NAND gate with latching outputs would not be a logic gate - even though it contains one. I'd usually call these the more general, "device" rather than "gate".

Ultimately though, as noted in other answers, there isn't a single widely held or standard definition. Whatever definition you choose to use is yours and may not be held by others, and it's not really worth spending a lot of time negotiating the best definition - just use whatever makes most sense to you (and isn't a million miles away from everyone else).

\$\endgroup\$
5
  • 1
    \$\begingroup\$ By your definition, a multiplexer could be a logic gate. \$\endgroup\$ Commented Dec 12, 2019 at 14:42
  • 1
    \$\begingroup\$ @ElliotAlderson: There are different kinds of multiplexers, some of which could be characterized as logic gates, and some of which could not. In particular, a multiplexer formed using pass-transistors to connect one input to an output would not qualify as a logic gate, because if its input voltage is near enough to the switching threshold to be barely valid, its output voltage may be slightly closer to the switching threshold and consequently be invalid. \$\endgroup\$
    – supercat
    Commented Dec 12, 2019 at 17:24
  • \$\begingroup\$ @supercat I think you are agreeing with me...I said a multiplexer could be a logic gate, and you said "could be characterized as logic gates". \$\endgroup\$ Commented Dec 13, 2019 at 16:01
  • \$\begingroup\$ @ElliotAlderson: Even a fairly restrictive definition of "logic gate" based on internal structure would recognize that a device which computes "not ((A and B) or (C and D))" is "one four-input logic gate" just as much as would be one that computes "not (A and B and C and D)" or "not (A or B or C or D)", despite the fact that such a device can multiplex signals in ways that would otherwise require three times as many NAND and/or NOR gates. \$\endgroup\$
    – supercat
    Commented Dec 13, 2019 at 17:19
  • \$\begingroup\$ @supercat Ummm...OK...thanks for the support. \$\endgroup\$ Commented Dec 13, 2019 at 17:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.