All Topics  
Temporal logic

 

 
   Email Print
   Bookmark   Link
 

 

Temporal logic
 
 
  Topics Temporal logic Topic Home

In logic
Logic

Logic is the study of the principles of valid demonstration and inference. Logic is a branch of philosophy, a part of the classical Trivium . The word derives from Greek language ?????? , fem....
, 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 component of the measurement used to sequence events, to compare the durations of events and the intervals between them, and to quantify the motions of objects....
. It is sometimes also used to refer to tense logic, a particular modal logic
Modal logic

A modal logic is any system of mathematical logic#Formal logic that attempts to deal with notions of possibility and necessity. Traditionally, there are three "modes" or "moods" or "modalities" of the Copula to be, namely, Logical possibility, probability, and Necessary_and_sufficient_conditions#Necessary_conditions....
-based system of temporal logic introduced by Arthur Prior
Arthur Prior

Arthur Norman Prior was a noted logic. Prior founded tense logic, now also known as temporal logic, and made important contributions to intensional logic, particularly in Prior ....
 in the 1960s. Subsequently it has been developed further by computer scientists, notably Amir Pnueli
Amir Pnueli

Amir Pnueli is an Israeli computer scientist who received the Turing Award in 1996 for seminal work introducing temporal logic into computing science and for outstanding contributions to program and systems verification....
, and logicians
Logicians

The Logicians or School of Names was a China philosophy school that grew out of Mohism in the Warring States Period.The philosophy is often translated to sophists or dialecticians....
.

Temporal logic was first studied in depth by Aristotle
Aristotle

Aristotle was a Greeks philosopher, a student of Plato and teacher of Alexander the Great. He wrote on many subjects, including physics, metaphysics, Poetics , theater, music, logic, rhetoric, politics, government, ethics, biology and zoology....
, whose writings are filled with an early, partially-developed form of first-order temporal modal binary logic.






Discussion
Ask a question about 'Temporal logic'
Start a new discussion about 'Temporal logic'
Answer questions from other users
Full Discussion Forum



Encyclopedia


In logic
Logic

Logic is the study of the principles of valid demonstration and inference. Logic is a branch of philosophy, a part of the classical Trivium . The word derives from Greek language ?????? , fem....
, 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 component of the measurement used to sequence events, to compare the durations of events and the intervals between them, and to quantify the motions of objects....
. It is sometimes also used to refer to tense logic, a particular modal logic
Modal logic

A modal logic is any system of mathematical logic#Formal logic that attempts to deal with notions of possibility and necessity. Traditionally, there are three "modes" or "moods" or "modalities" of the Copula to be, namely, Logical possibility, probability, and Necessary_and_sufficient_conditions#Necessary_conditions....
-based system of temporal logic introduced by Arthur Prior
Arthur Prior

Arthur Norman Prior was a noted logic. Prior founded tense logic, now also known as temporal logic, and made important contributions to intensional logic, particularly in Prior ....
 in the 1960s. Subsequently it has been developed further by computer scientists, notably Amir Pnueli
Amir Pnueli

Amir Pnueli is an Israeli computer scientist who received the Turing Award in 1996 for seminal work introducing temporal logic into computing science and for outstanding contributions to program and systems verification....
, and logicians
Logicians

The Logicians or School of Names was a China philosophy school that grew out of Mohism in the Warring States Period.The philosophy is often translated to sophists or dialecticians....
.

Temporal logic was first studied in depth by Aristotle
Aristotle

Aristotle was a Greeks philosopher, a student of Plato and teacher of Alexander the Great. He wrote on many subjects, including physics, metaphysics, Poetics , theater, music, logic, rhetoric, politics, government, ethics, biology and zoology....
, whose writings are filled with an early, partially-developed 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
Predicate logic

In mathematical logic, predicate logic is the generic term for symbolic formal systems like first-order logic, second-order logic, many-sorted logic or infinitary logic....
. Any logic which views time as a sequence of states
State theory

State theory is a theory of absolute time in which the number of states from the first moment in time up to the current moment in time can be counted....
 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
Formal verification

In the context of hardware and software systems, formal verification is the act of Mathematical proof or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal methods of mathematics....
, 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
Linear temporal logic

Linear temporal logic is a modal logic temporal logic with modalities referring to time. In LTL, one can encode formulae about the future of path such as that a condition will eventually be true, that a condition will be true until another fact becomes true, etc....
 (a linear time logic by Amir Pnueli
Amir Pnueli

Amir Pnueli is an Israeli computer scientist who received the Turing Award in 1996 for seminal work introducing temporal logic into computing science and for outstanding contributions to program and systems verification....
 and Zohar Manna
Zohar Manna

Zohar Manna is a professor of computer science at Stanford University. He is the author of The Mathematical Theory of Computation , one of the first texts to provide extensive coverage of the mathematical concepts behind computer programming....
) and Computation Tree Logic
Computational tree logic

Computation tree logic is a branching-time symbolic 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 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
Operator

In mathematics, an operator is a function which operates on another function. Often, an "operator" is a function which acts on functions to produce other functions ; or it may be a generalization of such a function, as in linear algebra, where some of the terminology reflects the origin of the subject in operations on the functions which ar...
s: logical operators and 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 function, and is "intuitively" characterised by expressing a modal attitude about the proposition to which the operator is applied....
s. 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:
  • 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 computer science and mathematical logic, a well-formed formula or simply formula is a symbol or string of symbols that is generated by the formal grammar 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....
.

Temporal logics


Temporal logics include
  • Interval temporal logic
    Interval temporal logic

    Interval temporal logic is a temporal logic for representing both propositional logic and first-order logic 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 logic
      Hennessy-Milner logic

      The Matthew Hennessy-Robin Milner logic is a temporal logic in computer science. It is used to specify properties of a labeled transition system, a structure similar to an automaton....
       (HML)
    • CTL*
      CTL*

      CTL* is a superset of CTL and LTL . It freely combines path quantors and temporal operators. Like CTL, CTL* is a branching time logic. The formal semantics of CTL* formulae are defined with respect to a given Kripke structure....
      , which includes as a subset
      • Computational tree logic
        Computational tree logic

        Computation tree logic is a branching-time symbolic 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 logic
        Linear temporal logic

        Linear temporal logic is a modal logic temporal logic with modalities referring to time. In LTL, one can encode formulae about the future of path such as that a condition will eventually be true, that a condition will be true until another fact becomes true, etc....
         (LTL)


See also

  • HPO formalism
    HPO formalism

    The History Projection Operator formalism is an approach to temporal logic quantum logic developed by Christopher Isham. It deals with the logical structure of quantum mechanics propositions asserted at different points in time....
  • Duration calculus
    Duration Calculus

    Duration calculus is an interval logic for real-time computing. It was originally developed by Zhou Chaochen with the help of Anders P. Ravn and C....
     (DC)
  • Hybrid logic
    Hybrid logic

    Hybrid logic refers to a number of extensions to propositional logic modal logic with more expressive power, though still less than first-order logic....
  • Temporal logic in finite-state verification
    Temporal logic in finite-state verification

    In finite-state verification, Model checking 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 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....
     (TLA)
  • Important publications in formal verification (including the use of temporal logic in formal verification
    Formal verification

    In the context of hardware and software systems, formal verification is the act of Mathematical proof or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal methods of mathematics....
    )


External links

  • Stanford Encyclopedia of Philosophy
    Stanford Encyclopedia of Philosophy

    The Stanford Encyclopedia of Philosophy is a Open access online encyclopedia of philosophy maintained by Stanford University. The SEP was initially developed with U.S....
    : "" -- by Anthony Galton.
  • by Yde Venema, formal description of syntax and semantics, questions of axiomatization. Treating also Kamp's dyadic temporal operators (since, until)
  • by Ian Hodkinson, including a formal description of first-order temporal logic
  • 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).