Digital logic

Digital logic is built on Boolean algebra, introduced by George Boole in the 19th century and later applied to circuit design by Claude Shannon in 1937¹. The basic operations—AND, OR, and NOT—combine binary inputs to produce a single output, following truth tables that define all possible outcomes. These operations are implemented using logic gates, which are electronic circuits that realize the Boolean functions. For example, an AND gate outputs 1 only when all inputs are 1, while an OR gate outputs 1 if any input is 1. The NOT gate inverts the input. From these primitives, more complex functions like NAND, NOR, XOR, and XNOR are derived, and any Boolean function can be expressed using only NAND or NOR gates, a property known as functional completeness².

Digital circuits fall into two categories: combinational and sequential. Combinational logic produces outputs solely from current inputs, with no memory; examples include adders, multiplexers, and encoders. Sequential logic, in contrast, uses storage elements like flip-flops to retain state, enabling circuits to remember past inputs. This distinction is crucial for building finite-state machines, which are the basis of processors and controllers. Sequential circuits are clocked, meaning they change state on the edge of a clock signal, allowing synchronous operation. Common flip-flops include SR, JK, D, and T types, each with specific behavior. The design of sequential logic involves state diagrams and state tables, and minimization techniques like Karnaugh maps help simplify both combinational and sequential circuits³.

Digital logic is implemented using various technologies, from early electromechanical relays and vacuum tubes to modern transistors. The invention of the integrated circuit in 1958 by Jack Kilby and Robert Noyce revolutionized the field, allowing millions of gates on a single chip. Transistor–transistor logic (TTL) and complementary metal–oxide–semiconductor (CMOS) are two dominant families; CMOS is preferred for its low power consumption and high density. The scaling of CMOS transistors has followed Moore's law, doubling roughly every two years, leading to the microprocessors used in computers and smartphones. However, physical limits and power dissipation have prompted research into alternative technologies such as quantum-dot cellular automata and reversible logic⁴.

Beyond the classic gates, digital logic includes lesser-known concepts like ternary logic, which uses three states (0, 1, and 2) and has been explored for potential efficiency gains. Another niche area is asynchronous logic, which operates without a global clock, offering advantages in speed and power but posing design challenges. The concept of logic families extends to emitter-coupled logic (ECL), known for high speed but high power consumption, used in supercomputers of the past. The history also includes the work of Charles Sanders Peirce, who discovered the functional completeness of the NOR gate decades before Shannon⁵. Additionally, digital logic is applied in non-electronic domains, such as pneumatic logic and fluidic logic, used in hazardous environments where electronics are unsafe.

Boolean algebra

A branch of algebra dealing with true/false values, used in digital logic design.

Logic gate

An electronic circuit that performs a Boolean operation on one or more inputs to produce a single output.

Flip-flop

A sequential logic circuit that stores one bit of data, changing state on a clock edge.

CMOS

Complementary metal–oxide–semiconductor, a technology for constructing integrated circuits with low power consumption.