<p>It is well known that connecting NAND gates allows the construction of arbitrary circuits. Furthermore, a NAND gate can be represented as a digraph with four vertices (in order, the two inputs, the "core" of the gate, and the output) and adjacency matrix </p>

<p>$\begin{pmatrix}0 &amp; 0 &amp; 1 &amp; 0 \\ 0 &amp; 0 &amp; 1 &amp; 0 \\ 0 &amp; 0 &amp; 0 &amp; 1 \\ 0 &amp; 0 &amp; 0 &amp; 0 \end{pmatrix}$.</p>

<p>Gluing these together gives a bijective correspondence between a certain class of digraphs and circuits built from wires and NAND gates. With this in mind, </p>

<blockquote>
  <p>is there a standard terminology for this correspondence/construction?
  Are there common references where it is discussed?</p>
</blockquote>

<p>I am particularly interested in the extent to which topological features of the digraph (e.g., the non-trivial homotopy induced by flip-flops) can be or have been related to the computational features of the corresponding circuit.</p>

<p>NB. This was <a href="https://math.stackexchange.com/questions/194361/boolean-circuits-and-digraphs">cross posted from MSE</a> after two days.</p>

CC BY-SA 3.0
2012-09-13T12:45:34.797Z
You should probably wait more than two days.
Tyson Williams
CC BY-SA 3.0
2012-09-13T16:50:35.787Z
I'm unclear as to how the digraph is representing the NAND gate. It doesn't seem to be a digraph representing the NAND function, e.g. as $(x,y) \mapsto (0,\;\mathrm{NAND}(x,y))$. Could you elaborate?
Niel de Beaudrap
CC BY-SA 3.0
2012-09-13T17:19:20.440Z
@Niel- Assume that wires are undirected edges. After gluing wires and graphs of the form in the question (and removing trivial wires, consecutive directed edges, etc.), we obtain a graph with some inputs (vertices with only one outbound edge and no undirected ones) and outputs (vertices with only one inbound edge and no undirected ones). Every vertex with two inbound directed edges and one outbound directed edge corresponds to a NAND in the following way: order the N input vertices and take a bitstring of length N: the kth bit goes to the kth input vector and is "propagated" along the...
S Huntsman
CC BY-SA 3.0
2012-09-13T17:22:30.983Z
...directed edge (continuing in the same direction along any undirected edges as well) until it hits a 2-in/1-out vertex, where the NAND of the inputs is computed and itself propagated. So to put it briefly, NAND as a Boolean function is represented but not implemented or emulated. Similarly, the Boolean circuit represented by the graph is not implemented or emulated--but it can be reproduced from the graph, and vice versa.
S Huntsman
CC BY-SA 3.0
2012-09-13T22:47:49.590Z
@Niel de Beaudrap: I cannot follow the asker’s argument in the comments, but I think that it is just the underlying DAG of the circuit made of two input gates, one NAND gate, and one output gate.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-14T03:32:41.053Z
SH, circuits in complexity theory are usually modelled with DAGs, not general digraphs. ok which maybe would be interesting to study wrt computing history/ FSMs because they could have loops, where the FSM models the circuit nodes at time $t$, but that would appear to be more an EE application... yeah maybe this is indeed studied somewhere...
vzn
CC BY-SA 3.0
2012-09-14T10:54:41.663Z
@vzn: It is also possible to have combinational circuits that are cyclic. See the page of Marc Riedel for papers on this. http://www.mriedel.ece.umn.edu/wiki/index.php/Papers,_Theses,_and_Slides#Computing_with_Feedback
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2012-09-14T15:12:16.440Z
@kristoffer, thx yeah exactly. note there are some deep thms on decomposition of FSMs. so one could convert the time/history-dependent "cyclic circuit" (which seems to be studied more in EE than CS?) to a FSM and apply eg the [krohn-rhodes decomposition](http://en.wikipedia.org/wiki/Krohn%E2%80%93Rhodes_theory) to reveal "deep structure". SH you mentioned you are interested in flip-flop structure which the K-R thm reveals a fundamental structure/decomposition. K-R called it decomposition into "primes" but as the wikipedia article notes, there is some nuance there.
vzn
<graph-theory><co.combinatorics><boolean-functions>
Boolean circuits and digraphs
S Huntsman
# Boolean circuits and digraphs

(Asked by: username_0 on 2012-09-13)

It is well known that connecting NAND gates allows the construction of arbitrary circuits. Furthermore, a NAND gate can be represented as a digraph with four vertices (in order, the two inputs, the "core" of the gate, and the output) and adjacency matrix

$\begin{pmatrix}0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix}$.

Gluing these together gives a bijective correspondence between a certain class of digraphs and circuits built from wires and NAND gates. With this in mind,

> is there a standard terminology for this correspondence/construction?
> Are there common references where it is discussed?

I am particularly interested in the extent to which topological features of the digraph (e.g., the non-trivial homotopy induced by flip-flops) can be or have been related to the computational features of the corresponding circuit.

NB. This was [cross posted from MSE](https://math.stackexchange.com/questions/194361/boolean-circuits-and-digraphs) after two days.

**Tags:** graph-theory, co.combinatorics, boolean-functions

> **Comments:**
> **username_1**: You should probably wait more than two days.  
> **username_2**: I'm unclear as to how the digraph is representing the NAND gate. It doesn't seem to be a digraph representing the NAND function, e.g. as $(x,y) \mapsto (0,\;\mathrm{NAND}(x,y))$. Could you elaborate?  
> **username_0**: @Niel- Assume that wires are undirected edges. After gluing wires and graphs of the form in the question (and removing trivial wires, consecutive directed edges, etc.), we obtain a graph with some inputs (vertices with only one outbound edge and no undirected ones) and outputs (vertices with only one inbound edge and no undirected ones). Every vertex with two inbound directed edges and one outbound directed edge corresponds to a NAND in the following way: order the N input vertices and take a bitstring of length N: the kth bit goes to the kth input vector and is "propagated" along the...  
> **username_0**: ...directed edge (continuing in the same direction along any undirected edges as well) until it hits a 2-in/1-out vertex, where the NAND of the inputs is computed and itself propagated. So to put it briefly, NAND as a Boolean function is represented but not implemented or emulated. Similarly, the Boolean circuit represented by the graph is not implemented or emulated--but it can be reproduced from the graph, and vice versa.  
> **username_3**: @username_2: I cannot follow the asker’s argument in the comments, but I think that it is just the underlying DAG of the circuit made of two input gates, one NAND gate, and one output gate.  
> **username_4**: SH, circuits in complexity theory are usually modelled with DAGs, not general digraphs. ok which maybe would be interesting to study wrt computing history/ FSMs because they could have loops, where the FSM models the circuit nodes at time $t$, but that would appear to be more an EE application... yeah maybe this is indeed studied somewhere...  
> **username_5**: @username_4: It is also possible to have combinational circuits that are cyclic. See the page of Marc Riedel for papers on this. http://www.mriedel.ece.umn.edu/wiki/index.php/Papers,_Theses,_and_Slides#Computing_with_Feedback  
> **username_4**: @kristoffer, thx yeah exactly. note there are some deep thms on decomposition of FSMs. so one could convert the time/history-dependent "cyclic circuit" (which seems to be studied more in EE than CS?) to a FSM and apply eg the [krohn-rhodes decomposition](http://en.wikipedia.org/wiki/Krohn%E2%80%93Rhodes_theory) to reveal "deep structure". SH you mentioned you are interested in flip-flop structure which the K-R thm reveals a fundamental structure/decomposition. K-R called it decomposition into "primes" but as the wikipedia article notes, there is some nuance there.  

---

## 0 answers

