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

(1)

論理数学 A ^期末試験 (2006 ^年 7 ^月 28 ^日実施 )

学生番号氏名

1.

命題論理において,

⊕

を以下のように定義される論理演算子とする.

p q p ⊕ q 0 0 0 0 1 1 1 0 1 1 1 0

このとき, 以下の文章が正しければ証明し, 間違っていれば反例を挙げよ.

(a) (A ⊕ B) → (B → ¬ A)

は恒真である.

(b) (B → ¬ A) → (A ⊕ B)

は恒真である.

(2)

2.

以下の問いに答えよ.

(a) A ⊕ B ≡ ( ¬ A ∧ B ) ∨ (A ∧ ¬ B)

であることを示せ.

(b) ¬ (A ⊕ B)

を

→

と

∧

だけを用いて表せ.

(c) ¬ (p → (q ⊕ r)) ∧ ¬ (r ⊕ p)

の連言標準形

(CNF)

を求めよ.

(3)

3.

半順序

≤

に対して, 以下のハッセの図式で与えられる半順序集合

P

_i

(1 ≤ i ≤ 7)

を考える.

P

1

P

2

P

3

P

4

P

5

P

6

P

7

さらに,

<, #,

および

,

述語

P , Q

を以下のように定義する.

1. x < y ⇐⇒ (x ≤ y) ∧ ¬ (y ≤ x), 2. x # y ⇐⇒ ¬ ((x ≤ y) ∨ (y ≤ x)), 3. P (x, y, z)

⇐⇒ (y < x) ∧ (z < x) ∧ (y # z) ∧¬∃ w((y < w) ∧ (w < x)) ∧¬∃ w((z < w) ∧ (w < x)), 4. Q(x, y, z)

⇐⇒ (x < y) ∧ (x < z) ∧ (y # z) ∧¬∃ w((x < w) ∧ (w < y)) ∧¬∃ w((x < w) ∧ (w < z)).

このとき,解答欄の上の半順序集合のもとで解答欄の左に与えられた論理式が真となるときには解答欄の空欄に○を, 偽となるときには解答欄の空欄に×を記入せよ.

論理式

P

₁

P

₂

P

₃

P

₄

P

₅

P

₆

P

₇

∃ x ∃ y ∃ z P (x, y, z)

∃ x ∃ y ∃ z Q(x, y, z)

∀ x ∀ y ∀ z(P (x, y, z) → ∀ w(w ≤ x))

∀ x ∀ y ∀ z(Q(x, y, z) → ∀ w(x ≤ w))

∀ x ∀ y ∀ z(P (x, y, z)

→ ¬∃ w((w ≤ y) ∨ (w ≤ z)))

∀ x ∀ y ∀ z(Q(x, y, z)

→ ¬∃ w((y ≤ w) ∨ (z ≤ w)))

(4)

4. P

を述語記号,

f, g

を関数記号,

a, b

を定数記号,

x, y, z, w, u, v

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

mgu

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

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

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

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

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

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

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

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

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

P (f (g(u), v), f(g(u), v))

(5)

5.

以下の節集合

Σ

の線形入力反駁を木の形で求めよ.

Σ =

⎧ ⎪

⎪ ⎪

⎨

⎪ ⎪

⎪ ⎩

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

¬ P (f(f (x)), f (x)) P (f (x), f (f(x)))

¬ Q(a)

⎫ ⎪

⎪ ⎪

⎬

⎪ ⎪

⎪ ⎭