In logic, temporal logic is any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of time. In a temporal logic we can then express statements like "I am always hungry", "I will eventually be hungry", or "I will be hungry until I eat something". Temporal logic is sometimes also used to refer to tense logic, a particular modal logicbased system of temporal logic introduced by Arthur Prior in the late 1950s, and important results were obtained by Hans Kamp. Subsequently it has been developed further 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 truth value of the statement can vary in time. Sometimes the statement is true, and sometimes the statement is false, but the statement is never true and false simultaneously. In a temporal logic, statements can have a truth value which can vary in time. Contrast this with an atemporal logic, which can only discuss statements whose truth value is constant in time. This treatment of truth values over time differentiates temporal logic from computational verb logic.
Temporal logic always has the ability to reason about a time line. Socalled linear time logics are restricted to this type of reasoning. Branching logics, however, can reason about multiple time lines. 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." We may also state that "there is a possibility that eventually I am no longer hungry." If we do not know whether or not I will ever get fed, these statements are both true some times.
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 firstorder 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]}
Template:Cquote
Arthur Prior was concerned with the philosophical matters of free will and predestination. According to his wife, he first considered formalizing temporal logic in 1953. He gave lectures on the topic at the University of Oxford in 19556, 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]} 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.^{[3]}
The binary temporal operators Since and Until were introduced by Hans Kamp in his 1968 Ph. D. thesis,^{[4]} which also contains an important result relating temporal logic to first order logic—a result now known as Kamp's theorem.^{[5]}^{[2]}^{[6]}
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 BenAri, 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.
Temporal operators
Temporal logic has two kinds of operators: truthfunctional operators ($\backslash neg,\backslash or,\backslash and,\backslash rightarrow$). The modal operators used in Linear Temporal Logic and Computation Tree Logic are defined as follows.
Textual

Symbolic

Definition

Explanation

Diagram

Binary operators

$\backslash phi$ U $\backslash psi$

$\backslash phi\; ~\backslash mathcal\{U\}~\; \backslash psi$

$\backslash begin\{matrix\}(B\backslash ,\backslash mathcal\{U\}\backslash ,C)(\backslash phi)=\; \backslash \backslash \; (\backslash exists\; i:C(\backslash phi\_i)\backslash land(\backslash forall\; j(\backslash phi\_j)))\backslash end\{matrix\}\; math>$ 
Until: $\backslash psi$ holds at the current or a future position, and $\backslash phi$ has to hold until that position. At that position $\backslash phi$ does not have to hold any more.

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

$\backslash phi$ R $\backslash psi$

$\backslash phi\; ~\backslash mathcal\{R\}~\; \backslash psi$

$\backslash begin\{matrix\}(B\backslash ,\backslash mathcal\{R\}\backslash ,C)(\backslash phi)=\; \backslash \backslash \; (\backslash forall\; i:C(\backslash phi\_i)\backslash lor(\backslash exists\; j(\backslash phi\_j)))\backslash end\{matrix\}\; math>$ 
Release: $\backslash phi$ releases $\backslash psi$ if $\backslash psi$ is true until the first position in which $\backslash phi$ is true (or forever if such a position does not exist).

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

Unary operators

N $\backslash phi$

$\backslash bigcirc\; \backslash phi$

$\backslash mathcal\{N\}B(\backslash phi\_i)=B(\backslash phi\_\{i+1\})$

Next: $\backslash phi$ has to hold at the next state. (X is used synonymously.)

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

F $\backslash phi$

$\backslash Diamond\; \backslash phi$

$\backslash mathcal\{F\}B(\backslash phi)=(true\backslash ,\backslash mathcal\{U\}\backslash ,B)(\backslash phi)$

Future: $\backslash phi$ eventually has to hold (somewhere on the subsequent path).

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

G $\backslash phi$

$\backslash Box\; \backslash phi$

$\backslash mathcal\{G\}B(\backslash phi)=\backslash neg\backslash mathcal\{F\}\backslash neg\; B(\backslash phi)$

Globally: $\backslash phi$ has to hold on the entire subsequent path.

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

A $\backslash phi$

$\backslash forall\; \backslash phi$

$\backslash begin\{matrix\}(\backslash mathcal\{A\}B)(\backslash psi)=\; \backslash \backslash \; (\backslash forall\; \backslash phi:\backslash phi\_0=\backslash psi\backslash to\; B(\backslash phi))\backslash end\{matrix\}$

All: $\backslash phi$ has to hold on all paths starting from the current state.


E $\backslash phi$

$\backslash exists\; \backslash phi$

$\backslash begin\{matrix\}(\backslash mathcal\{E\}B)(\backslash psi)=\; \backslash \backslash \; (\backslash exists\; \backslash phi:\backslash phi\_0=\backslash psi\backslash land\; B(\backslash phi))\backslash end\{matrix\}$

Exists: there exists at least one path starting from the current state where $\backslash phi$ holds.


Alternate symbols:
 operator R is sometimes denoted by V
 The operator W is the weak until operator: $f\; W\; g$ is equivalent to $f\; U\; g\; \backslash or\; G\; f$
Unary operators are wellformed formulas whenever B($\backslash phi$) is wellformed. Binary operators are wellformed formulas whenever B($\backslash phi$) and C($\backslash phi$) are wellformed.
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".^{[9]}^{[10]} One might also take note that in the Russian language, verbs have an aspect, based commonly upon time, but position also.
See also
Notes
References
 Mordechai BenAri, Zohar Manna, Amir Pnueli: The Temporal Logic of Branching Time. POPL 1981: 164176
 Amir Pnueli: The Temporal Logic of Programs FOCS 1977: 4657
 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, p 275306, 1987.
 E.A. Emerson, Temporal and modal logic, Handbook of Theoretical Computer Science, Chapter 16, the MIT Press, 1990
 preprint Historical perspective on how seemingly disparate ideas came together in computer science and engineering. (The reference to Church is to a little known 1957 in which he proposed a way to perform hardware verification.)
Further reading
External links
 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 firstorder 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).


 Overview 

 Academic areas  

 Foundations  


                

This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.