25,161
edits
Changes
Created page with "'''Home * Hardware * Combinatorial Logic''' [[FILE:Half Adder.svg|border|right|thumb|[https://en.wikipedia.org/wiki/Half_adder half adder circuit diagram] ]..."
'''[[Main Page|Home]] * [[Hardware]] * Combinatorial Logic'''
[[FILE:Half Adder.svg|border|right|thumb|[https://en.wikipedia.org/wiki/Half_adder half adder circuit diagram] ]]
A '''Combinatorial Logic''' (also Combinational Logic) is a [https://en.wikipedia.org/wiki/Digital_electronics digital circuit] where one or more outputs are [https://en.wikipedia.org/wiki/Boolean_function boolean functions] of multiple inputs. The basic boolean operations [https://en.wikipedia.org/wiki/Logical_conjunction conjunction], [https://en.wikipedia.org/wiki/Logical_disjunction disjunction] and [https://en.wikipedia.org/wiki/Logical_negation logical negation] are sufficient to derive all other boolean as well as arithmetical operations. Opposed to a [[Sequential Logic|sequential logic]], outputs are not dependent on their history, that is a combinatorial logic does not require [[Memory|memory]].
=Implementation=
In hardware, combinatorial logic can either realized with hardwired [https://en.wikipedia.org/wiki/Logic_gates gates] of certain [https://en.wikipedia.org/wiki/Logic_families logic families] or [https://en.wikipedia.org/wiki/Programmable_logic_device programmable logic devices]. If the number of inputs is reasonable small, a once programmed [[Memory#ROM|ROM]] or [https://en.wikipedia.org/wiki/Lookup_table#Hardware_LUTs LUT] can act as combinatorial logic. The inputs are the address, while one output is associated with a data-pin. In software this is like performing ALU-operations versus a memory lookup with pre-calculated outputs for all relevant inputs, related to the [[Space-Time Tradeoff|space-time tradeoff]].
=Basic Operations=
Operator symbols, [https://en.wikipedia.org/wiki/Truth_table truth tables], [https://en.wikipedia.org/wiki/International_Electrotechnical_Commission IEC] and [https://en.wikipedia.org/wiki/American_National_Standards_Institute ANSI] [https://en.wikipedia.org/wiki/Circuit_diagram circuit diagram] [https://en.wikipedia.org/wiki/Electronic_symbol symbols], as well as discrete and relay logic circuits are given.
==AND==
An [https://en.wikipedia.org/wiki/AND_gate AND gate] implements a [https://en.wikipedia.org/wiki/Logical_conjunction logical conjunction].
<span style="font-size: 140%;">a ∧ b</span>
===Truth Table===
{| class="wikitable"
|-
! a
! b
! a and b
|-
| style="text-align:center;" | 0
| style="text-align:center;" | 0
! style="text-align:center;" | 0
|-
| style="text-align:center;" | 0
| style="text-align:center;" | 1
! style="text-align:center;" | 0
|-
| style="text-align:center;" | 1
| style="text-align:center;" | 0
! style="text-align:center;" | 0
|-
| style="text-align:center;" | 1
| style="text-align:center;" | 1
! style="text-align:center;" | 1
|}
===Symbols and Circuits===
{|
|-
| [[FILE:IEC AND label.svg|none|border|text-bottom|160px]]
| [[FILE:AND ANSI Labelled.svg|none|border|text-bottom|160px]]
| [[FILE:Diode-AND2.png|none|border|text-bottom|220px]]
| [[FILE:Relay and.svg|none|border|text-bottom|220px]]
|}
==OR==
An [https://en.wikipedia.org/wiki/OR_gate OR gate] implements a [https://en.wikipedia.org/wiki/Logical_disjunction logical disjunction].
<span style="font-size: 140%;">a ∨ b</span>
===Truth Table===
{| class="wikitable"
|-
! a
! b
! a or b
|-
| style="text-align:center;" | 0
| style="text-align:center;" | 0
! style="text-align:center;" | 0
|-
| style="text-align:center;" | 0
| style="text-align:center;" | 1
! style="text-align:center;" | 1
|-
| style="text-align:center;" | 1
| style="text-align:center;" | 0
! style="text-align:center;" | 1
|-
| style="text-align:center;" | 1
| style="text-align:center;" | 1
! style="text-align:center;" | 1
|}
===Symbols and Circuits===
{|
|-
| [[FILE:IEC OR label.svg|none|border|text-bottom|160px]]
| [[FILE:Or-gate-en.svg|none|border|text-bottom|160px]]
| [[FILE:Diode-OR2.png|none|border|text-bottom|220px]]
| [[FILE:Relay or.svg|none|border|text-bottom|220px]]
|}
==NOT==
A [https://en.wikipedia.org/wiki/NOT_gate NOT gate] or '''Inverter''' implements a [https://en.wikipedia.org/wiki/Logical_negation logical negation].
<span style="font-size: 140%;">¬a</span>
===Truth Table===
{| class="wikitable"
|-
! a
! not a
|-
| style="text-align:center;" | 0
! style="text-align:center;" | 1
|-
| style="text-align:center;" | 1
! style="text-align:center;" | 0
|}
===Symbols and Circuits===
{|
|-
| [[FILE:IEC NOT label.svg|none|border|text-bottom|160px]]
| [[FILE:Not-gate-en.png|none|border|text-bottom|160px]]
| [[FILE:Transistor pegelumsetzer.svg|none|border|text-bottom|220px]]
| [[FILE:Relay not.svg|none|border|text-bottom|220px]]
|}
=Derived Operations=
Concrete electronic gates often combine AND and OR with trailing NOT for so called [https://en.wikipedia.org/wiki/NAND_gate NAND] and [https://en.wikipedia.org/wiki/NOR_gate NOR gates]. As application of [[General Setwise Operations#DeMorganslaws|De Morgan's laws]] a NAND can also be interpreted as OR of inverted inputs, and NOR as AND of inverted inputs.
==NAND==
A [https://en.wikipedia.org/wiki/NAND_gate NAND gate] is the inversion of AND, NOT AND.
<span style="font-size: 140%;">a ⊼ b</span>
===Truth Table===
{| class="wikitable"
|-
! a
! b
! not(a and b)
|-
| style="text-align:center;" | 0
| style="text-align:center;" | 0
! style="text-align:center;" | 1
|-
| style="text-align:center;" | 0
| style="text-align:center;" | 1
! style="text-align:center;" | 1
|-
| style="text-align:center;" | 1
| style="text-align:center;" | 0
! style="text-align:center;" | 1
|-
| style="text-align:center;" | 1
| style="text-align:center;" | 1
! style="text-align:center;" | 0
|}
===Symbols and Circuits===
{|
|-
| [[FILE:IEC NAND label.svg|none|border|text-bottom|160px]]
| [[FILE:AND ANSI Labelled.svg|none|border|text-bottom|160px]]
| [[FILE:TTL npn nand.svg|none|border|text-bottom|220px]]
| [[FILE:Relay nand.svg|none|border|text-bottom|220px]]
|}
==NOR==
A [https://en.wikipedia.org/wiki/NOR_gate NOR gate] is the inversion of OR, NOT OR.
<span style="font-size: 140%;">a ⊽ b</span>
===Truth Table===
{| class="wikitable"
|-
! a
! b
! not(a or b)
|-
| style="text-align:center;" | 0
| style="text-align:center;" | 0
! style="text-align:center;" | 1
|-
| style="text-align:center;" | 0
| style="text-align:center;" | 1
! style="text-align:center;" | 0
|-
| style="text-align:center;" | 1
| style="text-align:center;" | 0
! style="text-align:center;" | 0
|-
| style="text-align:center;" | 1
| style="text-align:center;" | 1
! style="text-align:center;" | 0
|}
===Symbols and Circuits===
{|
|-
| [[FILE:IEC NOR label.svg|none|border|text-bottom|160px]]
| [[FILE:NOR ANSI Labelled.svg|none|border|text-bottom|160px]]
| [[FILE:MC717 Circuit.svg|none|border|text-bottom|220px]]
| [[FILE:Relay nor.svg|none|border|text-bottom|220px]]
|}
==XOR==
A [https://en.wikipedia.org/wiki/XOR_gate XOR gate] implements a [https://en.wikipedia.org/wiki/Exclusive_disjunction exclusive disjunction], which might be derived from AND/OR/NOT, for instance from four NAND gates.
<span style="font-size: 140%;">a ⊻ b</span>
===Truth Table===
{| class="wikitable"
|-
! a
! b
! a xor b
|-
| style="text-align:center;" | 0
| style="text-align:center;" | 0
! style="text-align:center;" | 0
|-
| style="text-align:center;" | 0
| style="text-align:center;" | 1
! style="text-align:center;" | 1
|-
| style="text-align:center;" | 1
| style="text-align:center;" | 0
! style="text-align:center;" | 1
|-
| style="text-align:center;" | 1
| style="text-align:center;" | 1
! style="text-align:center;" | 0
|}
===Symbols and Circuits===
{|
|-
| [[FILE:IEC XOR label.svg|none|border|text-bottom|160px]]
| [[FILE:XOR ANSI.svg|none|border|text-bottom|160px]]
| [[FILE:XOR from NAND.svg|none|border|text-bottom|220px]]
| [[FILE:Relay xor.svg|none|border|text-bottom|220px]]
|}
=DNF and CNF=
Combinational logic can be visualized by [https://en.wikipedia.org/wiki/Truth_table truth tables] and the construction is generally done using [https://en.wikipedia.org/wiki/Disjunctive_normal_form disjunctive] (sum of products) or [https://en.wikipedia.org/wiki/Conjunctive_normal_form conjunctive normal form] (products of sums), and using [https://en.wikipedia.org/wiki/Boolean_algebra_%28logic%29 boolean algebra] or [https://en.wikipedia.org/wiki/Karnaugh_map Karnaugh maps] to simplify the expression.
<span id="ALU"></span>
=ALU=
Combinatorial logic is a huge part of the [https://en.wikipedia.org/wiki/Arithmetic_logic_unit arithmetic logic unit] (ALU) of [https://en.wikipedia.org/wiki/Central_processing_unit processors], which provides accordant boolean logical instructions working on all [[Bit|bits]] of a register in parallel as mentioned in [[General Setwise Operations]] of [[Bitboards]]. Therefor each Combinatorial Logic can of course emulated in [[Software|software]].
<span id="Adder"></span>
==Adder==
A [https://en.wikipedia.org/wiki/Adder_%28electronics%29#Half_adder half adder] performs an addition on two one-bit binary numbers. Output of an AND gate is the carry, while a XOR gate leaves the one-bit sum. A [https://en.wikipedia.org/wiki/Adder_%28electronics%29#Full_adder full adder] with tad more gates adds three one-bit binary numbers, the third usually to feed in the carry from the previous digit, usually in [https://en.wikipedia.org/wiki/Carry_lookahead_adder carry look ahead] architectures, such as [https://en.wikipedia.org/wiki/Kogge-Stone_adder Kogge-Stone adder], also mentioned as [[Parallel Prefix Algorithms#KoggeStoneAdder|parallel prefix algorithm]].
[[FILE:Full-adder logic diagram.svg|none|border|text-bottom]]
[https://en.wikipedia.org/wiki/Half_adder#Full_adder Full Adder]
[[FILE:4-bit carry lookahead adder.svg|none|border|text-bottom]]
[https://en.wikipedia.org/wiki/Adder_%28electronics%29#Carry_look-ahead_adders 4-bit adder] with [https://en.wikipedia.org/wiki/Carry_lookahead_adder Carry Look Ahead]
<span id="CombinatorialAttackandDefendMap"></span>
==Combinatorial Attacks==
Assuming there are 13 times 64 digital inputs from a hardware wired [[Chessboard|chessboard]]. The 13 inputs per [[Squares|square]] has one exclusive "one" signal for either one of the twelve [[Pieces|pieces]] or an empty signal. For each square a number of attacks/defend outputs may be defined to implement a huge Combinatorial Logic as a "zero cycle" [[Attack and Defend Maps|attack table]], i. e. output ''a8 is attacked from south by white rook'' as DNF (sum of products).
===C Syntax===
With [[C]]-like operators, that is '&' for AND and '|' for OR, the DNF would look like this:
<pre>
southAttackByWhiteRook(a8) ::=
wrook(a7)
| ( empty(a7) & wrook(a6) )
| ( empty(a7) & empty(a6) & wrook(a5) )
| ( empty(a7) & empty(a6) & empty(a5) & wrook(a4) )
| ( empty(a7) & empty(a6) & empty(a5) & empty(a4) & wrook(a3) )
| ( empty(a7) & empty(a6) & empty(a5) & empty(a4) & empty(a3) & wrook(a2) )
| ( empty(a7) & empty(a6) & empty(a5) & empty(a4) & empty(a3) & empty(a2) & wrook(a1) )
</pre>
===Circuit===
The same sample as circuit f. i. in [https://en.wikipedia.org/wiki/Diode_logic Diode logic] with 34 [https://en.wikipedia.org/wiki/Diode diodes] and 7 [https://en.wikipedia.org/wiki/Resistor resistors]:
<pre>
Board bus
empty white rook
a1 a2 a3 a4 a5 a6 a7 a8 a1 a2 a3 a4 a5 a6 a7 a8 ANDs (MIN) OR (MAX)
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | |
o--|--|--|--|--|------|--|--|--|--|--|--|----------|<|-----o---| R1 |---o +Vcc
o--|--|--|--|------|--|--|--|--|--|--|----------|<|-----|
| o--|--|--|------|--|--|--|--|--|--|----------|<|-----| D1-D7
| | o--|--|------|--|--|--|--|--|--|----------|<|-----|
| | | o--|------|--|--|--|--|--|--|----------|<|-----|
| | | | o------|--|--|--|--|--|--|----------|<|-----|
| | | | | o--|--|--|--|--|--|----------|<|-----o----------|>|------o D28
| | | | | | | | | | | |
o--|--|--|--|---------|--|--|--|--|--|----------|<|-----o---| R2 |---o +Vcc |
o--|--|--|---------|--|--|--|--|--|----------|<|-----| |
| o--|--|---------|--|--|--|--|--|----------|<|-----| D8-D13 |
| | o--|---------|--|--|--|--|--|----------|<|-----| |
| | | o---------|--|--|--|--|--|----------|<|-----| |
| | | | o--|--|--|--|--|----------|<|-----o----------|>|------o D29
| | | | | | | | | |
o--|--|--|------------|--|--|--|--|----------|<|-----o---| R3 |---o +Vcc |
o--|--|------------|--|--|--|--|----------|<|-----| |
| o--|------------|--|--|--|--|----------|<|-----| D14-18 |
| | o------------|--|--|--|--|----------|<|-----| |
| | | o--|--|--|--|----------|<|-----o----------|>|------o D30
| | | | | | | |
o--|--|---------------|--|--|--|----------|<|-----o---| R4 |---o +Vcc |
o--|---------------|--|--|--|----------|<|-----| D19-D22 |
| o---------------|--|--|--|----------|<|-----| |
| | o--|--|--|----------|<|-----o----------|>|------o D31
| | | | | |
o--|------------------|--|--|----------|<|-----o---| R5 |---o +Vcc |
o------------------|--|--|----------|<|-----| D23-D25 |
| o--|--|----------|<|-----o----------|>|------o D32
| | | |
o---------------------|--|----------|<|-----o---| R6 |---o +Vcc |
| | | D26-D27 |
o--|----------|<|-----o----------|>|------o D33
| | D34
o------------------o----------|>|------o-->--o a8 attacked
| by white rook
_ from south
| | R7
|_|
|
--o--
--- gnd
-
</pre>
=See also=
* [[Belle#Hardware|Belle | Hardware Move Generation]]
* [[CHEOPS]]
* [[General Setwise Operations]]
* [[Sequential Logic]]
=External Links=
* [https://en.wikipedia.org/wiki/Combinational_logic Combinational logic from Wikipedia]
* [http://www.ee.surrey.ac.uk/Projects/Labview/combindex.html Combinational Logic & Systems Tutorial Guide]
* [https://en.wikipedia.org/wiki/Proposition_(disambiguation) Proposition (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Propositional_calculus Propositional calculus from Wikipedia]
* [https://en.wikipedia.org/wiki/Logic_gates Logic gate from Wikipedia]
: [https://en.wikipedia.org/wiki/AND_gate AND gate]
: [https://en.wikipedia.org/wiki/OR_gate OR Gate]
: [https://en.wikipedia.org/wiki/NOT_gate NOT Gate]
: [https://en.wikipedia.org/wiki/NAND_gate NAND gate]
: [https://en.wikipedia.org/wiki/NOR_gate NOR gate]
: [https://en.wikipedia.org/wiki/XOR_gate XOR gate]
: [https://en.wikipedia.org/wiki/XNOR_gate XNOR gate]
: [https://en.wikipedia.org/wiki/Fredkin_gate Fredkin gate]
: [https://en.wikipedia.org/wiki/Toffoli_Gate Toffoli gate] <ref>[[Edward Fredkin]], [https://en.wikipedia.org/wiki/Tommaso_Toffoli Tommaso Toffoli] ('''1982'''). ''Conservative logic''. [https://en.wikipedia.org/wiki/International_Journal_of_Theoretical_Physics International Journal of Theoretical Physics], Vol. 21, [http://web.archive.org/web/20061017232512/http://www.digitalphilosophy.org/download_documents/ConservativeLogic.pdf pdf]</ref>
* [https://en.wikipedia.org/wiki/Logic_families Logic family from Wikipedia]
: [https://en.wikipedia.org/wiki/Relay Relay]
: [https://en.wikipedia.org/wiki/Diode_logic Diode logic]
: [https://en.wikipedia.org/wiki/Resistor%E2%80%93transistor_logic Resistor–transistor logic]
: [https://en.wikipedia.org/wiki/Diode%E2%80%93transistor_logic Diode–transistor logic]
: [https://en.wikipedia.org/wiki/Transistor%E2%80%93transistor_logic Transistor–transistor logic]
: [https://en.wikipedia.org/wiki/Emitter-coupled_logic Emitter-coupled logic]
: [https://en.wikipedia.org/wiki/CMOS Complementary metal–oxide–semiconductor]
: [https://en.wikipedia.org/wiki/Integrated_injection_logic Integrated injection logic]
* [https://en.wikipedia.org/wiki/Address_decoder Address decoder from Wikipedia]
* [https://en.wikipedia.org/wiki/Lookup_table Lookup table from Wikipedia]
* [https://en.wikipedia.org/wiki/Curved_Air Curved Air] - [https://en.wikipedia.org/wiki/Air_Conditioning_(album) Propositions] (1971), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=wIRxe_gcwVc|alignment=left|valignment=top}}
=References=
<references />
'''[[Hardware|Up one Level]]'''
[[FILE:Half Adder.svg|border|right|thumb|[https://en.wikipedia.org/wiki/Half_adder half adder circuit diagram] ]]
A '''Combinatorial Logic''' (also Combinational Logic) is a [https://en.wikipedia.org/wiki/Digital_electronics digital circuit] where one or more outputs are [https://en.wikipedia.org/wiki/Boolean_function boolean functions] of multiple inputs. The basic boolean operations [https://en.wikipedia.org/wiki/Logical_conjunction conjunction], [https://en.wikipedia.org/wiki/Logical_disjunction disjunction] and [https://en.wikipedia.org/wiki/Logical_negation logical negation] are sufficient to derive all other boolean as well as arithmetical operations. Opposed to a [[Sequential Logic|sequential logic]], outputs are not dependent on their history, that is a combinatorial logic does not require [[Memory|memory]].
=Implementation=
In hardware, combinatorial logic can either realized with hardwired [https://en.wikipedia.org/wiki/Logic_gates gates] of certain [https://en.wikipedia.org/wiki/Logic_families logic families] or [https://en.wikipedia.org/wiki/Programmable_logic_device programmable logic devices]. If the number of inputs is reasonable small, a once programmed [[Memory#ROM|ROM]] or [https://en.wikipedia.org/wiki/Lookup_table#Hardware_LUTs LUT] can act as combinatorial logic. The inputs are the address, while one output is associated with a data-pin. In software this is like performing ALU-operations versus a memory lookup with pre-calculated outputs for all relevant inputs, related to the [[Space-Time Tradeoff|space-time tradeoff]].
=Basic Operations=
Operator symbols, [https://en.wikipedia.org/wiki/Truth_table truth tables], [https://en.wikipedia.org/wiki/International_Electrotechnical_Commission IEC] and [https://en.wikipedia.org/wiki/American_National_Standards_Institute ANSI] [https://en.wikipedia.org/wiki/Circuit_diagram circuit diagram] [https://en.wikipedia.org/wiki/Electronic_symbol symbols], as well as discrete and relay logic circuits are given.
==AND==
An [https://en.wikipedia.org/wiki/AND_gate AND gate] implements a [https://en.wikipedia.org/wiki/Logical_conjunction logical conjunction].
<span style="font-size: 140%;">a ∧ b</span>
===Truth Table===
{| class="wikitable"
|-
! a
! b
! a and b
|-
| style="text-align:center;" | 0
| style="text-align:center;" | 0
! style="text-align:center;" | 0
|-
| style="text-align:center;" | 0
| style="text-align:center;" | 1
! style="text-align:center;" | 0
|-
| style="text-align:center;" | 1
| style="text-align:center;" | 0
! style="text-align:center;" | 0
|-
| style="text-align:center;" | 1
| style="text-align:center;" | 1
! style="text-align:center;" | 1
|}
===Symbols and Circuits===
{|
|-
| [[FILE:IEC AND label.svg|none|border|text-bottom|160px]]
| [[FILE:AND ANSI Labelled.svg|none|border|text-bottom|160px]]
| [[FILE:Diode-AND2.png|none|border|text-bottom|220px]]
| [[FILE:Relay and.svg|none|border|text-bottom|220px]]
|}
==OR==
An [https://en.wikipedia.org/wiki/OR_gate OR gate] implements a [https://en.wikipedia.org/wiki/Logical_disjunction logical disjunction].
<span style="font-size: 140%;">a ∨ b</span>
===Truth Table===
{| class="wikitable"
|-
! a
! b
! a or b
|-
| style="text-align:center;" | 0
| style="text-align:center;" | 0
! style="text-align:center;" | 0
|-
| style="text-align:center;" | 0
| style="text-align:center;" | 1
! style="text-align:center;" | 1
|-
| style="text-align:center;" | 1
| style="text-align:center;" | 0
! style="text-align:center;" | 1
|-
| style="text-align:center;" | 1
| style="text-align:center;" | 1
! style="text-align:center;" | 1
|}
===Symbols and Circuits===
{|
|-
| [[FILE:IEC OR label.svg|none|border|text-bottom|160px]]
| [[FILE:Or-gate-en.svg|none|border|text-bottom|160px]]
| [[FILE:Diode-OR2.png|none|border|text-bottom|220px]]
| [[FILE:Relay or.svg|none|border|text-bottom|220px]]
|}
==NOT==
A [https://en.wikipedia.org/wiki/NOT_gate NOT gate] or '''Inverter''' implements a [https://en.wikipedia.org/wiki/Logical_negation logical negation].
<span style="font-size: 140%;">¬a</span>
===Truth Table===
{| class="wikitable"
|-
! a
! not a
|-
| style="text-align:center;" | 0
! style="text-align:center;" | 1
|-
| style="text-align:center;" | 1
! style="text-align:center;" | 0
|}
===Symbols and Circuits===
{|
|-
| [[FILE:IEC NOT label.svg|none|border|text-bottom|160px]]
| [[FILE:Not-gate-en.png|none|border|text-bottom|160px]]
| [[FILE:Transistor pegelumsetzer.svg|none|border|text-bottom|220px]]
| [[FILE:Relay not.svg|none|border|text-bottom|220px]]
|}
=Derived Operations=
Concrete electronic gates often combine AND and OR with trailing NOT for so called [https://en.wikipedia.org/wiki/NAND_gate NAND] and [https://en.wikipedia.org/wiki/NOR_gate NOR gates]. As application of [[General Setwise Operations#DeMorganslaws|De Morgan's laws]] a NAND can also be interpreted as OR of inverted inputs, and NOR as AND of inverted inputs.
==NAND==
A [https://en.wikipedia.org/wiki/NAND_gate NAND gate] is the inversion of AND, NOT AND.
<span style="font-size: 140%;">a ⊼ b</span>
===Truth Table===
{| class="wikitable"
|-
! a
! b
! not(a and b)
|-
| style="text-align:center;" | 0
| style="text-align:center;" | 0
! style="text-align:center;" | 1
|-
| style="text-align:center;" | 0
| style="text-align:center;" | 1
! style="text-align:center;" | 1
|-
| style="text-align:center;" | 1
| style="text-align:center;" | 0
! style="text-align:center;" | 1
|-
| style="text-align:center;" | 1
| style="text-align:center;" | 1
! style="text-align:center;" | 0
|}
===Symbols and Circuits===
{|
|-
| [[FILE:IEC NAND label.svg|none|border|text-bottom|160px]]
| [[FILE:AND ANSI Labelled.svg|none|border|text-bottom|160px]]
| [[FILE:TTL npn nand.svg|none|border|text-bottom|220px]]
| [[FILE:Relay nand.svg|none|border|text-bottom|220px]]
|}
==NOR==
A [https://en.wikipedia.org/wiki/NOR_gate NOR gate] is the inversion of OR, NOT OR.
<span style="font-size: 140%;">a ⊽ b</span>
===Truth Table===
{| class="wikitable"
|-
! a
! b
! not(a or b)
|-
| style="text-align:center;" | 0
| style="text-align:center;" | 0
! style="text-align:center;" | 1
|-
| style="text-align:center;" | 0
| style="text-align:center;" | 1
! style="text-align:center;" | 0
|-
| style="text-align:center;" | 1
| style="text-align:center;" | 0
! style="text-align:center;" | 0
|-
| style="text-align:center;" | 1
| style="text-align:center;" | 1
! style="text-align:center;" | 0
|}
===Symbols and Circuits===
{|
|-
| [[FILE:IEC NOR label.svg|none|border|text-bottom|160px]]
| [[FILE:NOR ANSI Labelled.svg|none|border|text-bottom|160px]]
| [[FILE:MC717 Circuit.svg|none|border|text-bottom|220px]]
| [[FILE:Relay nor.svg|none|border|text-bottom|220px]]
|}
==XOR==
A [https://en.wikipedia.org/wiki/XOR_gate XOR gate] implements a [https://en.wikipedia.org/wiki/Exclusive_disjunction exclusive disjunction], which might be derived from AND/OR/NOT, for instance from four NAND gates.
<span style="font-size: 140%;">a ⊻ b</span>
===Truth Table===
{| class="wikitable"
|-
! a
! b
! a xor b
|-
| style="text-align:center;" | 0
| style="text-align:center;" | 0
! style="text-align:center;" | 0
|-
| style="text-align:center;" | 0
| style="text-align:center;" | 1
! style="text-align:center;" | 1
|-
| style="text-align:center;" | 1
| style="text-align:center;" | 0
! style="text-align:center;" | 1
|-
| style="text-align:center;" | 1
| style="text-align:center;" | 1
! style="text-align:center;" | 0
|}
===Symbols and Circuits===
{|
|-
| [[FILE:IEC XOR label.svg|none|border|text-bottom|160px]]
| [[FILE:XOR ANSI.svg|none|border|text-bottom|160px]]
| [[FILE:XOR from NAND.svg|none|border|text-bottom|220px]]
| [[FILE:Relay xor.svg|none|border|text-bottom|220px]]
|}
=DNF and CNF=
Combinational logic can be visualized by [https://en.wikipedia.org/wiki/Truth_table truth tables] and the construction is generally done using [https://en.wikipedia.org/wiki/Disjunctive_normal_form disjunctive] (sum of products) or [https://en.wikipedia.org/wiki/Conjunctive_normal_form conjunctive normal form] (products of sums), and using [https://en.wikipedia.org/wiki/Boolean_algebra_%28logic%29 boolean algebra] or [https://en.wikipedia.org/wiki/Karnaugh_map Karnaugh maps] to simplify the expression.
<span id="ALU"></span>
=ALU=
Combinatorial logic is a huge part of the [https://en.wikipedia.org/wiki/Arithmetic_logic_unit arithmetic logic unit] (ALU) of [https://en.wikipedia.org/wiki/Central_processing_unit processors], which provides accordant boolean logical instructions working on all [[Bit|bits]] of a register in parallel as mentioned in [[General Setwise Operations]] of [[Bitboards]]. Therefor each Combinatorial Logic can of course emulated in [[Software|software]].
<span id="Adder"></span>
==Adder==
A [https://en.wikipedia.org/wiki/Adder_%28electronics%29#Half_adder half adder] performs an addition on two one-bit binary numbers. Output of an AND gate is the carry, while a XOR gate leaves the one-bit sum. A [https://en.wikipedia.org/wiki/Adder_%28electronics%29#Full_adder full adder] with tad more gates adds three one-bit binary numbers, the third usually to feed in the carry from the previous digit, usually in [https://en.wikipedia.org/wiki/Carry_lookahead_adder carry look ahead] architectures, such as [https://en.wikipedia.org/wiki/Kogge-Stone_adder Kogge-Stone adder], also mentioned as [[Parallel Prefix Algorithms#KoggeStoneAdder|parallel prefix algorithm]].
[[FILE:Full-adder logic diagram.svg|none|border|text-bottom]]
[https://en.wikipedia.org/wiki/Half_adder#Full_adder Full Adder]
[[FILE:4-bit carry lookahead adder.svg|none|border|text-bottom]]
[https://en.wikipedia.org/wiki/Adder_%28electronics%29#Carry_look-ahead_adders 4-bit adder] with [https://en.wikipedia.org/wiki/Carry_lookahead_adder Carry Look Ahead]
<span id="CombinatorialAttackandDefendMap"></span>
==Combinatorial Attacks==
Assuming there are 13 times 64 digital inputs from a hardware wired [[Chessboard|chessboard]]. The 13 inputs per [[Squares|square]] has one exclusive "one" signal for either one of the twelve [[Pieces|pieces]] or an empty signal. For each square a number of attacks/defend outputs may be defined to implement a huge Combinatorial Logic as a "zero cycle" [[Attack and Defend Maps|attack table]], i. e. output ''a8 is attacked from south by white rook'' as DNF (sum of products).
===C Syntax===
With [[C]]-like operators, that is '&' for AND and '|' for OR, the DNF would look like this:
<pre>
southAttackByWhiteRook(a8) ::=
wrook(a7)
| ( empty(a7) & wrook(a6) )
| ( empty(a7) & empty(a6) & wrook(a5) )
| ( empty(a7) & empty(a6) & empty(a5) & wrook(a4) )
| ( empty(a7) & empty(a6) & empty(a5) & empty(a4) & wrook(a3) )
| ( empty(a7) & empty(a6) & empty(a5) & empty(a4) & empty(a3) & wrook(a2) )
| ( empty(a7) & empty(a6) & empty(a5) & empty(a4) & empty(a3) & empty(a2) & wrook(a1) )
</pre>
===Circuit===
The same sample as circuit f. i. in [https://en.wikipedia.org/wiki/Diode_logic Diode logic] with 34 [https://en.wikipedia.org/wiki/Diode diodes] and 7 [https://en.wikipedia.org/wiki/Resistor resistors]:
<pre>
Board bus
empty white rook
a1 a2 a3 a4 a5 a6 a7 a8 a1 a2 a3 a4 a5 a6 a7 a8 ANDs (MIN) OR (MAX)
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | |
o--|--|--|--|--|------|--|--|--|--|--|--|----------|<|-----o---| R1 |---o +Vcc
o--|--|--|--|------|--|--|--|--|--|--|----------|<|-----|
| o--|--|--|------|--|--|--|--|--|--|----------|<|-----| D1-D7
| | o--|--|------|--|--|--|--|--|--|----------|<|-----|
| | | o--|------|--|--|--|--|--|--|----------|<|-----|
| | | | o------|--|--|--|--|--|--|----------|<|-----|
| | | | | o--|--|--|--|--|--|----------|<|-----o----------|>|------o D28
| | | | | | | | | | | |
o--|--|--|--|---------|--|--|--|--|--|----------|<|-----o---| R2 |---o +Vcc |
o--|--|--|---------|--|--|--|--|--|----------|<|-----| |
| o--|--|---------|--|--|--|--|--|----------|<|-----| D8-D13 |
| | o--|---------|--|--|--|--|--|----------|<|-----| |
| | | o---------|--|--|--|--|--|----------|<|-----| |
| | | | o--|--|--|--|--|----------|<|-----o----------|>|------o D29
| | | | | | | | | |
o--|--|--|------------|--|--|--|--|----------|<|-----o---| R3 |---o +Vcc |
o--|--|------------|--|--|--|--|----------|<|-----| |
| o--|------------|--|--|--|--|----------|<|-----| D14-18 |
| | o------------|--|--|--|--|----------|<|-----| |
| | | o--|--|--|--|----------|<|-----o----------|>|------o D30
| | | | | | | |
o--|--|---------------|--|--|--|----------|<|-----o---| R4 |---o +Vcc |
o--|---------------|--|--|--|----------|<|-----| D19-D22 |
| o---------------|--|--|--|----------|<|-----| |
| | o--|--|--|----------|<|-----o----------|>|------o D31
| | | | | |
o--|------------------|--|--|----------|<|-----o---| R5 |---o +Vcc |
o------------------|--|--|----------|<|-----| D23-D25 |
| o--|--|----------|<|-----o----------|>|------o D32
| | | |
o---------------------|--|----------|<|-----o---| R6 |---o +Vcc |
| | | D26-D27 |
o--|----------|<|-----o----------|>|------o D33
| | D34
o------------------o----------|>|------o-->--o a8 attacked
| by white rook
_ from south
| | R7
|_|
|
--o--
--- gnd
-
</pre>
=See also=
* [[Belle#Hardware|Belle | Hardware Move Generation]]
* [[CHEOPS]]
* [[General Setwise Operations]]
* [[Sequential Logic]]
=External Links=
* [https://en.wikipedia.org/wiki/Combinational_logic Combinational logic from Wikipedia]
* [http://www.ee.surrey.ac.uk/Projects/Labview/combindex.html Combinational Logic & Systems Tutorial Guide]
* [https://en.wikipedia.org/wiki/Proposition_(disambiguation) Proposition (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Propositional_calculus Propositional calculus from Wikipedia]
* [https://en.wikipedia.org/wiki/Logic_gates Logic gate from Wikipedia]
: [https://en.wikipedia.org/wiki/AND_gate AND gate]
: [https://en.wikipedia.org/wiki/OR_gate OR Gate]
: [https://en.wikipedia.org/wiki/NOT_gate NOT Gate]
: [https://en.wikipedia.org/wiki/NAND_gate NAND gate]
: [https://en.wikipedia.org/wiki/NOR_gate NOR gate]
: [https://en.wikipedia.org/wiki/XOR_gate XOR gate]
: [https://en.wikipedia.org/wiki/XNOR_gate XNOR gate]
: [https://en.wikipedia.org/wiki/Fredkin_gate Fredkin gate]
: [https://en.wikipedia.org/wiki/Toffoli_Gate Toffoli gate] <ref>[[Edward Fredkin]], [https://en.wikipedia.org/wiki/Tommaso_Toffoli Tommaso Toffoli] ('''1982'''). ''Conservative logic''. [https://en.wikipedia.org/wiki/International_Journal_of_Theoretical_Physics International Journal of Theoretical Physics], Vol. 21, [http://web.archive.org/web/20061017232512/http://www.digitalphilosophy.org/download_documents/ConservativeLogic.pdf pdf]</ref>
* [https://en.wikipedia.org/wiki/Logic_families Logic family from Wikipedia]
: [https://en.wikipedia.org/wiki/Relay Relay]
: [https://en.wikipedia.org/wiki/Diode_logic Diode logic]
: [https://en.wikipedia.org/wiki/Resistor%E2%80%93transistor_logic Resistor–transistor logic]
: [https://en.wikipedia.org/wiki/Diode%E2%80%93transistor_logic Diode–transistor logic]
: [https://en.wikipedia.org/wiki/Transistor%E2%80%93transistor_logic Transistor–transistor logic]
: [https://en.wikipedia.org/wiki/Emitter-coupled_logic Emitter-coupled logic]
: [https://en.wikipedia.org/wiki/CMOS Complementary metal–oxide–semiconductor]
: [https://en.wikipedia.org/wiki/Integrated_injection_logic Integrated injection logic]
* [https://en.wikipedia.org/wiki/Address_decoder Address decoder from Wikipedia]
* [https://en.wikipedia.org/wiki/Lookup_table Lookup table from Wikipedia]
* [https://en.wikipedia.org/wiki/Curved_Air Curved Air] - [https://en.wikipedia.org/wiki/Air_Conditioning_(album) Propositions] (1971), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=wIRxe_gcwVc|alignment=left|valignment=top}}
=References=
<references />
'''[[Hardware|Up one Level]]'''
