Does combinational and sequential logic correspond to some mathematical logic systems?

Question

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?

Answer 1

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.

Answer 2

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:

^{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.