論理数学 A 期末試験 (2005 年 7 月 29 日実施 )

(1)

論理数学 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

の場合には解釈の例の欄には何も記入しなくてよい.

解答解釈の例

(a) 2 P (x) : x

^{が自然数のとき真}

Q(x) : x

^が

0

^のとき真

解答解釈の例

(a) P (x) :

Q(x) :

(b) P (x) :

Q(x) :

(c) P (x) :

Q(x) :

(d) P (x) :

Q(x) :

(2)

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)))

∃ x ∃ y ∃ z((x # y) ∧ (y # z)

∧¬∃ w((w ≤ x) ∧ (w ≤ y) ∧ (w ≤ z)))

∀ 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)

3. P

を述語記号,

f, g

を関数記号,

a, b

を定数記号,

x, y, z, w, u, v

を変数とする. このとき, 表の左の欄に与えられた二つのアトムが単一化可能な場合はそのときの

mgu

を,そうでない場合は×を表の右の欄に記入せよ.

P (x, f (x, f (x, x))) P (f(u, a), f (f (v, b)), w)

P (x, f (x, f (x, x))) P (f(u, v), f (f (v, u)), w)

P (x, f (x, f (x, x)) P (f(u, v), f (w, f (v, u)))

P (x, f (f(v, u), f (y, y))) P (f (u, v ), f (v, x))

P (f(f (x, y), z), f (f(g(z), g(w)), a)) P (f (u, v ), f (u, v))

P (f (x, g(y)), f (g(z), w)) P (f(g(u), v), f (u, f (x, v)))

P (f(x, f (x, y)), f (y, f (y, z)))

P (f(f (u, u), v), f(f (w, w), v ))

(4)

4.

以下の節集合

Σ

の線形反駁を求めよ.

Σ =

⎧ ⎪

⎪ ⎪

⎨

⎪ ⎪

⎪ ⎩

P (x) ∨ Q(x) P (x) ∨ ¬ Q(f (x))

¬ P (x) ∨ Q(f (x))

¬ P (x) ∨ ¬ P (f (x)) ∨ ¬ Q(x) Q(x) ∨ ¬ Q(f (x))

⎫ ⎪

⎪ ⎪

⎬

⎪ ⎪

⎪ ⎭