論理数学 A 期末試験 (2005 年 7 月 29 日実施 )
学生番号 氏名
1.
以下のような論理式
A
と
B
を考える.
(a) A = ∀ x(P (x) ∨ Q(x)), B = ∀ xP (x) ∨ ∀ xQ(x).
(b) A = ∀ x(P (x) ∧ Q(x)), B = ∀ xP (x) ∧ ∀ xQ(x).
(c) A = ∃ x(P (x) ∨ Q(x)), B = ∃ xP (x) ∨ ∃ xQ(x).
(d) A = ∃ x(P (x) ∧ Q(x)), B = ∃ xP (x) ∧ ∃ xQ(x).
このとき,
A ≡ B
ならば
1
を,
A | = B
かつ
B | = A
ならば
2
を,
B | = A
かつ
A | = B
なら
ば
3
をそれぞれ解答欄に記入せよ.
さらに, 2の場合には
B | = A
となるような領域が自然数のときの
P
と
Q
の解釈の例を,
3
の場合には
A | = B
となるような領域が自然数のときの
P
と
Q
の解釈の例を, 以下のよ
うに解釈の例の欄に記入せよ. ただし
, 1
の場合には解釈の例の欄には何も記入しなくて
よい.
解答 解釈の例
(1) 2 P (x) : x
が自然数のとき真
Q(x) : x
が0
のとき真
解答 解釈の例
(a) 3 P (x) : x
が偶数のとき真
x
が
0
のとき真
x
が素数のとき真
etc.
Q(x) : x
が奇数のとき真
x
が
0
でないとき真
x
が合成数のとき真
etc.
(b) 1 P (x) :
Q(x) :
(c) 1 P (x) :
Q(x) :
(d) 2 P (x) : x
が偶数のとき真
x
が
0
のとき真
x
が素数のとき真
etc.
Q(x) : x
が奇数のとき真
x
が
1
のとき真
x
が合成数のとき真
etc.
1. P
と
Q
が背反で
, P ∨ Q
が自然数全体が真となる解釈であれば正解.
4. P
と
Q
が背反で
, P ∧ Q
が常に偽となる解釈であれば正解.
2.
半順序
≤
に対して, 以下のハッセの図式で与えられる半順序集合
P
i (1 ≤ i ≤ 5)
を考
える.
P
1
P
2
P
3
P
4
P
5
P
6
さらに, #, および,述語
dm
を以下のように定義する.
1. x # y ⇐⇒ ¬ ((x ≤ y) ∨ (y ≤ x)),
2. dm (x, y, z, w) ⇐⇒ (x ≤ y) ∧ (x ≤ z) ∧ (y ≤ w) ∧ (z ≤ w) ∧ (y # z).
このとき,解答欄の上の半順序集合のもとで解答欄の左に与えられた論理式が真となると
きには解答欄の空欄に○を, 偽となるときには解答欄の空欄に×を記入せよ.
論理式
P
1
P
2
P
3
P
4
P
5
P
6
∃ x ∃ y ∃ z((x # y) ∧ (y # z)
× ○ ○ × ○ ×
∧¬∃ w((x ≤ w) ∧ (y ≤ w) ∧ (z ≤ w)))
(共通上界が存在しない比較不能な 3
点が存在)
∃ x ∃ y ∃ z((x # y) ∧ (y # z)
○ × ○ ○ × ×
∧¬∃ w((w ≤ x) ∧ (w ≤ y) ∧ (w ≤ z)))
(共通下界が存在しない比較不能な 3
点が存在)
∀ x ∀ y ∀ z ∀ w( dm (x, y, z, w) → ∀ v(x ≤ v))
× ○ × × × ○
(◇の下端点が最小値)
∀ x ∀ y ∀ z ∀ w( dm (x, y, z, w) → ∀ v(v ≤ w))
○ × × × × ○
(◇の上端点が最大値)
∃ x ∃ y ∃ z ∃ w( dm (x, y, z, w) ∧ ∃ v(v # x))
○ × ○ ○ ○ ×
(◇とその下端点と比較不能な点が存在)
∃ x ∃ y ∃ z ∃ w( dm (x, y, z, w) ∧ ∃ v(v # w))
× ○ ○ ○ ○ ×
(◇とその上端点と比較不能な点が存在)
3. P
を述語記号,
f, g
を関数記号,
a, b
を定数記号,
x, y, z, w, u, v
を変数とする. このとき,
表の左の欄に与えられた二つのアトムが単一化可能な場合はそのときの
mgu
を,そうでな
い場合は×を表の右の欄に記入せよ.
P (x, f (x, x)) x := f(u, g(u)), w := f(u, g(u)), v := u P (f(u, g(u)), f(w, f (v, g(v))))
P (x, f (y, x))
×
P (f(u, g(u)), f(w, f (g(v), v)))
P (x, f (x, f (g(a), g(b)))) y := g(a), z := g(b), x := f(g(a), g(b)), P (f (y, z ), f (w, w)) w := f(g (a), g(b))
P (x, f (x, g(a))) w := g(a), x := f (g (g (a)), g(g(a))), P (f(y, z), f (f(g(w), g(w)), w)) y := g(g(a)), z := g(g(a))
P (f(f (x, y), z), f (f(g(z), g(w)), a)) u := f(g(a), g(w)), v := a, y := g(w), P (f (u, v ), f (u, v)) x := g(a), z := a
P (f (x, g(y)), f (g(z), w)) x := g(g(z)), v := g (y), u := g(z), P (f(g(u), v), f (u, f (x, v))) w := f(g (g (z)), g(y))
P (f(x, f (x, y)), f (y, f (y, z))) x := f(w, w), v := f (f(u, u), f (w, w)),
P (f(f (u, u), v), f(f (w, w), v )) y := f (w, w), z := f (w, w)
