In automata theory, combinational logic (also referred to as time-independent logic) is a type of digital logic that 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 perform 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.
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 | B | C | Result | Logical equivalent |
|---|---|---|---|---|
| F | F | F | F |  |
| F | F | T | F |  |
| F | T | F | F |  |
| F | T | T | F |  |
| T | F | F | T |  |
| T | F | T | F |  |
| T | T | F | F |  |
| T | T | T | T |  |
Using sum of products, all logical statements which yield true results are summed, giving the result:
Using Boolean algebra, 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 becomes smaller, and easier to analyse, use, or build.
See also
- Asynchronous circuit
- Field-programmable gate array
- Formal verification
- Ladder logic
- Programmable logic controller
- Relay logic
- Sequential logic
- Tseytin transformation
References
- Predko, Michael; Predko, Myke (2004). Digital electronics demystified. McGraw-Hill. ISBN 0-07-144141-7.
External links
- Belton, D.; Bigwood, R. "Combinational Logic & Systems Tutorial Guide". Archived from the original on 2013-10-22.
In automata theory combinational logic also referred to as time independent logic is a type of digital logic that 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 Classes of automata Clicking on each layer gets an article on that subject Combinational logic is used in computer circuits to perform 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 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 RepresentationCombinational 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 B C Result Logical equivalentF F F F A B C displaystyle neg A wedge neg B wedge neg C F F T F A B C displaystyle neg A wedge neg B wedge C F T F F A B C displaystyle neg A wedge B wedge neg C F T T F A B C displaystyle neg A wedge B wedge C T F F T A B C displaystyle A wedge neg B wedge neg C T F T F A B C displaystyle A wedge neg B wedge C T T F F A B C displaystyle A wedge B wedge neg C T T T T A B C displaystyle A wedge B wedge C Using sum of products all logical statements which yield true results are summed giving the result A B C A B C displaystyle A wedge neg B wedge neg C vee A wedge B wedge C Using Boolean algebra the result simplifies to the following equivalent of the truth table A B C B C displaystyle A wedge neg B wedge neg C vee B wedge C Logic formula minimizationMinimization simplification of combinational logic formulas is done using the following rules based on the laws of Boolean algebra A B A C A B C A B A C A B C displaystyle begin aligned A vee B wedge A vee C amp A vee B wedge C A wedge B vee A wedge C amp A wedge B vee C end aligned A A B AA A B A displaystyle begin aligned A vee A wedge B amp A A wedge A vee B amp A end aligned A A B A BA A B A B displaystyle begin aligned A vee lnot A wedge B amp A vee B A wedge lnot A vee B amp A wedge B end aligned A B A B B A B A B B displaystyle begin aligned A vee B wedge lnot A vee B amp B A wedge B vee lnot A wedge B amp B end aligned A B A C B C A B A C A B A C B C A B A C displaystyle begin aligned A wedge B vee lnot A wedge C vee B wedge C amp A wedge B vee lnot A wedge C A vee B wedge lnot A vee C wedge B vee C amp A vee B wedge lnot A vee C end aligned With the use of minimization sometimes called logic optimization a simplified logical function or circuit may be arrived upon and the logic becomes smaller and easier to analyse use or build See alsoAsynchronous circuit Field programmable gate array Formal verification Ladder logic Programmable logic controller Relay logic Sequential logic Tseytin transformationReferencesSavant C J Jr Roden Martin Carpenter Gordon 1991 Electronic Design Circuits and Systems Benjamin Cummings Publishing Company p 682 ISBN 0 8053 0285 9 Lewin Douglas 1974 Logical Design of Switching Circuits 2nd ed Thomas Nelson and Sons pp 162 3 ISBN 017 771044 6 Predko Michael Predko Myke 2004 Digital electronics demystified McGraw Hill ISBN 0 07 144141 7 External linksBelton D Bigwood R Combinational Logic amp Systems Tutorial Guide Archived from the original on 2013 10 22
