5
\$\begingroup\$

Is it correct that the functionalities of digital circuits are divided into combinational logic and sequential logic?

Is combinational logic the same thing as propositional logic in mathematical logic?

In automata theory, combinational logic (sometimes also referred to as time-independent logic) is a type of digital logic which is implemented by Boolean circuits, where the output is a pure function of the present input only.

What mathematical logic system does sequential logic correspond to, if any? Modal logic, temporal logic, ...?

I have heard of finite state machine/automaton (a topic in formal languages and automata) for sequential logic. Are finite state machine/automaton and temporal/modal/... logic different (unrelated) approaches to study sequential logic?

\$\endgroup\$
5
  • \$\begingroup\$ Combinatorial logic only operates on the latest inputs. Sequential logic is combinatorial logic that includes past inputs. \$\endgroup\$
    – mbedded
    Sep 19, 2020 at 15:20
  • \$\begingroup\$ Thanks. Does Sequential logic correspond to modal logic in mathematical logic? \$\endgroup\$
    – Tim
    Sep 19, 2020 at 15:49
  • 1
    \$\begingroup\$ No. Incorporating history (memory) makes sequential logic much more powerful and useful, but the theory does not significantly depart from Boolean algebra. Modal logic compares against a theoretical or ideal world, and to model that sort of thing would require a higher logic. \$\endgroup\$
    – mbedded
    Sep 19, 2020 at 16:01
  • \$\begingroup\$ How about temporal logic? \$\endgroup\$
    – Tim
    Sep 19, 2020 at 16:04
  • 1
    \$\begingroup\$ That also requires a generalized model that you don't (immediately) get from sequential logic. You can build many kinds of modeling using sequential logic, but it takes more structure than the logic itself. \$\endgroup\$
    – mbedded
    Sep 19, 2020 at 16:19

2 Answers 2

4
\$\begingroup\$

Is it correct that the functionalities of digit circuits are divided into combinational logic and sequential logic?

Yes. And sequential logic in digital electronics is subdivided into asynchronous and synchronous sequential logic.

Is combinational logic the same thing as propositional logic in mathematical logic?

No, they are not the same. Propositional logic operates on propositions, which are declarative sentences. In digital electronics, combinational logic refers to circuits which implement Boolean operations, and whose outputs are a function of the current inputs. Hence it is time-independent. Boolean operations can be operated only on Boolean data types. Boolean data types can take only 2 values.

Are finite state machine/automaton and temporal/modal/... logic different (unrelated) approaches to study sequential logic?

Not entirely. Sequential Logic is built from combinational logic circuits and has memory. In sequential logic, the outputs will also depend on the previous inputs. Sequential circuits have feedback.

Finite State Machines are sequential logic since they have memory. An automaton can be implemented in sequential logic if it has a finite number of states and is deterministic.

There are also automata which are undecidable, and it is not possible to build sequential logic for these automata. For example, Conway's game of life.

Strictly speaking, only deterministic Finite State machines can be built using sequential logic.

Non-determinism can be emulated using Pseudorandom Number Generation. This is not true non-determinism.

Do combinational and sequential logics correspond to some mathematical logic systems?

Combinational logic directly corresponds to Boolean Algebra, which is an algebraic logic.

Sequential logic does not correspond to any mathematical logic system. Sequential logic does correspond to the strictly non-deterministic finite state machine in automata theory, which is considered to be a field of computer science.

\$\endgroup\$
3
\$\begingroup\$

Logic is logic. There are certain stylized "logics" like "first order logic" which are constraints on the expressivity. "Temporal logic" or "modal logic" but in the end it comes all back down to basic logic. The issue is mostly the nature and interpretation of the input variables and results. And that is where this notion of "sequential logic" comes from. You simply have a recursion here where an input variable is the result of an output variable at a previous state. And this is what automata theory is about with simple state-transition models or Petri-Nets. Are there systematic papers about this? Mathematical models? Sure! But essentially it's automata theory, isn't it?

When people say "temporal logic" they basically mean some stylized way by which they add the time dimension into their system. And that begins with how you conceptualize time in the first place. You can think of a naive absolute continuous time dimension, you can think of relative time or integral cycle/step count time. You can think of this temporal dimension of a partial ordering of states which apply in sub-networks of the whole system, and anyway in automata theory it just comes back to state, i.e., output of prior step becoming the input of the next step.

Modal logic is a different beast. It's about extending the area of discourse in which you apply logic beyond mere indicative statements. You begin talking about possibility, or IMO more generally important about other speech act moods, such as the logic of an order (imperative) or a promise. Now when you dissect the logic of an order or promise, you probably will use states, because what defines a promise is a future state in which the author of the promise has performed as promised, and then, whether such performance was successful or not. So, you could say "temporal" (fulfillment of the promise happening later) or just state: an expectation state and later a fulfillment of said expectation.

Coming back to electronics, just look at the simplest latch/flip-flop forms:

schematic

simulate this circuit – Schematic created using CircuitLab

All of them have a recursion, usually cross-over output feeding back to input and Q and !Q outputs. The recursion stabilizes the state when the original inputs change. I put an OR gate and an inverter loop as some less conventional examples that still sort-of work even if momentarily they have to force the feed-back input against its output. The point is, state that survives the change of input settings.

Mathematically what it is the overall state being a function of the prior state and the new input at time t:

$$S_{t} = f(S_{t-1}, I_t)$$

where you can think of the state S as a vector of individually measurable states $$S = [s_1, s_2, ..., s_i]$$ and the input as individual input settings, which you can really also include into that same vector. It all goes from there. But it all comes back to "combinatorial logic" where inputs depend on prior outputs.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ What do you mean by "You simply have a recursion here where an input variable is the result of an output variable at a previous state"? Shouldn't the current output be the result of current and previous inputs? Also, classifying those circuits as a recursion seems a bit too much. Is there any reasoning for that? Or is it just that any system that evolves in time is a "recursion" (e.g. an ODE or difference equation)? Or did you classify them as recursions for having feedback? \$\endgroup\$
    – jDAQ
    Sep 19, 2020 at 20:00
  • \$\begingroup\$ @jDAQ, I use the word "recursion" quite literally: you take a wire that comes out on the right side (output) and bend it back to plug it into the left side (input). But look at my functional notation for this to compute/simulate that you'd use iteration or recursion. Input to the function is the result of an output of a previous state. That makes the current output a function of the previous state. It's the same thing. When you want to distinguish previous from current state it's gets tangled up. As the previous output becomes the current state. \$\endgroup\$ Sep 19, 2020 at 21:58
  • 1
    \$\begingroup\$ I disagree that the feedback loop is a recursion, as I don't see how x[t+1]=f(x[t]) could be the same as a recursion where f(x) = f(x-1)+a, with f(0)=1, or some other function. In the sense of having a recursive definition and a base case (are the initial conditions considered to be a base case? Is the evolution itself a recursive step? If so any evolving system that depends on previous states would be recursive/recursions). \$\endgroup\$
    – jDAQ
    Sep 19, 2020 at 22:37
  • 1
    \$\begingroup\$ Also, your functional notation needs to have a memory of the previous inputs, not the previous outputs (unless I'm missing something). For example, say that you have $$S[t] = I[t] \oplus I[t-1],$$ if you only keep track of the previous \$S[t-1]\$, you will not be able to find a function \$g\$ for $$S[t] = g(I[t], S[t-1]).$$ While you could have one for $$S[t] = g(I[t], I[t-1]).$$ \$\endgroup\$
    – jDAQ
    Sep 19, 2020 at 22:39
  • \$\begingroup\$ $$S_{t+1} = f(S_t)$$ or $$S_t = f(S_{t-1})$$ are equivalent, aren't they? In my initial notation $$S_t = f(S_{t-1})$$ I have a tail recursion: to find the state at time t, apply f to the previous state at t-1. Now the way we index the inputs I, I said I[t] because its the state of the input at the time t that matters. HOWEVER, the output at t-1 is part of the state at t. \$\endgroup\$ Sep 19, 2020 at 22:57

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.