勉強日記

チラ裏

理論から学ぶデータベース実践入門 ch2 述語論理とリレーショナルモデル 2/3

RDB 勉強メモ

gihyo.jp

述語論理とリレーショナルモデル(続き)

命題論理の限界と量化

  • 対象となる命題を記号として表現できる限りは十分に実践的
  • PとかQとかで表現できない問題がある
    • 集団を対象にした真偽値を問うもの
  • この村のすべての村人が正直者だというわけではない
  • この村の村人は全員誰かと友達である
  • 量化
    • 全称量化 (∀)
      • ある集団の要素のすべてがある性質を満たすか
    • 存在量化 (∃)
      • ある集団の要素にはある性質を満たすものが存在するか

量子化と述語論理

述語論理

  • 命題論理の拡張
    • 集団についての性質を記した文章を、変数・量化子・関数を用いて論理式として表現
  • 量化子
    • 前述の∀や∃
  • 関数・変数
    • 「xは誰かと友達である」をF(x)のように表現
    • xの値により真または偽を返す
    • 命題関数、あるいは述語と呼ぶ
      • だから「述語論理」

この村の村人は全員誰かと友達である

  • 上記の文章は次の論理式で表せる
∀xF(x)

この村には正直でない者がいる

  • 上記の文章は次の論理式で表せる
∃x¬F(x)

量化子とともに用いる束縛変数

∃xF(x) ∧ ∀xG(x)
  • 束縛変数
    • 上記論理式のx
    • 束縛変項とも
  • スコープは対象の論理式の中のみ
    • ∧の前後のxは意味が異なる

量化子を伴わない自由変数

  • 関数単体で見てみる
F(x) ⊃ G(x)
  • 自由変数
    • 上記のx
    • 自由変項とも
  • 上記論理式のxはいずれのxも同じ意味

述語論理と集合論

述語と集合とは等価に置き換えが可能

象は草食動物である

∀x(F(x)⊃G(x))
  • where
    • F(x): 「xは象である」
    • G(x): 「xは草食動物である」
  • すべてのxについてF(x)を評価すると、F(x)が真となるすべてのxが得られる
  • 「F(x)が真となるすべてのx」とは、すべての象を含んだ集合
  • この集合をS_Fとする
F(x)
  • は集合の要素の包含に置き換えられる
    • これも真偽値を返す
x∈S_F
  • 同様にG(x)も置き換えて
∀x(x∈S_F ⊃ x∈S_G)

集合の包含関係

  • ⊃ (包含、IMP)
P Q P⊃Q
T T T
T F F
F T T
F F T
  • P⊃Qが真となるのは
    • Pが真ならQも真
    • Pが偽ならQは真偽問わない
  • つまり、Pが偽でQが真のケースがあるということ
  • x∈S_Fが偽でx∈S_Gが真
    • 象ではないが草食動物である
      • 【補】xがシマウマであるケースとか
  • 集合の包含関係
S_F ⊆ S_G

述語論理の公理系

∀xF(x)
  • 集合で置き換え
∀x{x∈S_F}
  • S_Fをn個の要素を持つ集合だと仮定
    • 【補】有限集合だけ考えればよい
S_F := {a1, a2, ..., an}
  • 具体的な要素を代入して得られる命題と等価
F(a1)∧F(a2)∧...∧F(an)
  • 同様に
∃xF(x)
  • は下記と等価
F(a1)∨F(a2)∨...∨F(an)
  • ∀や∃は∧や∨と似た性質を持つ
  • ド・モルガン
¬∃xF(x) ≡ ∀x¬F(x)
¬∀xF(x) ≡ ∃x¬F(x)
  • 「この村のすべての村人が正直者だというわけではない」
  • 「この村には正直者でない者がいる」

述語論理の公理系の導出規則

  • p.39の公理系を拡張

∀の導入

P(c) ⊃ ∀xP(x)
  • cは任意の値
  • すべての値に対して普遍的に成り立つ規則から、全称記号を用いた表現を導出

∀の除去

∀xP(x) ⊃ P(c)

∃の導入

P(a)⊃∃xP(x)
  • P(x)を満たす定項あるいは変項aが存在すれば
    存在量子化を用いた表現の論理式を導出してよい

∃の除去

(∃xP(x)∧(P(c)⊃Q))⊃Q
  • 前提1: P(c)⊃Q
    • 任意のcについて普遍的にP(c)⊃Q
  • 前提2: ∃xP(x)
    • P(x)を満たすxが存在する
  • 結論:
    • Q
  • 【所感】前件肯定式の一般化？
    • P(x)が前件にあたる

ドメイン

  • 議論領域、領域とも
  • 「任意のc」に実際に入れてよいものの集合
    • 「この村の村人」とか

一階述語論理

  • ここまで触れてきた述語論理
  • 古典論理とも
  • リレーショナルモデルのよりどころ

二階述語論理

  • 述語の特徴を表現する述語を扱う

「xは、真となるパラメータが1つ以上存在するが、恒真ではない述語である」

  • 述語と集合とは1対1対応
  • 集合を要素にした集合を扱う論理ともいえる
  • 自己言及がある
    • 二階述語自身が二階述語の対象となりうる
  • リレーショナルモデルの守備範囲外

リレーションの真の姿

  • リレーションには対応する述語がある
    • リレーションは集合
    • 集合には1対1で対応する述語がある
  • 述語をF(t)とするとリレーションは∀tF(t)
    • tupleの意

リレーションの意味は論理演算

  • リレーションは真の命題の集合である
    • リレーション∀tF(t)の個々のタプルtは、F(t)に代入すると真になる
    • 真の命題すなわち事実
      • リレーションは事実の集合である
  • したがって、リレーション演算は論理演算である
    • 本章後半にて対応関係を確認する

閉世界仮説

  • Closed World Assumption
    • 述語に代入して真となるのは、リレーションに含まれるタプルだけ
    • 真となる命題は、すべて漏れなく、リレーションに含まれている
  • リレーションは事実のすべてを過不足なく含んでいる
  • 演算結果の新しいリレーションも、事実のすべてを過不足なく含んでいる
  • すべての問いがリレーションの演算だけで解決する

矛盾したDBは役に立たない

  • Principle of explosion
    • 矛盾からはいかなる帰結も導出できる
  • 矛盾したデータを持つリレーションから導き出された問い合わせの結果はまったく信用ならない

コラム: リレーショナルモデルの限界

  • リレーショナルモデルは述語論理(集合論)に基づく
  • その枠から外れたデータや演算を表現できない
    • 例
      • グラフ
      • 時系列データ (順序をもつ)
  • リレーショナルモデルの範疇を見極めて適用することが肝要