In
automata theory
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματο ...
, combinational logic (also referred to as time-independent logic or combinatorial logic) is a type of
digital logic which is implemented by
Boolean circuit
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible inp ...
s, where the output is a
pure function
In computer programming, a pure function is a function that has the following properties:
# the function return values are identical for identical arguments (no variation with local static variables, non-local variables, mutable reference ar ...
of the present input only. This is in contrast to
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 ...
, in which the output depends not only on the present input but also on the history of the input. In other words, sequential logic has ''
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 remember ...
'' while combinational logic does not.
Combinational logic is used in
computer
A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations ( computation) automatically. Modern digital electronic computers can perform generic sets of operations known as programs. These prog ...
circuits to perform
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 i ...
on input signals and on stored data. Practical computer circuits normally contain a mixture of combinational and sequential logic. For example, the part of an
arithmetic logic unit
In computing, an arithmetic logic unit (ALU) is a 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 floating point num ...
, or ALU, that does mathematical calculations is constructed using combinational logic. Other circuits used in computers, such as
half adders,
full adder
An adder, or summer, is a digital circuit that performs addition of numbers. In many computers and other kinds of processors adders are used in the arithmetic logic units (ALUs). They are also used in other parts of the processor, where they are ...
s,
half subtractors,
full subtractors,
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,
demultiplexers,
encoders and
decoders are also made by using combinational logic.
Practical design of combinational logic systems may require consideration of the finite time required for practical logical elements to react to changes in their inputs. Where an output is the result of the combination of several different paths with differing numbers of switching elements, the output may momentarily change state before settling at the final state, as the changes propagate along different paths.
Representation
Combinational logic is used to build circuits that produce specified outputs from certain inputs. The construction of combinational logic is generally done using one of two methods: a sum of products, or a product of sums. Consider the following
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 arg ...
:
Using sum of products, all logical statements which yield true results are summed, giving the result:
:
Using
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 i ...
, the result simplifies to the following equivalent of the truth table:
:
Logic formula minimization
Minimization (simplification) of combinational logic formulas is done using the following rules based on the
laws of Boolean algebra:
:
:
:
:
:
With the use of minimization (sometimes called
logic optimization), a simplified logical function or circuit may be arrived upon, and the logic
combinational circuit becomes smaller, and easier to analyse, use, or build.
See also
*
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 ...
*
Asynchronous circuit
Asynchronous circuit (clockless or self-timed circuit) is a sequential digital logic circuit that does not use a global clock circuit or signal generator to synchronize its components. Instead, the components are driven by a handshaking circui ...
*
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-programmability, field-programmable''. The FPGA configuration is generally specifi ...
*
Formal verification
In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal met ...
*
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 calle ...
*
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 t ...
*
Ladder logic
Ladder logic was originally a written method to document the design and construction of relay racks as used in manufacturing and process control. Each device in the relay rack would be represented by a symbol on the ladder diagram with connecti ...
References
*
External links
*
{{DEFAULTSORT:Combinational Logic
Logic in computer science
Digital electronics