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
A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate ...
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 argume ...
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 i ...
, 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 remembered ...
'' while combinational logic does not.
Combinational logic is used in
computer 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, or ALU, that does mathematical calculations is constructed using combinational logic. Other circuits used in computers, such as
half 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,
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 argumen ...
:
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
Logic optimization is a process of finding an equivalent representation of the specified logic circuit under one or more specified constraints. This process is a part of a logic synthesis applied in digital electronics and integrated circuit d ...
), 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 i ...
*
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
*
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
*
Ladder logic
References
*
External links
*
{{DEFAULTSORT:Combinational Logic
Logic in computer science
Digital electronics