View source for Philosophy:Temporal logic

In [[Logic|logic]], '''temporal logic''' is any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of [[Time|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|modal logic]]-based system of temporal logic introduced by [[Biography:Arthur Prior|Arthur Prior]] in the late 1950s, with important contributions by Hans Kamp. It has been further developed by computer scientists, notably [[Biography:Amir Pnueli|Amir Pnueli]], and logicians.
Temporal logic has found an important application in [[Formal verification|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 [[Biography:Aristotle|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 logic|first-order]] temporal modal bivalent logic. Aristotle was particularly concerned with the [[Problem of future contingents|problem of future contingents]], where he could not accept that the [[Principle of bivalence|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".<ref>Vardi 2008, p. 153</ref>

There was little development for millennia, [[Biography:Charles Sanders Peirce|Charles Sanders Peirce]] noted in the 19th century:<ref name=v154>Vardi 2008, p. 154</ref>
{{cquote|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 [[Biography:Charles Sanders Peirce|Peirce]], the first system of temporal logic was constructed, as far as we know, in the first half of 20th century. Although [[Biography:Arthur Prior|Arthur Prior]] is widely known as a founder of temporal logic, the first formalization of such logic was provided in 1947 by Polish logician, [[Biography:Jerzy Łoś|Jerzy Łoś]].<ref name=":0">{{Cite journal|last1=Łoś|first1=Jerzy (1920-1998)|url=http://dlibra.umcs.lublin.pl/dlibra/doccontent?id=4085|title=Podstawy analizy metodologicznej kanonów Milla|last2=Łoś|first2=Jerzy (1920-1998)|journal=Zasoby Biblioteki Głównej Umcs |date=1947|publisher=nakł. Uniwersytetu Marii Curie-Skłodowskiej}}</ref> 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 [[Biography:Jerzy Łoś|Łoś]]' approach, emphasis was placed on the time factor. Thus, to reach his goal, he had to create a logic that could provide means for formalization of temporal functions. The logic could be seen as a byproduct of [[Biography:Jerzy Łoś|Łoś]]' main aim,<ref name=":1">{{Cite journal|last=Øhrstrøm|first=Peter|date=2019|title=The Significance of the Contributions of A.N.Prior and Jerzy Łoś in the Early History of Modern Temporal Logic|url=https://vbn.aau.dk/en/publications/the-significance-of-the-contributions-of-anprior-and-jerzy-%C5%82o%C5%9B-in|journal=Logic and Philosophy of Time: Further Themes from Prior, Volume 2|series=Logic and Philosophy of Time |isbn=9788772102658 |language=English}}</ref> albeit it was the first positional logic that, as a framework, was used later for [[Biography:Jerzy Łoś|Łoś]]' inventions in epistemic logic. The logic itself has syntax very different than Prior's tense logic, which uses modal operators. The language of [[Biography:Jerzy Łoś|Łoś]]' logic rather uses a realization operator, specific to positional logic, which binds the expression with the specific context in which its truth-value is considered. In [[Biography:Jerzy Łoś|Łoś]]' work this considered context was only temporal, thus expressions were bound with specific moments or intervals of time.

In the following years, research of temporal logic by [[Biography:Arthur Prior|Arthur Prior]] began.<ref name=":1" /> He was concerned with the philosophical implications of [[Philosophy:Free will|free will]] and [[Philosophy:Predestination|predestination]]. According to his wife, he first considered formalizing temporal logic in 1953. Results of his research were first presented at the conference in [[Place:Wellington|Wellington]] in 1954.<ref name=":1" /> The system Prior presented, was similar syntactically to [[Biography:Jerzy Łoś|Łoś]]' logic, although not until 1955 did he explicitly refer to [[Biography:Jerzy Łoś|Łoś]]' work, in the last section of Appendix 1 in Prior’s ''Formal Logic''.<ref name=":1" />

[[Biography:Arthur Prior|Prior]] gave lectures on the topic at the [[Organization:University of Oxford|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 operator|modal operator]]s), 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 [[Biography:Saul Kripke|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".<ref name="v154" />{{Clarify|date=April 2011}} Between 1958 and 1965 Prior also corresponded with [[Biography:Charles Leonard Hamblin|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.<ref>{{cite book|author1=Peter Øhrstrøm|author2=Per F. V. Hasle|title=Temporal logic: from ancient ideas to artificial intelligence|year=1995|publisher=Springer|isbn=978-0-7923-3586-3}} pp.&nbsp;176–178, 210</ref>

Along with '''tense logic,''' [[Biography:Arthur Prior|Prior]] constructed a few systems of positional logic, which inherited their main ideas from [[Biography:Jerzy Łoś|Łoś]].<ref name=":2">{{Cite journal|last1=Rescher|first1=Nicholas|last2=Garson|first2=James|date=January 1969|title=Topological Logic|url=https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/topological-logic/5ADE3A9CA7CE00FBD8D69E4DDA8B1BC8|journal=The Journal of Symbolic Logic|language=en|volume=33|issue=4|pages=537–548|doi=10.2307/2271360|jstor=2271360 |s2cid=2110963 |issn=0022-4812}}</ref> Work in positional temporal logics was continued by [[Biography:Nicholas Rescher|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 [[Biography:Jerzy Łoś|Łoś]]' and [[Biography:Arthur Prior|Prior]]'s systems. Moreover, he proved that [[Biography:Arthur Prior|Prior]]'s tense operators could be defined using a realization operator in specific positional logics.<ref name=":2" /> [[Biography:Nicholas Rescher|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,<ref>{{cite web|url=https://plato.stanford.edu/entries/logic-temporal/#AddSinUnt |title=Temporal Logic (Stanford Encyclopedia of Philosophy) |publisher=Plato.stanford.edu |access-date=2014-07-30}}</ref> which also contains an important result relating temporal logic to [[First-order logic|first-order logic]]—a result now known as Kamp's theorem.<ref name="CarnielliPizzi2008">{{cite book|author1=Walter Carnielli|author2=Claudio Pizzi|title=Modalities and Multimodalities|url=https://books.google.com/books?id=XpAFM04G6BAC&pg=PA181|year=2008|publisher=Springer|isbn=978-1-4020-8589-5|page=181}}</ref><ref name=v154>Vardi 2008, p. 154</ref><ref name="TessarisFranconi2009">{{cite book|author1=Sergio Tessaris|author2=Enrico Franconi|author3=Thomas Eiter|title=Reasoning Web. Semantic Technologies for Information Systems: 5th International Summer School 2009, Brixen-Bressanone, Italy, August 30 – September 4, 2009, Tutorial Lectures|url=https://books.google.com/books?id=JdyeU7zs4-AC&pg=PA112|year=2009|publisher=Springer|isbn=978-3-642-03753-5|page=112}}</ref>

Two early contenders in formal verifications were linear temporal logic, a linear-time logic by [[Biography:Amir Pnueli|Amir Pnueli]], and [[Computation tree logic|computation tree logic]] (CTL), a branching-time logic by [[Biography:Mordechai Ben-Ari|Mordechai Ben-Ari]], Zohar Manna and Amir Pnueli. An almost equivalent formalism to CTL was suggested around the same time by [[Biography:Edmund M. Clarke|E. M. Clarke]] and [[Biography:E. Allen Emerson|E. A. Emerson]]. The fact that the second logic can be [[Decision problem|decided]] [[Computational complexity|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ś' positional logic ==
[[Biography:Jerzy Łoś|Łoś]]’ logic was published as his 1947 master’s thesis ''Podstawy Analizy Metodologicznej Kanonów Milla'' (''The Foundations of a Methodological Analysis of Mill’s Methods'').<ref name="Tkaczyk 2019 259–276">{{Cite journal|last1=Tkaczyk|first1=Marcin|last2=Jarmużek|first2=Tomasz|date=2019|title=Jerzy Łoś Positional Calculus and the Origin of Temporal Logic|url=https://apcz.umk.pl/LLP/article/view/LLP.2018.013|journal=Logic and Logical Philosophy|language=en|volume=28|issue=2|pages=259–276|doi=10.12775/LLP.2018.013|issn=2300-9802|doi-access=free}}</ref> His philosophical and formal concepts could be seen as continuations of those of the Lviv–Warsaw School of Logic, as his supervisor was Jerzy Słupecki, disciple of [[Biography:Jan Łukasiewicz|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]]''. This review contained core concepts of [[Biography:Jerzy Łoś|Łoś]]’ work and was enough to popularize his results among the 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 the importance of temporal functions in the structure of Mill'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 ===
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:<ref name=":0" />

* first-order logic operators  ‘¬’, ‘∧’, ‘∨’, ‘→’, ‘≡’, ‘∀’ and ‘∃’
* realization operator U
* functional symbol δ
* propositional variables p<sub>1</sub>,p<sub>2</sub>,p<sub>3</sub>,...
* variables denoting time moments t<sub>1</sub>,t<sub>2</sub>,t<sub>3</sub>,...
* variables denoting time intervals n<sub>1</sub>,n<sub>2</sub>,n<sub>3</sub>,...

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

* variables denoting time moments or intervals are terms
* if <math>\tau \in S</math> and <math>\epsilon</math> is a time interval variable, then <math>\delta(\tau, \epsilon) \in S</math>

The set of formulas (denoted by For) is constructed as follows:<ref name="Tkaczyk 2019 259–276"/>

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

=== Original Axiomatic System ===

# <math>U_{t_{1}}\neg p_{1} \equiv \neg U_{t_{1}} p_{1}</math>
# <math>U_{t_{1}}(p_{1} \rightarrow p_{2}) \rightarrow (U_{t_{1}} p_{1} \rightarrow U_{t_{1}} p_{2})</math>
# <math>U_{t_{1}}((p_{1} \rightarrow p_{2}) \rightarrow ((p_{2} \rightarrow p_{3}) \rightarrow (p_{1} \rightarrow p_{3})))</math>
# <math>U_{t_{1}}(p_{1} \rightarrow (\neg p_{1} \rightarrow p_{2}))</math>
# <math>U_{t_{1}}((\neg p_{1} \rightarrow p_{1}) \rightarrow p_{1})</math>
# <math>\forall_{t_{1}}U_{t_{1}}p_{1} \rightarrow p_{1}</math>
# <math>\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})</math>
# <math>\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})</math>
# <math>\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}))</math>

== Prior's tense logic (TL) ==
The sentential tense logic introduced in ''Time and Modality'' has four (non-[[Truth function|truth-functional]]) [[Modal operator|modal operator]]s (in addition to all usual truth-functional operators in [[Propositional calculus|first-order propositional logic]]).<ref>{{Cite book|title=Time and modality: the John Locke lectures for 1955–6, delivered at the University of Oxford|last=Prior|first=Arthur Norman|publisher=The Clarendon Press|year=2003|isbn=9780198241584|location=Oxford|oclc=905630146|}}</ref>
* ''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:<ref>{{Cite web|url=https://www.cas.mcmaster.ca/~lawford/2F03/Notes/model.pdf|title=An Introduction to Temporal Logics|last=Lawford|first=M.|date=2004|website=Department of Computer Science McMaster University}}</ref>

* <math>\pi \vDash F G \phi</math>: "At a certain point, <math>\phi</math> is true at all future states of the path"
* <math>\pi \vDash G F \phi</math>: "<math>\phi</math> is true at infinitely many states on the path"

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

<math>\begin{align}
  F &\equiv \lnot G\lnot \\
  P &\equiv \lnot H\lnot
\end{align}</math>

=== Syntax and semantics ===

A minimal syntax for TL is specified with the following [[Backus–Naur form|BNF grammar]]:

<math>\phi ::= a \;|\; \bot \;|\; \lnot\phi \;|\; \phi\lor\phi \;|\; G\phi \;|\; H\phi</math>

where ''a'' is some [[Physics:Atomic formula|atomic formula]].<ref>{{Cite book|url=https://plato.stanford.edu/archives/win2015/entries/logic-temporal/|title=The Stanford Encyclopedia of Philosophy|last1=Goranko|first1=Valentin|last2=Galton|first2=Antony|date=2015|publisher=Metaphysics Research Lab, Stanford University|editor-last=Zalta|editor-first=Edward N.|edition=Winter 2015}}</ref>

[[Kripke semantics|Kripke models]] are used to evaluate the truth of [[Philosophy:Sentence (mathematical logic)|sentences]] in TL. A pair ({{Var|T}}, <) of a set {{Var|T}} and a [[Binary relation|binary relation]] < on {{Var|T}} (called "precedence") is called a '''frame'''. A '''model''' is given by triple ({{Var|T}}, <, {{Var|V}}) of a frame and a function {{Var|V}} called a '''valuation''' that assigns to each pair ({{Var|a}}, {{Var|u}}) of an atomic formula and a time value some truth value. The notion "{{Var|ϕ}} is true in a model {{Var|U}}=({{Var|T}}, <, {{Var|V}}) at time {{Var|u}}" is abbreviated {{var|U}}[[Double turnstile|⊨]]{{var|ϕ}}[{{var|u}}]. With this notation,<ref>{{Cite book|title=The continuum companion to philosophical logic|last=Müller|first=Thomas|publisher=A&C Black|year=2011|editor-last=Horsten|editor-first=Leon|pages=329|chapter=Tense or temporal logic|chapter-url=http://kops.uni-konstanz.de/bitstream/handle/123456789/27232/Mueller_272322.pdf?sequence=2}}</ref>

{| class="wikitable"
|+
! Statement 
! ... is true just when
|-
| {{var|U}}⊨{{var|a}}[{{var|u}}]
| {{var|V}}({{var|a}},{{var|u}})=true
|-
| {{var|U}}⊨¬{{var|ϕ}}[{{var|u}}]
| not {{var|U}}⊨{{var|ϕ}}[{{var|u}}]
|-
| {{var|U}}⊨({{var|ϕ}}∧{{var|ψ}})[{{var|u}}]
| {{var|U}}⊨{{var|ϕ}}[{{var|u}}] and {{var|U}}⊨{{var|ψ}}[{{var|u}}]
|-
| {{var|U}}⊨({{var|ϕ}}∨{{var|ψ}})[{{var|u}}]
| {{var|U}}⊨{{var|ϕ}}[{{var|u}}] or {{var|U}}⊨{{var|ψ}}[{{var|u}}]
|-
| {{var|U}}⊨({{var|ϕ}}→{{var|ψ}})[{{var|u}}]
| {{var|U}}⊨{{var|ψ}}[{{var|u}}] if {{var|U}}⊨{{var|ϕ}}[{{var|u}}]
|-
| {{var|U}}⊨G{{var|ϕ}}[{{var|u}}]
| {{var|U}}⊨{{var|ϕ}}[{{var|v}}] for all {{var|v}} with {{var|u}}<{{var|v}}
|-
| {{var|U}}⊨H{{var|ϕ}}[{{var|u}}]
| {{var|U}}⊨{{var|ϕ}}[{{var|v}}] for all {{var|v}} with {{var|v}}<{{var|u}}
|}

Given a class {{var|F}} of frames, a sentence {{var|ϕ}} of TL is
* '''valid''' with respect to {{var|F}} if for every model {{var|U}}=({{var|T}},<,{{var|V}}) with ({{var|T}},<) in {{var|F}} and for every {{var|u}} in {{var|T}}, {{var|U}}⊨{{var|ϕ}}[{{var|u}}]
* '''satisfiable''' with respect to {{var|F}} if there is a model {{var|U}}=({{var|T}},<,{{var|V}}) with ({{var|T}},<) in {{var|F}} such that for some {{var|u}} in {{var|T}}, {{var|U}}⊨{{var|ϕ}}[{{var|u}}]
* a '''consequence''' of a sentence {{var|ψ}} with respect to {{var|F}} if for every model {{var|U}}=({{var|T}},<,{{var|V}}) with ({{var|T}},<) in {{var|F}} and for every {{var|u}} in {{var|T}}, if {{var|U}}⊨{{var|ψ}}[{{var|u}}], then {{var|U}}⊨{{var|ϕ}}[{{var|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 reduction|transitive]], [[Antisymmetric relation|antisymmetric]], [[Reflexive relation|reflexive]], [[Trichotomy (mathematics)|trichotomic]], irreflexive, [[Total order|total]], [[Dense order|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:<ref>{{Cite book|title=Philosophical logic|last=Burgess|first=John P.|publisher=Princeton University Press|year=2009|isbn=9781400830497|location=Princeton, New Jersey|page=21|oclc=777375659|}}</ref>
# {{var|A}} where {{var|A}} is a [[Philosophy:Tautology (logic)|tautology]] of [[First-order logic|first-order logic]]
# G({{var|A}}→{{var|B}})→(G{{var|A}}→G{{var|B}})
# H({{var|A}}→{{var|B}})→(H{{var|A}}→H{{var|B}})
# {{var|A}}→GP{{var|A}}
# {{var|A}}→HF{{var|A}}
with the following rules of deduction:
# given {{var|A}}→{{var|B}} and {{var|A}}, deduce {{var|B}} ([[Modus ponens|modus ponens]])
# given ''a tautology'' {{var|A}}, infer G{{var|A}}
# given ''a tautology'' {{var|A}}, infer H{{var|A}}

One can derive the following rules:
# '''Becker's rule''': given {{var|A}}→{{var|B}}, deduce T{{var|A}}→T{{var|B}} where T is a '''tense''', any sequence made of G, H, F, and P.
# '''Mirroring''': given a theorem {{var|A}}, deduce its '''mirror statement''' {{var|A}}<sup>§</sup>, which is obtained by replacing G by H (and so F by P) and vice versa.
# '''Duality''': given a theorem {{var|A}}, deduce its '''dual statement''' {{var|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|first-order logic]] with one free variable {{Var|x}}<sub>0</sub> (representing the present moment). This translation {{Var|M}} is defined recursively as follows:<ref>{{Cite book|title=Philosophical logic|last=Burgess|first=John P.|publisher=Princeton University Press|year=2009|isbn=9781400830497|location=Princeton, New Jersey|page=17|oclc=777375659|}}</ref>

<math>\begin{align}
  & 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{align}</math>

where <math>A^+</math> is the sentence <math>A</math> with all variable indices incremented by 1 and <math>a^*</math> is a one-place predicate defined by <math>x \mapsto V(a, x)</math>.

==Temporal operators==
Temporal logic has two kinds of operators: logical operators and modal operators.<ref>{{cite web |url=http://plato.stanford.edu/entries/logic-temporal/ |title=Temporal Logic |date=February 7, 2020 |website=Stanford Encyclopedia of Philosophy |access-date=April 19, 2022}}</ref> Logical operators are usual truth-functional operators (<math>\neg,\lor,\land,\rightarrow</math>). The modal operators used in linear temporal logic and computation tree logic are defined as follows.

{| class="wikitable"
|-
! Textual
! Symbolic
! Definition
! Explanation
! Diagram
|-
! colspan="4" | Binary operators
|-
|{{mvar|&phi;}} '''U''' {{mvar|&psi;}}
|<math>\phi ~\mathcal{U}~ \psi</math>
|<math>(B\,\mathcal{U}\,C)(\phi)= \ (\exists i:C(\phi_i)\land(\forall j<i:B(\phi_j)))</math>
|'''U'''ntil: {{mvar|&psi;}} holds at the current or a future position, and {{mvar|&phi;}} has to hold until that position. At that position {{mvar|&phi;}} does not have to hold any more.
|<timeline>
ImageSize = width:240 height:94
PlotArea = left:30 bottom:30 top:0 right:20
DateFormat = x.y
Period = from:0 till:6
TimeAxis = orientation:horizontal
AlignBars = justify
ScaleMajor = gridcolor:black increment:1 start:0
ScaleMinor = gridcolor:black increment:1 start:0

PlotData=
 bar:p color:red width:10 align:left fontsize:S
 from:1 till:3

 bar:q color:red width:10 align:left fontsize:S
 from:3 till:5

 bar:pUq color:red width:10 align:left fontsize:S
 from:1 till:5
</timeline>
|-
|{{mvar|&phi;}} '''R''' {{mvar|&psi;}}
|<math>\phi ~\mathcal{R}~ \psi</math>
|<math>(B\,\mathcal{R}\,C)(\phi)= \ (\forall i:C(\phi_i)\lor(\exists j<i:B(\phi_j)))</math>
|'''R'''elease: {{mvar|&phi;}} releases {{mvar|&psi;}} if {{mvar|&psi;}} is true up until and including the first position in which {{mvar|&phi;}} is true (or forever if such a position does not exist).
|<timeline>
ImageSize = width:240 height:100
PlotArea = left:30 bottom:30 top:0 right:20
DateFormat = x.y
Period = from:0 till:8
TimeAxis = orientation:horizontal
AlignBars = justify
ScaleMajor = gridcolor:black increment:1 start:0
ScaleMinor = gridcolor:black increment:1 start:0

PlotData=
 bar:p color:red width:10 align:left fontsize:S
 from:2 till:4
 from:6 till:8

 bar:q color:red width:10 align:left fontsize:S
 from:1 till:3
 from:5 till:6
 from:7 till:8

 bar:pRq color:red width:10 align:left fontsize:S
 from:1 till:3
 from:7 till:8
</timeline>
|-
! colspan="4" | Unary operators
|-
|'''N''' {{mvar|&phi;}}
|<math>\bigcirc \phi</math>
|<math>\mathcal{N}B(\phi_i)=B(\phi_{i+1})</math>
|'''N'''ext: {{mvar|&phi;}} has to hold at the next state. ('''X''' is used synonymously.)
|<timeline>
ImageSize = width:240 height:60
PlotArea = left:30 bottom:30 top:0 right:20
DateFormat = x.y
Period = from:0 till:6
TimeAxis = orientation:horizontal
AlignBars = justify
ScaleMajor = gridcolor:black increment:1 start:0
ScaleMinor = gridcolor:black increment:1 start:0

PlotData=
 bar:p color:red width:10 align:left fontsize:S
 from:2 till:3
 from:5 till:6

 bar:Np color:red width:10 align:left fontsize:S
 from:1 till:2
 from:4 till:5
</timeline>
|-
|'''F''' {{mvar|&phi;}}
|<math>\Diamond \phi</math>
|<math>\mathcal{F}B(\phi)=(true\,\mathcal{U}\,B)(\phi)</math>
|'''F'''uture: {{mvar|&phi;}} eventually has to hold (somewhere on the subsequent path).
|<timeline>
ImageSize = width:240 height:60
PlotArea = left:30 bottom:30 top:0 right:20
DateFormat = x.y
Period = from:0 till:6
TimeAxis = orientation:horizontal
AlignBars = justify
ScaleMajor = gridcolor:black increment:1 start:0
ScaleMinor = gridcolor:black increment:1 start:0

PlotData=
 bar:p color:red width:10 align:left fontsize:S
 from:2 till:3
 from:4 till:5

 bar:Fp color:red width:10 align:left fontsize:S
 from:0 till:5
</timeline>
|-
|'''G''' {{mvar|&phi;}}
|<math>\Box \phi</math>
|<math>\mathcal{G}B(\phi)=\neg\mathcal{F}\neg B(\phi)</math>
|'''G'''lobally: {{mvar|&phi;}} has to hold on the entire subsequent path.
|<timeline>
ImageSize = width:240 height:60
PlotArea = left:30 bottom:30 top:0 right:20
DateFormat = x.y
Period = from:0 till:6
TimeAxis = orientation:horizontal
AlignBars = justify
ScaleMajor = gridcolor:black increment:1 start:0
ScaleMinor = gridcolor:black increment:1 start:0

PlotData=
 bar:p color:red width:10 align:left fontsize:S
 from:1 till:3
 from:4 till:6

 bar:Gp color:red width:10 align:left fontsize:S
 from:4 till:6
</timeline>
|-
|'''A''' {{mvar|&phi;}}
|<math>\forall \phi</math>
|<math>(\mathcal{A}B)(\psi)= \ (\forall \phi:\phi_0=\psi\to B(\phi))</math>
|'''A'''ll: {{mvar|&phi;}} has to hold on all paths starting from the current state.
|
|-
|'''E''' {{mvar|&phi;}}
|<math>\exists \phi</math>
|<math>(\mathcal{E}B)(\psi)= \ (\exists \phi:\phi_0=\psi\land B(\phi))</math>
|'''E'''xists: there exists at least one path starting from the current state where {{mvar|&phi;}} holds.
|
|}

Alternate symbols:

* operator '''R''' is sometimes denoted by '''V'''
* The operator '''W''' is the ''weak until'' operator: <math>f \mathbf W g</math> is equivalent to <math>f \mathbf U g \lor \mathbf G f</math>

Unary operators are [[Well-formed formula|well-formed formula]]s whenever {{math|B({{var|&phi;}})}} is well-formed. Binary operators are well-formed formulas whenever {{math|B({{var|&phi;}})}} and {{math|C({{var|&phi;}})}} are well-formed.

In some logics, some operators cannot be expressed. For example, '''N''' operator cannot be expressed in [[Temporal logic of actions|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)<ref name="autogenerated2004"/>
* Timestamp temporal logic (TTL)<ref>{{Cite journal|doi=10.1145/3126510|title=Timestamp Temporal Logic (TTL) for Testing the Timing of Cyber-Physical Systems|year=2017|last1=Mehrabian|first1=Mohammadreza|last2=Khayatian|first2=Mohammad|last3=Shrivastava|first3=Aviral|last4=Eidson|first4=John C.|last5=Derler|first5=Patricia|last6=Andrade|first6=Hugo A.|last7=Li-Baboud|first7=Ya-Shian|last8=Griffor|first8=Edward|last9=Weiss|first9=Marc|last10=Stanton|first10=Kevin|journal=ACM Transactions on Embedded Computing Systems|volume=16|issue=5s|pages=1–20|s2cid=3570088|doi-access=free}}</ref>
* [[Property Specification Language|Property specification language]] (PSL)
* [[CTL*]], which generalizes LTL and CTL
* [[Hennessy–Milner logic]] (HML)
* [[Philosophy:Modal μ-calculus|Modal μ-calculus]], which includes as a subset HML and CTL*
* Metric temporal logic (MTL)<ref>Koymans, R. (1990). "Specifying real-time properties with metric temporal logic", ''Real-Time Systems'' '''2'''(4): 255–299. {{doi|10.1007/BF01995674}}.</ref>
* Metric interval temporal logic (MITL)<ref name="autogenerated2004">Maler, O.; Nickovic, D. (2004). "Monitoring temporal properties of continuous signals". {{doi|10.1007/978-3-540-30206-3_12}}.</ref>
* Timed propositional temporal logic (TPTL)
* Truncated Linear Temporal Logic (TLTL)<ref>Li, Xiao, Cristian-Ioan Vasile, and Calin Belta. "Reinforcement learning with temporal logic rewards." {{doi|10.1109/IROS.2017.8206234}}</ref>
* Hyper temporal logic (HyperLTL) <ref>{{Cite book|chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-54792-8_15|doi = 10.1007/978-3-642-54792-8_15|chapter = Temporal Logics for Hyperproperties|title = Principles of Security and Trust|series = Lecture Notes in Computer Science|year = 2014|last1 = Clarkson|first1 = Michael R.|last2 = Finkbeiner|first2 = Bernd|last3 = Koleini|first3 = Masoud|last4 = Micinski|first4 = Kristopher K.|last5 = Rabe|first5 = Markus N.|last6 = Sánchez|first6 = César|volume = 8414|pages = 265–284|isbn = 978-3-642-54791-1|s2cid = 8938993}}</ref>
A variation, closely related to temporal or chronological or tense logics, are modal logics based upon "topology", "place", or "spatial position".<ref>{{Cite book | doi=10.1007/978-94-017-3546-9_13| chapter=Topological Logic| title=Topics in Philosophical Logic| pages=229–249| year=1968| last1=Rescher| first1=Nicholas| isbn=978-90-481-8331-9}}</ref><ref>{{Cite book |doi = 10.1007/978-94-009-9407-2_9|chapter = A Modal Logic of Place|title = The Philosophy of Nicholas Rescher|pages = 65–73|year = 1979|last1 = von Wright|first1 = Georg Henrik|isbn = 978-94-009-9409-6}}</ref>

==See also==
* [[Physics:HPO formalism|HPO formalism]]
* Kripke structure
* [[Automata theory]]
* Chomsky grammar
* State transition system
* [[Duration calculus]] (DC)
* [[Philosophy:Hybrid logic|Hybrid logic]]
* [[Temporal logic in finite-state verification]]
* [[Reo Coordination Language]]
* [[Modal logic]]
* Research Materials: Max Planck Society Archive

==Notes==
{{reflist}}

==References==
* Mordechai Ben-Ari, Zohar Manna, Amir Pnueli: ''[https://link.springer.com/article/10.1007/BF01257083 The Temporal Logic of Branching Time]''. POPL 1981: 164–176
* Amir Pnueli: ''[https://www.dimap.ufrn.br/~richard/pubs/dim0436/papers/pnueli_temporal_1977.pdf 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, "[https://www.sciencedirect.com/science/article/pii/0167642387900360/pdf?md5=43227d5832bc2b176eb3de0da978418d&isDTMRedir=Y&pid=1-s2.0-0167642387900360-main.pdf&_valck=1 Modalities for model checking: branching time logic strikes back]", in ''Science of Computer Programming'' 8, pp.&nbsp;275–306, 1987.
* E. A. Emerson, "[https://profs.info.uaic.ro/~masalagiu/pub/handbook3.pdf Temporal and modal logic]", ''Handbook of Theoretical Computer Science'', Chapter 16, the MIT Press, 1990
* [https://www.springer.com/engineering/circuits+%26+systems/book/978-0-387-35313-5 ''A Practical Introduction to PSL''], Cindy Eisner, Dana Fisman
* {{cite book|editor1=Orna Grumberg|editor2=Helmut Veith|title=25 years of model checking: history, achievements, perspectives|year=2008|publisher=Springer|isbn=978-3-540-69849-4|chapter=From Church and Prior to [[Property Specification Language|PSL]]|first=Moshe Y. |last=Vardi|}} [http://www.cs.rice.edu/~vardi/papers/25mc.ps.gz 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==
* {{cite book|author1=Peter Øhrstrøm|author2=Per F. V. Hasle|title=Temporal logic: from ancient ideas to artificial intelligence|year=1995|publisher=Springer|isbn=978-0-7923-3586-3}}

==External links==
*''[[Stanford Encyclopedia of Philosophy]]'': "[http://plato.stanford.edu/entries/logic-temporal/ Temporal Logic]"—by Anthony Galton.
*[http://staff.science.uva.nl/~yde/papers/TempLog.pdf ''Temporal Logic''] by Yde Venema, formal description of syntax and semantics, questions of axiomatization. Treating also Kamp's dyadic temporal operators (since, until)
*[http://www.doc.ic.ac.uk/~imh/papers/sa.ps.gz Notes on games in temporal logic] by Ian Hodkinson, including a formal description of first-order temporal logic
*[http://cadp.inria.fr CADP – provides generic model checkers for various temporal logic]
*[http://www.comp.nus.edu.sg/~pat/ 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).

{{Non-classical logic}}

[[Category:Philosophy of time]]

{{Sourceattribution|Temporal logic}}