Combinational logic

﻿
Combinational logic

In digital circuit theory, combinational logic (sometimes also referred to as 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 is in contrast to sequential logic, 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 while combinational logic does not.

Combinational logic is used in computer circuits to do boolean algebra 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 adders, full adders, half subtractors, full subtractors, multiplexers, demultiplexers, encoders and decoders are also made by using combinational logic.

Representation

Combinational logic is used for building circuits where certain outputs are desired, given certain inputs. The construction of combinational logic is generally done using one of two methods: a sum of products, or a product of sums. A sum of products can be easily visualized by looking at a truth table:

A B C Result Logical equivalent
F F F F $\neg A \cdot \neg B \cdot \neg C$
F F T F $\neg A \cdot \neg B \cdot C$
F T F F $\neg A \cdot B \cdot \neg C$
F T T F $\neg A \cdot B \cdot C$
T F F T $A \cdot \neg B \cdot \neg C$
T F T F $A \cdot \neg B \cdot C$
T T F F $A \cdot B \cdot \neg C$
T T T T $A \cdot B \cdot C$

Using sum of products, we take the sum of all logical statements which yield true results. Thus, our result would be:

$A \cdot \neg B \cdot \neg C + A \cdot B \cdot C \,$

It could then be simplified using Boolean algebra to:

$A \cdot (\neg B \cdot \neg C + B \cdot C) \,$

Logic formulas minimization

Minimization (simplification) of combinational logic formulas is done using the following rules:

$(A + B) \cdot (A + C) = A + (B \cdot C);$
$\quad (A \cdot B) + (A \cdot C) = A \cdot (B + C);$
$A + (A \cdot B) = A;$
$\quad A \cdot (A + B) = A;$
$A + (\lnot A \cdot B) = A + B;$
$\quad A \cdot(\lnot A + B) = A \cdot B;$
$(A + B)\cdot(\lnot A + B)=B;$
$\quad (A \cdot B) + (\lnot A \cdot B)=B.$
$(A \cdot B) + (\lnot A \cdot B) + (B \cdot C) = (A \cdot B) + (\lnot A \cdot B);$

With the use of minimization, a simplified logical function or circuit may be arrived at, and the logic combinational circuit becomes smaller, and easier to analyse, use, or build.

References

• Michael Predko and Myke Predko, Digital electronics demystified, McGraw-Hill, 2004. ISBN 0-071-44141-7

Wikimedia Foundation. 2010.

Look at other dictionaries:

• combinational logic — kombinatorinė logika statusas T sritis automatika atitikmenys: angl. combinational logic; combinatory logic; combinatorial logic vok. kombinatorische Logik, f; Schaltlogik, f rus. комбинаторная логика, f pranc. logique combinatoire, f …   Automatikos terminų žodynas

• combinational logic — noun Said of a digital circuit block: that the current outputs are entirely a function of the current inputs, without having a memory a previous inputs or states. Ant: sequential logic …   Wiktionary

• combinational logic element — kombinacinis loginis elementas statusas T sritis automatika atitikmenys: angl. combinational logic element vok. kombinatorisches logisches Element, n rus. комбинационный логический элемент, m pranc. élément logique, m …   Automatikos terminų žodynas

• combinational logic function — kombinacinė loginė funkcija statusas T sritis automatika atitikmenys: angl. combinational logic function vok. kombinatorische Logikfunktion, f rus. комбинационная логическая функция, f pranc. fonction logique combinatoire, f …   Automatikos terminų žodynas

• Logic optimization — a part of logic synthesis, is the process of finding an equivalent representation of the specified logic circuit under one or more specified constraints. Generally the circuit is constrained to minimum chip area meeting a prespecified delay.… …   Wikipedia

• Logic gate — A logic gate is an idealized or physical device implementing a Boolean function, that is, it performs a logical operation on one or more logic inputs and produces a single logic output. Depending on the context, the term may refer to an ideal… …   Wikipedia

• Logic synthesis — is a process by which an abstract form of desired circuit behavior (typically register transfer level (RTL) or behavioral) is turned into a design implementation in terms of logic gates. Common examples of this process include synthesis of HDLs,… …   Wikipedia

• Logic level — In digital circuits, a logic level is one of a finite number of states that a signal can have. Logic levels are usually represented by the voltage difference between the signal and ground (or some other common reference point), although other… …   Wikipedia

• Category:Logic in computer science — Logic in computer science is that branch of mathematical logic which is approximately the intersection between mathematical logic and computer science. It contains: Those investigations into logic that are guided by applications in computer… …   Wikipedia

• Programmable Array Logic — The term Programmable Array Logic (PAL) is used to describe a family of programmable logic device semiconductors used to implement logic functions in digital circuits introduced by Monolithic Memories, Inc. (MMI) in March 1978.cite journal |… …   Wikipedia