Temporal logic 321481 224072103 2008-07-07T04:49:09Z Lightbot 7178666 Units/dates/other In [[logic]], the term '''temporal logic''' is used to describe any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of [[time]]. It is sometimes also used to refer to '''tense logic''', a particular [[modal logic]]-based system of temporal logic introduced by [[Arthur Prior]] in the 1960s. Subsequently it has been developed further by [[computer scientists]], notably [[Amir Pnueli]], and [[logicians]]. Temporal logic was first studied in depth by [[Aristotle]], whose writings are filled with a crude form of first-order temporal modal binary logic. Any logic which uses the [[existential quantifier]] or the [[universal quantifier]] is said to be a [[predicate logic]]. Any logic which views time as a sequence of [[state theory|states]] is a temporal logic, and any logic which uses only two truth values is a [[binary logic]]. 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 handle statements whose truth value is constant in 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 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. Temporal logic always has the ability to reason about a time line. So called 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. Two early contenders in formal verifications were [[Linear Temporal Logic]] (a linear time logic by [[Amir Pnueli]] and [[Zohar Manna]]) and [[Computational tree logic|Computation Tree Logic]], a branching time logic by Edmund Clarke and E. Allen Emerson. The fact that the second logic is more efficient 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 [[operator]]s: [[logical operator]]s and [[modal operator]]s[http://plato.stanford.edu/entries/logic-temporal/]. Logical operators are usual [[truth-functional]] operators (<math>\neg,\or,\and,\rightarrow</math>). The modal operators used in Linear Temporal Logic and Computation Tree Logic are defined as follows. {| border="1" cellspacing="0" cellpadding="2" style="border-collapse: collapse;" |- | style="background:#efefef;" | Textual | style="background:#efefef;" | Symbolic | style="background:#efefef;" | Definition | style="background:#efefef;" | Explanation | style="background:#efefef;" | Diagram |- | colspan="4" align="center" | [[Binary operator]]s |- |<math>\phi</math> '''U''' <math>\psi</math> |<math>\phi ~\mathcal{U}~ \psi</math> |<math>\begin{matrix}(B\,\mathcal{U}\,C)(\phi)= \\ (\exists i:C(\phi_i))\land(\forall j<i:B(\phi_j))\end{matrix}</math> |'''U'''ntil: <math>\psi</math> holds at the current or a future position, and <math>\phi</math> has to hold until that position. At that position <math>\phi</math> 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> |- |<math>\phi</math> '''R''' <math>\psi</math> |<math>\phi ~\mathcal{R}~ \psi</math> |<math>\begin{matrix}(B\,\mathcal{R}\,C)(\phi)= \\ (\forall i:C(\phi_i))\lor(\exists j<i:B(\phi_j))\end{matrix}</math> |'''R'''elease: <math>\phi</math> releases <math>\psi</math> if <math>\psi</math> is true until the first position in which <math>\phi</math> 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: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:4 bar:q color:red width:10 align:left fontsize:S from:1 till:3 from:5 till:6 bar:pRq color:red width:10 align:left fontsize:S from:1 till:3 from:5 till:6 </timeline> |- | colspan="4" align="center" | [[Unary operator]]s |- |'''N''' <math>\phi</math> |<math>\circ \phi</math> |<math>\mathcal{N}B(\phi_i)=B(\phi_{i+1})</math> |'''N'''ext: <math>\phi</math> 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''' <math>\phi</math> |<math>\Diamond \phi</math> |<math>\mathcal{F}B(\phi)=(true\,\mathcal{U}\,B)(\phi)</math> |'''F'''uture: <math>\phi</math> 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''' <math>\phi</math> |<math>\Box \phi</math> |<math>\mathcal{G}B(\phi)=\neg\mathcal{F}\neg B(\phi)</math> |'''G'''lobally: <math>\phi</math> 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''' <math>\phi</math> | |<math>\begin{matrix}(\mathcal{A}B)(\psi)= \\ (\forall \phi:\phi_0=\psi\to B(\phi))\end{matrix}</math> |'''A'''ll: <math>\phi</math> has to hold on all paths starting from the current state. | |- |'''E''' <math>\phi</math> | |<math>\begin{matrix}(\mathcal{E}B)(\psi)= \\ (\exists \phi:\phi_0=\psi\land B(\phi))\end{matrix}</math> |'''E'''xists: there exists at least one path starting from the current state where <math>\phi</math> holds. | |} Alternate symbols: * operator '''R''' is sometimes denoted by '''V''' * The operator '''W''' is the ''weak until'' operator: <math>f W g</math> is equivalent to <math>f U g \or G f</math> Unary opearators are [[well-formed formula]]s whenever B(<math>\phi</math>) is well-formed. Binary operators are well-formed formulas whenever B(<math>\phi</math>) and C(<math>\phi</math>) 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 * [[CTL*]], which includes as a subset ** [[Computational tree logic]] (CTL) ** [[Linear temporal logic]] (LTL) * [[Interval temporal logic]] (ITL) * [[mu calculus|μ calculus]]. which includes as a subset ** [[Hennessy-Milner logic]] (HML) ==See also== * [[HPO formalism]] * [[Duration calculus]] (DC) * [[Hybrid logic]] * [[Temporal logic in finite-state verification]] * [[Temporal logic of actions]] (TLA) * [[List of important publications in computer science#Formal verification|Important publications in formal verification]] (including the use of temporal logic in [[formal verification]]) ==References== *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 275-306, 1987. *E.A. Emerson, Temporal and modal logic, ''Handbook of Theoretical Computer Science'', Chapter 16, the MIT Press, 1990 ==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://www.inrialpes.fr/vasy/cadp CADP - provides generic model checkers for various temporal logic] {{portalpar|Logic}} {{Logic}} [[Category:Formal methods]] [[Category:Modal logic]] [[es:Lógica temporal]] [[fr:Logique temporelle]] [[nl:Tijdslogica]] [[ja:時相論理]] [[pl:Logika temporalna]] [[sk:Temporálna logika]] [[fi:Temporaalilogiikka]] [[zh:时间逻辑]]