KAOS (94) 過程ベースの仕様 (4.4.2-6)

今回は,過去を示す演算子である.引き続き教科書 1から例をとる.ただ,記号が特殊でテキストでは書きづらいので,記号は,KAOS教科書にあるものを使う.このあたりの記号の豊富さが,絵文字に仲間意識を感じるように,魅力的なところかもしれない.

「前(Previous)」演算子 ●

未来の○に対応する.

(σ, j) ⊧ ● p iff    j>0 and (σ, j – 1) ⊧ p.

下記は「前」演算子の真理値である.ゼロから1に変化する場所を示す.「次」演算子も合わせて示している.なお,真になるためには,j>0の条件があるので,最初(j=0)では,無条件で偽になる.

「(x=1)∧●(x=0)」真理値表
j 0 1 2 3 4 5 6
x 1 1 0 0 1 1 0
(x=1)∧●(x=0) F F F F T F F
(x=0)∧○(x=1) F F F T F F F

 

「以前(Has-alwasy-been)」演算子 ■

(σ, j) ⊧ ■p   iff   (σ, k) ⊧ p for all k, 0 ≤ k ≤ j.

未来の□に対応する.「ずっと,pであった」ということを意味する.

以下に例を示す.

「■ (x ≤ 3)」真理値表
j 0 1 2 3 4 5 6
x 1 2 3 4 5 6 7
■ (x ≤ 3) T T T F F F F

時刻2までは,式が成立している.

「かつて(Once)」演算子 ◆

(σ, j) ⊧ ◆p   iff   (σ, k) ⊧ p for some k, 0 ≤ k ≤ j.

「pで真あったことがある」という意味である.

「◆ (x = 4)」真理値表
j 0 1 2 3 4 5 6
x 1 2 3 4 5 6 7
◆ (x = 4) F F F T T T F

「以来(Since)」S 演算子

(σ, j) ⊧ p S q   iff   0 ≤ k ≤ j となる k があり,(σ, k) ⊧ q が成り立つ.かつ,k < i ≤ j で,全ての i において (σ, i) ⊧ p.

かつて q に出会った.それ以降は p であった.q p … p という列を考えている.

次は,(x ≤ 6) S (x = 3) の例である

「(x ≤ 6) S (x = 3)」真理値表
j 0 1 2 3 4 5 6
x 1 2 3 4 5 6 7
x ≤ 6 T T T T T T F
x = 3 F F T F F F F
(x ≤ 6) S (x = 3) F F T T T T F

「(よわい)以来(Back-to)」B 演算子

(σ, j) ⊧ p B q   iff   (σ, j) ⊧ p S q  or  (σ, j) ⊧ ■p.

基本的には,Sと同じである.ただ,q に出会わなくても良い.その場合は,p が続いていた.

ちょうど,U に対するWと同様の関係にある.

次の真理を考える.(x ≠ 4)  B  (x = 6)

「(x ≠ 4) B (x = 6)」真理値表
j 0 1 2 3 4 5 6 7 8
x 1 2 3 4 5 6 7 8 9
x ≠ 4 T T T F T T T T T
x = 6 F F F F F T F F F
(x ≠ 4) B (x = 6) T T T F F T T T T

前半の真の部分は,■ p による.後半は,p S q が機能している.

他にも過去の演算子はあるが,基本的なものは上記になる.

(nil)

Notes:

  1. Pnueli, Amir, and Zohar Manna. “The temporal logic of reactive and concurrent systems.” , 1992.

KAOS (93) 過程ベースの仕様 (4.4.2-5)

これまでの演算子を使った例である.p, q はもちろん状態を含んだ式になる.

p → ◇ q

最初 p が真ならば,いつかは q が真になる.

□ ( p → ◇ q)

先の例に対して,「以後」演算子がついている.t=0 で,pが真な場合だけではなく,pが出てくると,いつかは必ず q になるということを示している.

□◇q

どの時間でも,qの出現可能性があることを示している.

◇□q

演算子が逆のパターンである.いつか,以後ずっとqになる.

(¬q) W p

p が真になるまで ¬q が続くか,無限に¬qが続く.pが出現したときの q の真偽は不明である.

□(p →○p)

恒に式が真であるためには,次の様になる.まず,かっこの中である.条件部の p (t=i) が真であれば,○p が真の必要があり,次は p (t = i+1) が真でなくてはいけない.p が真であれば,次も p が真になるということがずっと続く.pが偽であれば,次は真であろうが偽であろうが構わない.

(nil)

KAOS (92) 過程ベースの仕様 (4.4.2-4)

演算子の続きである.

「以後(henceforth)」演算子 □

(σ, j) ⊧ □p   iff   (σ, k) ⊧ p for all k ≥ j.

これといった訳語がない.「ずっと p である」といった意味になる.

この記号は,様相論理では,「必然」であった.必然ということばは,「〜して当然」という含意もあり,その解釈はさまざまであった.時相論理における□には,そういうややこしさはない.

次に,□ (x > 3) の真理値表を考えてみる.今回も,時間経過を示す j と x を混同しないようにというのが注意である.

「□ (x > 3)」真理値表
j 0 1 2 3 4 5 6
x 1 3 2 4 3 5 4
x > 3 F F F T F T T
□ (x > 3) F F F F F T T

時間 7 以降も,x は 4 より大きいとしている.

「いつか(eventually)」演算子 ◇

(σ, j) ⊧ ◇p   iff   (σ, k) ⊧ p for some k ≥ j.

「いつかは p になる」という意味である.

様相論理では,「可能」という意味であった.

「◇ (x = 4)」真理値表
j 0 1 2 3 4 5 6
x 1 2 3 4 5 6 7
x = 4 F F F T F F F
◇ (x = 4) T F T T F F F

「まで」U (until) 演算子

(σ, j) ⊧ p U q   iff   k ≥ j となる k があり,(σ, k) ⊧ q が成り立つ.かつ,全ての i において,j ≤ i < k で,(σ, i) ⊧ p.

どこかで q に出会う.それまで p が続く.p … p q という列を考えている.

次は,(3 ≤ x ≤ 5) U ( x = 6) の例である

「(3 ≤ x ≤ 5) U ( x = 6) 」真理値表
j 0 1 2 3 4 5 6
x 1 2 3 4 5 6 7
3 ≤ x ≤ 5 F F T T T T F
x = 6 F F F F F T F
(3 ≤ x ≤ 5) U ( x = 6) F F T T T T F

「(よわい)まで」W (Unless, Waiting-for) 演算子

(σ, j) ⊧ p W q   iff    (σ, j) ⊧ p U q or (σ, j) ⊧ □p.

基本的には,Uと同じである.ただ,q に出会わなくても良い.その場合は,p が続く.

訳語が難しく,ここでは,「(よわい)まで」とした.

次の真理を考える.[(3 ≤ x ≤ 5)  ∨  (x ≥ 8)] W ( x = 6)

「[(3 ≤ x ≤ 5)  ∨  (x ≥ 8)] W ( x = 6) 」真理値表
j 0 1 2 3 4 5 6 7 8
x 1 2 3 4 5 6 7 8 9
(3 ≤ x ≤ 5) ∨ (x ≥ 8) F F T T T T F T T
x = 6 F F F F F T F F F
[(3 ≤ x ≤ 5) ∨(x ≥ 8)] W ( x = 6) F F T T T T F T T

表をおいかけるのは面倒だが,対象とする命題の真偽が,時間によって変わるのが実感できる.

なお,ここまでにでてきた演算子は,お気づきの通り,「未来」に関するものである.次回は,幾つかの例をみてから,簡単に過去の時制演算子を見ることにしたい.

(nil)