Temporální logika

Temporální logika je široké spektrum formálních systémů, jejichž společným cílem je formalizovat a analyzovat věty obsahující časové (temporální) komponenty jako někdy, vždy či dokud. Kromě původních, spíše lingvistických a filosofických motivací nachází temporální logika od poslední třetiny dvacátého století uplatnění i v informatice a umělé inteligenci.

Úvod

Temporální logika má svůj počátek v díle Arthura Priora.^{[pozn. 1]} Jak už naznačuje její název, jde o formální vědu zabývající se studiem modelů času. Jejím cílem není odhalit ty charakteristiky, které „skutečně" času náleží, naopak podobně jako jiná odvětví matematické logiky ji lze spíše chápat jako nástroj na popis a zpřehlednění struktur, které si s během času a problémem jeho zachycení lze představit. Oproti běžnému úzu ve studiu modálních logik postupoval historický vývoj jednotlivých temporálních logik od zamýšlených interpretací (modelů, struktur) k formálním systémům, a nikoli naopak.

Z hlediska času jako takového nachází temporální logika uplatnění například ve filosofických diskuzích.^{[pozn. 2]} Už však motivace jejího vzniku byly především lingvistického rázu,^{[pozn. 3]} totiž objasnit strukturu temporálních forem přirozeného jazyka, případně nabídnout pro tyto formy adekvátní sémantiku. To se například týká temporálních adverbií nebo slovesných časů. Na konci šedesátých a v sedmdesátých letech dvacátého století se začaly objevovat aplikace některých systémů v oblasti umělé inteligence^{[pozn. 4]} a v informatice.^{[pozn. 5]} To vedlo k dalšímu rozšiřování již tak velkého množství různých teorií co do šířky (například obohacování syntaxe), hloubky (studium logických vlastností jako úplnost, rozhodnutelnost, definovatelnost, kvantitativní aspekty) a spektra záběru.

Priorova výroková temporální logika TL

Výrokovou verzi Minimální temporální logiky ${\displaystyle K_{t}}$ lze syntakticky chápat jako rozšíření klasické výrokové logiky KVL o dva unární modální operátory ${\displaystyle G}$ a ${\displaystyle H}$. Interpretace výroku ${\displaystyle Gp}$ je „vždy v budoucnosti p”, interpretace ${\displaystyle Hp}$ je „vždy v minulosti p”. Podobně jako v modální logice s operátorem ${\displaystyle \Box }$ mají i ${\displaystyle G}$ a ${\displaystyle H}$ svoje duální verze ${\displaystyle F}$ a ${\displaystyle P}$, „někdy v budoucnosti” a „někdy v minulosti”.^[1] Ze sémantického hlediska lze ${\displaystyle K_{t}}$ také chápat jako zjemnění KVL, totiž tak, že hodnota formule ${\displaystyle \varphi }$ se relativizuje vzhledem k časovému okamžiku ${\displaystyle t}$. Sémantika klasické logiky je v sémantice ${\displaystyle K_{t}}$ zahrnuta v tom smyslu, že čistě výrokové formule, které neobsahují temporální operátory, se vyhodnocují lokálně.

Syntax a sémantika

Nechť ${\displaystyle L_{t}}$ značí jazyk KVL obohacený o operátory ${\displaystyle G}$ a ${\displaystyle H}$. Jejich duály ${\displaystyle P}$ a ${\displaystyle F}$ jsou definovány následovně:

${\displaystyle {\begin{aligned}P\varphi &\equiv \neg H\neg \varphi \\F\varphi &\equiv \neg G\neg \varphi \end{aligned}}}$

Interpretaci formulí ${\displaystyle L_{t}}$ tvoří standardní sémantika modálních logik, kripkovské rámce, které se v temporální logice nazývají časové rámce. Jde o dvojici ${\displaystyle (T,R)}$, z níž ${\displaystyle T}$ je neprázdná množina časových okamžiků a ${\displaystyle R}$ je binární relace, intuitivně ${\displaystyle R(t_{1},t_{2})}$ značí tvrzení „${\displaystyle t_{2}}$ následuje po ${\displaystyle t_{1}}$”.

Pro temporální logiku je tedy zamýšlená interpretace relace ${\displaystyle R}$ ostré (částečné) uspořádání ${\displaystyle <}$, u minimální logiky ${\displaystyle K_{t}}$ se však na ${\displaystyle R}$ žádná omezení nekladou. Ohodnocení proměnných je funkce ${\displaystyle e:(Var,T)\rightarrow \{0,1\}}$, tedy každé dvojici ${\displaystyle (atom,vrchol)}$ se přiřadí hodnota True ci False. Model ${\displaystyle M}$ nad rámcem ${\displaystyle (T,R)}$ je trojice ${\displaystyle (T,R,e)}$ pro nějaké ${\displaystyle e}$.

Formální sémantiku temporálních operátorů tvoří následující dvě klauze (hodnota formule se počítá vůči modelu ${\displaystyle M}$ a vrcholu ${\displaystyle t}$):

${\displaystyle {\begin{aligned}M,t\models H\varphi \ \Leftrightarrow \ \forall t'&<t\ (M,t'\models \varphi )\\M,t\models G\varphi \ \Leftrightarrow \ \forall t'&>t\ (M,t'\models \varphi )\end{aligned}}}$

Tvrzení ${\displaystyle M,t\models \varphi }$ značí, že ${\displaystyle \varphi }$ je splněna v ${\displaystyle t}$ ohodnocením ${\displaystyle e}$. Definice platnosti v modelu, rámci a třídě rámců je následující: ${\displaystyle \varphi }$ platí v ${\displaystyle M}$ právě tehdy, když ${\displaystyle \varphi }$ je splněna v každém ${\displaystyle t}$, formule ${\displaystyle \varphi }$ platí v ${\displaystyle T}$ právě tehdy, když ${\displaystyle \varphi }$ platí v každém modelu nad ${\displaystyle T}$, a formule ${\displaystyle \varphi }$ platí ve třídě rámců ${\displaystyle C}$ právě tehdy, když ${\displaystyle \varphi }$ platí v každém ${\displaystyle T\in C}$.

Definovatelnost

Definice platnosti ve třídě časových rámců umožňuje zkoumat, které třídy rámců jsou „vydělitelné" pomocí některé formule ${\displaystyle L_{t}}$, případně porovnávat expresivitu jazyka prvořádové logiky a jazyka ${\displaystyle L_{t}}$ logiky temporální. Temporální formule ${\displaystyle \varphi }$ definuje (charakterizuje) třídu rámců ${\displaystyle C}$, pokud ${\displaystyle \varphi }$ platí právě v každém rámci ${\displaystyle T}$ ve třídě ${\displaystyle C}$. Lze se například ptát, zda existují temporální formule charakterizující částečně uspořádané rámce, lineární rámce, hustě uspořádané lineární rámce, diskrétně uspořádané lineární rámce (jednoznačný následník a předchůdce každého bodu), shora neomezené rámce (každý bod má následníka), dobře uspořádané rámce, úplně uspořádané rámce, a další. Existují prvořádové vlastnosti, které nejsou vyjádřitelné temporální formulí. Jako příklady lze vzít antireflexivitu a antisymetrii. Na druhou stranu existují i vlastnosti rámců definovatelné temporální formulí, které nejsou vyjádřitelné jazykem prvořádové logiky. Důležité příklady jsou spojitost a dobré uspořádání.^[2]

Standardní překlad, axiomatizace, úplnost

Nechť ${\displaystyle L_{t}=\{\neg ,\wedge ,H,G,\bot \}}$. Minimální logiku ${\displaystyle K_{t}}$ lze přeložit do klasické predikátové logiky s rovností. Nechť její jazyk ${\displaystyle L_{p}}$ obsahuje jeden binární predikát ${\displaystyle R}$ a spočetně mnoho unárních predikátů ${\displaystyle P_{1},P_{2},P_{3},\dots }$ Potom lze nadefinovat standardní překlad ${\displaystyle sp}$ z jazyka ${\displaystyle L_{t}}$ do ${\displaystyle L_{p}}$ následovně:

${\displaystyle {\begin{aligned}sp(p_{i})&=P_{i}(x)\\sp(\bot )&=\bot \\sp(\neg \varphi )&=\neg sp(\varphi )\\sp(\varphi \wedge \psi )&=sp(\varphi )\wedge sp(\psi )\\sp(H\varphi )&=\forall y(yRx)\rightarrow st(\varphi _{y}(x))\\sp(G\varphi )&=\forall y(xRy)\rightarrow st(\varphi _{y}(x))\end{aligned}}}$

Proměnná ${\displaystyle x}$ symbolizuje aktuální stav věcí (přítomnost) a zápis ${\displaystyle \varphi _{y}(x)}$ značí substituci proměnné ${\displaystyle x}$ za všechny volné výskyty ${\displaystyle y}$ ve ${\displaystyle \varphi }$. Tímto způsobem lze každou formuli temporálního jazyka ${\displaystyle L_{t}}$ přeložit do prvořádové logiky.^[3] Ačkoli je studium temporálních logik primárně motivováno strukturami zamýšlenými k popisu, například přirozenými ${\displaystyle \mathbb {N} }$ či racionálními ${\displaystyle \mathbb {Q} }$ čísly, jako u všech ostatních logik je k dispozici i deduktivní (axiomatická) stránka. Minimální temporální logika ${\displaystyle K_{t}}$ má kromě vhodných výrokových axiomů následující dvě temporální obdoby modálního axiomu ${\displaystyle K}$, dva axiomy stanovující dualitu operátorů ${\displaystyle G}$ a ${\displaystyle H}$, a nakonec tranzitivitu ${\displaystyle G}$ (a tedy i ${\displaystyle H}$):

${\displaystyle {\begin{aligned}G(\varphi \rightarrow \psi )&\rightarrow (G\varphi \rightarrow G\psi )\\H(\varphi \rightarrow \psi )&\rightarrow (H\varphi \rightarrow H\psi )\\\varphi &\rightarrow GP\varphi \\\varphi &\rightarrow HF\varphi \\G\varphi &\rightarrow GG\varphi \\\end{aligned}}}$

Kromě pravidla modus ponens (MP) se přidají ještě dvě odvozovací pravidla, obdoby necesitace z modálních logik:

${\displaystyle {\begin{aligned}\vdash \varphi &\Rightarrow \,\,\,\vdash G\varphi \\\vdash \varphi &\Rightarrow \,\,\,\vdash H\varphi \end{aligned}}}$

${\displaystyle K_{t}}$ je silně úplná vůči všem časovým rámcům. Důkaz je standardní jako u běžných modálních logik, konstruuje se tzv. kanonický model jakožto protipříklad na danou dvojici ${\displaystyle (\Gamma ,\varphi )}$ takovou, že ${\displaystyle \Gamma \not \vdash \varphi }$. Tuto základní větu o úplnosti lze zesílit na úplnost vůči všem antisymetrickým rámcům.^[4] Důsledek tohoto zesílení je, že neexistuje temporální formule charakterizující právě antisymetrické rámce.

Rozšíření a varianty

Rozšíření TL na lineárních rámcích

Ostré lineární (totální) uspořádání ${\displaystyle <}$ je antireflexivní a tranzitivní relace taková, že každé dva objekty jsou srovnatelné, tj. ${\displaystyle \forall x,y(x<y\vee y<x)}$. Ovšem ani tato vlastnost, ani antireflexivita nejsou vyjádřitelné jazykem ${\displaystyle L_{t}}$ . K zachycení žádoucích struktur jako ${\displaystyle \mathbb {N} }$, ${\displaystyle \mathbb {Q} }$ nebo ${\displaystyle \mathbb {R} }$ se využije následující vlastnosti, která je temporálně charakterizovatelná:

Binární relace ${\displaystyle R}$ se nevětví do budoucnosti, pokud ${\displaystyle \forall x,y,z(xRy\wedge xRz\rightarrow yRz\vee y=z\vee zRy)}$, relace ${\displaystyle R}$ se nevětví do minulosti, pokud ${\displaystyle \forall x,y,z(zRx\wedge zRx\rightarrow yRz\vee z=y\vee zRy)}$, a ${\displaystyle R}$ se nevětví, pokud se nevětví do budoucnosti ani do minulosti.

Podmínka, že se struktura nevětví, například nevylučuje seriální lineární přímky. Výhoda však je, že tuto vlastnost lze temporálně vyjádřit následující formulí:

${\displaystyle (F\varphi \rightarrow G(\varphi \vee F\varphi \vee P\varphi ))\wedge (P\varphi \rightarrow H(\varphi \vee F\varphi \vee P\varphi ))}$

Logika ${\displaystyle K_{t}}$ spolu s tímto axiomem se někdy nazývá ${\displaystyle Lin}$ a tento systém je silně úplný vůči všem lineárním rámcům.^[5] Nabízí se také možnost rozšířit ho o další axiomy, které tyto rámce blíže specifikují. Můžeme požadovat, aby tyto struktury byly hustě či diskrétně uspořádané, aby měly či neměly koncové body, nebo například aby byly Dedekindovsky úplné, tedy aby neobsahovaly „mezery”. Všechny tyto varianty lze vyjádřit jazykem ${\displaystyle L_{t}}$ a ukazuje se, že dané axiomy věrně popisují zamýšlené interpretace.

Racionální čísla ${\displaystyle (\mathbb {Q} ,<)}$ jsou strukturálně spočetné a husté lineární uspořádání bez koncových bodů. Přidáme-li k ${\displaystyle Lin}$ axiomy charakterizující hustotu ${\displaystyle GG\varphi \rightarrow G\varphi }$ a neexistenci nejmenšího ${\displaystyle P\top }$ a největšího ${\displaystyle F\top }$ bodu, dostaneme logiku ${\displaystyle Q}$. Tato logika je silně úplná vůči všem hustě uspořádaným lineárním rámcům bez koncových bodů. Poslední požadovaná vlastnost, spočetnost, není vyjádřitelná temporálně ani prvořádově. Avšak ze standardního důkazu věty o úplnosti vyjde spočetný protipříklad, neboť jazyk ${\displaystyle L_{t}}$ je také spočetný. A jelikož každé každé spočetné a husté lineární uspořádání bez koncových bodů je izomorfní se strukturou ${\displaystyle (\mathbb {Q} ,<)}$ racionálních čísel, logika ${\displaystyle Q}$ je silně úplná dokonce vůči této struktuře.^[6]

Reálná čísla ${\displaystyle (\mathbb {R} ,<)}$ jsou husté a úplné uspořádání bez koncových bodů, které navíc obsahuje ${\displaystyle \mathbb {Q} }$ jako hustě vnořenou podmnožinu. Úplnost uspořádání nelze vyjádřit jazykem prvořádové logiky, ale lze ukázat, že v ${\displaystyle L_{t}}$ ji charakterizuje následující formule (kde ${\displaystyle \Box \varphi }$ je zkratka za formuli ${\displaystyle \varphi \wedge G\varphi \wedge H\varphi }$, intuitivně tedy nutnost jako platnost všude):

${\displaystyle \Box (G\varphi \rightarrow PG\varphi )\rightarrow (G\varphi \rightarrow H\varphi )}$

Logika ${\displaystyle Q}$ rozšířena o tento axiom se nazývá ${\displaystyle R}$ a je silně úplná vůči všem hustým a spojitým uspořádáním bez koncových bodů. Toto tvrzení lze opět zesílit do té podoby, že ${\displaystyle R}$ je silně úplná vůči struktuře ${\displaystyle (\mathbb {R} ,<)}$.^[7]

Diskrétně uspořádaná množina je taková, že každý její prvek (kromě případného maxima a minima) má bezprostředního předchůdce a následníka. Zamýšlená struktura odpovídající spočetnému a diskrétnímu lineárnímu uspořádání bez koncových bodu je ${\displaystyle (\mathbb {Z} ,<)}$, struktura celých čísel. Existenci bezprostředního předchůdce lze vyjádřit formulí ${\displaystyle (\varphi \wedge G\varphi )\rightarrow PG\varphi }$, existenci bezprostředního následníka formulí ${\displaystyle (\varphi \wedge H\varphi )\rightarrow FH\varphi }$. Logika ${\displaystyle Lin+F\top +P\top }$ spolu s těmito dvěma axiomy tvoří logiku diskrétního času ${\displaystyle D}$, která je silně úplná vůči všem diskrétním lineárním rámcům bez koncových bodů. Avšak toto tvrzení oproti předchozím příkladům nelze zesílit na silnou úplnost vůči jedné konkrétní struktuře reprezentující tuto třídu uspořádání, tedy ${\displaystyle (\mathbb {Z} ,<)}$.^[8]

Varianty temporálních logik

Existuje mnoho systémů, jejichž základ tvoří původní Priorova minimální temporální logika, a které ji tak či onak rozšiřují. Jeden přístup, ilustrovaný v následující sekci, je fixovat strukturu, která tvoří zamýšlenou interpretaci daného systému, a rozšířit ${\displaystyle L_{t}}$ o další symboly a zvýšit tím jeho expresivitu. Jiná možnost je zobecnit uvažované struktury i na nelineární částečná uspořádání. Další se potom týká zobecnění vůbec základních entit, s nimiž temporální logika pracuje, totiž časových jednotek. Původní motivace těchto tří přístupů, které jsou krátce představeny níže, pocházejí primárně z informatiky a filosofie.

Výroková lineární temporální logika LTL

Jedno významné rozšíření Priorovy minimální logiky, které našlo velké uplatnění v informatice, je takzvaná Lineární temporální logika ${\displaystyle LTL}$. Hlavní motivace stojící za jejím vznikem je hledání vhodného formalismu pro specifikaci a verifikaci korektnosti (potenciálně nekonečných) reaktivních systémů.^{[pozn. 6]} Vzhledem k této aplikaci se jako podkladová struktura uvažuje především dopředu neomezené, diskrétní a reflexivní lineární uspořádání s počátečním stavem. To odpovídá struktuře ${\displaystyle (\mathbb {N} ,\leq )}$ přirozených čísel, kde ${\displaystyle \leq }$ je reflexivní totální uspořádání.

Základní myšlenka se týká rozšíření jazyka ${\displaystyle L_{t}}$ o dva operátory, unární next time ${\displaystyle X}$ a binární until ${\displaystyle U}$. Intuitivně ${\displaystyle Xp}$ značí tvrzení „v příštím stavu ${\displaystyle p}$”, formuli ${\displaystyle p\,Uq}$ lze číst jako „${\displaystyle p}$, dokud ${\displaystyle q}$”. Zbytek syntaxe tvoří jazyk ${\displaystyle L_{t}}$. Je-li ${\displaystyle x\in \mathbb {N} }$ a ${\displaystyle v}$ ohodnocení atomických formulí na ${\displaystyle \mathbb {N} }$, lze sémantiku těchto operátorů formálně zachytit následujícími formulemi:

${\displaystyle {\begin{aligned}&v,x\models X\varphi \ \ \ \Leftrightarrow \ v,s(x)\models \varphi \\\\&v,x\models \varphi \,U\psi \Leftrightarrow \exists j\,(s^{j}(x)\models \psi \wedge \forall i<j(s^{i}(x)\models \varphi )),\end{aligned}}}$

kde ${\displaystyle s^{k}(x)}$ značí ${\displaystyle k}$-tého následníka ${\displaystyle x}$. Temporální operátory ${\displaystyle G}$ a ${\displaystyle H}$ (případně ${\displaystyle F}$ a ${\displaystyle P}$ ) jsou nad ${\displaystyle (\mathbb {N} ,\leq )}$ vyjádřitelné pomocí until, například ${\displaystyle Fp}$ lze zapsat jako ${\displaystyle p\,U\,\top }$, ale until jazykem ${\displaystyle L_{t}}$ vyjádřitelné není. Jako příklad tvrzení formalizovatelného pomocí until lze vzít věty typu “pokud ${\displaystyle p}$, pak ${\displaystyle q}$ dokud ${\displaystyle r}$”. Tedy například větu „nastane-li stav pohotovosti, je spuštěn alarm dokud nebezpečí nepomine”^{[pozn. 7]} lze zapsat jako

${\displaystyle G(nebezpeci\rightarrow (alarm\,U\,bezpeci))}$

Nelineární uspořádání

Podmínka, že minulost plně určuje veškerou budoucnost, není samozřejmá. Z hlediska modelování toku času dává dobrý smysl uvažovat i obecnější struktury, které umožňují větvení do budoucnosti, a tedy otevírají cestu budoucím alternativám. Tato základní úvaha stojí za logikami, jejichž modely tvoří stromové struktury. Podle zamýšlené interpretace formule ${\displaystyle Fp}$ na těchto strukturách, „v jakékoli možné budoucnosti ${\displaystyle p}$” a „v reálné budoucnosti ${\displaystyle p}$” se odlišují dva základní přístupy k logikám „větvícího času” (branching-time logic), Peircův a Ockhamův.

První interpretace „někdy v budoucnosti ${\displaystyle p}$” kvantifikuje přes všechny možné budoucnosti, reprezentované na dané struktuře maximálními větvemi. Jde tedy o druhořádovou definici zachycující ideu, že nezávisle na tom, co se stane, ${\displaystyle p}$ bude platit.

Ockhamova interpretace naproti tomu relativizuje hodnotu formule navíc vůči jedné konkrétní větvi reprezentující realitu. Takto lze formálně zachytit tu ideu, že hodnota formule závisí jak na přítomnosti, tak na té budoucnosti, která je fixována.^[9]

Interval jako základní pojem

Časové body jako primitivní entity lze napadat z různých pohledů. Zaprvé jde o velmi abstraktní objekty, se kterými nemáme přímou zkušenost. Jiný způsob kritiky jde vést tím směrem, že některé temporální vlastnosti typicky nejsou připisovány fixním okamžikům, ale intervalům (periodám). Dvě události se například mohou překrývat, tedy mohou mít společný průnik, který ale nemusí být pojatý diskrétně jako množina bodů.

Zatřetí lze odmítnutí reprezentace času jako sestávajícího z množiny diskrétních bodů motivovat různými typy paradoxů, ze kterých patrně nejslavnějším je Zenonův paradox letícího šípu. Předpokládáme-li, že se čas skládá z množiny nerozlehlých okamžiků, pak pokud se fixuje libovolný takový moment, šíp se nehýbe. Souhrn těchto okamžiků, v jejichž rámci pohyb neexistuje, neboť nemají žádnou extenzi, pohybu vzniknout nedá. Tento argument má mít za cíl ukázat, že pohyb neexistuje. Jeden z jeho podstatných předpokladů je však to, že tok času je tvořen množinou neextenzivních okamžiků.

Tyto (a jiné) úvahy stojí za vznikem přístupů k modelování času, které za základní jednotky berou intervaly (periody). Nabízejí se dvě možnosti. Jedna je chápat intervaly sice formálně jako odvozené pomocí dvou hraničních bodů (t.j. interval ${\displaystyle I}$ na lineární množině ${\displaystyle S}$ lze zapsat jako ${\displaystyle I=(i,j)}$, kde ${\displaystyle i}$ a ${\displaystyle j}$ jsou prvky ${\displaystyle S}$), avšak pracovat s těmito intervaly jako objekty per se. Druhá možnost je vzít za prvky podkladové množiny přímo intervaly se souborem relevantních vztahů. Příklady takových vztahů, které lze mezi intervaly uvažovat, jsou precedence, inkluze nebo překrývání (overlapping).^[10]

Odkazy

Poznámky

Reference

Související články

• Matematická logika
• Modální logika
• Lingvistika
• Informatika

Externí odkazy

• Obrázky, zvuky či videa k tématu Temporální logika na Wikimedia Commons