Темпоральна логіка

Темпоральна логіка (англ. temporal logic) в сучасній некласичній логіці — логіка, яка враховує причинно-наслідкові зв'язки в умовах часу. Використовується для опису послідовностей явищ та їх взаємозв'язку з часовою шкалою. Вона була розроблена в 1960-х Артуром Пріором на основі модальної логіки і отримала подальший розвиток у інформатиці завдяки праці лауреата Премії Тюрінга Аміра Пнуелі. В античності теорії темпоральних логік вивчали філософи мегарської школи, зокрема, Діодор Крон та стоїки.

Є два підходи темпоральної логіки, засновані на принципах здорового глузду і діалектики:

1 — «після цього» означає «внаслідок цього»;

2 — «після цього» означає «пізніше» в хронологічному сенсі.

Приклад

Розглянемо твердження: «Я голодний»:

Хоча зміст виразу не змінюється з часом, його істинність може змінитися. Твердження в конкретний момент часу може бути істинним, або хибним, але не одночасно. На противагу нетемпоральним логікам, де значення тверджень не змінюються з часом, в темпоральної логіці значення залежить від того, коли воно перевіряється. Темпоральна логіка дозволяє висловити затвердження типу «Я завжди голодний», «Я іноді голодний» або «Я голодний, поки я не поїм».

Темпоральні оператори

У темпоральній логіці буває два види операторів: логічні і модальні. Як логічні оператори зазвичай використовуються ($\neg ,\lor ,\land ,\rightarrow$). Модальні оператори, які використовуються в логіці лінійного часу і логіці дерев обчислень, визначаються наступним чином.

Текстове значення	Символьне значення	Визначення	Опис	Діаграма
Бинарні оператори
$\phi$ U $\psi$	$\phi ~{\mathcal {U}}~\psi$	${\begin{matrix}(B\,{\mathcal {U}}\,C)(\phi )=\\(\exists i:C(\phi _{i})\land (\forall j<i:B(\phi _{j})))\end{matrix}}$	Until (strong): $\psi$ повинно виконатися в деякому стані в майбутньому (можливо, в поточному), властивість $\phi$ мало виконуватися у всіх станах до позначеного (не включно).
$\phi$ R $\psi$ $\phi$ V $\psi$	$\phi ~{\mathcal {R}}~\psi$ $\phi ~{\mathcal {V}}~\psi$	${\begin{matrix}(B\,{\mathcal {R}}\,C)(\phi )=\\(\forall i:C(\phi _{i})\lor (\exists j<i:B(\phi _{j})))\end{matrix}}$	Release: $\phi$ вивільняє $\psi$, якщо $\psi$ істинно, поки не наступить момент, коли $\phi$ перший раз стане істинно (або завжди, якщо такий момент не наступить). Інакше, $\phi$ повинно хоча б раз стати істинним, поки $\psi$ не стало істинним перший раз.
Унарні оператори
N $\phi$ X $\phi$	$\circ \phi$	${\mathcal {N}}B(\phi _{i})=B(\phi _{i+1})$	NeXt: $\phi$ повинно бути істинним в стані, безпосередньо наступним за даними.
F $\phi$	$\Diamond \phi$	${\mathcal {F}}B(\phi )=(true\,{\mathcal {U}}\,B)(\phi )$	Future: $\phi$ має стати істинним хоча б в одному стані в майбутньому.
G $\phi$	$\Box \phi$	${\mathcal {G}}B(\phi )=\neg {\mathcal {F}}\neg B(\phi )$	Globally: $\phi$ має бути істинно у всіх майбутніх станах.
A $\phi$	${\mathcal {A}}\phi$	${\begin{matrix}({\mathcal {A}}B)(\psi )=\\(\forall \phi :\phi _{0}=\psi \to B(\phi ))\end{matrix}}$	All: $\phi$ повинно виконуватися на всіх гілках, що починаються з даної.
E $\phi$	${\mathcal {E}}\phi$	${\begin{matrix}({\mathcal {E}}B)(\psi )=\\(\exists \phi :\phi _{0}=\psi \land B(\phi ))\end{matrix}}$	Exists: існує хоча б одна гілка, на якій $\phi$ виконується.

Інші модальні оператори

• Оператор W, що означає Weak until: $fWg$ еквівалентно $fUg\lor Gf$

Тотожності подвійності

Подібно правилам де Моргана існують властивості подвійності для темпоральних операторів:

• $\phi ~{\mathcal {U}}~\psi =\neg (\neg \phi ~{\mathcal {V}}~\neg \psi )$
• $\neg \Diamond \phi =\Box \neg \phi$
• $\neg {\mathcal {A}}\phi ={\mathcal {E}}\neg \phi$

Темпоральні логіки часто застосовуються для вираження вимог формальної верифікації. Наприклад, властивості типу «Якщо надійшов запит, то на нього обов'язково прийде відповідь» або «Функція викликається не більше одного разу за обчислення» зручно формулювати за допомогою темпоральої логіки. Для перевірки таких властивостей використовуються різні автомати, наприклад, автомати Бюхи для перевірки властивостей, виражених логікою лінійного часу LTL.

Темпоральні логіки

Відомі такі темпоральні логіки:

• Інтервальна темпоральна логіка
• μ-числення
  • CTL *
    • Логіка лінійного часу LTL
    • Логіка дерев обчислень CTL

Джерела

• Кларк Э. М., Грамберг О., Пелед Д. Верификация моделей программ. Model Checking. М.: МЦНМО. 2002. ISBN 5-94057-054-2

Література

• Логіка часу // Філософський енциклопедичний словник / В. І. Шинкарук (гол. редкол.) та ін. — Київ : Інститут філософії імені Григорія Сковороди НАН України : Абрис, 2002. — 742 с. — 1000 екз. — ББК 87я2. — ISBN 966-531-128-X.