時相論理

時相論理とは、時間との関連で問題を理解し表現するための規則と表記法の体系である。時相論理では、「私はいつも腹ペコだ」、「私はそのうち腹ペコになる」、「私は何かを食べるまで腹ペコだろう」といった文を表現できる。1950年代末にアーサー・プライアーが提唱した様相論理に基づいた時相論理を特に時制論理と呼ぶことがある。ハンス・カンプが重要な業績を残した。その後、そこから発展し、アミール・プヌーリら計算機科学者や論理学者が研究を進めた。

時相論理はシステムのハードウェアやソフトウェアの要求仕様を記述する方法として形式的検証で利用される。例えば、「要求が発生したら常にリソースへのアクセスがそのうちに承認される。ただし、決して2つの要求を同時に承認してはならない」といった文章は時相論理で表せる。

1. 概要
-----

「私は腹ペコだ」という文を考えてみよう。この文の意味は時間経過に関わらず一定であるが、その真偽は時間経過によって変化する。あるときは真だし、またあるときは偽である。しかし、同時に真でもあり偽でもあるということはありえない。時相論理では、時と共に真理値の変化する文を扱う。非時相論理では、時間経過によって真理値が変化しない文しか扱えない。

時相論理は常に時系列について判断する能力を有する。線形時間論理と呼ばれるものはこの種の推論に限定されている。分岐論理は複数の時系列を判断できる。これは予測不能な挙動を示す環境を前提とする。さらに言えば、分岐論理では「私が永遠に腹ペコのままでいる可能性がある」といった文が表現可能である。他にも「私がもう腹ペコではなくなる可能性がある」という文も表現可能である。「私」が食べ物にありつけるかどうか不明ならば、これらの文はどちらも真である。

2. 歴史
-----

アリストテレスは主に三段論法を研究したが、現代の時相論理のような研究もしており、一階時相二値論理のような形式を部分的に検討したことがある。特に不確定な未来の事象を扱う際、アリストテレスは二値の意味論を適用できないと考え、例えば「明日、海戦が勃発するだろう」といった文の真偽を現時点で決定できないとしたVardi。

その後数千年間、ほとんど発展は見られなかった。19世紀、チャールズ・サンダース・パースは次のように記している。

アーサー・プライアーは自由意志や予定説といった哲学的問題を検討した。彼の妻によれば、彼が最初に時相論理を定式化したのは1953年のことだという。1955年から56年にかけてオックスフォード大学でそれについて講義をし、1957年には //Time and Modality// を出版。その中で2つの時相接続子FとPを備えた命題様相論理を説明している。この先駆的取り組みで、プライアーは時間を線型なものとみなしている。しかし1958年、ソール・クリプキはプライアーへの手紙で、その仮定は不当だと指摘した。計算機科学での同様な考え方を予示しつつ、プライアーは熟慮の上それを採用し2つの分岐時間の理論を考案、"Ockhamist" と "Peircean" と名付けたVardidate=2011年4月}}。1958年から1965年にかけて、プライアーは Charles Leonard Hamblin と共同で時相論理について研究した。1967年、時相論理に関する研究の集大成として //Past, Present, and Future// を出版。その2年後に亡くなった。

ハンス・カンプは1968年の博士論文で二値の時相作用素 //Since// と //Until// を導入し、その論文で時相論理と一階述語論理を関連付ける重要な考察も行い、それが「カンプの定理」と呼ばれるようになったVardi。

形式的検証では、線形時相論理と計算木論理が競っている。後者のほうが分岐を扱えるぶんだけ前者よりも効果的であると指摘されることがある。エマーソンと Lei は、いかなる線形論理も複雑性を変えずに分岐論理に拡張可能であることを示した。

3. 時相作用素
--------

時相論理では2種類の作用素を使用する。論理作用素と様相作用素である[1]。論理作用素は一般的な真理関数作用素である。線形時相論理や計算木論理で使用される様相作用素を以下に示す。

他の表現:

作用素 R は V で表記されることがある。
作用素 W は //weak until// を意味する。 は と等価である。B が論理式であれば、単項作用素は全て論理式である。B と C が論理式であれば、二項作用素は全て論理式である。

論理体系によっては一部の作用素は表現できない。例えば、Temporal Logic of Actions では N 作用素は表現できない。

4. 様々な時相論理
----------

インターバル時相論理 
ヘネシー・ミルナー論理 
計算木論理 
線形時相論理 
Metric Interval Temporal Logic 
Signal Temporal Logic  時相論理と密接に関連する論理として、トポロジーや場所や空間的位置を扱う様相論理がある。

5. 脚注
-----

6. 参考文献
-------

Mordechai Ben-Ari, Zohar Manna, Amir Pnueli: The Temporal Logic of Branching Time. POPL 1981: 164-176
Amir Pnueli: The Temporal Logic of Programs FOCS 1977: 46-57
Venema, Yde, 2001, "Temporal Logic," in Goble, Lou, ed., //The Blackwell Guide to Philosophical Logic//. Blackwell.
E. A. Emerson and C. Lei, modalities for model checking: branching time logic strikes back, in //Science of Computer Programming// 8, p 275-306, 1987.
E.A. Emerson, Temporal and modal logic, //Handbook of Theoretical Computer Science//, Chapter 16, the MIT Press, 1990
editor=Orna Grumberg, Helmut Veith [2]

7. 関連文献
-------

8. 関連項目
-------

オートマトン
チョムスキー階層
状態遷移系
様相論理

9. 外部リンク
--------

[3] by Yde Venema, formal description of syntax and semantics, questions of axiomatization. Treating also Kamp's dyadic temporal operators 
[4] by Ian Hodkinson, including a formal description of first-order temporal logic
[5]
[6] is a powerful free model checker, LTL checker, simulator and refinement checker for CSP and its extensions .