Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

(Cross-posted to CSTheory after two days)

share|cite|improve this question
up vote 1 down vote accepted

Any Boolean circuit can be viewed as a directed acyclic graph (DAG) by forgetting the type of the gates. This DAG is sometimes called the underlying DAG of the circuit.

Given a DAG G which is the underlying DAG of some Boolean circuit C, it is not possible in general to recover C unless you make some assumptions about C. For example, if you assume that C consists of input gates, NAND gates of fan-in 2, and output gates of fan-in 1 which copy the value of the preceding gate, then you can recover C from its underlying DAG because the fan-in of each gate uniquely determines the gate type, and this set of assumptions seems to be consistent with what you wrote in the question. But as you can hopefully see from my explicit statement of the assumptions, this set of assumptions is quite arbitrary, and I do not think that there is a standard name for it.

You may make a different set of assumptions, but I doubt that there is a set of assumptions on circuits which is (1) sufficient to determine the circuit you stated in the question from the DAG you stated in the question and (2) natural enough to deserve a standard name at the same time.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.