Temporal logic

In

Temporal logic has found an important application in formal verification, where it is used to state requirements of hardware or software systems. For instance, one may wish to say that whenever a request is made, access to a resource is eventually granted, but it is never granted to two requestors simultaneously. Such a statement can conveniently be expressed in a temporal logic.

Motivation

Consider the statement "I am hungry". Though its meaning is constant in time, the statement's truth value can vary in time. Sometimes it is true, and sometimes false, but never simultaneously true and false. In a temporal logic, a statement can have a truth value that varies in time—in contrast with an atemporal logic, which applies only to statements whose truth values are constant in time. This treatment of truth-value over time differentiates temporal logic from computational verb logic.

Temporal logic always has the ability to reason about a timeline. So-called "linear-time" logics are restricted to this type of reasoning. Branching-time logics, however, can reason about multiple timelines. This permits in particular treatment of environments that may act unpredictably. To continue the example, in a branching-time logic we may state that "there is a possibility that I will stay hungry forever", and that "there is a possibility that eventually I am no longer hungry". If we do not know whether or not I will ever be fed, these statements can both be true.

History

Although

There was little development for millennia, Charles Sanders Peirce noted in the 19th century:^[2]

Time has usually been considered by logicians to be what is called 'extralogical' matter. I have never shared this opinion. But I have thought that logic had not yet reached the state of development at which the introduction of temporal modifications of its forms would not result in great confusion; and I am much of that way of thinking yet.

Surprisingly for

In the following years, research of temporal logic by Arthur Prior began.^[4] He was concerned with the philosophical implications of free will and predestination. According to his wife, he first considered formalizing temporal logic in 1953. Results of his research were first presented at the conference in Wellington in 1954.^[4] The system Prior presented, was similar syntactically to Łoś' logic, although not until 1955 did he explicitly refer to Łoś' work, in the last section of Appendix 1 in Prior’s Formal Logic.^[4]

Along with tense logic, Prior constructed a few systems of positional logic, which inherited their main ideas from Łoś.^[6] Work in positional temporal logics was continued by Nicholas Rescher in the 60s and 70s. In such works as Note on Chronological Logic (1966), On the Logic of Chronological Propositions (1968), Topological Logic (1968), and Temporal Logic (1971) he researched connections between Łoś' and Prior's systems. Moreover, he proved that Prior's tense operators could be defined using a realization operator in specific positional logics.^[6] Rescher, in his work, also created more general systems of positional logics. Although the first ones were constructed for purely temporal uses, he proposed the term topological logics for logics that were meant to contain a realization operator but had no specific temporal axioms—like the clock axiom.

The binary temporal operators Since and Until were introduced by Hans Kamp in his 1968 Ph.D. thesis,^[7] which also contains an important result relating temporal logic to first-order logic—a result now known as Kamp's theorem.^[8][2][9]

Two early contenders in formal verifications were linear temporal logic, a linear-time logic by Amir Pnueli, and computation tree logic (CTL), a branching-time logic by Mordechai Ben-Ari, Zohar Manna and Amir Pnueli. An almost equivalent formalism to CTL was suggested around the same time by E. M. Clarke and E. A. Emerson. The fact that the second logic can be decided more efficiently than the first does not reflect on branching- and linear-time logics in general, as has sometimes been argued. Rather, Emerson and Lei show that any linear-time logic can be extended to a branching-time logic that can be decided with the same complexity.

Łoś's positional logic

Syntax

The language of the logic first published in Podstawy Analizy Metodologicznej Kanonów Milla (The Foundations of a Methodological Analysis of Mill’s Methods) consisted of:^[3]

• first-order logic operators ‘¬’, ‘∧’, ‘∨’, ‘→’, ‘≡’, ‘∀’ and ‘∃’
• realization operator U
• functional symbol δ
• propositional variables p₁,p₂,p₃,...
• variables denoting time moments t₁,t₂,t₃,...
• variables denoting time intervals n₁,n₂,n₃,...

The set of terms (denoted by S) is constructed as follows:

• variables denoting time moments or intervals are terms
• if ${\displaystyle \tau \in S}$ and ${\displaystyle \epsilon }$ is a time interval variable, then ${\displaystyle \delta (\tau ,\epsilon )\in S}$

The set of formulas (denoted by For) is constructed as follows:^[10]

• all first-order logic formulas are valid
• if ${\displaystyle \tau \in S}$ and ${\displaystyle \phi }$ is a propositional variable, then ${\displaystyle U_{\tau }(\phi )\in For}$
• if ${\displaystyle \phi \in For}$, then ${\displaystyle \neg \phi \in For}$
• if ${\displaystyle \phi ,\psi \in For}$ and ${\displaystyle \circ \in \{\wedge ,\vee ,\rightarrow ,\equiv \}}$, then ${\displaystyle \phi \circ \psi \in For}$
• if ${\displaystyle \phi \in For}$ and ${\displaystyle Q\in \{\forall ,\exists \}}$ and υ is a propositional, moment or interval variable, then ${\displaystyle Q_{\upsilon }\phi \in For}$

Original Axiomatic System

1. ${\displaystyle U_{t_{1}}\neg p_{1}\equiv \neg U_{t_{1}}p_{1}}$
2. ${\displaystyle U_{t_{1}}(p_{1}\rightarrow p_{2})\rightarrow (U_{t_{1}}p_{1}\rightarrow U_{t_{1}}p_{2})}$
3. ${\displaystyle U_{t_{1}}((p_{1}\rightarrow p_{2})\rightarrow ((p_{2}\rightarrow p_{3})\rightarrow (p_{1}\rightarrow p_{3})))}$
4. ${\displaystyle U_{t_{1}}(p_{1}\rightarrow (\neg p_{1}\rightarrow p_{2}))}$
5. ${\displaystyle U_{t_{1}}((\neg p_{1}\rightarrow p_{1})\rightarrow p_{1})}$
6. ${\displaystyle \forall _{t_{1}}U_{t_{1}}p_{1}\rightarrow p_{1}}$
7. ${\displaystyle \forall _{t_{1}}\forall _{n_{1}}\exists _{t_{2}}\forall _{p_{1}}(U_{\delta (t_{1},n_{1})}p_{1}\equiv U_{t_{2}}p_{1})}$
8. ${\displaystyle \forall _{t_{1}}\forall _{n_{1}}\exists _{t_{2}}\forall _{p_{1}}(U_{\delta (t_{2},n_{1})}p_{1}\equiv U_{t_{1}}p_{1})}$
9. ${\displaystyle \forall _{t_{1}}\exists _{p_{1}}\forall _{t_{2}}(U_{t_{2}}p_{1}\equiv \forall _{p_{2}}(U_{t_{1}}p_{2}\equiv U_{t_{2}}p_{2}))}$

Prior's tense logic (TL)

The sentential tense logic introduced in Time and Modality has four (non-truth-functional) modal operators (in addition to all usual truth-functional operators in first-order propositional logic).^[11]

• P: "It was the case that..." (P stands for "past")
• F: "It will be the case that..." (F stands for "future")
• G: "It always will be the case that..."
• H: "It always was the case that..."

These can be combined if we let π be an infinite path:^[12]

• ${\displaystyle \pi \vDash FG\phi }$: "At a certain point, ${\displaystyle \phi }$ is true at all future states of the path"
• ${\displaystyle \pi \vDash GF\phi }$: "${\displaystyle \phi }$ is true at infinitely many states on the path"

From P and F one can define G and H, and vice versa:

${\displaystyle {\begin{aligned}F&\equiv \lnot G\lnot \\P&\equiv \lnot H\lnot \end{aligned}}}$

Syntax and semantics

A minimal syntax for TL is specified with the following BNF grammar:

${\displaystyle \phi ::=a\;|\;\bot \;|\;\lnot \phi \;|\;\phi \lor \phi \;|\;G\phi \;|\;H\phi }$

where a is some atomic formula.^[13]

Kripke models are used to evaluate the truth of sentences in TL. A pair (T, <) of a set T and a binary relation < on T (called "precedence") is called a frame. A model is given by triple (T, <, V) of a frame and a function V called a valuation that assigns to each pair (a, u) of an atomic formula and a time value some truth value. The notion "ϕ is true in a model U=(T, <, V) at time u" is abbreviated U⊨ϕ[u]. With this notation,^[14]

Given a class F of frames, a sentence ϕ of TL is

• valid with respect to F if for every model U=(T,<,V) with (T,<) in F and for every u in T, U⊨ϕ[u]
• satisfiable with respect to F if there is a model U=(T,<,V) with (T,<) in F such that for some u in T, U⊨ϕ[u]
• a consequence of a sentence ψ with respect to F if for every model U=(T,<,V) with (T,<) in F and for every u in T, if U⊨ψ[u], then U⊨ϕ[u]

Many sentences are only valid for a limited class of frames. It is common to restrict the class of frames to those with a relation < that is

Burgess outlines a logic that makes no assumptions on the relation <, but allows for meaningful deductions, based on the following axiom schema:[15]

1. A where A is a tautology of first-order logic
2. G(A→B)→(GA→GB)
3. H(A→B)→(HA→HB)
4. A→GPA
5. A→HFA

with the following rules of deduction:

1. given A→B and A, deduce B (modus ponens)
2. given a tautology A, infer GA
3. given a tautology A, infer HA

One can derive the following rules:

1. Becker's rule: given A→B, deduce TA→TB where T is a tense, any sequence made of G, H, F, and P.
2. Mirroring: given a theorem A, deduce its mirror statement A^§, which is obtained by replacing G by H (and so F by P) and vice versa.
3. Duality: given a theorem A, deduce its dual statement A*, which is obtained by interchanging ∧ with ∨, G with F, and H with P.

Translation to predicate logic

Burgess gives a Meredith translation from statements in TL into statements in first-order logic with one free variable x₀ (representing the present moment). This translation M is defined recursively as follows:^[16]

${\displaystyle {\begin{aligned}&M(a)&&=a^{*}x_{0}\\&M(\lnot \phi )&&=\lnot M(\phi )\\&M(\phi \land \psi )&&=M(\phi )\land M(\psi )\\&M({\mathsf {G}}\phi )&&=\forall x_{1}(x_{0}<x_{1}\rightarrow M(A^{+}))\\&M({\mathsf {H}}\phi )&&=\forall x_{1}(x_{1}<x_{0}\rightarrow M(A^{+}))\end{aligned}}}$

where ${\displaystyle A^{+}}$ is the sentence ${\displaystyle A}$ with all variable indices incremented by 1 and ${\displaystyle a^{*}}$ is a one-place predicate defined by ${\displaystyle x\mapsto V(a,x)}$.

Temporal operators

Temporal logic has two kinds of operators:

Logical operators are usual truth-functional operators (${\displaystyle \neg ,\lor ,\land ,\rightarrow }$). The modal operators used in linear temporal logic and computation tree logic are defined as follows.

Textual	Symbolic	Definition	Explanation	Diagram
Binary operators
φ U ψ	${\displaystyle \phi ~{\mathcal {U}}~\psi }$	${\displaystyle (B\,{\mathcal {U}}\,C)(\phi )=\ (\exists i:C(\phi _{i})\land (\forall j<i:B(\phi _{j})))}$	Until: ψ holds at the current or a future position, and φ has to hold until that position. At that position φ does not have to hold any more.
φ R ψ	${\displaystyle \phi ~{\mathcal {R}}~\psi }$	${\displaystyle (B\,{\mathcal {R}}\,C)(\phi )=\ (\forall i:C(\phi _{i})\lor (\exists j<i:B(\phi _{j})))}$	Release: φ releases ψ if ψ is true up until and including the first position in which φ is true (or forever if such a position does not exist).
Unary operators
N φ	${\displaystyle \bigcirc \phi }$	${\displaystyle {\mathcal {N}}B(\phi _{i})=B(\phi _{i+1})}$	Next: φ has to hold at the next state. (X is used synonymously.)
F φ	${\displaystyle \Diamond \phi }$	${\displaystyle {\mathcal {F}}B(\phi )=(true\,{\mathcal {U}}\,B)(\phi )}$	Future: φ eventually has to hold (somewhere on the subsequent path).
G φ	${\displaystyle \Box \phi }$	${\displaystyle {\mathcal {G}}B(\phi )=\neg {\mathcal {F}}\neg B(\phi )}$	Globally: φ has to hold on the entire subsequent path.
A φ	${\displaystyle \forall \phi }$	${\displaystyle ({\mathcal {A}}B)(\psi )=\ (\forall \phi :\phi _{0}=\psi \to B(\phi ))}$	All: φ has to hold on all paths starting from the current state.
E φ	${\displaystyle \exists \phi }$	${\displaystyle ({\mathcal {E}}B)(\psi )=\ (\exists \phi :\phi _{0}=\psi \land B(\phi ))}$	Exists: there exists at least one path starting from the current state where φ holds.

Alternate symbols:

• operator R is sometimes denoted by V
• The operator W is the weak until operator: ${\displaystyle f\mathbf {W} g}$ is equivalent to ${\displaystyle f\mathbf {U} g\lor \mathbf {G} f}$

Unary operators are well-formed formulas whenever B(φ) is well-formed. Binary operators are well-formed formulas whenever B(φ) and C(φ) are well-formed.

In some logics, some operators cannot be expressed. For example, N operator cannot be expressed in temporal logic of actions.

Temporal logics

Temporal logics include:

• Some systems of positional logic
• Linear temporal logic (LTL) temporal logic without branching timelines
• Computation tree logic (CTL) temporal logic with branching timelines
• Interval temporal logic (ITL)
• Temporal logic of actions (TLA)
• Signal temporal logic (STL)^[18]
• Timestamp temporal logic (TTL)^[19]
• Property specification language (PSL)
• CTL*, which generalizes LTL and CTL
• Hennessy–Milner logic (HML)
• Modal μ-calculus, which includes as a subset HML and CTL*
• Metric temporal logic (MTL)^[20]
• Metric interval temporal logic (MITL)^[18]
• Timed propositional temporal logic (TPTL)
• Truncated Linear Temporal Logic (TLTL)^[21]
• Hyper temporal logic (HyperLTL) ^[22]

A variation, closely related to temporal or chronological or tense logics, are modal logics based upon "topology", "place", or "spatial position".^[23][24]

See also

• HPO formalism
• Kripke structure
• Automata theory
• Chomsky grammar
• State transition system
• Duration calculus (DC)
• Hybrid logic
• Temporal logic in finite-state verification
• Reo Coordination Language
• Modal logic
• Research Materials: Max Planck Society Archive

Notes

References

• Mordechai Ben-Ari, Zohar Manna, Amir Pnueli: The Temporal Logic of Branching Time. POPL 1981: 164–176
• Amir Pnueli: The Temporal Logic of Programs FOCS 1977: 46–57
• Venema, Yde, 2001, "Temporal Logic," in Goble, Lou, ed., The Blackwell Guide to Philosophical Logic. Blackwell.
• E. A. Emerson and Chin-Laung Lei, "Modalities for model checking: branching time logic strikes back", in Science of Computer Programming 8, pp. 275–306, 1987.
• E. A. Emerson, "Temporal and modal logic", Handbook of Theoretical Computer Science, Chapter 16, the MIT Press, 1990
• A Practical Introduction to PSL, Cindy Eisner, Dana Fisman
• ISBN 978-3-540-69849-4. preprint
  . Historical perspective on how seemingly disparate ideas came together in computer science and engineering. (The mention of Church in the title of this paper is a reference to a little-known 1957 paper, in which Church proposed a way to perform hardware verification.)

Further reading

• Peter Øhrstrøm; Per F. V. Hasle (1995). Temporal logic: from ancient ideas to artificial intelligence. Springer.
  ISBN 978-0-7923-3586-3
  .

External links

Wikimedia Commons has media related to Temporal logic.

• Stanford Encyclopedia of Philosophy: "Temporal Logic"—by Anthony Galton.
• Temporal Logic by Yde Venema, formal description of syntax and semantics, questions of axiomatization. Treating also Kamp's dyadic temporal operators (since, until)
• Notes on games in temporal logic by Ian Hodkinson, including a formal description of first-order temporal logic
• CADP – provides generic model checkers for various temporal logic
• PAT is a powerful free model checker, LTL checker, simulator and refinement checker for CSP and its extensions (with shared variable, arrays, wide range of fairness).