Temporal logic

Summary

In logic, temporal logic is any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of time (for example, "I am always hungry", "I will eventually be hungry", or "I will be hungry until I eat something"). It is sometimes also used to refer to tense logic, a modal logic-based system of temporal logic introduced by Arthur Prior in the late 1950s, with important contributions by Hans Kamp. It has been further developed by computer scientists, notably Amir Pnueli, and logicians.

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 logics, however, can reason about multiple timelines. This presupposes an environment that may act unpredictably. To continue the example, in a branching 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 Aristotle's logic is almost entirely concerned with the theory of the categorical syllogism, there are passages in his work that are now seen as anticipations of temporal logic, and may imply an early, partially developed form of first-order temporal modal binary logic. Aristotle was particularly concerned with the problem of future contingents, where he could not accept that the principle of bivalence applies to statements about future events, i.e. that we can presently decide if a statement about a future event is true or false, such as "there will be a sea battle tomorrow".[1]

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.

Suprisingly for Peirce, the first system of temporal logic was constructed, as far as we know, in the first half of 20th century. Although Arthur Prior is widely known as a founder of temporal logic, the first formalization of such logic was provided in 1947 by Polish logician, Jerzy Łoś.[3] In his work Podstawy Analizy Metodologicznej Kanonów Milla (The Foundations of a Methodological Analysis of Mill’s Methods) he presented a formalization of Mill's canons. In Łoś.' approach emphasis was placed on the time factor. Thus, to reach his goal, he had to create a logic which could provide means for formalization of temporal functions. The logic could be seen as a byproduct of Łoś' main aim,[4] albeit it was the first positional logic which, as a framework was used later for Łoś' inventions in epistemic logic. The logic itself has syntax very different than Prior's tense logic, which uses modal operators. Language of Łoś' logic rather uses a specific for positional logic, realization operator that binds the expression with the specific context in which its truth-value is considered. In Łoś' work this considered context was only temporal, thus expressions were binded with specific moments or intervals of time.

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 firstly presented at the conference in Wellington in 1954.[4] The system Prior presented, was similar syntactically to Łoś' logic, although not until 1955 he explicitly referred to Łoś' work, in last section of Appendix 1 in Prior’s Formal Logic.[4]

Prior gave lectures on the topic at the University of Oxford in 1955–6, and in 1957 published a book, Time and Modality, in which he introduced a propositional modal logic with two temporal connectives (modal operators), F and P, corresponding to "sometime in the future" and "sometime in the past". In this early work, Prior considered time to be linear. In 1958 however, he received a letter from Saul Kripke, who pointed out that this assumption is perhaps unwarranted. In a development that foreshadowed a similar one in computer science, Prior took this under advisement, and developed two theories of branching time, which he called "Ockhamist" and "Peircean".[2][clarification needed] Between 1958 and 1965 Prior also corresponded with Charles Leonard Hamblin, and a number of early developments in the field can be traced to this correspondence, for example Hamblin implications. Prior published his most mature work on the topic, the book Past, Present, and Future in 1967. He died two years later.[5]

Along with tense logic, Prior constructed few systems of positional logic, which inherited main ideas from Łoś.[6] Work in positional temporal logics was continued by Nicholas Rescher in 60's and 70's. In such works as Note on Chronological Logic (1966), On the Logic of Chronological Propositions (1968), Topological Logic (1968), Temporal Logic (1971) he researched connections between Łoś' and Prior's systems. Moreover he proved that Prior's tense operators could be defined using realization operator in specific positional logics.[6] Rescher in his work also created more general systems of positional logics. Althought the first ones were constructed for purely temporal uses, he proposed a term of topological 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, 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 logics in general, as has sometimes been argued. Rather, Emerson and Lei show that any linear logic can be extended to a branching logic that can be decided with the same complexity.

Łoś' positional logic

Łoś’s logic was published as his master’s thesis was entitled in 1947 in Polish.[10] His philosophical and formal concepts could be seen as continuation of Lviv-Warsaw School of Logic as his supervisor was Jerzy Słupecki, disciple of Jan Łukasiewicz. The paper was not translated into English until 1977, although Henryk Hiż presented in 1951 a brief, but informative review in the Journal of Symbolic Logic. His review contained core concepts of his work and was enough to popularize Łoś’s results among logical community. The main aim of this work was to present Mill's canons in the framework of formal logic. To achieve this goal the author researched importance of temporal functions in the structure of Miil's concept. Having that he provided his axiomatic system of logic that would fit as a framework for Mill's canons along with their temporal aspects.

Syntax

Language of the logic firstly 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 p1,p2,p3,...
  • variables denoting time moments t1,t2,t3,...
  • variables denoting time intervals n1,n2,n3,...

Set of terms (denoted by S) is constructed as following:

  • variables denoting time moments or intervals are terms
  • if and is a time interval variable, then

Set of formulas (denoted by For) is constructed as following:[10]

  • all first order logic formulas are valid
  • if and is a propositional variable, then
  • if , then
  • if and , then
  • if and and υ is a propositional, moment or interval variable, then

Original Axiomatic System

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]

  • : "At a certain point, is true at all future states of the path"
  • : " is true at infinitely many states on the path"

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

Syntax and semantics

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

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]

Statement ... is true just when
Ua[u] V(a,u)=true
U⊨¬ϕ[u] not Uϕ[u]
U⊨(ϕψ)[u] Uϕ[u] and Uψ[u]
U⊨(ϕψ)[u] Uϕ[u] or Uψ[u]
U⊨(ϕψ)[u] Uψ[u] if Uϕ[u]
U⊨Gϕ[u] Uϕ[v] for all v with u<v
U⊨Hϕ[u] Uϕ[v] for all v with v<u

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 transitive, antisymmetric, reflexive, trichotomic, irreflexive, total, dense, or some combination of these.

A minimal axiomatic logic

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(AB)→(GA→GB)
  3. H(AB)→(HA→HB)
  4. A→GPA
  5. A→HFA

with the following rules of deduction:

  1. given AB 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 AB, 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 x0 (representing the present moment). This translation M is defined recursively as follows:[16]

where is the sentence with all variable indices incremented by 1 and is a one-place predicate defined by .

Temporal operators

Temporal logic has two kinds of operators: logical operators and modal operators [1]. Logical operators are usual truth-functional operators (). The modal operators used in linear temporal logic and computation tree logic are defined as follows.

Textual Symbolic Definition Explanation Diagram
Binary operators
φ U ψ 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 ψ 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 φ Next: φ has to hold at the next state. (X is used synonymously.)
F φ Future: φ eventually has to hold (somewhere on the subsequent path).
G φ Globally: φ has to hold on the entire subsequent path.
A φ All: φ has to hold on all paths starting from the current state.
E φ 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: is equivalent to

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:

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

See also

Notes

  1. ^ Vardi 2008, p. 153
  2. ^ a b c Vardi 2008, p. 154
  3. ^ a b Łoś, Jerzy (1920-1998); Łoś, Jerzy (1920-1998) (1947). Podstawy analizy metodologicznej kanonów Milla. nakł. Uniwersytetu Marii Curie-Skłodowskiej.
  4. ^ a b c d Øhrstrøm, Peter (2019). "The Significance of the Contributions of A.N.Prior and Jerzy Łoś in the Early History of Modern Temporal Logic". Logic and Philosophy of Time: Further Themes from Prior, Volume 2.
  5. ^ Peter Øhrstrøm; Per F. V. Hasle (1995). Temporal logic: from ancient ideas to artificial intelligence. Springer. ISBN 978-0-7923-3586-3. pp. 176–178, 210
  6. ^ a b Rescher, Nicholas; Garson, James (January 1969). "Topological Logic". The Journal of Symbolic Logic. 33 (4): 537–548. doi:10.2307/2271360. ISSN 0022-4812.
  7. ^ "Temporal Logic (Stanford Encyclopedia of Philosophy)". Plato.stanford.edu. Retrieved 2014-07-30.
  8. ^ Walter Carnielli; Claudio Pizzi (2008). Modalities and Multimodalities. Springer. p. 181. ISBN 978-1-4020-8589-5.
  9. ^ Sergio Tessaris; Enrico Franconi; Thomas Eiter (2009). Reasoning Web. Semantic Technologies for Information Systems: 5th International Summer School 2009, Brixen-Bressanone, Italy, August 30 – September 4, 2009, Tutorial Lectures. Springer. p. 112. ISBN 978-3-642-03753-5.
  10. ^ a b Tkaczyk, Marcin; Jarmużek, Tomasz (2019). "Jerzy Łoś Positional Calculus and the Origin of Temporal Logic". Logic and Logical Philosophy. 28 (2): 259–276. doi:10.12775/LLP.2018.013. ISSN 2300-9802.
  11. ^ Prior, Arthur Norman (2003). Time and modality: the John Locke lectures for 1955–6, delivered at the University of Oxford. Oxford: The Clarendon Press. ISBN 9780198241584. OCLC 905630146.
  12. ^ Lawford, M. (2004). "An Introduction to Temporal Logics" (PDF). Department of Computer Science McMaster University.
  13. ^ Goranko, Valentin; Galton, Antony (2015). Zalta, Edward N. (ed.). The Stanford Encyclopedia of Philosophy (Winter 2015 ed.). Metaphysics Research Lab, Stanford University.
  14. ^ Müller, Thomas (2011). "Tense or temporal logic" (PDF). In Horsten, Leon (ed.). The continuum companion to philosophical logic. A&C Black. p. 329.
  15. ^ Burgess, John P. (2009). Philosophical logic. Princeton, New Jersey: Princeton University Press. p. 21. ISBN 9781400830497. OCLC 777375659.
  16. ^ Burgess, John P. (2009). Philosophical logic. Princeton, New Jersey: Princeton University Press. p. 17. ISBN 9781400830497. OCLC 777375659.
  17. ^ a b Maler, O.; Nickovic, D. (2004). "Monitoring temporal properties of continuous signals". doi:10.1007/978-3-540-30206-3_12.
  18. ^ Mehrabian, Mohammadreza; Khayatian, Mohammad; Shrivastava, Aviral; Eidson, John C.; Derler, Patricia; Andrade, Hugo A.; Li-Baboud, Ya-Shian; Griffor, Edward; Weiss, Marc; Stanton, Kevin (2017). "Timestamp Temporal Logic (TTL) for Testing the Timing of Cyber-Physical Systems". ACM Transactions on Embedded Computing Systems. 16 (5s): 1–20. doi:10.1145/3126510. S2CID 3570088.
  19. ^ Koymans, R. (1990). "Specifying real-time properties with metric temporal logic", Real-Time Systems 2(4): 255–299. doi:10.1007/BF01995674.
  20. ^ Li, Xiao, Cristian-Ioan Vasile, and Calin Belta. "Reinforcement learning with temporal logic rewards." doi:10.1109/IROS.2017.8206234
  21. ^ Clarkson, Michael R.; Finkbeiner, Bernd; Koleini, Masoud; Micinski, Kristopher K.; Rabe, Markus N.; Sánchez, César (2014). "Temporal Logics for Hyperproperties". Principles of Security and Trust. Lecture Notes in Computer Science. Vol. 8414. pp. 265–284. doi:10.1007/978-3-642-54792-8_15. ISBN 978-3-642-54791-1. S2CID 8938993.
  22. ^ Rescher, Nicholas (1968). "Topological Logic". Topics in Philosophical Logic. pp. 229–249. doi:10.1007/978-94-017-3546-9_13. ISBN 978-90-481-8331-9.
  23. ^ von Wright, Georg Henrik (1979). "A Modal Logic of Place". The Philosophy of Nicholas Rescher. pp. 65–73. doi:10.1007/978-94-009-9407-2_9. ISBN 978-94-009-9409-6.

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 C. 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
  • Vardi, Moshe Y. (2008). "From Church and Prior to PSL". In Orna Grumberg; Helmut Veith (eds.). 25 years of model checking: history, achievements, perspectives. Springer. 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

  • 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).