Editing Combinational logic

{{Short description|Type of digital logic implemented by Boolean circuits}}
{{distinguish|text=[[combinatory logic]], a topic in mathematical logic}}

{{Automata theory}}

In [[automata theory]], '''combinational logic''' (also referred to as '''time-independent logic'''<ref>
{{cite book | first1=C.J. Jr. | last1=Savant |first2=Martin |last2=Roden |first3=Gordon |last3=Carpenter |title=Electronic Design: Circuits and Systems |publisher= Benjamin/Cummings Publishing Company|date=1991 |isbn=0-8053-0285-9 |pages=682 |url=}}
</ref>) is a type of [[digital logic]] that is implemented by [[Boolean circuit]]s, 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 ''[[computer storage|memory]]'' while combinational logic does not.

Combinational logic is used in [[computer]] circuits to perform [[Boolean algebra (logic)|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 adder]]s, [[full adder]]s, [[half subtractor]]s, [[Half subtractor|full subtractors]], [[multiplexer]]s, [[Multiplexer|demultiplexers]], [[Simple encoder|encoder]]s and [[Binary decoder|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. <ref>{{cite book |first=Douglas |last=Lewin |title=Logical Design of Switching Circuits |publisher=Thomas Nelson and Sons |edition=2nd |date=1974 |isbn=017-771044-6 |pages=162–3 |url=}}</ref>

==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]]:

{| class="wikitable" style="margin: 1em auto 1em auto; text-align:center;"
|-
! {{nobold|{{mvar|A}}}} || {{nobold|{{mvar|B}}}} || {{nobold|{{mvar|C}}}} || Result || [[logical equivalence|Logical equivalent]]
|-
| {{no|F}} || {{no|F}} || {{no|F}} || {{no|F}} || <math>\neg A \wedge \neg B \wedge \neg C</math>
|-
| {{no|F}} || {{no|F}} || {{yes|T}} || {{no|F}} || <math>\neg A \wedge \neg B \wedge C</math>
|-
| {{no|F}} || {{yes|T}} || {{no|F}} || {{no|F}} || <math>\neg A \wedge B \wedge \neg C</math>
|-
| {{no|F}} || {{yes|T}} || {{yes|T}} || {{no|F}} || <math>\neg A \wedge B \wedge C</math>
|-
| {{yes|T}} || {{no|F}} || {{no|F}} || {{yes|T}} || <math>A \wedge \neg B \wedge \neg C</math>
|-
| {{yes|T}} || {{no|F}} || {{yes|T}} || {{no|F}} || <math>A \wedge \neg B \wedge C</math>
|-
| {{yes|T}} || {{yes|T}} || {{no|F}} || {{no|F}} || <math>A \wedge B \wedge \neg C</math>
|-
| {{yes|T}} || {{yes|T}} || {{yes|T}} || {{yes|T}} || <math>A \wedge B \wedge C</math>
|}


Using sum of products, all logical statements which yield true results are summed, giving the result:

: <math>(A \wedge \neg B \wedge \neg C) \vee (A \wedge B \wedge C) \,</math>

Using [[Boolean algebra]], the result simplifies to the following equivalent of the truth table:

: <math>A \wedge ((\neg B \wedge \neg C) \vee (B \wedge C)) \,</math>

==Logic formula minimization==
Minimization (simplification) of combinational logic formulas is done using the following rules based on the [[Boolean algebra#Laws|laws of Boolean algebra]]:

: <math>\begin{align}
(A \vee B) \wedge (A \vee C) &= A \vee (B \wedge C) \\
(A \wedge B) \vee (A \wedge C) &= A \wedge (B \vee C)
\end{align}</math>

: <math>\begin{align}
A \vee (A \wedge B) &= A \\
A \wedge (A \vee B) &= A

\end{align}</math>

: <math>\begin{align} 

A \vee (\lnot A \wedge B) &= A \vee B \\
A \wedge(\lnot A \vee B) &= A \wedge B

\end{align}</math>

: <math>\begin{align} 

(A \vee B)\wedge(\lnot A \vee B)&=B \\
(A \wedge B) \vee (\lnot A \wedge B)&=B

\end{align}</math>

: <math>\begin{align}

(A \wedge B) \vee (\lnot A \wedge C) \vee (B \wedge C) &= (A \wedge B) \vee (\lnot A \wedge C) \\
(A \vee B) \wedge (\lnot A \vee C) \wedge (B \vee C) &= (A \vee B) \wedge (\lnot A \vee C)

\end{align}</math>

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==
* [[Asynchronous circuit]]
* [[Field-programmable gate array]]
* [[Formal verification]]
* [[Ladder logic]]
* [[Programmable logic controller]]
* [[Relay logic]]
* [[Sequential logic]]
* [[Tseytin transformation]]

==References==
{{reflist}}
*{{cite book |first1=Michael |last1=Predko |first2=Myke |last2=Predko |title=Digital electronics demystified |publisher=McGraw-Hill |date=2004 |isbn=0-07-144141-7 }}

== External links ==
*{{cite web |first1=D. |last1=Belton |first2=R. |last2=Bigwood |title=Combinational Logic & Systems Tutorial Guide |url=http://www.ee.surrey.ac.uk/Projects/Labview/combindex.html |archive-url=https://web.archive.org/web/20131022174334/http://www.ee.surrey.ac.uk/Projects/Labview/combindex.html |archive-date=2013-10-22 }}

{{Digital electronics}}
{{authority control}}
{{DEFAULTSORT:Combinational Logic}}
[[Category:Logic in computer science]]
[[Category:Digital electronics]]