計算木論理

計算木論理（けいさんきろんり、Computational Tree Logic、CTL）は、分岐時相論理の一種である。その時間モデルでは未来は決定されておらず木構造のように分岐している。未来の複数の経路のうちの1つが実際に現実の経路となる。
文法.
formula_1
ここで、p は原子項である。A は「すべての経路について; along All Paths」（必然的に）を表し、E は「少なくとも1つの経路が存在し; along at least there Exists one path」（時には）を表す。例えば、以下はCTLの論理式である。
formula_2
しかし、以下はCTLの論理式ではない。
formula_3
この文字列の問題点は、U に前置されるのが必ず A か E でなければならないという構文規則を守っていない点である。
CTL は一階述語論理の語彙を構成要素として利用し、それにさらに時相の様相作用素を交えた論理式を生成する。
作用素.
論理作用素.
論理作用素は formula_4 や formula_5 といった一般的なものである。その他にブーリアンの定数 true と false も使用することがある。
時相作用素.
時相作用素には以下のものがある:
CTL* では、時相作用素は自由に混合できる。CTL では作用素は上記のように2つにグループ分けされ、経路作用素と状態作用素の組み合わせだけが可能である。後述の例を参照されたい。
作用素の最小セット.
CTL には作用素の最小セットがある。全てのCTLの論理式は、この最小セットだけを使った論理式に書き換え可能である。これはモデル検査の際に便利である。最小セットの例として {false, formula_26, EG, EU, EX} がある。
以下に時相作用素に関する書き換えの例を示す:
例.
P の意味が「私はチョコレートが好きだ」であるとし、Q の意味が「外は暖かい」であるとする。
他の論理との関係.
計算木論理(CTL)は線形時相論理(LTL)と同様 CTL* のサブセットである。CTL と LTL は共通部分もあるが等価ではない。