情報論理学第8回講義復習問題

2015 年 6 月 9 日
情報論理学第 8 回講義復習問題
問題 1 シグニチャ L = h{+2 , 00 , ×2 , . . .}, {<2 , ≤2 , . . .}i を考える．このとき，自然
数集合の L-構造 N および整数集合の L-構造 Z のそれぞれについて， [[∀x∀y(x×x ≈
y × y → x ≈ y)]]v を求めよ． (根拠も示せ． )
以下では， P(X) は X のべき集合 (部分集合全体の集合) を表わすものとする．
問題 2 シグニチャ L = h{g1 , h2 }, {P2 }i を考える．このとき， L-構造 M を M =
hP(N), gM , hM , PM i， gM (X) = N\X (X の補集合)， hM (X, Y ) = X∪Y ， PM (X, Y ) =
{hX, Y i | X ∩ Y = ∅} と定める．このとき，以下の値を求めよ． (根拠も示せ． )
(1) [[∃x ∀y (h(x, y) ≈ y)]]v
(2) [[∀x P(x, g(x))]]v
問題 3 シグニチャ L = h∅, {P1 }i を考える．このとき，述語論理式 ∀x ∀y (P(x)∧x ≈
y → P(y)) は恒真となることを示せ．
問題 4 シグニチャ L = h∅, {P1 , Q1 }i を考える．このとき，述語論理式 ∀x (P(x) ∧
Q(x)) → ∀x P(x) ∧ ∀x Q(x) は恒真となることを示せ．
問題 5 以下の述語論理式に対する反例を与えるとともに，それが反例になってい
ることを示せ．
(1) ∀x (P(x) ∨ Q(x)) → ∀x P(x) ∨ ∀x Q(x)
(2) ∃x P(x) → ∀x P(x)
(3) ∀x P(x, x) → ∀y ∀z P(y, z)
問題 6 以下の述語論理式に対する反例を与えるとともに，それが反例になってい
ることを示せ．
(1) ∀x P(x)
(2) ∀x (P(x) → Q(x)) → ∀x Q(x)
(3) ∀x ∃y P(x, y) → ∃x P(x, x)
問題 7 下記のハッセ図 (ア )∼ (カ ) で表わされる半順序集合の L-構造のうち，以下
の述語論理式のモデルとなるのはどれか答えよ．
(1)
(2)
(3)
(4)
∃x ∀y (x ≤ y) ∧ ∃x ∀y (y ≤ x)
∃x ∃y (¬(x ≤ y) ∧ ¬(y ≤ x))
∃x ∀y (x ≤ y ∨ y ≤ x → x ≈ y)
∀x ∀y ∀z (x ≤ y ∧ y ≤ z → x ≈ y ∨ y ≈ z)
b
b
b
b
b
b
b
b
b
b
b
b
b
b
(ア )
(イ )
b
b
(ウ )
(エ )
1
b
b
b
b
b
b
b
b
(オ )
(カ )
問題 8 ハッセ図 (ア )∼ (オ ) を以下のようにおく．
b
b
b
b
b
b
b
b
b
(ア )
b
(イ )
b
b
b
(ウ )
b
b
(エ )
(オ )
このときそれぞれのハッセ図で表わされる半順序集合の L-構造のうち，このうち，
以下のそれぞれの述語論理式について，モデルとなっているものを全て挙げよ．
(1) ∃x ∀y (x ≤ y)
(2) ∃x ∀y (x ≤ y) → ∃x ∀y (y ≤ x)
(3) ∀x (¬∃y (x < y) ∨ ¬∃y (y < x))
問題 9 シグニチャを L = h∅, {P2 }i とするとき， L-構造 Mi = h|Mi |, PMi i (1 ≤
i ≤ 5) を以下のように定める．
M1 = hZ, {hx, yi | x < y}i
M2 = hN, {hx, yi | x ≤ y}i
M3 = h{2n + 1 | n ∈ Z}, {hx, yi | x + y = 2}i
M4 = h{n ∈ N | n は素数, n ≥ 5}, {hx, yi | x × y 6= 0}i
M5 = h{2n | n ∈ Z} ∪ {3n | n ∈ Z}, {hx, yi | x 6= y}i
以下の (1)∼ (4) の述語論理式それぞれについて， M1 ∼ M5 のうちでそのモデルと
なっている L-構造をすべて挙げよ．
(1) ∃x ∃y P(x, y)
(2) ∃x ∀y P(x, y)
(3) ∀x ∀y (P(x, y) → P(y, x))
(4) ∃x (P(x, x) → ∀y P(x, y))
問題 10 シグニチャ L = h∅, {<}i を考えるとき，半順序集合の L-構造上の付値 v
にもとづく解釈が， v(x) より大きい要素が高々 1 つしかないことを意味する述語論
理式を記せ．
問題 11 シグニチャ L = h{f1 , ×2 , 00 , 10 }, {<2 }i を考えるとき，自然数集合の L-構
造 N 上の解釈が，関数 fN が単射であることを意味する述語論理式を記せ．
2
情報論理学第 8 回講義復習問題解答
問題 1
N のとき．
N では， f (n) = n2 なる関数 f は単射であるため，任意の n, m ∈ N について，
[[x×x ≈ y×y → x ≈ y]]v[n/x][m/y] = T．よって， [[∀x∀y(x×x ≈ y×y → x ≈ y)]]N = T
となる．
Z のとき．
−1 × −1 = 1 × 1 だが −1 6= 1 なので， [[x × x ≈ y × y → x ≈ y]]v[1/x][−1/y] = F．
よって， [[∀x ∀y (x × x ≈ y × y → x ≈ y)]]Z = F となる．
問題 2 (1) 任意の集合 Y ⊆ N について， ∅ ∪ Y = Y となるから， [[∀y (h(x, y) ≈
y)]]v[∅/x] = T．よって， [[∃x ∀y (h(x, y) ≈ y)]]v = T となる．
(2) 任意の集合 X ⊆ N について， X ∩ (N \ X) = ∅．よって， [[∀x P(x, g(x))]]v = T
となる．
問題 3 任意の L-構造 M と， L-構造 M への任意の付値 v について， [[∀x ∀y (P(x) ∧
x ≈ y → P(y))]]v = T となることを示す．
M を L-構造， v を M への付値とする．
このとき，解釈の定義より，任意の a, b ∈ |M| について， [[P(x) ∧ x ≈ y →
P(y)]]v[a/x][b/y] = T，つまり， [[P(x)]]v[a/x][b/y] = [[x ≈ y]]v[a/x][b/y] = T となるならば，
[[P(y)]]v[a/x][b/y] = T となることを示せばよい．
[[P(x)]]v[a/x][b/y] = [[x ≈ y]]v[a/x][b/y] = T と仮定する．このとき， [[P(x)]]v[a/x][b/y] = T
より， a ∈ PM が成立する．また， [[x ≈ y]]v[a/x][b/y] = T より， a = [[x]]v[a/x][b/y] =
[[y]]v[a/x][b/y] = b が成立する．よって， b ∈ PM ．したがって，解釈の定義より，
[[P(y)]]v[a/x][b/y] = T．以上より， [[∀x ∀y (P(x) ∧ x ≈ y → P(y))]]v = T が成立する．問題 4 任意の L-構造 M と， L-構造 M への任意の付値 v について， [[∀x (P(x) ∧
Q(x)) → ∀x P(x) ∧ ∀x Q(x)]]v = T となることを示す．
M を L-構造， v を M への付値とする．
このとき， [[∀x (P(x) ∧ Q(x))]]v = T ならば， [[∀x P(x) ∧ ∀x Q(x)]]v = T となること
を示せばよい．
[[∀x (P(x) ∧ Q(x))]]v = T と仮定する．このとき，解釈の定義から，任意の a ∈ |M|
について， [[P(x) ∧ Q(x)]]v[a/x] = T，つまり， a ∈ PM かつ a ∈ QM が成立する．よっ
て， PM = QM = |M| が成立する．
したがって，任意の a ∈ |M| について [[P(x)]]v[a/x] = T となるので， [[∀x P(x)]]v = T
となる．また，任意の a ∈ |M| について [[Q(x)]]v[a/x] = T となるので， [[∀x Q(x)]]v = T
も成立する．
よって， [[∀x P(x) ∧ ∀x Q(x)]]v = T が成立する．
以上より， [[∀x (P(x) ∧ Q(x)) → ∀x P(x) ∧ ∀x Q(x)]]v = T が成立する．
3
問題 5
(1) 解答例
L-構造として M = h{0, 1}, PM , QM i， PM = {0}, QM = {1} をとる．このとき，
[[P(x)]]v[1/x] = F より [[∀x P(x)]]v = F． [[Q(x)]]v[0/x] = F より [[∀x Q(x)]]v = F．一方，
[[P(x)]]v[0/x] = T より [[P(x) ∨ Q(x)]]v[0/x] = T，また， [[Q(x)]]v[1/x] = T より [[P(x) ∨
Q(x)]]v[1/x] = T．よって， [[∀x (P(x)∨Q(x))]]v = T となる．よって， [[∀x (P(x)∨Q(x)) →
∀x P(x) ∨ ∀x Q(x)]]v = F．以上より， [[∀x (P(x) ∨ Q(x)) → ∀x P(x) ∨ ∀x Q(x)]]M = F
となり， M は与式の反例．
(2) 解答例
L-構造 M = hN, PM i， PM = {2n | n ∈ N} をとる．すると， [[P(x)]]v[0/x] = T より
[[∃x P(x)]]v = T．一方， [[P(x)]]v[1/x] = F より [[∀x P(x)]]v = F．よって， [[∃x P(x) →
∀x P(x)]]v = F．以上より， [[∃x P(x) → ∀x P(x)]]M = F となり， M は与式の反例．
(3) 解答例
L-構造として M = hN, PM i， PM = {hn, ni | n ∈ N} をとる．すると，任意の
n ∈ N について， hn, ni ∈ PM より [[P(x, x)]]v[n/x] = T．よって， [[∀x P(x, x)]]v =
T．一方， [[P(x, y)]]v[0/x][1/y] = F であるから， [[∀z P(x, z)]]v[0/x] = F となる．従っ
て， [[∀y ∀z P(y, z)]]v = F．以上より， [[∀x P(x, x) → ∀y ∀z P(y, z)]]v = F．よって，
[[∀x P(x, x) → ∀y ∀z P(y, z)]]M = F となり， M は与式の反例．
問題 6
(1) 解答例
L-構造として， M = h{0, 1}, PM i， PM = {0} をとる．このとき， [[P(x)]]v[1/x] = F
より， [[∀x P(x)]]v = F．よって， [[∀x P(x)]]M = F となり， M は与式の反例．
(2) 解答例
L-構造として， M = h{0, 1, 2}, PM , QM i， PM = {0}， QM = {0, 1} をとる．こ
のとき， PM ⊆ QM より， [[∀x (P(x) → Q(x))]]v = T となる．また，このとき，
[[Q(x)]]v[2/x] = F より， [[∀x Q(x)]]v = F．よって， [[∀x (P(x) → Q(x)) → ∀x Q(x)]]v = F．
以上より， [[∀x (P(x) → Q(x)) → ∀x Q(x)]]M = F となり， M は与式の反例．
(3) 解答例
L-構造として， M = hN, PM i， PM = < をとる． N 上で，任意の n ∈ N に対
して， m = n + 1 ∈ N が存在して [[P(x, y)]]v[n/x][m/y] = T となる．よって，任意
の n ∈ N に対して， [[∃y P(x, y)]]v[n/x] = T．従って， [[∀x ∃y P(x, y)]]v = T．一方，
0 < 0 とはならないので， [[P(x, x)]]v[0/x] = F．よって， [[∃x P(x, x)]]v = F．以上よ
り， [[∀x ∃y P(x, y) → ∃x P(x, x)]]v = F．よって， [[∀x ∃y P(x, y) → ∃x P(x, x)]]M = F
となり， M は与式の反例．
問題 7
(1) エ , カ
(2) ア , イ , ウ , エ , オ
(3) イ
(4) ア , イ , オ
4
問題 8
(1) イ，ウ，エ，オ
(2) ア，イ，エ，オ
(3) ア，イ．ウ
問題 9
(1) M1 ,
(2) M2 ,
(3) M3 ,
(4) M1 ,
M2 , M3 , M4 , M5
M4
M4 , M5
M2 , M4 , M5
問題 10 ∀y ∀z ((x < y) ∧ (x < z) → (y ≈ z))
問題 11 ∀x ∀y (f(x) ≈ f(y) → x ≈ y)
関数 f が単射であるとは， f (x) = f (y) ならば x = y となるときをいうことに注意．
5

Download Report