Logic gate
A logic gate is an elementary electronic circuit that implements a Boolean function, taking one or more binary inputs (representing 0 or 1, false or true) and producing a single binary output based on a specific logical operation, serving as the foundational component of all digital systems.[1] These gates operate using voltage levels to represent binary states, where low voltage typically denotes 0 and high voltage denotes 1, enabling the processing of information in computers and other digital devices.[2] The concept of logic gates originates from Boolean algebra, developed by George Boole in 1854 as a mathematical framework for logical operations using binary variables.[3] In 1937, Claude Shannon's master's thesis at MIT demonstrated how Boolean algebra could be applied to electrical switching circuits, effectively establishing the theoretical basis for logic gates in electronic design and bridging mathematics with practical engineering.[4] Early physical implementations used mechanical relays or vacuum tubes, but the invention of the transistor in 1947 revolutionized the field, allowing for smaller, faster, and more efficient gates that form the basis of integrated circuits.[5] There are seven basic types of logic gates: AND, OR, NOT (inverter), NAND, NOR, XOR, and XNOR, each defined by its truth table that specifies the output for all possible input combinations.[6] For instance, an AND gate outputs 1 only if all inputs are 1, while an OR gate outputs 1 if at least one input is 1; the NOT gate inverts its single input.[7] More complex gates like NAND and NOR are universal, meaning any Boolean function can be constructed using only them, which simplifies circuit design in practice.[8] Logic gates are interconnected to form combinational and sequential circuits, underpinning processors, memory units, and arithmetic logic units (ALUs) in modern computing hardware.[9] Their scalability has driven Moore's Law, enabling the billions of transistors in contemporary microprocessors, and they remain essential in fields ranging from telecommunications to artificial intelligence hardware.[10] Advances in materials, such as CMOS technology introduced in the 1960s, have reduced power consumption and increased speed, ensuring logic gates' continued relevance in nanoscale and quantum computing explorations.[5]Fundamentals
Definition and principles
A logic gate is an idealized or physical electronic device that performs a Boolean function on one or more binary inputs, producing a single binary output.[2] These devices implement fundamental logical operations, such as conjunction (AND), disjunction (OR), and negation (NOT), serving as the basic units for processing binary signals in digital systems.[11] The principles of logic gates are rooted in binary logic, a two-valued system where inputs and outputs represent truth values—typically denoted as true (1 or high voltage) or false (0 or low voltage).[11] Each gate operates deterministically, computing its output based solely on the current input combination, without memory of prior states.[2] In general, a logic gate realizes a Boolean function f(x_1, x_2, \dots, x_n), where x_1 through x_n are binary input variables (each 0 or 1), and the output is the result of applying the function to those inputs.[2] These gates form the foundational building blocks of digital circuits, interconnecting to construct more complex logical structures.[1] In computing and electronics, logic gates enable essential functions such as arithmetic operations, control signals, and data routing by combining into larger circuits that perform sophisticated tasks.[12] For instance, networks of gates can implement addition, decision-making, and information flow in processors and memory systems, underpinning the operation of modern digital devices.[13] This binary decision-making capability, derived from Boolean algebra, allows for the reliable manipulation of information in computational environments.[14]Basic logic gates
Basic logic gates form the foundational building blocks of digital circuits, performing fundamental Boolean operations on binary inputs to produce a single binary output. These gates operate on logic levels representing 0 (false or low) and 1 (true or high), and they are essential for implementing conditional logic in electronic systems. The primary basic gates include the AND, OR, NOT, NAND, NOR, XOR, and XNOR, each with distinct input/output behaviors that enable the construction of more complex functions. While most gates accept two or more inputs, the NOT gate is unique in requiring only one. The AND gate outputs a logic 1 only if all of its inputs are 1; otherwise, it outputs 0. It typically has a minimum of two inputs but can be extended to multiple inputs for broader conjunction operations. This gate performs a function analogous to multiplication in binary arithmetic, where the output represents the product of inputs. For example, in a security system, an AND gate can ensure that multiple sensors (such as a door lock and a keycard reader) must all detect valid conditions before granting access.[8][15][16] The OR gate outputs a logic 1 if at least one of its inputs is 1; it outputs 0 only if all inputs are 0. Like the AND gate, it supports a minimum of two inputs and can handle multiple inputs for disjunction logic. This inclusive OR function detects the presence of any true condition, differing from the exclusive variant (XOR) which requires exactly one true input. In applications such as alarm systems, an OR gate triggers an alert if any sensor detects an intrusion, like a door opening or glass breaking.[8][16][17] The NOT gate, also known as an inverter, takes a single input and outputs the logical complement: 1 if the input is 0, and 0 if the input is 1. With only one input, it serves as the basic negation operator in digital logic. It is fundamental for inverting signals, such as flipping a control bit to deactivate a previously active function in simple switching circuits.[8][16][1] The NAND gate is the inverted form of the AND gate, outputting 0 only if all inputs are 1, and 1 otherwise. It requires a minimum of two inputs and, like the AND, supports multi-input configurations. As a universal gate, NAND can implement any Boolean function when combined appropriately, making it versatile for compact circuit designs.[8][16] The NOR gate inverts the OR function, outputting 1 only if all inputs are 0, and 0 otherwise. It also has a minimum of two inputs and can be multi-input. NOR is similarly universal, capable of realizing all other logic functions, which contributes to its use in efficient implementations of complex logic.[8][16] The XOR gate outputs 1 if its inputs differ (one is 1 and the other is 0), and 0 if they are the same. It operates on exactly two inputs, as multi-input versions are typically constructed from pairs. XOR is key in applications like binary addition, where it generates the sum bit, and parity checking, where it detects an odd number of 1s in data for error detection.[8][16][17] The XNOR gate, or equivalence gate, inverts the XOR output, producing 1 if its two inputs are identical and 0 if they differ. It is used for equality comparisons, such as verifying matching bits in data validation processes.[8][16]Representation
Graphical symbols
Graphical symbols for logic gates provide a standardized visual language for representing digital circuits in schematics, allowing designers to abstract away physical implementations and focus on logical interconnections. These symbols emphasize input-output relationships and facilitate international communication in engineering documentation. The primary standards include the distinctive-shape symbols derived from earlier military specifications like MIL-STD-806B and the rectangular-outline symbols defined in ANSI/IEEE Std 91-1984, which is compatible with IEC 60617-12 for broader adoption.[18][19][20][21] Distinctive-shape symbols use unique geometric forms to intuitively convey gate functions, with inputs typically on the left and outputs on the right. The AND gate appears as a D-shaped enclosure (curved on the right), accepting multiple inputs that converge to a single output. The OR gate features a curved shape with pointed extensions on the input side, symbolizing addition-like behavior. The NOT gate is depicted as a right-pointing triangle with a small circle (bubble) at the output tip, indicating inversion. For multi-input versions, additional lines connect to the main body, such as three inputs joining the AND shape. These shapes, while mnemonic, have largely been supplanted by rectangular forms for compactness in complex diagrams.[20][19] In contrast, rectangular-outline symbols employ uniform boxes to promote consistency, with the gate's operation denoted by an internal label or qualifier. Under ANSI/IEEE Std 91-1984, the AND gate is a rectangle containing the ampersand (&), the OR gate uses ≥1, and the NOT gate includes a flag-like extension or the numeral 1 with negation. Multi-input notations leverage dependency symbols, such as subscripted G for ANDed inputs (e.g., G1, G2) or V for ORed inputs, placed near the rectangle to indicate grouping without drawing multiple lines. This approach supports hierarchical designs and is prevalent in modern integrated circuit schematics.[18][19] Variations exist across standards to accommodate regional or historical preferences. IEC 60617-12 favors rectangular shapes exclusively, aligning closely with IEEE but using flags for negation instead of bubbles in some cases. Older European styles, like DIN 40700, occasionally appear in legacy documentation with slightly altered curvatures. Bubble notation—a small open circle—universally denotes inversion or active-low signals, placed at inputs for complemented logic (e.g., active-low enable) or outputs for negated results (e.g., NAND as AND with output bubble). An alternative triangular polarity indicator specifies active-low without inversion in positive-logic contexts, enhancing precision in mixed-signal diagrams. These elements ensure symbols remain versatile for schematic abstraction and standardization.[20][18][19]Truth tables
Truth tables provide a tabular method to enumerate all possible input combinations for a logic gate and determine the corresponding output based on its logical function. For a gate with n binary inputs, the table consists of 2n rows, each representing a unique input combination, with columns dedicated to the input variables and the output. This exhaustive listing ensures complete coverage of the gate's behavior, using 0 to denote false and 1 to denote true. Intermediate columns may be included for complex expressions to break down the computation step by step.[22][9] The NOT gate, which inverts a single input, has the simplest truth table with two rows:| Input A | Output |
|---|---|
| 0 | 1 |
| 1 | 0 |
| Input A | Input B | Output (A AND B) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
| Input A | Input B | Output (A OR B) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
| Input A | Input B | Output (A XOR B) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Advanced Concepts
Universal logic gates
A universal logic gate is one that, by itself, can be used to construct any possible Boolean function, thereby forming a functionally complete set. The NAND and NOR gates qualify as universal because they inherently combine logical conjunction (AND) or disjunction (OR) with inversion (NOT), enabling the replication of all basic operations through appropriate interconnections.[25][26][27] The NAND gate's universality is demonstrated by its ability to implement NOT, AND, OR, and more complex functions like XOR using only NAND gates. To create a NOT gate, connect both inputs of a NAND gate to the same signal A; the output is \overline{A \land A} = \overline{A}. An AND gate follows by cascading a NAND gate with a NOT gate: the output of the NAND on inputs A and B feeds into the NOT, yielding A \land B. For an OR gate, apply De Morgan's theorem by first inverting the inputs (\overline{A} and \overline{B}, each via a NAND with tied inputs) and then applying NAND to those inverses: \overline{\overline{A} \land \overline{B}} = A \lor B, requiring three NAND gates total. An XOR gate can be built with four NAND gates: let M = \overline{A \land B}, then X_1 = \overline{A \land M}, X_2 = \overline{B \land M}, and output \overline{X_1 \land X_2} = A \oplus B.[9][28][29][30] Similarly, the NOR gate serves as a universal gate through analogous constructions that leverage its disjunctive and inverting properties. A NOT gate is formed by tying both NOR inputs to A, yielding \overline{A \lor A} = \overline{A}. An OR gate is simply a NOR followed by a NOT: \overline{\overline{A \lor B}} = A \lor B. To build an AND gate, invert the inputs first (\overline{A} and \overline{B} via tied NORs), then apply NOR to those: \overline{\overline{A} \lor \overline{B}} = A \land B, using three NOR gates. For XOR, five NOR gates are required, typically by constructing an XNOR with four NOR gates (dual to the NAND XOR) and adding a final NOT.[31][9][25][32] The proof of universality for both NAND and NOR rests on their capacity to generate the primitive operations AND, OR, and NOT, which together form a complete basis for all Boolean functions. Since any Boolean expression can be rewritten in conjunctive or disjunctive normal form using these primitives, and each primitive is constructible from either NAND or NOR alone, any logic circuit can be realized using only that gate type. This functional completeness is verified through the explicit gate constructions outlined above, confirming that no other gate types are needed.[26][33][34] Using universal gates like NAND and NOR offers advantages in circuit design and manufacturing, as they simplify integrated circuit fabrication by reducing the variety of gate types required, leading to more economical production and fewer potential points of failure.[35][36]De Morgan equivalents
De Morgan's laws provide a fundamental duality in Boolean algebra, enabling the transformation of logical expressions involving AND and OR operations through negation. The first law states that the negation of the conjunction of two variables is equivalent to the disjunction of their negations: (A \land B)' = A' \lor B'. The second law states that the negation of the disjunction is equivalent to the conjunction of the negations: (A \lor B)' = A' \land B'.[37] These laws can be verified through exhaustive truth table comparisons, where both sides of each equation yield identical output values for all input combinations of A and B.[38] In digital circuit representation, De Morgan's laws manifest as symbolic equivalents using inversion bubbles on gate inputs and outputs, illustrating the duality between AND and OR gates. For instance, an AND gate with inverted inputs and an inverted output is logically equivalent to an OR gate with non-inverted inputs, as the bubbles represent negations that align with the laws. Similarly, an OR gate with inverted inputs and inverted output equates to an AND gate without inversions. This bubble-pushing technique simplifies schematic diagrams by allowing designers to swap gate types while preserving functionality.[39][40] These equivalents facilitate circuit optimization by enabling redesigns that reduce the number of gates or adapt to specific logic families, such as converting an AND-OR realization to a NAND-NAND structure. Consider a sum-of-products expression implemented as an AND-OR circuit; applying De Morgan's laws to negate and dualize the operations transforms it into a product-of-sums form suitable for NAND gates, often minimizing component count in two-level logic designs.[41][42] The laws extend naturally to multiple variables, maintaining the pattern of duality under negation. For three inputs, (A \land B \land C)' = A' \lor B' \lor C' and (A \lor B \lor C)' = A' \land B' \land C', allowing scalable transformations in complex expressions without altering the overall logic.[43][37]Circuit Applications
Combinational logic
Combinational logic circuits are digital circuits composed of interconnected logic gates where the output values are determined solely by the current input values, without any storage elements or feedback paths that would retain information from previous inputs. This design ensures that the circuit behaves as a pure function of its inputs, producing outputs instantaneously upon input changes. In contrast, sequential logic circuits incorporate memory components, allowing outputs to depend on both current inputs and prior states.[44] A fundamental example of a combinational circuit is the half-adder, which performs binary addition on two single-bit inputs, A and B, to produce a sum bit S and a carry-out bit C_o. The sum is computed using an XOR gate, S = A \oplus B, while the carry is generated by an AND gate, C_o = A \cdot B. This simple structure adds the two bits without considering any incoming carry from a previous stage.[45] The full-adder extends the half-adder to handle three inputs: A, B, and a carry-in bit C_i, producing sum S and carry-out C_o. It can be implemented by cascading two half-adders—the first adding A and B to generate an intermediate sum and carry, which the second half-adder combines with C_i—followed by an OR gate to compute the final carry: S = (A \oplus B) \oplus C_i and C_o = (A \cdot B) + (A \oplus B) \cdot C_i + B \cdot C_i. Alternatively, it uses two XOR gates, two AND gates, and one OR gate directly for the same functions. Full-adders serve as building blocks for multi-bit adders in arithmetic operations.[45][46] Another key combinational circuit is the multiplexer (MUX), which selects one of several input signals and forwards it to a single output line based on select signals. For a 2-to-1 MUX with inputs x_0, x_1, and select s, the output Y = \overline{s} \cdot x_0 + s \cdot x_1, implemented using AND, OR, and NOT gates. Larger MUXes, such as 4-to-1 with two select bits, use decoders internally to enable one input path via AND-OR logic. Multiplexers are versatile for data routing and implementing arbitrary Boolean functions by connecting variables to selects and constants to inputs.[47][46] The design of combinational circuits typically begins with a truth table specifying outputs for all input combinations, followed by conversion to a canonical form like sum-of-products (SOP), where the output is expressed as an OR of AND terms (minterms) corresponding to rows where the output is 1. For instance, from a truth table, minterms are identified—each a product of all input literals (variables or their complements)—and summed: F = \sum m_i, where m_i are the minterms. This SOP expression is then realized with AND gates for products, OR gates for summation, and inverters as needed, often minimized using Boolean algebra to reduce gate count.[48][49] Combinational circuits find widespread applications in processors, including arithmetic logic units (ALUs) for operations like addition via chains of full-adders, as well as encoders that convert active inputs to binary codes and decoders that activate one of multiple outputs from a binary address. These components enable efficient data processing and control signal generation without state retention.[44][47]Sequential logic
Sequential logic refers to digital circuits where the output depends not only on the current inputs but also on the previous state of the circuit, achieved through memory elements that incorporate feedback loops and often synchronized by clock signals.[50] These circuits enable state transitions, allowing them to store information and respond to sequences of inputs over time, in contrast to combinational logic which produces instantaneous outputs solely from current inputs.[51] A fundamental building block of sequential logic is the SR latch, constructed using two cross-coupled NOR gates that provide feedback to maintain the output state. The SR latch has two inputs, Set (S) and Reset (R), and two complementary outputs, Q and Q-bar; when S=1 and R=0, Q=1 (set state); when S=0 and R=1, Q=0 (reset state); and when S=0 and R=0, the latch holds its previous state, while S=1 and R=1 is an invalid condition that should be avoided.[52] For clocked operation, an enable input can be added to control when the latch responds to S and R. The D flip-flop extends this by providing edge-triggered storage, typically positive-edge triggered, where the output Q captures the value of the D input precisely at the rising edge of the clock signal and holds it until the next edge. This ensures synchronous behavior in larger systems, preventing race conditions from asynchronous changes. The JK flip-flop addresses limitations of the SR latch by adding toggle functionality; it uses J and K inputs where J=0 and K=0 holds the state, J=1 and K=0 sets Q=1, J=0 and K=1 resets Q=0, and J=1 and K=1 toggles Q to its complement on the clock edge, eliminating the invalid state.[53] Sequential logic finds applications in counters, which increment or decrement a stored value on each clock pulse to track events or generate timing signals; shift registers, which move data bits serially or in parallel for tasks like data buffering and conversion; and finite state machines (FSMs), which model control logic by transitioning between defined states based on inputs and current state.[54][55] Timing in sequential circuits is governed by clock signals that synchronize state changes, with setup time defined as the minimum duration the data input must be stable before the clock edge, and hold time as the minimum duration it must remain stable after the edge, to ensure reliable capture without metastability.[56] These parameters are critical for system reliability, as violations can lead to incorrect state transitions. Flip-flops serve as the core memory elements in static random-access memory (SRAM), where arrays of them store bits addressably, enabling fast read and write operations in computing systems.[57]Implementation
Electronic gates
Electronic logic gates are primarily implemented using semiconductor transistors, with complementary metal-oxide-semiconductor (CMOS) technology serving as the dominant approach due to its low power consumption and high noise immunity.[58] In CMOS, basic gates like AND, OR, and NOT are constructed from pairs of n-channel (NMOS) and p-channel (PMOS) transistors arranged in complementary configurations.[58] The simplest element, the NOT gate or inverter, consists of a single NMOS transistor connected in series with a PMOS transistor between the supply voltage (VDD) and ground, with the input applied to both gates and the output taken from their common drain connection.[58] When the input is high (VDD), the NMOS turns on, pulling the output low (to ground), while the PMOS turns off; conversely, a low input turns the PMOS on, charging the output to VDD, and the NMOS off.[58] More complex gates, such as NAND and NOR, extend this by paralleling PMOS transistors for NAND (or NMOS for NOR) and series-connecting the opposite type, enabling efficient realization of AND and OR functions through De Morgan's theorem.[58] The performance of CMOS gates is influenced by fan-in (number of inputs) and fan-out (number of driven loads), which impact propagation delay due to increased capacitive loading.[58] High fan-in raises internal capacitance, slowing switching, while excessive fan-out—typically limited to over 50 in CMOS before delay becomes prohibitive—requires buffering to maintain speed.[59] Various logic families define the electronic characteristics of these gates, balancing speed, power, and noise margins. Transistor-transistor logic (TTL), using bipolar junction transistors, operates at 5V with a propagation delay of 1.5–33 ns, power dissipation of 1–22 mW per gate, fan-out of 10, and very good noise immunity (DC margins around 0.4V).[60][59] CMOS, leveraging MOSFET pairs, excels in low power (1 mW at 1 MHz, quiescent near 25 nW), excellent noise immunity (margins ~1.5V at 5V), fan-out exceeding 50, but slower propagation (1–200 ns at 3.3–5V).[60][59] Emitter-coupled logic (ECL), also bipolar-based, prioritizes speed with 1–4 ns delays at -5.2V, but at higher power (4–55 mW) and fan-out of 25, with good noise immunity suitable for high-frequency applications.[59] The following table compares key characteristics of these families:| Family | Voltage (V) | Propagation Delay (ns) | Power Dissipation (mW/gate) | Fan-out | Noise Immunity |
|---|---|---|---|---|---|
| TTL | 5 | 1.5–33 | 1–22 | 10 | Very Good |
| CMOS | 3.3–5 | 1–200 | 1 (at 1 MHz) | >50 | Excellent |
| ECL | -5.2 | 1–4 | 4–55 | 25 | Good |
| Enable (EN) | Input (IN) | Output (OUT) |
|---|---|---|
| 0 | 0 | Hi-Z |
| 0 | 1 | Hi-Z |
| 1 | 0 | 0 |
| 1 | 1 | 1 |