まとめ
-
クロージャ(閉包)
- リレーションの演算結果はリレーション
- 述語を組み合わせた結果は述語
-
クエリを記述する際の目標: 述語で集合から新しい集合を導出
- 述語論理と集合論は1:1で対応
述語論理とリレーショナルモデル
- リレーショナルモデルは述語論理に基づいたデータモデルでもある
- 正規化の理解に必須
命題
- ある物事について記述した文で、真か偽か問えるもの
命題論理
-
ある命題の真偽値から別の命題の真偽値を導出することに特化した学問
- 大切なのは真偽値のみ
- 他の意味を取り去るために命題を
PやQなどの記号で表現する
-
結合子
- 2つあるいは1つの命題から新たな真偽値を導出するための記号
- 複雑な命題を構築する
-
種類
- ¬(否定、NOT)
- ∧(連言、論理積、AND)
- ∨(選言、論理和、OR)
- ⊃(包含、IMP)
- ≡(同値、EQ)
- ↑(否定論理積、NAND)
- ↓(否定論理和、NOR)
- ⊻(排他的論理和)
| P | Q | ¬P | P∧Q | P∨Q | P⊃Q |
|---|---|---|---|---|---|
| T | T | F | T | T | T |
| T | F | F | F | T | F |
| F | T | T | F | T | T |
| F | F | T | F | F | T |
| P | Q | P≡Q | P↑Q | P↓Q | P⊻Q |
|---|---|---|---|---|---|
| T | T | T | F | F | F |
| T | F | F | T | F | T |
| F | T | F | T | F | T |
| F | F | T | T | T | F |
トートロジーと定理
-
トートロジー(恒真式)
- PやQなどの命題の真偽値が何であっても式全体としてつねに真
- 命題論理では、トートロジーは定理になっている
同一律 P⊃P
| P | P⊃Q |
|---|---|
| T | T |
| F | T |
排中律 P∨¬P
| P | ¬P | P∨¬P |
|---|---|---|
| T | F | T |
| F | T | T |
二重否定律 ¬¬P≡P
| P | ¬P | ¬¬P | ¬¬P≡P |
|---|---|---|---|
| T | F | T | T |
| F | T | F | T |
矛盾律 ¬(P∧¬P)
| P | ¬P | P∧¬P | ¬(P∧¬P) |
|---|---|---|---|
| T | F | F | T |
| F | T | F | T |
P∧¬Pは恒偽式
Principle of explosion (P∧¬P)⊃Q
| P | ¬P | P∧¬P | Q | (P∧¬P)⊃Q |
|---|---|---|---|---|
| T | F | F | T | T |
| T | F | F | F | T |
| F | T | F | T | T |
| F | T | F | F | T |
- 「前提が矛盾していればいかなる結論も導出できてしまう」というやつ
対偶律 (P⊃Q)⊃(¬Q⊃¬P)
| P | Q | P⊃Q | ¬Q | ¬P | ¬Q⊃¬P | (P⊃Q)⊃(¬Q⊃¬P) |
|---|---|---|---|---|---|---|
| T | T | T | F | F | T | T |
| T | F | F | T | F | F | T |
| F | T | T | F | T | T | T |
| F | F | T | T | T | T | T |
推移律 ((P⊃Q)∧(Q⊃R))⊃(P⊃R)
| P | Q | R | P⊃Q | Q⊃R | (P⊃Q)∧(Q⊃R) | P⊃R | ((P⊃Q)∧(Q⊃R))⊃(P⊃R) |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | T | F | T | F | F | F | T |
| T | F | T | F | T | F | T | T |
| T | F | F | F | T | F | F | T |
| F | T | T | T | T | T | T | T |
| F | T | F | T | F | F | T | T |
| F | F | T | T | T | T | T | T |
| F | F | F | T | T | T | T | T |
分配律1 P∧(Q∨R) ≡ (P∧Q)∨(P∧R)
| P | Q | R | Q∨R | P∧(Q∨R) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | T | F | T | T |
| T | F | T | T | T |
| T | F | F | F | F |
| F | T | T | T | F |
| F | T | F | T | F |
| F | F | T | T | F |
| F | F | F | F | F |
| P | Q | R | P∧Q | P∧R | (P∧Q)∨(P∧R) |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | T | F | T | F | T |
| T | F | T | F | T | T |
| T | F | F | F | F | F |
| F | T | T | F | F | F |
| F | T | F | F | F | F |
| F | F | T | F | F | F |
| F | F | F | F | F | F |
合同
分配律2 P∨(Q∧R) ≡ (P∨Q)∧(P∨R)
| P | Q | R | Q∧R | P∨(Q∧R) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | T | F | F | T |
| T | F | T | F | T |
| T | F | F | F | T |
| F | T | T | T | T |
| F | T | F | F | F |
| F | F | T | F | F |
| F | F | F | F | F |
| P | Q | R | P∨Q | P∨R | (P∨Q)∧(P∨R) |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | T | F | T | T | T |
| T | F | T | T | T | T |
| T | F | F | T | T | T |
| F | T | T | T | T | T |
| F | T | F | T | F | F |
| F | F | T | F | T | F |
| F | F | F | F | F | F |
合同
ド・モルガン1 ¬(P∨Q)≡¬P∧¬Q
| P | Q | ¬P | ¬Q | P∨Q | ¬(P∨Q) | ¬P∧¬Q | ¬(P∨Q)≡ ¬P∧¬Q |
|---|---|---|---|---|---|---|---|
| T | T | F | F | T | F | F | T |
| T | F | F | T | T | F | F | T |
| F | T | T | F | T | F | F | T |
| F | F | T | T | F | T | T | T |
ド・モルガン2 ¬(P∧Q)≡¬P∨¬Q
| P | Q | ¬P | ¬Q | P∧Q | ¬(P∧Q) | ¬P∨¬Q | ¬(P∧Q)≡ ¬P∨¬Q |
|---|---|---|---|---|---|---|---|
| T | T | F | F | T | F | F | T |
| T | F | F | T | F | T | T | T |
| F | T | T | F | F | T | T | T |
| F | F | T | T | F | T | T | T |
前件肯定式 ((P⊃Q)∧P)⊃Q
| P | Q | P⊃Q | (P⊃Q)∧P | ((P⊃Q)∧P)⊃Q |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | F | T |
| F | T | T | F | T |
| F | F | T | F | T |
-
【補】例
- (前提1) P⊃Q: セックスしたら出られる部屋
- (前提2) P: セックスした
- (結論) Q: 出られる
- 後件肯定は誤謬:
| P | Q | P⊃Q | (P⊃Q)∧Q | ((P⊃Q)∧Q)⊃P |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | F | T |
| F | T | T | T | F |
| F | F | T | F | T |
-
例(誤謬)
- (前提1) P⊃Q: セックスしたら出られる部屋
- (前提2) Q: 出られた
- (結論) P: セックスした
-
セックスしていないが出られるケースが存在しうる
- 実はキスでも出られる部屋かもしれない
後件否定式 ((P⊃Q)∧¬Q)⊃¬P
| P | Q | ¬P | ¬Q | P⊃Q | (P⊃Q)∧¬Q | ((P⊃Q)∧¬Q)⊃¬P |
|---|---|---|---|---|---|---|
| T | T | F | F | T | F | T |
| T | F | F | T | F | F | T |
| F | T | T | F | T | F | T |
| F | F | T | T | T | T | T |
-
【補】例
- (前提1) P⊃Q: セックスしたら出られる部屋
- (前提2) ¬Q: 出られていない
- (結論) ¬P: セックスしなかった
- 前件否定は誤謬:
| P | Q | ¬P | ¬Q | P⊃Q | (P⊃Q)∧¬P | ((P⊃Q)∧¬P)⊃¬Q |
|---|---|---|---|---|---|---|
| T | T | F | F | T | F | T |
| T | F | F | T | F | F | T |
| F | T | T | F | T | T | F |
| F | F | T | T | T | T | T |
-
例(誤謬)
- (前提1) P⊃Q: セックスしたら出られる部屋
- (前提2) ¬P: セックスしなかった
- (結論) ¬Q: 出られない
-
セックスしていないが出られるケースが存在しうる
- 実はキスでも出られる部屋かもしれない
選言的三段論法
| P | Q | ¬P | P∨Q | (P∨Q)∧¬P | ((P∨Q)∧¬P)⊃Q |
|---|---|---|---|---|---|
| T | T | F | T | F | T |
| T | F | F | T | F | T |
| F | T | T | T | T | T |
| F | F | T | F | F | T |
命題論理と公理系
- 定理には前提となる別の定理がある
- どこまでさかのぼれるの？
-
公理
- 他の定理の出発点となる定理
- 一切の前提なく正しいと認めましょう、という合意
-
公理系
- 公理の集合
-
満たすべき性質
-
無矛盾性
- 公理として定義された命題同士に矛盾のなきこと
-
完全性
- 扱うテーマにとって包括的に全体をカバーするものであること
-
- 1通りではない
-
命題論理の公理系のうち代表的なもの
- 長いので略(P.39)
-
以下、公理系を出発点とした定理証明
- 間違ってるかも
Principle of explosion
-
仮定
- P∧¬P
-
∧の除去
- P
-
∧の除去
- ¬P
-
∨の導入
- P∨Q
-
選言的三段論法
- Q
-
⊃の導入
- (P∧¬P)⊃Q
- 仮定の解消
対偶律
-
仮定1
- P
-
仮定2
- P⊃Q
-
⊃の除去
- Q
-
仮定3
- ¬Q
-
∧の導入
- Q∧¬Q
-
⊃の導入
- P⊃(Q∧¬Q)
- 仮定1を解消
-
¬の導入
- ¬P
-
⊃の導入
- ¬Q⊃¬P
- 仮定3を解消
-
⊃の導入
- (P⊃Q)⊃(¬Q⊃¬P)
- 仮定2を解消
推移律
-
仮定1
- (P⊃Q)∧(Q⊃R)
-
仮定2
- P
-
∧の除去
- P⊃Q
-
∧の除去
- Q⊃R
-
⊃の除去
- Q
-
⊃の除去
- R
-
⊃の導入
- P⊃R
- 仮定2を解消
-
⊃の導入
- ( (P⊃Q)∧(Q⊃R))⊃(P⊃R)
- 仮定1を解消
前件肯定式
-
仮定
- ((P⊃Q)∧P)
-
∧の除去
- (P⊃Q)
-
∧の除去
- P
-
⊃の除去
- Q
-
⊃の導入
- ((P⊃Q)∧P)⊃Q
- 仮定を解消
後件否定式
-
仮定
- ((P⊃Q)∧¬Q)
-
∧の除去
- (P⊃Q)
-
∧の除去
- ¬Q
-
対偶律
- (P⊃Q)⊃(¬Q⊃¬P)
-
⊃の除去
- (¬Q⊃¬P)
-
⊃の除去
- ¬P
-
⊃の導入
- ((P⊃Q)∧¬Q)⊃¬P
- 仮定を解消
選言式三段論法
-
仮定
- (P∨Q)∧¬P
-
分配律 (A)
- (P∧¬P)∨(Q∧¬P)
-
Principle of explosion (B)
- (P∧¬P)⊃(Q∧¬P)
-
同一律 (C)
- (Q∧¬P)⊃(Q∧¬P)
-
(A), (B), (C)より、∨の除去
- Q∧¬P
-
∧の除去
- Q
-
⊃の導入
- ((P∨Q)∧¬P)⊃Q
- 仮定を解消
コラム: プリミティブな演算子
-
導出規則に含まれる結合子
- ⊃
- ¬
- ∧
- ∨
- 本当にすべて必要なのか？
-
いいえ
-
上記の中では下記の組で全てを表せる
¬と∧¬と∨
- 上記にないものでは、NANDあるいはNORひとつで全てを表せる
-