Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Combinational logic
open-in-new
<h2 id="representation">Representation</h2> <p>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 <a href="/facts/Truth_table/4KsmArDW">truth table</a>: </p> <table><tbody><tr><th>A</th><th>B</th><th>C</th><th>Result</th><th><a href="/facts/Logical_equivalence/ysCWmsxA">Logical equivalent</a></th></tr><tr><td>F</td><td>F</td><td>F</td><td>F</td><td> ¬ A ∧ ¬ B ∧ ¬ C {\displaystyle \neg A\wedge \neg B\wedge \neg C} </td></tr><tr><td>F</td><td>F</td><td>T</td><td>F</td><td> ¬ A ∧ ¬ B ∧ C {\displaystyle \neg A\wedge \neg B\wedge C} </td></tr><tr><td>F</td><td>T</td><td>F</td><td>F</td><td> ¬ A ∧ B ∧ ¬ C {\displaystyle \neg A\wedge B\wedge \neg C} </td></tr><tr><td>F</td><td>T</td><td>T</td><td>F</td><td> ¬ A ∧ B ∧ C {\displaystyle \neg A\wedge B\wedge C} </td></tr><tr><td>T</td><td>F</td><td>F</td><td>T</td><td> A ∧ ¬ B ∧ ¬ C {\displaystyle A\wedge \neg B\wedge \neg C} </td></tr><tr><td>T</td><td>F</td><td>T</td><td>F</td><td> A ∧ ¬ B ∧ C {\displaystyle A\wedge \neg B\wedge C} </td></tr><tr><td>T</td><td>T</td><td>F</td><td>F</td><td> A ∧ B ∧ ¬ C {\displaystyle A\wedge B\wedge \neg C} </td></tr><tr><td>T</td><td>T</td><td>T</td><td>T</td><td> A ∧ B ∧ C {\displaystyle A\wedge B\wedge C} </td></tr></tbody></table> <p> Using sum of products, all logical statements which yield true results are summed, giving the result: </p> ( A ∧ ¬ B ∧ ¬ C ) ∨ ( A ∧ B ∧ C ) {\displaystyle (A\wedge \neg B\wedge \neg C)\vee (A\wedge B\wedge C)\,} <p>Using <a href="/facts/Boolean_algebra/VkCToAmg">Boolean algebra</a>, the result simplifies to the following equivalent of the truth table: </p> A ∧ ( ( ¬ B ∧ ¬ C ) ∨ ( B ∧ C ) ) {\displaystyle A\wedge ((\neg B\wedge \neg C)\vee (B\wedge C))\,} <h2 id="logic-formula-minimization">Logic formula minimization</h2> <p>Minimization (simplification) of combinational logic formulas is done using the following rules based on the <a href="/facts/Boolean_algebra/VkCToAmg">laws of Boolean algebra</a>: </p> ( A ∨ B ) ∧ ( A ∨ C ) = A ∨ ( B ∧ C ) ( A ∧ B ) ∨ ( A ∧ C ) = A ∧ ( B ∨ C ) {\displaystyle {\begin{aligned}(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{aligned}}} A ∨ ( A ∧ B ) = A A ∧ ( A ∨ B ) = A {\displaystyle {\begin{aligned}A\vee (A\wedge B)&=A\\A\wedge (A\vee B)&=A\end{aligned}}} A ∨ ( ¬ A ∧ B ) = A ∨ B A ∧ ( ¬ A ∨ B ) = A ∧ B {\displaystyle {\begin{aligned}A\vee (\lnot A\wedge B)&=A\vee B\\A\wedge (\lnot A\vee B)&=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)&=B\\(A\wedge B)\vee (\lnot A\wedge B)&=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)&=(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{aligned}}} <p>With the use of minimization (sometimes called <a href="/facts/Logic_optimization/7wSV4nut">logic optimization</a>), a simplified logical function or circuit may be arrived upon, and the logic combinational circuit becomes smaller, and easier to analyse, use, or build. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Asynchronous_circuit/n4ah2j7H">Asynchronous circuit</a></li> <li><a href="/facts/Field-programmable_gate_array/M8LSGcAU">Field-programmable gate array</a></li> <li><a href="/facts/Formal_verification/BYD4GnJR">Formal verification</a></li> <li><a href="/facts/Ladder_logic/67UVVQwq">Ladder logic</a></li> <li><a href="/facts/Programmable_logic_controller/bqh0GAdb">Programmable logic controller</a></li> <li><a href="/facts/Relay_logic/eEs4FXVn">Relay logic</a></li> <li><a href="/facts/Sequential_logic/Rcs4thlu">Sequential logic</a></li> <li><a href="/facts/Tseytin_transformation/4mdL5t7q">Tseytin transformation</a></li></ul> <ul><li>Predko, Michael; Predko, Myke (2004). <i>Digital electronics demystified</i>. McGraw-Hill. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-07-144141-7.</li></ul> <h2 id="external-links">External links</h2> <ul><li>Belton, D.; Bigwood, R. <a href="https://web.archive.org/web/20131022174334/http://www.ee.surrey.ac.uk/Projects/Labview/combindex.html">"Combinational Logic & Systems Tutorial Guide"</a>. Archived from <a href="http://www.ee.surrey.ac.uk/Projects/Labview/combindex.html">the original</a> on 2013-10-22.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Savant, C.J. Jr.; Roden, Martin; Carpenter, Gordon (1991). Electronic Design: Circuits and Systems. Benjamin/Cummings Publishing Company. p. 682. ISBN 0-8053-0285-9. <a href="0-8053-0285-9" target="_blank">0-8053-0285-9</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Lewin, Douglas (1974). Logical Design of Switching Circuits (2nd ed.). Thomas Nelson and Sons. pp. 162–3. ISBN 017-771044-6. <a href="017-771044-6" target="_blank">017-771044-6</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> </ol>