词条 | Temporal logic | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
释义 |
In logic, temporal logic is any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of 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-based system of temporal logic introduced by Arthur Prior in the late 1950s, with important contributions by Hans Kamp. It has been further developed 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. MotivationConsider 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 logics, however, can reason about multiple timelines. 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", 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. HistoryAlthough 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 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] {{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.}}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 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]{{Clarify|date=April 2011}} 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][6][7] 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 Ben-Ari, 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. Prior's tense logic (TL)The sentential tense logic introduced in Time and Modality has four (non-truth-functional) modal operators (in addition to all usual truth-functional operators in first-order propositional logic.[8]
From P and F one can define G and H, and vice versa: Syntax and semanticsA minimal syntax for TL is specified with the following BNF grammar: where a is some atomic formula.[9] Kripke models are used to evaluate the truth of sentences in TL. A pair ({{Var|T}}, <) of a set {{Var|T}} and a 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}}⊨{{var|ϕ}}[{{var|u}}]. With this notation,[10]
Given a class {{var|F}} of frames, a sentence {{var|ϕ}} of TL is
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, antisymmetric, reflexive, trichotomic, irreflexive, total, dense, or some combination of these. A minimal axiomatic logicBurgess outlines a logic that makes no assumptions on the relation <, but allows for meaningful deductions, based on the following axiom schema:[11]
with the following rules of deduction:
One can derive the following rules:
Translation to predicate logicBurgess gives a Meredith translation from statements in TL into statements in first-order logic with one free variable {{Var|x}}0 (representing the present moment). This translation {{Var|M}} is defined recursively as follows:[12] where is the sentence with all variable indices incremented by 1 and is a one-place predicate defined by . Temporal operatorsTemporal logic has two kinds of operators: logical operators and modal operators . 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 formulas 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 logicsTemporal logics include
A variation, closely related to temporal or chronological or tense logics, are modal logics based upon "topology", "place", or "spatial position".[16][17] See also{{Portal|Logic}}
Notes1. ^Vardi 2008, p. 153 2. ^1 Vardi 2008, p. 154 3. ^{{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. 176–178, 210 4. ^{{cite web|url=https://plato.stanford.edu/entries/logic-temporal/#AddSinUnt |title=Temporal Logic (Stanford Encyclopedia of Philosophy) |publisher=Plato.stanford.edu |date= |accessdate=2014-07-30}} 5. ^{{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}} 6. ^Vardi 2008, p. 154 7. ^{{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}} 8. ^{{Cite book|title=Time and modality: the John Locke lectures for 1955–6, delivered at the University of Oxford|last=Prior|first=Arthur Norman|date=|publisher=The Clarendon Press|year=2003|isbn=9780198241584|location=Oxford|pages=|oclc=905630146|author-link=Arthur Prior}} 9. ^{{Cite book|url=https://plato.stanford.edu/archives/win2015/entries/logic-temporal/|title=The Stanford Encyclopedia of Philosophy|last=Goranko|first=Valentin|last2=Galton|first2=Antony|date=2015|publisher=Metaphysics Research Lab, Stanford University|editor-last=Zalta|editor-first=Edward N.|edition=Winter 2015}} 10. ^{{Cite book|title=The continuum companion to philosophical logic|last=Müller|first=Thomas|publisher=A&C Black|year=2011|isbn=|editor-last=Horsten|editor-first=Leon|location=|pages=329|chapter=Tense or temporal logic}} 11. ^{{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|author-link=John P. Burgess}} 12. ^{{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|author-link=John P. Burgess}} 13. ^ https://asu.pure.elsevier.com/en/publications/timestamp-temporal-logic-ttl-for-testing-the-timing-of-cyber-phys 14. ^Koymans, R. (1990). "Specifying real-time properties with metric temporal logic", Real-Time Systems 2(4): 255–299. {{doi|10.1007/BF01995674}}. 15. ^1 Maler, O.; Nickovic, D. (2004). "Monitoring temporal properties of continuous signals". {{doi|10.1007/978-3-540-30206-3_12}}. 16. ^Nicholas Rescher, James Garson, "Topological Logic" in The Journal of Symbolic Logic, 33(4):537–548, December, 1968 17. ^Georg Henrik von Wright, "A Modal Logic of Place", in E. Sosa (Editor), pp. 65–73, The Philosophy of Nicholas Rescher: Discussion and Replies, D. Reidel, Dordrecht, Holland, 1979 References
Further reading
External links{{Commonscat}}
1 : Temporal logic |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。