HOME

TheInfoList



OR:

A logic gate is an idealized or physical device implementing a
Boolean function In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ( ...
, a
logical operation In Mathematical logic, logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax (logic), syntax o ...
performed on one or more
binary Binary may refer to: Science and technology Mathematics * Binary number, a representation of numbers using only two digits (0 and 1) * Binary function, a function that takes two arguments * Binary operation, a mathematical operation that ta ...
inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, one that has for instance zero
rise time In electronics, when describing a voltage or current step function, rise time is the time taken by a signal to change from a specified low value to a specified high value. These values may be expressed as ratiosSee for example , and . or, equivale ...
and unlimited
fan-out In digital electronics, the fan-out is the number of gate inputs driven by the output of another single logic gate. In most designs, logic gates are connected to form more complex circuits. While no logic gate input can be fed by more than one ...
, or it may refer to a non-ideal physical device (see
Ideal and real op-amps An operational amplifier (often op amp or opamp) is a DC-coupled high-gain electronic voltage amplifier with a differential input and, usually, a single-ended output. In this configuration, an op amp produces an output potential (relative to ...
for comparison). Logic gates are primarily implemented using
diode A diode is a two-terminal electronic component that conducts current primarily in one direction (asymmetric conductance); it has low (ideally zero) resistance in one direction, and high (ideally infinite) resistance in the other. A diode ...
s or
transistor upright=1.4, gate (G), body (B), source (S) and drain (D) terminals. The gate is separated from the body by an insulating layer (pink). A transistor is a semiconductor device used to Electronic amplifier, amplify or electronic switch, switch e ...
s acting as electronic switches, but can also be constructed using
vacuum tube A vacuum tube, electron tube, valve (British usage), or tube (North America), is a device that controls electric current flow in a high vacuum between electrodes to which an electric voltage, potential difference has been applied. The type kn ...
s, electromagnetic
relay A relay Electromechanical relay schematic showing a control coil, four pairs of normally open and one pair of normally closed contacts An automotive-style miniature relay with the dust cover taken off A relay is an electrically operated switch ...
s (
relay logic Relay logic is a method of implementing combinational logic in electrical control circuits by using several electrical relays wired in a particular configuration. Ladder logic The schematic diagrams for relay logic circuits are often called l ...
),
fluidic logic Fluidics, or fluidic logic, is the use of a fluid to perform analog or digital operations similar to those performed with electronics. The physical basis of fluidics is pneumatics and hydraulics, based on the theoretical foundation of fluid dyn ...
, pneumatic logic,
optics Optics is the branch of physics that studies the behaviour and properties of light, including its interactions with matter and the construction of instruments that use or detect it. Optics usually describes the behaviour of visible, ultraviole ...
, molecules, or even
mechanical Mechanical may refer to: Machine * Machine (mechanical), a system of mechanisms that shape the actuator input to achieve a specific application of output forces and movement * Mechanical calculator, a device used to perform the basic operations of ...
elements. Now, most logic gates are made from MOSFETs (metal–oxide–semiconductor
field-effect transistor The field-effect transistor (FET) is a type of transistor that uses an electric field to control the flow of current in a semiconductor. FETs ( JFETs or MOSFETs) are devices with three terminals: ''source'', ''gate'', and ''drain''. FETs cont ...
s). With amplification, logic gates can be cascaded in the same way that Boolean functions can be composed, allowing the construction of a physical model of all of
Boolean logic In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variable (mathematics), variables are the truth values ''true'' and ''false'', usually denote ...
, and therefore, all of the algorithms and
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
that can be described with Boolean logic. Logic circuits include such devices as
multiplexer In electronics, a multiplexer (or mux; spelled sometimes as multiplexor), also known as a data selector, is a device that selects between several analog or digital input signals and forwards the selected input to a single output line. The sel ...
s, registers,
arithmetic logic unit In computing, an arithmetic logic unit (ALU) is a Combinational logic, combinational digital circuit that performs arithmetic and bitwise operations on integer binary numbers. This is in contrast to a floating-point unit (FPU), which operates on ...
s (ALUs), and
computer memory In computing, memory is a device or system that is used to store information for immediate use in a computer or related computer hardware and digital electronic devices. The term ''memory'' is often synonymous with the term ''primary storage ...
, all the way up through complete
microprocessor A microprocessor is a computer processor where the data processing logic and control is included on a single integrated circuit, or a small number of integrated circuits. The microprocessor contains the arithmetic, logic, and control circu ...
s, which may contain more than 100 million logic gates. Compound logic gates AND-OR-Invert (AOI) and OR-AND-Invert (OAI) are often employed in circuit design because their construction using MOSFETs is simpler and more efficient than the sum of the individual gates. In reversible logic, Toffoli or
Fredkin gate The Fredkin gate (also CSWAP gate and conservative logic gate) is a computational circuit suitable for reversible computing, invented by Edward Fredkin. It is ''universal'', which means that any logical or arithmetic operation can be constructed e ...
s are used.


Electronic gates

A
functionally complete In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression.. ("Complete set of logical connectives").. (" ...
logic system may be composed of
relay A relay Electromechanical relay schematic showing a control coil, four pairs of normally open and one pair of normally closed contacts An automotive-style miniature relay with the dust cover taken off A relay is an electrically operated switch ...
s,
valves A valve is a device or natural object that regulates, directs or controls the flow of a fluid (gases, liquids, fluidized solids, or slurries) by opening, closing, or partially obstructing various passageways. Valves are technically fitting ...
(vacuum tubes), or
transistor upright=1.4, gate (G), body (B), source (S) and drain (D) terminals. The gate is separated from the body by an insulating layer (pink). A transistor is a semiconductor device used to Electronic amplifier, amplify or electronic switch, switch e ...
s. The simplest family of logic gates uses
bipolar transistors A bipolar junction transistor (BJT) is a type of transistor that uses both electrons and electron holes as charge carriers. In contrast, a unipolar transistor, such as a field-effect transistor, uses only one kind of charge carrier. A bipolar t ...
, and is called
resistor–transistor logic Resistor–transistor logic (RTL) (sometimes also transistor–resistor logic (TRL)) is a class of digital circuits built using resistors as the input network and bipolar junction transistors (BJTs) as switching devices. RTL is the earliest class ...
(RTL). Unlike simple diode logic gates (which do not have a gain element), RTL gates can be cascaded indefinitely to produce more complex logic functions. RTL gates were used in early
integrated circuit An integrated circuit or monolithic integrated circuit (also referred to as an IC, a chip, or a microchip) is a set of electronic circuits on one small flat piece (or "chip") of semiconductor material, usually silicon. Large numbers of tiny ...
s. For higher speed and better density, the resistors used in RTL were replaced by diodes resulting in
diode–transistor logic Diode–transistor logic (DTL) is a class of digital circuits that is the direct ancestor of transistor–transistor logic. It is called so because the logic gating function (e.g., AND) is performed by a diode network and the amplifying function ...
(DTL).
Transistor–transistor logic Transistor–transistor logic (TTL) is a logic family built from bipolar junction transistors. Its name signifies that transistors perform both the logic function (the first "transistor") and the amplifying function (the second "transistor"), as o ...
(TTL) then supplanted DTL. As integrated circuits became more complex, bipolar transistors were replaced with smaller
field-effect transistor The field-effect transistor (FET) is a type of transistor that uses an electric field to control the flow of current in a semiconductor. FETs ( JFETs or MOSFETs) are devices with three terminals: ''source'', ''gate'', and ''drain''. FETs cont ...
s ( MOSFETs); see PMOS and NMOS. To reduce power consumption still further, most contemporary chip implementations of digital systems now use CMOS logic. CMOS uses complementary (both n-channel and p-channel) MOSFET devices to achieve a high speed with low power dissipation. For small-scale logic, designers now use prefabricated logic gates from families of devices such as the
TTL TTL may refer to: Photography * Through-the-lens metering, a camera feature * Zenit TTL, an SLR film camera named for its TTL metering capability Technology * Time to live, a computer data lifespan-limiting mechanism * Transistor–transistor lo ...
7400 series The 7400 series of integrated circuits (ICs) are a popular logic family of transistor–transistor logic (TTL) logic chips. In 1964, Texas Instruments introduced the SN5400 series of logic chips, in a ceramic semiconductor package. A lo ...
by
Texas Instruments Texas Instruments Incorporated (TI) is an American technology company headquartered in Dallas, Texas, that designs and manufactures semiconductors and various integrated circuits, which it sells to electronics designers and manufacturers globall ...
, the CMOS 4000 series by
RCA The RCA Corporation was a major American electronics company, which was founded as the Radio Corporation of America in 1919. It was initially a patent trust owned by General Electric (GE), Westinghouse, AT&T Corporation and United Fruit Comp ...
, and their more recent descendants. Increasingly, these fixed-function logic gates are being replaced by
programmable logic device A programmable logic device (PLD) is an electronic component used to build reconfigurable digital circuits. Unlike digital logic constructed using discrete logic gates with fixed functions, a PLD has an undefined function at the time of manu ...
s, which allow designers to pack many mixed logic gates into a single integrated circuit. The field-programmable nature of
programmable logic device A programmable logic device (PLD) is an electronic component used to build reconfigurable digital circuits. Unlike digital logic constructed using discrete logic gates with fixed functions, a PLD has an undefined function at the time of manu ...
s such as
FPGAs A field-programmable gate array (FPGA) is an integrated circuit designed to be configured by a customer or a designer after manufacturinghence the term '' field-programmable''. The FPGA configuration is generally specified using a hardware de ...
has reduced the 'hard' property of hardware; it is now possible to change the logic design of a hardware system by reprogramming some of its components, thus allowing the features or function of a hardware implementation of a logic system to be changed. Other types of logic gates include, but are not limited to: Electronic logic gates differ significantly from their relay-and-switch equivalents. They are much faster, consume much less power, and are much smaller (all by a factor of a million or more in most cases). Also, there is a fundamental structural difference. The switch circuit creates a continuous metallic path for current to flow (in either direction) between its input and its output. The semiconductor logic gate, on the other hand, acts as a high-
gain Gain or GAIN may refer to: Science and technology * Gain (electronics), an electronics and signal processing term * Antenna gain * Gain (laser), the amplification involved in laser emission * Gain (projection screens) * Information gain in de ...
voltage Voltage, also known as electric pressure, electric tension, or (electric) potential difference, is the difference in electric potential between two points. In a static electric field, it corresponds to the work needed per unit of charge to m ...
amplifier An amplifier, electronic amplifier or (informally) amp is an electronic device that can increase the magnitude of a signal (a time-varying voltage or current). It may increase the power significantly, or its main effect may be to boost the v ...
, which sinks a tiny current at its input and produces a low-impedance voltage at its output. It is not possible for current to flow between the output and the input of a semiconductor logic gate. Another important advantage of standardized integrated circuit logic families, such as the 7400 and 4000 families, is that they can be cascaded. This means that the output of one gate can be wired to the inputs of one or several other gates, and so on. Systems with varying degrees of complexity can be built without great concern of the designer for the internal workings of the gates, provided the limitations of each integrated circuit are considered. The output of one gate can only drive a finite number of inputs to other gates, a number called the '
fan-out In digital electronics, the fan-out is the number of gate inputs driven by the output of another single logic gate. In most designs, logic gates are connected to form more complex circuits. While no logic gate input can be fed by more than one ...
limit'. Also, there is always a delay, called the '
propagation delay Propagation delay is the time duration taken for a signal to reach its destination. It can relate to networking, electronics or physics. ''Hold time'' is the minimum interval required for the logic level to remain on the input after triggering e ...
', from a change in input of a gate to the corresponding change in its output. When gates are cascaded, the total propagation delay is approximately the sum of the individual delays, an effect which can become a problem in high-speed
synchronous circuit In digital electronics, a synchronous circuit is a digital circuit in which the changes in the state of memory elements are synchronized by a clock signal. In a sequential digital logic circuit, data are stored in memory devices called flip-fl ...
s. Additional delay can be caused when many inputs are connected to an output, due to the distributed
capacitance Capacitance is the capability of a material object or device to store electric charge. It is measured by the change in charge in response to a difference in electric potential, expressed as the ratio of those quantities. Commonly recognized are ...
of all the inputs and wiring and the finite amount of current that each output can provide.


History and development

The
binary number system A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" ( one). The base-2 numeral system is a positional notatio ...
was refined by
Gottfried Wilhelm Leibniz Gottfried Wilhelm (von) Leibniz . ( – 14 November 1716) was a German polymath active as a mathematician, philosopher, scientist and diplomat. He is one of the most prominent figures in both the history of philosophy and the history of mathema ...
(published in 1705), influenced by the ancient ''
I Ching The ''I Ching'' or ''Yi Jing'' (, ), usually translated ''Book of Changes'' or ''Classic of Changes'', is an ancient Chinese divination text that is among the oldest of the Chinese classics. Originally a divination manual in the Western Zho ...
''s binary system. Leibniz established that using the binary system combined the principles of
arithmetic Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers— addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th ...
and
logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
. In an 1886 letter,
Charles Sanders Peirce Charles Sanders Peirce ( ; September 10, 1839 – April 19, 1914) was an American philosopher, logician, mathematician and scientist who is sometimes known as "the father of pragmatism". Educated as a chemist and employed as a scientist for t ...
described how logical operations could be carried out by electrical switching circuits.Peirce, C. S., "Letter, Peirce to A. Marquand", dated 1886, '' Writings of Charles S. Peirce'', v. 5, 1993, pp. 421–423. See Eventually,
vacuum tube A vacuum tube, electron tube, valve (British usage), or tube (North America), is a device that controls electric current flow in a high vacuum between electrodes to which an electric voltage, potential difference has been applied. The type kn ...
s replaced relays for logic operations.
Lee De Forest Lee de Forest (August 26, 1873 – June 30, 1961) was an American inventor and a fundamentally important early pioneer in electronics. He invented the first electronic device for controlling current flow; the three-element "Audion" triode va ...
's modification, in 1907, of the
Fleming valve The Fleming valve, also called the Fleming oscillation valve, was a thermionic valve or vacuum tube invented in 1904 by English physicist John Ambrose Fleming as a detector for early radio receivers used in electromagnetic wireless telegraphy. ...
can be used as a logic gate.
Ludwig Wittgenstein Ludwig Josef Johann Wittgenstein ( ; ; 26 April 1889 – 29 April 1951) was an Austrian-British philosopher who worked primarily in logic, the philosophy of mathematics, the philosophy of mind, and the philosophy of language. He is considere ...
introduced a version of the 16-row
truth table A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...
as proposition 5.101 of ''
Tractatus Logico-Philosophicus The ''Tractatus Logico-Philosophicus'' (widely abbreviated and cited as TLP) is a book-length philosophical work by the Austrian philosopher Ludwig Wittgenstein which deals with the relationship between language and reality and aims to define the ...
'' (1921).
Walther Bothe Walther Wilhelm Georg Bothe (; 8 January 1891 – 8 February 1957) was a German nuclear physicist, who shared the Nobel Prize in Physics in 1954 with Max Born. In 1913, he joined the newly created Laboratory for Radioactivity at the Reich Physi ...
, inventor of the
coincidence circuit In physics and electrical engineering, a coincidence circuit or coincidence gate is an electronic device with one output and two (or more) inputs. The output activates only when the circuit receives signals within a time window accepted as ''at the ...
, got part of the 1954
Nobel Prize The Nobel Prizes ( ; sv, Nobelpriset ; no, Nobelprisen ) are five separate prizes that, according to Alfred Nobel's will of 1895, are awarded to "those who, during the preceding year, have conferred the greatest benefit to humankind." Alfr ...
in physics, for the first modern electronic AND gate in 1924.
Konrad Zuse Konrad Ernst Otto Zuse (; 22 June 1910 – 18 December 1995) was a German civil engineer, pioneering computer scientist, inventor and businessman. His greatest achievement was the world's first programmable computer; the functional program ...
designed and built electromechanical logic gates for his computer Z1 (from 1935 to 1938). From 1934 to 1936,
NEC is a Japanese multinational information technology and electronics corporation, headquartered in Minato, Tokyo. The company was known as the Nippon Electric Company, Limited, before rebranding in 1983 as NEC. It provides IT and network soluti ...
engineer
Akira Nakashima Akira Nakashima (中嶋 章 or 中島 章, also written as ''Nakashima Akira'', ''Nakasima Akira'' or ''Nakajima Akira'', 5 January 1908 – 29 October 1970) was a Japanese electrical engineer of the NEC. He got a bachelor's degree in electri ...
,
Claude Shannon Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American people, American mathematician, electrical engineering, electrical engineer, and cryptography, cryptographer known as a "father of information theory". As a 21-year-o ...
and Viktor Shestakov introduced
switching circuit theory Switching circuit theory is the mathematical study of the properties of networks of idealized switches. Such networks may be strictly combinational logic, in which their output state is only a function of the present state of their inputs; or ma ...
in a series of papers showing that two-valued
Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in e ...
, which they discovered independently, can describe the operation of switching circuits. (3+207+1 pages
10:00 min
/ref> Using this property of electrical switches to implement logic is the fundamental concept that underlies all electronic digital
computer A computer is a machine that can be programmed to Execution (computing), carry out sequences of arithmetic or logical operations (computation) automatically. Modern digital electronic computers can perform generic sets of operations known as C ...
s. Switching circuit theory became the foundation of digital circuit design, as it became widely known in the electrical engineering community during and after
World War II World War II or the Second World War, often abbreviated as WWII or WW2, was a world war that lasted from 1939 to 1945. It involved the vast majority of the world's countries—including all of the great powers—forming two opposin ...
, with theoretical rigor superseding the ''ad hoc'' methods that had prevailed previously. Metal-oxide-semiconductor (MOS) devices in the forms of PMOS and NMOS were demonstrated by
Bell Labs Nokia Bell Labs, originally named Bell Telephone Laboratories (1925–1984), then AT&T Bell Laboratories (1984–1996) and Bell Labs Innovations (1996–2007), is an American industrial research and scientific development company owned by mult ...
engineers
Mohamed M. Atalla Mohamed M. Atalla ( ar, محمد عطاالله; August 4, 1924 – December 30, 2009) was an Egyptian-American engineer, physicist, cryptographer, inventor and entrepreneur. He was a semiconductor pioneer who made important contributions to ...
and
Dawon Kahng Dawon Kahng ( ko, 강대원; May 4, 1931 – May 13, 1992) was a Korean-American electrical engineer and inventor, known for his work in solid-state electronics. He is best known for inventing the MOSFET (metal–oxide–semiconductor field-effe ...
in 1960. Both types were later combined and adapted into
complementary MOS Complementary metal–oxide–semiconductor (CMOS, pronounced "sea-moss", ) is a type of metal–oxide–semiconductor field-effect transistor (MOSFET) fabrication process that uses complementary and symmetrical pairs of p-type and n-type MOSFE ...
(CMOS) logic by Chih-Tang Sah and
Frank Wanlass Frank Marion Wanlass (May 17, 1933 in Thatcher, AZ – September 9, 2010 in Santa Clara, California) was an American electrical engineer. He is best known for inventing CMOS (complementary MOS) logic with Chih-Tang Sah in 1963. CMOS has since ...
at Fairchild Semiconductor in 1963. Active research is taking place in
molecular logic gate A molecular logic gate is a molecule that performs a logical operation based on one or more physical or chemical inputs and a single output. The field has advanced from simple logic systems based on a single chemical or physical input to molecules ...
s.


Symbols

There are two sets of symbols for elementary logic gates in common use, both defined in
ANSI The American National Standards Institute (ANSI ) is a private non-profit organization that oversees the development of voluntary consensus standards for products, services, processes, systems, and personnel in the United States. The organi ...
/
IEEE The Institute of Electrical and Electronics Engineers (IEEE) is a 501(c)(3) professional association for electronic engineering and electrical engineering (and associated disciplines) with its corporate office in New York City and its operation ...
Std 91-1984 and its supplement ANSI/IEEE Std 91a-1991. The "distinctive shape" set, based on traditional schematics, is used for simple drawings and derives from
United States Military Standard A United States defense standard, often called a military standard, "MIL-STD", "MIL-SPEC", or (informally) "MilSpecs", is used to help achieve standardization objectives by the U.S. Department of Defense. Standardization is beneficial in achievin ...
MIL-STD-806 of the 1950s and 1960s. It is sometimes unofficially described as "military", reflecting its origin. The "rectangular shape" set, based on ANSI Y32.14 and other early industry standards as later refined by IEEE and IEC, has rectangular outlines for all types of gate and allows representation of a much wider range of devices than is possible with the traditional symbols. The IEC standard,
IEC The International Electrotechnical Commission (IEC; in French: ''Commission électrotechnique internationale'') is an international standards organization that prepares and publishes international standards for all electrical, electronic and r ...
60617-12, has been adopted by other standards, such as EN 60617-12:1999 in Europe, BS EN 60617-12:1999 in the United Kingdom, and DIN EN 60617-12:1998 in Germany. The mutual goal of IEEE Std 91-1984 and IEC 60617-12 was to provide a uniform method of describing the complex logic functions of digital circuits with schematic symbols. These functions were more complex than simple AND and OR gates. They could be medium scale circuits such as a 4-bit counter to a large scale circuit such as a microprocessor. IEC 617-12 and its successor IEC 60617-12 do not explicitly show the "distinctive shape" symbols, but do not prohibit them. These are, however, shown in ANSI/IEEE 91 (and 91a) with this note: "The distinctive-shape symbol is, according to IEC Publication 617, Part 12, not preferred, but is not considered to be in contradiction to that standard." IEC 60617-12 correspondingly contains the note (Section 2.1) "Although non-preferred, the use of other symbols recognized by official national standards, that is distinctive shapes in place of symbols ist of basic gates shall not be considered to be in contradiction with this standard. Usage of these other symbols in combination to form complex symbols (for example, use as embedded symbols) is discouraged." This compromise was reached between the respective IEEE and IEC working groups to permit the IEEE and IEC standards to be in mutual compliance with one another. A third style of symbols, DIN 40700 (1976), was in use in Europe and is still widely used in European academia, see the logic table in
German Wikipedia The German Wikipedia (german: Deutschsprachige Wikipedia) is the German-language edition of Wikipedia, a free and publicly editable online encyclopedia. Founded on March 16, 2001, it is the second-oldest Wikipedia (after the English Wikipedia), ...
. In the 1980s, schematics were the predominant method to design both
circuit boards A printed circuit board (PCB; also printed wiring board or PWB) is a medium used in electrical and electronic engineering to connect electronic components to one another in a controlled manner. It takes the form of a laminated sandwich struc ...
and custom ICs known as
gate array A gate array is an approach to the design and manufacture of application-specific integrated circuits (ASICs) using a prefabricated chip with components that are later interconnected into logic devices (e.g. NAND gates, flip-flops, etc.) according ...
s. Today custom ICs and the
field-programmable gate array A field-programmable gate array (FPGA) is an integrated circuit designed to be configured by a customer or a designer after manufacturinghence the term '' field-programmable''. The FPGA configuration is generally specified using a hardware d ...
are typically designed with
Hardware Description Languages In computer engineering, a hardware description language (HDL) is a specialized computer language used to describe the structure and behavior of electronic circuits, and most commonly, digital logic circuits. A hardware description language en ...
(HDL) such as
Verilog Verilog, standardized as IEEE 1364, is a hardware description language (HDL) used to model electronic systems. It is most commonly used in the design and verification of digital circuits at the register-transfer level of abstraction. It is als ...
or
VHDL The VHSIC Hardware Description Language (VHDL) is a hardware description language (HDL) that can model the behavior and structure of digital systems at multiple levels of abstraction, ranging from the system level down to that of logic gate ...
.


Truth tables

Output comparison of 1-input logic gates. Output comparison of 2-input logic gates.


Universal logic gates

Charles Sanders Peirce Charles Sanders Peirce ( ; September 10, 1839 – April 19, 1914) was an American philosopher, logician, mathematician and scientist who is sometimes known as "the father of pragmatism". Educated as a chemist and employed as a scientist for t ...
(during 1880–1881) showed that NOR gates alone (or alternatively NAND gates alone) can be used to reproduce the functions of all the other logic gates, but his work on it was unpublished until 1933. The first published proof was by Henry M. Sheffer in 1913, so the NAND logical operation is sometimes called
Sheffer stroke In Boolean functions and propositional calculus, the Sheffer stroke denotes a logical operation that is equivalent to the negation of the conjunction operation, expressed in ordinary language as "not both". It is also called nand ("not and") ...
; the logical NOR is sometimes called ''Peirce's arrow''. Consequently, these gates are sometimes called ''universal logic gates''.


De Morgan equivalent symbols

By use of
De Morgan's laws In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British math ...
, an ''AND'' function is identical to an ''OR'' function with negated inputs and outputs. Likewise, an ''OR'' function is identical to an ''AND'' function with negated inputs and outputs. A NAND gate is equivalent to an OR gate with negated inputs, and a NOR gate is equivalent to an AND gate with negated inputs. This leads to an alternative set of symbols for basic gates that use the opposite core symbol (''AND'' or ''OR'') but with the inputs and outputs negated. Use of these alternative symbols can make logic circuit diagrams much clearer and help to show accidental connection of an active high output to an active low input or vice versa. Any connection that has logic negations at both ends can be replaced by a negationless connection and a suitable change of gate or vice versa. Any connection that has a negation at one end and no negation at the other can be made easier to interpret by instead using the De Morgan equivalent symbol at either of the two ends. When negation or polarity indicators on both ends of a connection match, there is no logic negation in that path (effectively, bubbles "cancel"), making it easier to follow logic states from one symbol to the next. This is commonly seen in real logic diagrams – thus the reader must not get into the habit of associating the shapes exclusively as OR or AND shapes, but also take into account the bubbles at both inputs and outputs in order to determine the "true" logic function indicated. A De Morgan symbol can show more clearly a gate's primary logical purpose and the polarity of its nodes that are considered in the "signaled" (active, on) state. Consider the simplified case where a two-input NAND gate is used to drive a motor when either of its inputs are brought low by a switch. The "signaled" state (motor on) occurs when either one OR the other switch is on. Unlike a regular NAND symbol, which suggests AND logic, the De Morgan version, a two negative-input OR gate, correctly shows that OR is of interest. The regular NAND symbol has a bubble at the output and none at the inputs (the opposite of the states that will turn the motor on), but the De Morgan symbol shows both inputs and output in the polarity that will drive the motor. De Morgan's theorem is most commonly used to implement logic gates as combinations of only NAND gates, or as combinations of only NOR gates, for economic reasons.


Data storage

Logic gates can also be used to store data. A storage element can be constructed by connecting several gates in a "
latch A latch or catch (called sneck in Northern England and Scotland) is a type of mechanical fastener that joins two (or more) objects or surfaces while allowing for their regular separation. A latch typically engages another piece of hardware on t ...
" circuit. Latching circuitry is used in
static random-access memory Static random-access memory (static RAM or SRAM) is a type of random-access memory (RAM) that uses latching circuitry (flip-flop) to store each bit. SRAM is volatile memory; data is lost when power is removed. The term ''static'' differen ...
. More complicated designs that use clock signals and that change only on a rising or falling edge of the clock are called edge-triggered "
flip-flops Flip-flops are a type of light sandal, typically worn as a form of casual footwear. They consist of a flat sole held loosely on the foot by a Y-shaped strap known as a toe thong that passes between the first and second toes and around both side ...
". Formally, a flip-flop is called a bistable circuit, because it has two stable states which it can maintain indefinitely. The combination of multiple flip-flops in parallel, to store a multiple-bit value, is known as a register. When using any of these gate setups the overall system has memory; it is then called a
sequential logic In automata theory, sequential logic is a type of logic circuit whose output depends on the present value of its input signals and on the sequence of past inputs, the input history. This is in contrast to ''combinational logic'', whose output i ...
system since its output can be influenced by its previous state(s), i.e. by the ''sequence'' of input states. In contrast, the output from
combinational logic In automata theory, combinational logic (also referred to as time-independent logic or combinatorial logic) is a type of digital logic which is implemented by Boolean circuits, where the output is a pure function of the present input only. This i ...
is purely a combination of its present inputs, unaffected by the previous input and output states. These logic circuits are used in computer
memory Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembered, ...
. They vary in performance, based on factors of
speed In everyday use and in kinematics, the speed (commonly referred to as ''v'') of an object is the magnitude of the change of its position over time or the magnitude of the change of its position per unit of time; it is thus a scalar quanti ...
, complexity, and reliability of storage, and many different types of designs are used based on the application.


Three-state logic gates

A three-state logic gate is a type of logic gate that can have three different outputs: high (H), low (L) and high-impedance (Z). The high-impedance state plays no role in the logic, which is strictly binary. These devices are used on buses of the CPU to allow multiple chips to send data. A group of three-states driving a line with a suitable control circuit is basically equivalent to a
multiplexer In electronics, a multiplexer (or mux; spelled sometimes as multiplexor), also known as a data selector, is a device that selects between several analog or digital input signals and forwards the selected input to a single output line. The sel ...
, which may be physically distributed over separate devices or plug-in cards. In electronics, a high output would mean the output is sourcing current from the positive power terminal (positive voltage). A low output would mean the output is sinking current to the negative power terminal (zero voltage). High impedance would mean that the output is effectively disconnected from the circuit.


Manufacturing

Since the 1990s, most logic gates are made in CMOS (complementary metal oxide semiconductor) technology that uses both NMOS and PMOS transistors. Often millions of logic gates are packaged in a single
integrated circuit An integrated circuit or monolithic integrated circuit (also referred to as an IC, a chip, or a microchip) is a set of electronic circuits on one small flat piece (or "chip") of semiconductor material, usually silicon. Large numbers of tiny ...
.


Non-electronic logic gates

Non-electronic implementations are varied, though few of them are used in practical applications. Many early electromechanical digital computers, such as the Harvard Mark I, were built from
relay logic Relay logic is a method of implementing combinational logic in electrical control circuits by using several electrical relays wired in a particular configuration. Ladder logic The schematic diagrams for relay logic circuits are often called l ...
gates, using electro-mechanical
relay A relay Electromechanical relay schematic showing a control coil, four pairs of normally open and one pair of normally closed contacts An automotive-style miniature relay with the dust cover taken off A relay is an electrically operated switch ...
s. Logic gates can be made using pneumatic devices, such as the Sorteberg relay or mechanical logic gates, including on a molecular scale. Logic gates have been made out of DNA (see
DNA nanotechnology DNA nanotechnology is the design and manufacture of artificial nucleic acid structures for technological uses. In this field, nucleic acids are used as non-biological engineering materials for nanotechnology rather than as the carriers of geneti ...
) and used to create a computer called MAYA (see
MAYA-II MAYA-II (molecular array, Molecular Array of YES (logic gate), YES and NAND gate, ANDNOT logic gates) is a DNA computer, based on DNA nanotechnology#Stem Loop Controllers, DNA Stem Loop Controllers, developed by scientists at Columbia University and ...
). Logic gates can be made from
quantum mechanical Quantum mechanics is a fundamental theory in physics that provides a description of the physical properties of nature at the scale of atoms and subatomic particles. It is the foundation of all quantum physics including quantum chemistry, qua ...
effects, see quantum logic gate.
Photonic logic Optical computing or photonic computing uses light waves produced by lasers or incoherent sources for data processing, data storage or data communication for computing. For decades, photons have shown promise to enable a higher bandwidth than the ...
gates use
nonlinear optical Nonlinear optics (NLO) is the branch of optics that describes the behaviour of light in ''nonlinear media'', that is, media in which the polarization density P responds non-linearly to the electric field E of the light. The non-linearity is typic ...
effects. In principle any method that leads to a gate that is
functionally complete In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression.. ("Complete set of logical connectives").. (" ...
(for example, either a NOR or a NAND gate) can be used to make any kind of digital logic circuit. Note that the use of 3-state logic for bus systems is not needed, and can be replaced by digital multiplexers, which can be built using only simple logic gates (such as NAND gates, NOR gates, or AND and OR gates).


Logic families

There are several
logic families In computer engineering, a logic family is one of two related concepts: * A logic family of monolithic digital integrated circuit devices is a group of electronic logic gates constructed using one of several different designs, usually with compati ...
with different characteristics (power consumption, speed, cost, size) such as: RDL (resistor–diode logic), RTL (resistor-transistor logic), DTL (diode–transistor logic),
TTL TTL may refer to: Photography * Through-the-lens metering, a camera feature * Zenit TTL, an SLR film camera named for its TTL metering capability Technology * Time to live, a computer data lifespan-limiting mechanism * Transistor–transistor lo ...
(transistor–transistor logic) and CMOS. There are also sub-variants, e.g. standard CMOS logic vs. advanced types using still CMOS technology, but with some optimizations for avoiding loss of speed due to slower PMOS transistors.


See also

*
And-inverter graph An and-inverter graph (AIG) is a directed, acyclic Graph (discrete mathematics), graph that represents a structural implementation of the logical functionality of a digital circuit, circuit or network. An AIG consists of two-input nodes represent ...
*
Boolean algebra topics This is a list of topics around Boolean algebra and propositional logic. Articles with a wide scope and introductions * Algebra of sets Talk:Algebra of sets, * Boolean algebra (structure) Talk:Boolean algebra (structure), * Boolean algebra ...
*
Boolean function In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ( ...
* Digital circuit *
Espresso heuristic logic minimizer The ESPRESSO logic minimizer is a computer program using heuristic and specific algorithms for efficiently reducing the complexity of digital logic gate circuits. ESPRESSO-I was originally developed at IBM by Robert K. Brayton et al. in 1982. ...
*
Fan-out In digital electronics, the fan-out is the number of gate inputs driven by the output of another single logic gate. In most designs, logic gates are connected to form more complex circuits. While no logic gate input can be fed by more than one ...
*
Field-programmable gate array A field-programmable gate array (FPGA) is an integrated circuit designed to be configured by a customer or a designer after manufacturinghence the term '' field-programmable''. The FPGA configuration is generally specified using a hardware d ...
(FPGA) *
Flip-flop (electronics) In electronics, a flip-flop or latch is a circuit that has two stable states and can be used to store state information – a bistable multivibrator. The circuit can be made to change state by signals applied to one or more control inputs and ...
*
Functional completeness In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression.. ("Complete set of logical connectives").. (" ...
*
Karnaugh map The Karnaugh map (KM or K-map) is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 ''logi ...
*
Combinational logic In automata theory, combinational logic (also referred to as time-independent logic or combinatorial logic) is a type of digital logic which is implemented by Boolean circuits, where the output is a pure function of the present input only. This i ...
*
List of 4000 series integrated circuits The following is a list of CMOS 4000-series digital logic integrated circuits. In 1968, the original 4000-series was introduced by RCA. Although more recent parts are considerably faster, the 4000 devices operate over a wide power supply range ...
*
List of 7400 series integrated circuits The following is a list of 7400-series digital logic integrated circuits. In the mid-1960s, the original 7400-series integrated circuits were introduced by Texas Instruments with the prefix "SN" to create the name SN74xx. Due to the popularity o ...
*
Logic family In computer engineering, a logic family is one of two related concepts: * A logic family of monolithic digital integrated circuit devices is a group of electronic logic gates constructed using one of several different designs, usually with compati ...
*
Logic level In digital circuits, a logic level is one of a finite number of states that a digital signal can inhabit. Logic levels are usually represented by the voltage difference between the signal and ground, although other standards exist. The range ...
*
Logical graph A logical graph is a special type of diagrammatic structure in any one of several systems of graphical syntax that Charles Sanders Peirce developed for logic. In his papers on '' qualitative logic'', '' entitative graphs'', and '' existential grap ...
*
NMOS logic N-type metal-oxide-semiconductor logic uses n-type (-) MOSFETs (metal-oxide-semiconductor field-effect transistors) to implement logic gates and other digital circuits. These nMOS transistors operate by creating an inversion layer in a p-type t ...
*
Processor design Processor design is a subfield of computer engineering and electronics engineering (fabrication) that deals with creating a processor, a key component of computer hardware. The design process involves choosing an instruction set and a certain exec ...
*
Programmable logic controller A programmable logic controller (PLC) or programmable controller is an industrial computer that has been ruggedized and adapted for the control of manufacturing processes, such as assembly lines, machines, robotic devices, or any activity tha ...
(PLC) *
Programmable Logic Device A programmable logic device (PLD) is an electronic component used to build reconfigurable digital circuits. Unlike digital logic constructed using discrete logic gates with fixed functions, a PLD has an undefined function at the time of manu ...
(PLD) *
Propositional calculus Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations ...
* Quantum logic gate *
Race hazard A race condition or race hazard is the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events. It becomes a bug when one or more of ...
*
Reversible computing Reversible computing is any model of computation where the computational process, to some extent, is time-reversible. In a model of computation that uses deterministic transitions from one state of the abstract machine to another, a necessary co ...
*
Truth table A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...


References


Further reading

* * *


External links

* {{DEFAULTSORT:Logic Gate