1
$\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

Improve this question
$\endgroup$
2
  • $\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, 2016 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, 2016 at 22:37

1 Answer 1

Reset to default
4
$\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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ nice, is the flip-flop a combinatorial circuit? $\endgroup$
    – Nikos M.
    Jan 8, 2016 at 10:26
  • $\begingroup$ No, since its underlying graph is not a DAG. $\endgroup$
    – Yuval Filmus
    Jan 8, 2016 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, 2016 at 10:40
  • $\begingroup$ They are summarily ignored. $\endgroup$
    – Yuval Filmus
    Jan 8, 2016 at 10:45
  • $\begingroup$ @NikosM., the nicer can be modelized as state machines. $\endgroup$
    – AProgrammer
    Jan 8, 2016 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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