2
$\begingroup$

I am doing practice after just learning what combinational circuits are, yet I am unsure of why (c) is combinational, but (d) is not. Can someone please explain to me why this is? The Solution mentions that for (d) node n6 connects to the output terminals of both I3 and I4, but how is this different from the circuit in (c)?


Problem

$\endgroup$
  • $\begingroup$ I suggest you check the definition of "combinational circuit" (I don't know what that definition is). The difference between (c) and (d) appears to be that, in (d), the output wires of the two gates on the left are connected together and fed into the single output of the gate on the right, whereas, in (c), the outputs of the two AND gates aren't connected together; rather, the output of one AND goes into one input of the OR gate, and the output of the other AND goes into the other input. $\endgroup$ – David Richerby Jan 7 '16 at 21:58
  • 1
    $\begingroup$ Please don't include the question as an image. It makes information retrieval (i.e., finding your question) much harder. Instead, transcribe its textual parts. $\endgroup$ – Yuval Filmus Jan 7 '16 at 22:37
3
$\begingroup$

A combinatorial circuit corresponds to a "straight-line program" that computes the outputs of the circuit given its inputs. (It has to satisfy some constraints that will exclude circuit (f) among others.)

As an example, if we denote the inputs of circuit (c) by $x_1,x_2,x_3,x_4$ (top to bottom) and the output by $o$, then using $g_1,g_2$ for the intermediate gates, the circuit corresponds to the program

$g_1 = x_1 \land x_2$

$g_2 = x_3 \land x_4$

$o = g_1 \lor g_2$

It also corresponds to the formula $(x_1 \land x_2) \lor (x_3 \land x_4)$. However, not every circuit corresponds to a formula. (The difference is that in some circuits, the output of a gate can appear as an input to more than one gate.)

Circuit (d) cannot be written in this form, since the outputs of I3 and I4 are wired together. What is the relation between the input to the rightmost gate and the outputs of I3 and I4? Not something that can be described combinatorially.

The difference between circuit (c) and circuit (d) is that in circuit (c) wires are not joined together. Rather, the output of each of the AND gates is connected to its own input of the OR gate. In contrast, in circuit (d) the rightmost NOT gate has only one input, but two incoming wires that must share the same input pin.

$\endgroup$
  • $\begingroup$ nice, is the flip-flop a combinatorial circuit? $\endgroup$ – Nikos M. Jan 8 '16 at 10:26
  • $\begingroup$ No, since its underlying graph is not a DAG. $\endgroup$ – Yuval Filmus Jan 8 '16 at 10:38
  • $\begingroup$ how are these type of circuits handled in theoretical computer science (circuits with feedback, or loops lets say)? $\endgroup$ – Nikos M. Jan 8 '16 at 10:40
  • $\begingroup$ They are summarily ignored. $\endgroup$ – Yuval Filmus Jan 8 '16 at 10:45
  • $\begingroup$ @NikosM., the nicer can be modelized as state machines. $\endgroup$ – AProgrammer Jan 8 '16 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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