このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

4値の論理のベキ集合モデル

昨日話題にした4値の論理ですけど、短絡評価をしないことにして論理AND(∧)の真偽表を書いてみると:

true false indef
true true false indef
false false false false
indef indef false indef

この演算に、別な解釈を与えてみます。

一般に、集合A上に二項演算 ○:A×A→A があるとき、この二項演算を、Aのベキ集合 Pow(A) 上に持ち上げることができます。Pow(A)×Pow(A)→Pow(A)の演算 ◎ を次のように定義します。

  • X⊆A、Y⊆A に対して、X◎Y = {x○y | x∈X, y∈Y}

新しく定義した演算◎も、もとの演算と同じ記号○を使ってしまうことが多いですね(記号の乱用)。つまり、X○Y = {x○y | x∈X, y∈Y} 。典型的な例は、文字列の連接演算を、文字列集合の演算に持ち上げることです。文字列集合は形式言語理論の意味で「言語」と呼ぶので、言語の連接演算が定義できます。

さて、二元集合 {true, false} の上の二項演算∧(論理AND)を、ベキ集合に持ち上げてみます。{true, false} のベキ集合は4元集合で、{{}, {true}, {false}, {true, false}} です。いくつかの計算例を見てみると:

  • {} ∧ {true} = {}
  • {true} ∧ {false} = {true∧false} = {false}
  • {true} ∧ {true, false} = {true∧true, true∧false} = {true, false}
  • {true, false} ∧ {false} = {true∧false, false∧false} = {false, false} = {false}

次のように対応させると、演算∧は、先の4値論理とベキ集合で同じ定義になっています。

4値の論理 ベキ集合
{}
true {true}
false {false}
indef {true, false}

論理AND演算による「値」ではなくて、「値の可能性」を考えてみると次のように言えます。

  • 結果が ⊥ のときは何の値も出力されないので空集合 {}
  • 結果が true のときは出力された値の集合はシングルトンで {true}
  • 結果が false のときも出力された値の集合はシングルトンで {false}
  • 結果が indef のときは両方の可能性を保留して中断したと考えれば、可能な値の集合は {true, false}

いちおう、それらしい解釈となります。