From a Logic Circuit to a Directed Graph
A logic circuit computes Boolean outputs from Boolean inputs. Its gates are connected by wires, and a wire carries the output of one input or gate to an input of another gate. A directed graph records this dependency: its vertices represent inputs and gates, and each directed edge points from the signal source to the gate that receives it. If the graph has no directed cycle, the circuit can be evaluated in an order that never asks for a signal before its value is known.
Throughout, a Boolean value is either \(0\) or \(1\). We use \(\land\) for AND, \(\lor\) for OR, and \(\neg\) for NOT. An AND or OR gate takes the values on its incoming wires as inputs; a NOT gate has one incoming wire. An input vertex has a fixed value supplied from outside the circuit. A constant vertex, if present, has a fixed value of \(0\) or \(1\). The circuit's designated output is the value at a specified input or gate vertex.
In this tutorial, the examples have no loops or repeated directed edges, and each gate's incoming edges supply its inputs. The indegree of a vertex is the number of edges directed into it; its outdegree is the number directed out of it. An input or constant has indegree zero. A gate's output may have several outgoing edges, so one computed signal can feed more than one later gate.
Why Acyclicity Gives an Evaluation Order
The key fact is that a finite directed graph has a topological ordering exactly when it has no directed cycle. Here is a proof, including the finite-graph step used to build the ordering.
Proof. First suppose the graph has a topological ordering. Along every directed edge, the tail must occur earlier than the head. If there were a directed cycle \(v_1\to v_2\to\cdots\to v_k\to v_1\), these requirements would put \(v_1\) earlier than \(v_2\), \(v_2\) earlier than \(v_3\), and so on, with \(v_k\) earlier than \(v_1\). These strict ordering requirements cannot all hold. Thus the graph is acyclic.
Conversely, suppose the graph is finite and acyclic. If it has at least one vertex, it must have a vertex of indegree zero. Otherwise, starting at any vertex and repeatedly following an incoming edge backwards would produce a sequence of vertices longer than the number of vertices. Some vertex would repeat; the edges between its repetitions would give a directed cycle, contrary to the assumption. Remove a vertex of indegree zero and list it first. The remaining graph is still finite and acyclic, since removing vertices cannot create a directed cycle. Repeat this procedure until no vertices remain. If the original graph is empty, use the empty list instead. To verify the resulting list, consider any edge \(u\to v\). The vertex \(v\) could not have been removed while \(u\) remained, because then \(v\) would still have an incoming edge. Thus \(u\) appears before \(v\). The list is a topological ordering. \(\square\)
This proof gives a procedure: repeatedly remove a vertex that has no incoming edge from the vertices still present, recording each removed vertex. If all vertices are removed, the recorded list is a topological ordering. If vertices remain but none has indegree zero, the remaining graph contains a directed cycle, as the backwards-following argument in the proof shows.
Proof. Choose a topological ordering. Give each input and constant vertex its prescribed value. Now process the gates in that order. Every edge into a gate comes from a vertex earlier in the ordering, so every input value required by the gate has already been assigned. The gate's Boolean rule therefore assigns it a value. This constructs values for all vertices. For uniqueness, compare any two assignments that agree on the prescribed inputs and constants. Proceed along the same topological ordering. At an input or constant, the assignments agree by prescription. At a gate, they agree on every incoming value because those vertices came earlier; applying the same gate function gives the same output. By induction along the finite ordering, they agree at every vertex. Hence the evaluation exists and is unique. \(\square\)
Evaluating a Circuit in Topological Order
Worked Example: Four Gates and a Designated Output
Let the inputs be \(a,b,c\), and let the gates be \(g_1,g_2,g_3,g_4\), with \(g_1\) an AND gate, \(g_2\) an OR gate, \(g_3\) a NOT gate and \(g_4\) an AND gate. The designated output is \(g_4\). The circuit graph has vertex set \(V=\{a,b,c,g_1,g_2,g_3,g_4\}\) and edge set \(E=\{a g_1,b g_1,b g_2,c g_2,g_1 g_3,g_2 g_4,g_3 g_4\}\), where each listed pair is directed from left to right. Set \(a=1\), \(b=0\) and \(c=1\).
A topological ordering is \(a,b,c,g_1,g_2,g_3,g_4\). Evaluate the gates in that order. First, \(g_1=a\land b=1\land0=0\). Next, \(g_2=b\lor c=0\lor1=1\). Then, \(g_3=\neg g_1=\neg0=1\). Finally, \(g_4=g_2\land g_3=1\land1=1\). Thus the designated output is \(1\).
Check: Substituting the input values into the output expression gives \(g_4=(b\lor c)\land\neg(a\land b)=(0\lor1)\land\neg(1\land0)=1\land\neg0=1\land1=1\), agreeing with the gate-by-gate evaluation. Each gate was evaluated only after its incoming signals had values.
When several vertices are available, more than one topological ordering may be valid. For example, independent inputs can appear in either order. The theorem about circuit evaluation shows that this freedom does not change the computed values: the ordering affects when a gate is evaluated, but not which values reach it.
Shared Subcomputations and Fan-Out
A gate with more than one outgoing edge sends its computed value to more than one later gate. In the graph, this is called fan-out. It lets the circuit represent a shared subcomputation directly: calculate a value once, then use that vertex as a predecessor of several gates. In a formula written as a tree, the same expression may instead be written out separately wherever it is used.
Worked Example: Reusing an AND Gate's Output
Let the inputs be \(a,b,c,d\), and define \(p=a\land b\), \(r=p\lor c\) and \(s=p\land d\). The circuit graph has vertex set \(V=\{a,b,c,d,p,r,s\}\) and edge set \(E=\{a p,b p,p r,c r,p s,d s\}\), with edges directed from left to right. The designated outputs are \(r\) and \(s\). Set \(a=1\), \(b=1\), \(c=0\) and \(d=1\).
One topological ordering is \(a,b,c,d,p,r,s\). First compute \(p=a\land b=1\land1=1\). Then \(r=p\lor c=1\lor0=1\), and \(s=p\land d=1\land1=1\). The single vertex \(p\) has two outgoing edges, \(p r\) and \(p s\), so its value is shared by both outputs.
Check: Evaluating the two expressions separately gives \(r=(1\land1)\lor0=1\lor0=1\) and \(s=(1\land1)\land1=1\land1=1\). These agree with the graph evaluation. The graph has \(7\) vertices and \(6\) edges: its listed edge set has exactly the six wires \(a p,b p,p r,c r,p s,d s\).
Sharing changes the structure of the representation, not the Boolean rule. In this example, \(p\) has to be evaluated before either \(r\) or \(s\), and its one value is supplied to both. A topological ordering makes that dependency explicit.
Detecting a Feedback Loop
A directed cycle represents a dependency that returns to an earlier part of the circuit. No topological ordering can place each signal source before the gate that depends on it all the way around the cycle. Consequently, the evaluation procedure proved above applies to acyclic circuits, not to circuits with feedback. Feedback circuits require a different model and analysis; they are not evaluated by simply following a topological ordering.
Worked Example: A Feedback Loop That Cannot Be Evaluated in Order
Let \(x\) be an input, \(g\) a NOT gate and \(h\) an AND gate. Set the gate rules to \(g=\neg h\) and \(h=x\land g\). The circuit graph has vertex set \(V=\{x,g,h\}\) and edge set \(E=\{x h,g h,h g\}\), directed from left to right. The edges \(g h\) and \(h g\) form the directed cycle \(g\to h\to g\).
Test the source-removal procedure. Initially, \(x\) has indegree \(0\), \(g\) has indegree \(1\) from \(h\), and \(h\) has indegree \(2\) from \(x\) and \(g\). Remove \(x\). Among the remaining vertices, \(g\) has an incoming edge from \(h\), while \(h\) has an incoming edge from \(g\). Thus each remaining vertex still has indegree \(1\), and neither can be removed. The procedure stops with the cycle \(g\to h\to g\), confirming that there is no topological ordering.
For a further check, set \(x=1\). The gate rules would require \(h=1\land g=g\) and \(g=\neg h\), so together they require \(g=\neg g\). If \(g=0\), then \(\neg g=1\), contradicting \(g=\neg g\); if \(g=1\), then \(\neg g=0\), also a contradiction. There is no Boolean assignment satisfying these rules for \(x=1\), consistent with the fact that the acyclic evaluation theorem does not apply.
Common Mistakes and a Reliable Checklist
Mistake: claiming that no vertex has indegree zero when one does. In the feedback example, it would be wrong to say that no vertex has indegree zero: \(x\) has indegree zero. The procedure must start by removing \(x\). Only after \(x\) is removed do \(g\) and \(h\) remain, each with an incoming edge from the other. Keeping track of the graph that remains at each step prevents this contradiction.
Mistake: treating a directed edge as an evaluation step by itself. An edge only records which signal feeds which gate; the gate's Boolean rule determines the value. For an AND gate, all incoming values must be known before its output can be calculated. In particular, an edge into a gate does not mean the gate is evaluated before its other predecessors.
To model and evaluate a combinational circuit, identify the input, constant and gate vertices; direct every wire from the signal source to the receiving gate; and check that the resulting graph is acyclic. Find a topological ordering and apply each gate's rule when all its incoming signals have values. If source removal leaves vertices behind, the remaining graph contains a directed cycle, so this evaluation method cannot be used for the whole circuit.
Check Your Understanding
For each question, use the definitions and results above; when asked to evaluate a circuit, show the gate values in a topological order.
- Let \(V=\{a,b,p,q\}\), \(E=\{a p,b p,p q\}\), with \(p=a\lor b\), \(q=\neg p\), and inputs \(a=0,b=1\). Find a topological ordering and the value at \(q\).
- In a circuit graph, what does a vertex with two outgoing edges represent? Explain how it can encode a shared subcomputation.
- Prove that every directed edge in a circuit graph points from an earlier vertex to a later vertex in any topological ordering.
- Suppose source removal stops with a nonempty set of vertices and every remaining vertex has positive indegree within that set. Explain why this guarantees a directed cycle.
- For the feedback example, set \(x=0\). Test \(g=1,h=0\) in both gate rules. Does this assignment satisfy them, and does that make the circuit graph acyclic?