Časová logika - Temporal logic

v logika, časová logika je jakýkoli systém pravidel a symboliky pro reprezentaci a odůvodňování návrhů kvalifikovaných z hlediska čas (například: „Jsem vždy hladový, „budu nakonec buď hladový, nebo „budu mít hlad dokud Něco jem. “). Někdy se to také označuje napjatá logika, a modální logika - systém časové logiky založený na Arthur Prior na konci padesátých let, s významnými příspěvky od Hans Kamp. To bylo dále vyvinuto počítačoví vědci, zejména Amir Pnueli, a logici.

Časová logika našla v aplikaci důležitou aplikaci formální ověření, kde se používá ke stanovení požadavků hardwarových nebo softwarových systémů. Například by to někdo chtěl říct kdykoli je podán požadavek, přístup ke zdroji je nakonec udělen, ale je nikdy udělena dvěma žadatelům současně. Takové prohlášení lze pohodlně vyjádřit v časové logice.

Motivace

Zvažte výrok „Mám hlad“. Ačkoli je jeho význam v čase konstantní, jeho pravdivostní hodnota se může časem měnit. Někdy je to pravda a někdy nepravda, ale nikdy to není pravda současně a Nepravdivé. V časové logice může mít tvrzení pravdivostní hodnotu, která se mění v čase - na rozdíl od atemporální logiky, která platí pouze pro tvrzení, jejichž pravdivostní hodnoty jsou v čase konstantní. Toto zacházení s pravdivostní hodnotou v čase odlišuje časovou logiku od výpočetní slovesná logika.

Časová logika má vždy schopnost uvažovat o časové ose. Takzvané lineární „časové logiky“ jsou omezeny na tento typ uvažování. Větvení logiky však může být důvodem pro více časových os. To předpokládá prostředí, které může jednat nepředvídatelně. Pro pokračování příkladu můžeme v rozvětvené logice konstatovat, že „existuje možnost, že Já navždy zůstane hladový “, a že„ existuje možnost, že nakonec Já už nemám hlad. "Pokud nevíme, zda nebo ne Já budou někdy krmeni, mohou být obě tvrzení pravdivá.

Dějiny

Ačkoli Aristoteles Logika se téměř úplně zabývá teorií kategorický úsudek, v jeho díle jsou pasáže, které jsou nyní považovány za očekávání časové logiky a mohou znamenat časnou, částečně rozvinutou formu časové modální binární logiky prvního řádu. Aristoteles byl zvláště znepokojen problém budoucích kontingentů, kde nemohl přijmout, že princip bivalence platí pro prohlášení o budoucích událostech, tj. že v současné době můžeme rozhodnout, zda je prohlášení o budoucí události pravdivé nebo nepravdivé, například „zítra bude námořní bitva“.[1]

Po tisíciletí došlo k malému vývoji, Charles Sanders Peirce uvedeno v 19. století:[2]

Čas logici obvykle považovali za to, čemu se říká „extralogická“ záležitost. Nikdy jsem nesdílel tento názor. Myslel jsem si však, že logika ještě nedosáhla stavu vývoje, kdy by zavedení časových modifikací jejích forem nevedlo k velkému zmatku; a já jsem hodně z tohoto způsobu myšlení ještě.

Arthur Prior se zabýval filozofickými záležitostmi svobodná vůle a předurčení. Podle jeho manželky poprvé uvažoval o formalizaci časové logiky v roce 1953. Přednášel na toto téma na konferenci University of Oxford v letech 1955–6 a v roce 1957 vydal knihu, Čas a modalita, ve kterém představil a propoziční modální logika se dvěma časovými spojkami (modální operátoři ), F a P, což odpovídá „někdy v budoucnosti“ a „někdy v minulosti“. V této rané práci považoval Prior čas za lineární. V roce 1958 však dostal dopis od Saul Kripke, který poukázal na to, že tento předpoklad je možná neoprávněný. Ve vývoji, který předznamenal podobný vývoj v počítačové vědě, to vzal Prior pod dohledem a vyvinul dvě teorie větvícího se času, které nazval „Ockhamist“ a „Peircean“.[2][je zapotřebí objasnění ] V letech 1958 až 1965 Prior rovněž korespondoval s Charles Leonard Hamblin K této korespondenci lze vysledovat například řadu počátečních vývojových trendů v této oblasti Hamblinovy ​​důsledky. Prior vydal svou nejvyspělejší práci na toto téma, knihu Minulost, současnost a budoucnost v roce 1967. Zemřel o dva roky později.[3]

Binární časové operátory Od té doby a Dokud byly představeny Hans Kamp v jeho 1968 Ph.D. teze,[4] který také obsahuje důležitý výsledek vztahující se k časové logice k logika prvního řádu —Výsledek nyní známý jako Kampova věta.[5][2][6]

Dva první uchazeči o formální ověření byli lineární časová logika, lineární časová logika podle Amir Pnueli, a logika výpočetního stromu, větvící se časová logika Mordechai Ben-Ari, Zohar Manna a Amir Pnueli. Přibližně ve stejné době navrhl téměř rovnocenný formalismus jako CTL E. M. Clarke a E. A. Emerson. Skutečnost, že o druhé logice lze rozhodovat efektivněji než o první, neodráží obecně větvení a lineární logiku, jak se někdy argumentovalo. Emerson a Lei spíše ukazují, že jakoukoli lineární logiku lze rozšířit na větvící logiku, o které lze rozhodnout se stejnou složitostí.

Priorova napjatá logika (TL)

Logika sentimentálního času zavedená v Čas a modalita má čtyři (pravda-funkční ) modální operátoři (kromě všech obvyklých operátorů pravdivých funkcí v výroková logika prvního řádu.[7]

  • P: „Bylo to tak, že ...“ (P znamená „minulost“)
  • F: „Bude to tak, že ...“ (F znamená „budoucnost“)
  • G: "Vždy to tak bude, že ..."
  • H: "Vždy to bylo tak, že ..."

Ty lze kombinovat, pokud necháme π nekonečnou cestu[8]:

  • : „V určitém okamžiku platí ve všech budoucích stavech cesty “
  • : " platí pro nekonečně mnoho států na cestě “

Z P a F lze definovat G a Ha naopak:

Syntaxe a sémantika

Minimální syntaxe pro TL je určena následujícím textem BNF gramatika:

kde A je nějaký atomový vzorec.[9]

Modely Kripke se používají k hodnocení pravdy věty v TL. Pár (T, <) množiny T a a binární relace T (nazývané „přednost“) se nazývá a rám. A Modelka je dán trojitým (T, <, PROTI) rámečku a funkce PROTI volal a ocenění který přiřazuje každému páru (A, u) atomového vzorce a časová hodnota nějakou pravdivostní hodnotu. Pojem "ϕ platí v modelu U=(T, <, PROTI) v čase u„je zkráceno U⊨ϕ[u]. S touto notací[10]

Prohlášení... je pravda, když
U⊨A[u]PROTI(A,u) = pravda
U⊨¬ϕ[u]ne U⊨ϕ[u]
U⊨(ϕ∧ψ)[u]U⊨ϕ[u] a U⊨ψ[u]
U⊨(ϕ∨ψ)[u]U⊨ϕ[u] nebo U⊨ψ[u]
U⊨(ϕ→ψ)[u]U⊨ψ[u] pokud U⊨ϕ[u]
U⊨Gϕ[u]U⊨ϕ[proti] pro všechny proti s u<proti
U⊨Hϕ[u]U⊨ϕ[proti] pro všechny proti s proti<u

Vzhledem k třídě F rámců, věta ϕ TL je

  • platný s ohledem na F pokud pro každý model U=(T,<,PROTI) s (T, <) v F a pro každého u v T, U⊨ϕ[u]
  • uspokojivý s ohledem na F pokud existuje model U=(T,<,PROTI) s (T, <) v F takové, že pro některé u v T, U⊨ϕ[u]
  • A následek věty ψ s ohledem na F pokud pro každý model U=(T,<,PROTI) s (T, <) v F a pro každého u v T, pokud U⊨ψ[u], pak U⊨ϕ[u]

Mnoho vět platí pouze pro omezenou třídu rámců. Je běžné omezit třídu snímků na ty, které mají relaci tranzitivní, antisymetrický, reflexní, trichotomický, nereagující, celkový, hustý nebo jejich kombinace.

Minimální axiomatická logika

Burgess nastiňuje logiku, která nevytváří žádné předpoklady o vztahu <, ale umožňuje smysluplné dedukce na základě následujícího schématu axiomu:[11]

  1. A kde A je tautologie z logika prvního řádu
  2. G(A→B) → (G.A→ GB)
  3. H (A→B) → (HA→ HB)
  4. A→ GPA
  5. A→ HFA

s následujícími pravidly odpočtu:

  1. daný A→B a A, odvodit B (modus ponens )
  2. daný tautologie A, vyvodit GA
  3. daný tautologie A, odvodit HA

Lze odvodit následující pravidla:

  1. Beckerovo pravidlo: dané A→B, odvodit TA→ TB kde T je a čas, libovolná sekvence vytvořená z G, H, F a P.
  2. Zrcadlení: daný teorém A, odvodit jeho zrcadlové prohlášení A§, který se získá nahrazením G H (a tedy F P) a naopak.
  3. Dualita: daný teorém A, odvodit jeho dvojí prohlášení A*, který se získá záměnou ∧ s ∨, G s F a H s P.

Překlad do predikátové logiky

Burgess dává Meredith překlad z příkazů v TL do výpisů v logika prvního řádu s jednou volnou proměnnou X0 (představující přítomný okamžik). Tento překlad M je definován rekurzivně takto:[12]

kde je věta se všemi variabilními indexy zvýšenými o 1 a je jednomístný predikát definovaný .

Časové operátory

Časová logika má dva druhy operátorů: logické operátory a modální operátoři [1]. Logické operátory jsou obvyklé operátory pravdivé funkce (). Modální operátory používané v lineární časové logice a logice výpočetního stromu jsou definovány následovně.

TextovýSymbolickýDefiniceVysvětleníDiagram
Binární operátory
U Until: - drží se na současné nebo budoucí pozici a - musí vydržet do této polohy. Na té pozici již nemusí držet.
R Release: zprávy -li platí až do a včetně první pozice, ve které je pravda (nebo navždy, pokud taková pozice neexistuje).
Unární operátoři
N Next: musí vydržet v dalším stavu. (X se používá synonymně.)
F Future: nakonec musí vydržet (někde na následující cestě).
G Globálně: musí vydržet celou následující cestu.
A All: musí vydržet všechny cesty počínaje aktuálním stavem.
E Exists: existuje alespoň jedna cesta začínající od aktuálního stavu kde drží.

Alternativní symboly:

  • operátor R je někdy označován PROTI
  • Operátor Ž je slabý do operátor: je ekvivalentní k

Unární operátoři jsou dobře formulované vzorce kdykoli B () je dobře tvarovaný. Binární operátory jsou dobře formulované vzorce, kdykoli B () a C () jsou dobře tvarované.

V některých logikách nelze některé operátory vyjádřit. Například, N operátor nelze vyjádřit v časová logika akcí.

Časová logika

Časová logika zahrnuje

Variace, úzce související s časovou nebo chronologickou nebo napjatou logikou, jsou modální logiky založené na „topologii“, „místě“ nebo „prostorové poloze“.[17][18]

Viz také

Poznámky

  1. ^ Vardi 2008, s. 153
  2. ^ A b C Vardi 2008, s. 154
  3. ^ Peter Øhrstrøm; Per F. V. Hasle (1995). Časová logika: od starověkých myšlenek po umělou inteligenci. Springer. ISBN  978-0-7923-3586-3. 176–178, 210
  4. ^ „Časová logika (Stanfordská encyklopedie filozofie)“. Plato.stanford.edu. Citováno 2014-07-30.
  5. ^ Walter Carnielli; Claudio Pizzi (2008). Způsoby a multimodality. Springer. str. 181. ISBN  978-1-4020-8589-5.
  6. ^ Sergio Tessaris; Enrico Franconi; Thomas Eiter (2009). Zdůvodňující web. Sémantické technologie pro informační systémy: 5. mezinárodní letní škola 2009, Brixen-Bressanone, Itálie, 30. srpna - 4. září 2009, výukové přednášky. Springer. str. 112. ISBN  978-3-642-03753-5.
  7. ^ Prior, Arthur Norman (2003). Čas a modalita: přednášky Johna Locka pro období 1955–6, přednesené na Oxfordské univerzitě. Oxford: Clarendon Press. ISBN  9780198241584. OCLC  905630146.
  8. ^ Lawford, M. (2004). „Úvod do časové logiky“ (PDF). Katedra informatiky McMaster University.
  9. ^ Goranko, Valentin; Galton, Antony (2015). Zalta, Edward N. (ed.). Stanfordská encyklopedie filozofie (Zima 2015 ed.). Výzkumná laboratoř metafyziky, Stanford University.
  10. ^ Müller, Thomas (2011). „Napjatá nebo časová logika“ (PDF). V Horsten, Leon (ed.). Společník kontinua filozofické logiky. A&C Black. str. 329.
  11. ^ Burgess, John P. (2009). Filozofická logika. Princeton, New Jersey: Princeton University Press. str. 21. ISBN  9781400830497. OCLC  777375659.
  12. ^ Burgess, John P. (2009). Filozofická logika. Princeton, New Jersey: Princeton University Press. str. 17. ISBN  9781400830497. OCLC  777375659.
  13. ^ A b Maler, O .; Nickovic, D. (2004). Msgstr "Monitorování časových vlastností spojitých signálů". doi:10.1007/978-3-540-30206-3_12.
  14. ^ https://asu.pure.elsevier.com/en/publications/timestamp-temporal-logic-ttl-for-testing-the-timing-of-cyber-phys
  15. ^ Koymans, R. (1990). "Specifikace vlastností v reálném čase s metrickou časovou logikou", Systémy v reálném čase 2(4): 255–299. doi:10.1007 / BF01995674.
  16. ^ Li, Xiao, Cristian-Ioan Vasile a Calin Belta. „Posílení učení s časovými logickými odměnami.“ doi:10.1109 / IROS.2017.8206234
  17. ^ Rescher, Nicholas (1968). "Topologická logika". Témata ve filozofické logice. str. 229–249. doi:10.1007/978-94-017-3546-9_13. ISBN  978-90-481-8331-9.
  18. ^ von Wright, Georg Henrik (1979). "Modální logika místa". Filozofie Nicholase Reschera. str. 65–73. doi:10.1007/978-94-009-9407-2_9. ISBN  978-94-009-9409-6.

Reference

Další čtení

  • Peter Øhrstrøm; Per F. V. Hasle (1995). Časová logika: od starověkých myšlenek po umělou inteligenci. Springer. ISBN  978-0-7923-3586-3.

externí odkazy