2014 年度 情報論理学 第 10 回講義
2014 年 7 月 1 日 (火)
青戸等人 (東北大学 電気通信研究所)
目次
- 述語論理式の同値式と 同値変形
- 述語論理式の省略記法
- 述語論理の自然演繹体系 (1): ∀ の推論
重要な同値式 (1)
命題論理の場合と 同様， 以下の同値式が成立す る ．
A∧A∼
= A, A ∨ A ∼
=A
A∧B ∼
= B ∧ A, A ∨ B ∼
=B∨A
(A ∧ B) ∧ C ∼
= A ∧ (B ∧ C),
(A ∨ B) ∨ C ∼
= A ∨ (B ∨ C)
分配律
A ∧ (B ∨ C) ∼
= (A ∧ B) ∨ (A ∧ C),
A ∨ (B ∧ C) ∼
= (A ∨ B) ∧ (A ∨ C)
吸収律 A ∧ (A ∨ B) ∼
= A, A ∨ (A ∧ B) ∼
=A
ド ・ モ ルガン の法則
¬(A ∧ B) ∼
= (¬A) ∨ (¬B)
¬(A ∨ B) ∼
= (¬A) ∧ (¬B)
巾等律
交換律
結合律
1
二重否定の法則
¬(¬A) ∼
=A
対偶
A→B∼
= (¬B) → (¬A)
含意の法則
A→B∼
= (¬A) ∨ B
⊥ 規則/⊤ 規則
A ∧ (¬A) ∼
= ⊥, A ∨ (¬A) ∼
=⊤
¬⊤ ∼
= ⊥, ¬⊥ ∼
=⊤
A∧⊥∼
= ⊥, A ∧ ⊤ ∼
=A
A∨⊥∼
=⊤
= A, A ∨ ⊤ ∼
A→⊥∼
= ¬A, ⊤ → A ∼
=A
2
重要な同値式 (2)
束縛の交換
∀x ∀y A ∼
= ∀y ∀x A
束縛の分配
∀x (A ∧ B) ∼
= ∀x A ∧ ∀x B
ド ・ モ ルガン の法則
¬∀x A ∼
= ∃x ¬A
∃x ∃y A ∼
= ∃y ∃x A
∃x (A ∨ B) ∼
= ∃x A ∨ ∃x B
¬∃x A ∼
= ∀x ¬A
3
束縛変数の名前替え
(A′ は A から 束縛変数の名前替え で得ら れる と す る )
A∼
= A′
束縛の導入・ 消去 (x ∈
/ FV(C) と す る )
∃x C ∼
∀x C ∼
=C
=C
束縛の移動 (x ∈
/ FV(C) と す る )
∀x (A ∨ C) ∼
∃x (A ∧ C) ∼
= ∀x A ∨ C
= ∃x A ∧ C
4
定理 1. 任意の変数 x, y ， 述語論理式 A, B, C について ， 1
∼ 4 ページ の同値式が成立す る ．
(証明)
∀x ∀y A ∼
= ∀y ∀x A
A を シ グ ニチャ L 上の述語論理式と す る ．
任意の L-構造 M と ， L-構造 M への任意の付値 v について ，
[[∀x ∀y A]]v = [[∀y ∀x A]]v と なる こ と を 示せばよ い．
x = y の場合． ∀x ∀x A ∼
= ∀x ∀x A と なり ， こ れは ∼
= の反射
性よ り 成立す る ．
x = y の場合． M を L-構造， v を M への付値と す る ．
こ のと き ， 解釈の定義よ り ，
[[∀x ∀y A]]v = T
⇔ 任意の a ∈ |M| について ， [[∀y A]]v[a/x] = T
5
⇔ 任意の a, b ∈ |M| について ， [[A]]v[a/x][b/y] = T．
ま た，
[[∀y ∀x A]]v = T
⇔ 任意の b ∈ |M| について ， [[∀x A]]v[b/y] = T
⇔ 任意の a, b ∈ |M| について ， [[A]]v[b/y][a/x] = T．
こ のと き ， x = y よ り ， v[a/x][b/y] = v[b/y][a/x]．
よ っ て，
[[∀x ∀y A]]v = T
⇔ 任意の a, b ∈ |M| について ， [[A]]v[a/x][b/y] = T
⇔ 任意の a, b ∈ |M| について ， [[A]]v[b/y][a/x] = T
⇔ [[∀y ∀x A]]v = T．
∀x (A ∧ B) ∼
= ∀x A ∧ ∀x B
A を シ グ ニ チャ L 上の述語論理式と す る ． こ のと き ， 任意6
の L-構造 M と ， L-構造 M への任意の付値 v に つ い て ，
[[∀x (A ∧ B)]]v = [[∀x A ∧ ∀x B]]v と なる こ と を 示せばよ
い． こ れには， M を L-構造， v を M への付値と し たと き ，
[[∀x (A ∧ B)]]v = T ⇔ [[∀x A ∧ ∀x B]]v = T を 示せばよ い．
(⇒)
[[∀x (A ∧ B)]]v = T と 仮定す る ．
こ のと き ， 解釈の定義よ り ， 任意の a ∈ |M| について ， [[A∧
B]]v[a/x] = T．
従っ て ， a ∈ |M| と し たと き ， [[A ∧ B]]v[a/x] = T．
こ のと き ， 解釈の定義よ り ， [[A]]v[a/x] = T かつ [[B]]v[a/x] =
T．
よっ て ， a ∈ |M| の取り 方は任意だっ たから ， [[∀x A]]v[a/x] =
T が成立す る ．
同様に， [[∀x B]]v[a/x] = T も 成立す る ．
7
よ っ て ， [[∀x A ∧ ∀x B]]v = T が成立す る ．
(⇐)
[[∀x A ∧ ∀x B]]v = T と 仮定す る ． こ のと き ， 解釈の定義よ
り ， [[∀x A]]v = T およ び同様に， [[∀x B]]v = T．
よ っ て ， 解釈の定義よ り ， 任意の a ∈ |M| に つ い て ，
[[A]]v[a/x] = T が成立す る ．
同様に， 任意の b ∈ |M| について ， [[B]]v[b/x] = T が成立す
る．
よ っ て ， 任意の c ∈ |M| を と る と き ， [[A]]v[c/x] = T も
[[B]]v[c/x] = T も 成立す る ． よ っ て ， 任意の c ∈ |M| に つ
いて ， [[A ∧ B]]v[c/x] = T． す なわち ， [[∀x (A ∧ B)]]v = T．
(そ の他について は省略． )
8
述語論理式の同値変形
命題論理式の場合と 同様， 以下の定理が成立す る ．
定理 2. 論理的同値性は述語論理式上の合同関係で あ る ．
つま り ， A ∼
= Qx B (Q ∈
= ¬B ， Qx A ∼
= B なら ば， ¬A ∼
{∀, ∃}) が成立し ， A ∼
= B かつ C ∼
= D なら ば， A◦C ∼
= B ◦D
(◦ ∈ {∧, ∨, →}) が成立す る ．
従っ て ， 命題論理式の場合と 同様にし て ， 同値変形を 行
う こ と が可能．
¬∃x ∀y ¬(x ≈ y) ∼
= ∀x ¬∀y ¬(x ≈ y) (ド ・ モ ルガン )
∼
= ∀x ∃y ¬¬(x ≈ y) (二重否定)
∼
= ∀x ∃y (x ≈ y)
9
例．
∃x (P(x) → Q(x)) ∼
= ∃x (¬P(x) ∨ Q(x))
∼
= ∃x ¬P(x) ∨ ∃x Q(x)
∼
= ¬∀x P(x) ∨ ∃x Q(x))
∼
= ∀x P(x) → ∃x Q(x)
∀x (P(x) → Q)
∼
=
∼
=
∼
=
∼
=
∀x (¬P(x) ∨ Q)
∀x ¬P(x) ∨ Q
¬∃x P(x) ∨ Q
∃x P(x) → Q
(含意)
(存在と 論理和の交換)
(ド ・ モ ルガン の法則)
(ド ・ モ ルガン の法則)
(含意)
(束縛の移動)
(ド ・ モ ルガン の法則)
(含意)
演習 3. 以下の同値式を 示せ．
(1) ∀x (P ∧ Q(x)) ∼
= P ∧ ∀x Q(x)
(2) ∀x (P → Q(x)) ∼
= P → ∀x Q(x)
(3) ∃x P(x) ∧ ∃x Q(x) ∼
= ∃x ∃y (P(x) ∧ Q(y))
10
(1) 解答例
∀x (P ∧ Q(x)) ∼
= ∀x P ∧ ∀x Q(x) (束縛の分配)
∼
(束縛の導入・ 消去)
= P ∧ ∀x Q(x)
(2) 解答例
∀x (P → Q(x)) ∼
= ∀x (¬P ∨ Q(x)) (ド ・ モ ルガン の法則)
∼
= ∀x (Q(x) ∨ ¬P) (交換律)
∼
(束縛の移動)
= ∀x Q(x) ∨ ¬P
∼
(交換律)
= ¬P ∨ ∀x Q(x)
∼
(ド ・ モ ルガン の法則)
= P → ∀x Q(x)
(3) 解答例
∃x P(x) ∧ ∃x Q(x) ∼
= ∃x (P(x) ∧ ∃x Q(x)) (束縛の移動)
∼
= ∃x (P(x) ∧ ∃y Q(y)) (束縛変数の名前替え )
∼
= ∃x ∃y (P(x) ∧ Q(y)) (束縛の移動)
11
目次
- 述語論理式の同値式と 同値変形
- 述語論理式の省略記法
- 述語論理の自然演繹体系 (1): ∀ の推論
11
述語論理式の省略記法
(1) 並んだ同じ 量化記号の省略
∀x1 · · · ∀xn A
∃x1 · · · ∃xn A
を ， そ れぞれ，
∀x1, . . . , xn A
∃x1, . . . , xn A
と 省略す る こ と がある ．
12
(2) 制約付き の量化子 (1)
∀x ∈ u A
∀x ≤ n A
∀x > 0 A
は， そ れぞれ，
∀x (x ∈ u → A)
∀x (x ≤ n → A)
∀x (x > 0 → A)
の省略． (x ∈ u, x ≤ n, x > 0 のと こ ろ は， 他にも いろ いろ
あり 得る ． )
13
(3) 制約付き の量化子 (2)
∃x ∈ u A
∃x ≤ n A
∃x > 0 A
は， そ れぞれ
∃x (x ∈ u ∧ A)
∃x (x ≤ n ∧ A)
∃x (x > 0 ∧ A)
の省略．
制約付き の量化子は， ∀ と ∃ で制約の解釈が異なる こ と に
注意．
14
制約付き の全称・ 存在について も ， ド ・ モ ルガン の法則
が成立す る
¬∀x ∈ u A = ¬∀x (x ∈ u → A)
∼
= ∃x ¬(x ∈ u → A)
∼
= ∃x ¬(¬(x ∈ u) ∨ A)
∼
= ∃x (¬(¬(x ∈ u)) ∧ ¬A)
∼
= ∃x (x ∈ u ∧ ¬A)
= ∃x ∈ u ¬A
演習 4. 同様にし て ， ¬∃x ∈ u A ∼
= ∀x ∈ u ¬A と なる こ と
を 確かめよ ．
ただし ， いつも 制約 “∈ u” 等を 追加し て 恒真性が保たれる と いう こ
と で はない． 例え ば， ∀x P(x) → ∃x P(x) は恒真だが， ∀x ∈ u P(x) →
∃x ∈ u P(x) は恒真でない．
15
目次
- 述語論理式の同値変形
- 述語論理式の省略記法
- 述語論理の自然演繹体系 (1): ∀ の推論
15
自然演繹体系 (1): ∀ の推論
述語論理の自然演繹体系は， 命題論理の自然演繹体系に
∀, ∃ のそ れぞれについて の導入規則， 除去規則， 等号に関す
る 推論規則を 追加す る こ と によ っ て 得ら れる ．
(11) ∀ の導入
(12) ∀ の除去
..
A ∀I
∀x A
..
∀x A ∀E
[x := t](A)
ただし ， x が自由に出現す
る 仮定は， 全て 除去さ れて
いる と す る ．
こ こ で， t は任意の項を 表す．
16
∀ の除去規則の適用例と 注意
∀ の除去規則の適用例．
(1)
..
∀x (x ≈ x)
0 ≈ 0 ∀E
(2)
..
∀x (0 ≈ x × 0)
0 ≈ s(0) × 0 ∀E
∀ の除去規則は， ∀x A が成立し て いれば， A の x のと こ ろ
に何を 代入し て も 成立す る ， と いう 推論． こ れは， ∀x A の
意味を 考え る と ， 自然な推論．
17
∀ の除去規則の適用す る 際の注意．
推論規則の結論部 [x := t](A) では， 代入を 実行し て い
る ． こ のため， 代入に関す る 注意事項を 思い出す こ と ．
演習 5. 以下の ∀E の適用例が正し いかど う か述べよ ．
..
∀x∀y P(x, y)
∀y P(0, y) ∀E
P(0, 0) ∀E
..
∀x∀y P(x, y)
∀y P(x, y) ∀E
P(x, y) ∀E
..
∀x∀y P(x, y)
∀y P(z, y) ∀E
P(z, z) ∀E
..
∀x∀y P(x, y)
∀y P(x, y) ∀E
P(x, x) ∀E
..
∀x∀y P(x, y)
∀y P(y, y) ∀E
P(y, y) ∀E
..
∀x∀y P(x, y)
∀z P(y, z) ∀E
P(y, y) ∀E
18
∀ の導入規則の適用例と 注意
∀ の導入規則の適用例.
..
x×1≈x
∀x (x × 1 ≈ x) ∀I
ただし ， こ のよ う な推論が成立する のは， x に関する 仮定が
何も さ れて いない時のみ．
推論規則の条件
「 x が自由に 出現す る 仮定は， 全て 除去さ れて いる と
する 」
はこ れを 保証す る ．
19
∀ の導入規則の正し く ない適用例.
[x ≈ 0]
..
x×1≈0
∀x (x × 1 ≈ 0) ∀I
こ の場合， 除去さ れて いない仮定 [x ≈ 0] のなかに， 変数 x
の自由な出現がある ので ダメ ． も し こ のよ う なこ と を 許し
たと す る と ， ∀E 規則と 合わせて ，
[x ≈ 0]
..
x×1≈0
∀x (x × 1 ≈ 0) ∀I
1 × 1 ≈ 0 ∀E
のよ う な証明が出来て し ま う ため， 明ら かにおかし い．
20
演習 6. 以下の ∀I の適用例が正し いかど う か述べよ ．
[∀y (P(x) ∧ Q(y))]
P(x) ∧ Q(z) ∀E
∀x (P(x) ∧ Q(z)) ∀I
[∀y (P(x) ∧ Q(y))]
P(x) ∧ Q(z) ∀E
∀z (P(x) ∧ Q(z)) ∀I
[∀y (P(x) ∧ Q(y))]
P(x) ∧ Q(z) ∀E
∀y (P(x) ∧ Q(z)) ∀I
[∀y (P(x) ∧ Q(y))]
P(x) ∧ Q(x) ∀E
∀x (P(x) ∧ Q(x)) ∀I
[∀y (P(y) ∧ Q(y))]
P(x) ∧ Q(x) ∀E
∀x (P(x) ∧ Q(x)) ∀I
[∀y (P(y) ∧ Q(y))]
P(y) ∧ Q(y) ∀E
∀y (P(y) ∧ Q(y)) ∀I
21
∀I, ∀E を 用いた証明図の例．
[∀x∀y P(x, y)]1
∀y P(x, y) ∀E
P(x, y) ∀E
∀x P(x, y) ∀I
∀y∀x P(x, y) ∀I
1
→I
∀x∀y P(x, y) → ∀y∀x P(x, y)
[∀x P(x)]1
P(y) ∀E
∀y P(y) ∀I
1
→I
∀x P(x) → ∀y P(y)
22
演習 7. 以下の証明図は正し いか？ 正し く ないなら ， ど こ
が誤っ て いる 推論ス テッ プが指摘せよ ．
[∀x P(x, x)]1
P(y, z) ∀E
∀z P(y, z) ∀I
∀y∀z P(y, z) ∀I
1
→I
∀x P(x, x) → ∀y∀z P(y, z)
演習 8. ∀y P(y) ∧ ∀z Q(z) → ∀x (P(x) ∧ Q(x)) の省略さ れて
いる 括弧を 補え ． ま た， そ の証明図を 書け．
23
(((∀y P(y)) ∧ (∀z Q(z))) → (∀x (P(x) ∧ Q(x))))
[∀y P(y) ∧ ∀z Q(z)]1
[∀y P(y) ∧ ∀z Q(z)]1
∧E
∧E
∀y P(y)
∀z Q(z)
P(x) ∀E
Q(x) ∀E
∧I
P(x) ∧ Q(x)
∀x (P(x) ∧ Q(x)) ∀I
1
→I
∀y P(y) ∧ ∀z Q(z) → ∀x (P(x) ∧ Q(x))
24
まとめ
• 述語論理式の同値式と 同値変形
重要な同値式
同値変形
• 述語論理式の省略記法
並んだ量化記号の省略
制約付き の量化子
• 述語論理の自然演繹体系 (1)
∀ の導入規則と 除去規則
∀ の導入規則におけ る 変数条件
25
© Copyright 2024 ExpyDoc
