Temporal logic
Encyclopedia
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
. 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 logic
-based system of temporal logic introduced by Arthur Prior
in the late 1950s, and important results obtained were 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.
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 some times.
'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".
There was little development for millennia, Charles Sanders Peirce noted in the 19th century:
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 1955-6, and in 1957 published a book, Time and Modality, in which he introduce a propositional modal logic with two temporal connectives (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 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”. 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.
The binary temporal operators Since and Until were introduced by Hans Kamp
in his 1968 Ph. D. thesis, which also contains an important result relating temporal logic to first order logic—a result now known as Kamp's theorem.
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 E.M. Clarke
and E.A. 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.
s http://plato.stanford.edu/entries/logic-temporal/. Logical operators are usual truth-functional operators (
). The modal operators used in Linear Temporal Logic and Computation Tree Logic are defined as follows.
Alternate symbols:
Unary operators are well-formed formula
s 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
.
A variation, closely related to Temporal or Chronological or Tense logics, are Modal logics based upon "topology", "place", or "spatial position". One might also take note that in the Russian language, verbs have an aspect, based commonly upon time, but position also.
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
, 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
Time
Time is a part of the measuring system used to sequence events, to compare the durations of events and the intervals between them, and to quantify rates of change such as the motions of objects....
. 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 logic
Modal logic
Modal logic is a type of formal logic that extends classical propositional and predicate logic to include operators expressing modality. Modals — words that express modalities — qualify a statement. For example, the statement "John is happy" might be qualified by saying that John is...
-based system of temporal logic introduced by Arthur Prior
Arthur Prior
Arthur Norman Prior was a noted logician and philosopher. Prior founded tense logic, now also known as temporal logic, and made important contributions to intensional logic, particularly in Prior .-Biography:Prior was entirely educated in New Zealand, where he was fortunate to have come under the...
in the late 1950s, and important results obtained were by Hans Kamp
Hans Kamp
Johan Anthony Willem Kamp is a Dutch philosopher and linguist, responsible for introducing Discourse Representation Theory in 1981. Kamp received a Ph.D. in Philosophy from UCLA in 1968...
. Subsequently it has been developed further by computer scientists, notably Amir Pnueli, and logicians.
Temporal logic has found an important application in formal verification
Formal verification
In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal methods of mathematics .- Usage :Formal verification can be...
, 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. 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 some times.
History
Although AristotleAristotle
Aristotle was a Greek philosopher and polymath, a student of Plato and teacher of Alexander the Great. His writings cover many subjects, including physics, metaphysics, poetry, theater, music, logic, rhetoric, linguistics, politics, government, ethics, biology, and zoology...
'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
Principle of bivalence
In logic, the semantic principle of bivalence states that every declarative sentence expressing a proposition has exactly one truth value, either true or false...
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".
There was little development for millennia, Charles Sanders Peirce noted in the 19th century:
Arthur Prior
Arthur Prior
Arthur Norman Prior was a noted logician and philosopher. Prior founded tense logic, now also known as temporal logic, and made important contributions to intensional logic, particularly in Prior .-Biography:Prior was entirely educated in New Zealand, where he was fortunate to have come under the...
was concerned with the philosophical matters of free will
Free will
"To make my own decisions whether I am successful or not due to uncontrollable forces" -Troy MorrisonA pragmatic definition of free willFree will is the ability of agents to make choices free from certain kinds of constraints. The existence of free will and its exact nature and definition have long...
and predestination
Predestination
Predestination, in theology is the doctrine that all events have been willed by God. John Calvin interpreted biblical predestination to mean that God willed eternal damnation for some people and salvation for others...
. According to his wife, he first considered formalizing temporal logic in 1953. He gave lectures on the topic at the University of Oxford
University of Oxford
The University of Oxford is a university located in Oxford, United Kingdom. It is the second-oldest surviving university in the world and the oldest in the English-speaking world. Although its exact date of foundation is unclear, there is evidence of teaching as far back as 1096...
in 1955-6, and in 1957 published a book, Time and Modality, in which he introduce a propositional modal logic with two temporal connectives (modal operator
Modal operator
In modal logic, a modal operator is an operator which forms propositions from propositions. In general, a modal operator has the "formal" property of being non-truth-functional, and is "intuitively" characterised by expressing a modal attitude about the proposition to which the operator is applied...
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 Saul Kripke
Saul Kripke
Saul Aaron Kripke is an American philosopher and logician. He is a professor emeritus at Princeton and teaches as a Distinguished Professor of Philosophy at the CUNY Graduate Center...
, 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”. Between 1958 and 1965 Prior also corresponded with Charles Leonard Hamblin
Charles Leonard Hamblin
Charles Leonard Hamblin was an Australian philosopher, logician, and computer pioneer, as well as a professor of philosophy at the Technical University of New South Wales in Sydney....
, 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.
The binary temporal operators Since and Until were introduced by Hans Kamp
Hans Kamp
Johan Anthony Willem Kamp is a Dutch philosopher and linguist, responsible for introducing Discourse Representation Theory in 1981. Kamp received a Ph.D. in Philosophy from UCLA in 1968...
in his 1968 Ph. D. thesis, which also contains an important result relating temporal logic to first order logic—a result now known as Kamp's theorem.
Two early contenders in formal verifications were Linear Temporal Logic
Linear temporal logic
In logic, Linear temporal logic is a modal temporal logic with modalities referring to time. In LTL, one can encode formulae about the future of paths such as that a condition will eventually be true, that a condition will be true until another fact becomes true, etc. It is a fragment of the more...
(a linear time logic by Amir Pnueli) and Computation Tree Logic
Computational tree logic
Computation tree logic is a branching-time logic, meaning that its model of time is a tree-like structure in which the future is not determined; there are different paths in the future, any one of which might be an actual path that is realised...
, a branching time logic by E.M. Clarke
Edmund M. Clarke
Edmund Melson Clarke, Jr. is a computer scientist and academic noted for developingmodel checking, a method for formally verifying hardware and software designs....
and E.A. Emerson
E. Allen Emerson
Ernest Allen Emerson is a computer scientist and endowed professor at the University of Texas, Austin, USA.He won the 2007 A.M. Turing Award along with Edmund M...
. 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 operators: logical operators and modal operatorModal operator
In modal logic, a modal operator is an operator which forms propositions from propositions. In general, a modal operator has the "formal" property of being non-truth-functional, and is "intuitively" characterised by expressing a modal attitude about the proposition to which the operator is applied...
s http://plato.stanford.edu/entries/logic-temporal/. 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 until 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 formula
Well-formed formula
In mathematical logic, a well-formed formula, shortly wff, often simply formula, is a word which is part of a formal language...
s 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 Logic of Actions
Temporal logic of actions is a logic developed by Leslie Lamport, which combines temporal logic with a logic of actions.It is used to describe behaviours of concurrent systems.- Details :...
.
Temporal logics
Temporal logics include- Interval temporal logicInterval temporal logicInterval temporal logic is a temporal logic for representing both propositional and first-order logical reasoning about periods of time that is capable of handling both sequential and parallel composition...
(ITL) - μ calculus. which includes as a subset
- Hennessy-Milner logicHennessy-Milner logicIn computer science, Hennessy–Milner logic is a multimodal logic used to specify properties of a labeled transition system, a structure similar to an automaton...
(HML) - CTL*, which includes as a subset
- Computational tree logicComputational tree logicComputation tree logic is a branching-time logic, meaning that its model of time is a tree-like structure in which the future is not determined; there are different paths in the future, any one of which might be an actual path that is realised...
(CTL) - Linear temporal logicLinear temporal logicIn logic, Linear temporal logic is a modal temporal logic with modalities referring to time. In LTL, one can encode formulae about the future of paths such as that a condition will eventually be true, that a condition will be true until another fact becomes true, etc. It is a fragment of the more...
(LTL)
- Computational tree logic
- Hennessy-Milner logic
A variation, closely related to Temporal or Chronological or Tense logics, are Modal logics based upon "topology", "place", or "spatial position". One might also take note that in the Russian language, verbs have an aspect, based commonly upon time, but position also.
See also
- Computational verb logic
- HPO formalismHPO formalismThe History Projection Operator formalism is an approach to temporal quantum logic developed by Chris Isham. It deals with the logical structure of quantum mechanical propositions asserted at different points in time.- Introduction :...
- Kripke structureKripke structureA Kripke structure is a type of nondeterministic finite state machine proposed by Saul Kripke , used in model checking to represent the behavior of a system.It is a simple abstract machine to capture an idea of a computing machine,...
- Automata theoryAutomata theoryIn theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
- Chomsky grammar
- State transition systemState transition systemIn theoretical computer science, a state transition system is an abstract machine used in the study of computation. The machine consists of a set of states and transitions between states, which may be labeled with labels chosen from a set; the same label may appear on more than one transition...
- Duration calculusDuration CalculusDuration calculus is an interval logic for real-time systems. It was originally developed by Zhou Chaochen with the help of Anders P. Ravn and C. A. R. Hoare on the European ESPRIT Basic Research Action ProCoS project on Provably Correct Systems.DC is mainly useful at the requirements level of...
(DC) - Hybrid logicHybrid logicHybrid logic refers to a number of extensions to propositional modal logic with more expressive power, though still less than first-order logic. In formal logic, there is a trade-off between expressiveness and computational tractability . The history of hybrid logic began with Arthur Prior's work...
- Temporal logic in finite-state verificationTemporal logic in finite-state verificationIn finite-state verification, model checkers examine finite-state machines representing concurrent software systems looking for errors in design. Errors are defined as violations of requirements expressed as properties of the system...
- Temporal logic of actionsTemporal Logic of ActionsTemporal logic of actions is a logic developed by Leslie Lamport, which combines temporal logic with a logic of actions.It is used to describe behaviours of concurrent systems.- Details :...
(TLA) - Important publications in formal verification (including the use of temporal logic in formal verificationFormal verificationIn the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal methods of mathematics .- Usage :Formal verification can be...
) - Reo Coordination LanguageReo Coordination LanguageIn computer science, Reo is a channel-based exogenous coordination language.- Overview :In the context of distributed application, correction and validity of single processes does not imply the correctness of the whole system. In such systems, the communication between the processes is of a high...
- Modal logicModal logicModal logic is a type of formal logic that extends classical propositional and predicate logic to include operators expressing modality. Modals — words that express modalities — qualify a statement. For example, the statement "John is happy" might be qualified by saying that John is...
External links
- Stanford Encyclopedia of PhilosophyStanford Encyclopedia of PhilosophyThe Stanford Encyclopedia of Philosophy is a freely-accessible online encyclopedia of philosophy maintained by Stanford University. Each entry is written and maintained by an expert in the field, including professors from over 65 academic institutions worldwide...
: "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).