論理数学 A 期末試験 (2003 年 2 月 18 日実施 )

(1)

論理数学

A

^期末試験

(2003

^年

2

^月

18

^日実施

)

学籍番号氏名

1.

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

(a) A

が充足不能で

B

が恒真であるとき, (A

∧ C) → (B ∨ C)

は恒真である.

正しい.

A

が充足不能なので,

I(A ∧ C) = 0

である.

B

が恒真なので,

I(B ∨ C) = 1

である. よって,

I((A ∧ C) → (B ∨ C)) = 1

である.

以下のような真理値表でも正解.

A B C A ∧ C B ∨ C (A ∧ C) → (B ∨ C)

0 1 0 0 1 1

0 1 1 0 1 1

(b) A

が充足不能で

B

が恒真であるとき, (A

→ (A → C)) → (B → C)

は充足可能である.

間違い.

A = C = p ∧ ¬ p, B = p ∨ ¬ p

とする. このとき,

I(A → (A → C)) = 1, I(B → C) = 0

となるので,

I((A → (A → C)) → (B → C)) = 0

である.

(c) ∃ xP (x) → ∀ xP (x)

を真とする構造は存在しない.

間違い.

構造

M = ( { a } , P

^M

)

を考える. ここで,

P

^M

(x)

を

x = a

のとき真となる述語とする. このとき,

∃ xP (x)

も

∀ xP (x)

も

M

のもとで真となる. したがって,

∃ xP (x) → ∀ xP (x)

も

M

のもとで真となる.

(2)

2.

以下のハッセの図式で与えられる半順序集合を考える.

P

1

P

2

P

3

P

4

P

5

P

6

P

7

さらに,半順序

≤

に対して,

=, #, icmp

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

1. x = y ⇐⇒ ¬ ((x ≤ y) ∧ (y ≤ x)).

2. x # y ⇐⇒ ¬ ((x ≤ y) ∨ (y ≤ x)).

3. icmp (x, y, z) ⇐⇒ (x # y) ∧ (y # z) ∧ (z # x).

このとき, 以下の表の空欄に, 左に与えられた論理式が上に与えられた構造のもとで真となるときには○を, 偽となるときには×を記入せよ.

論理式

P

₁

P

₂

P

₃

P

₄

P

₅

P

₆

P

₇

∀ x ∀ y((x # y) → ¬∃ z((x ≤ z) ∧ (y ≤ z))

× × ○ × ○ × ○

∀ x ∀ y((x # y) → ¬∃ z((z ≤ x) ∧ (z ≤ y))

× × × ○ ○ ○ ×

∃ x ∃ y ∃ z( icmp (x, y, z))

○ ○ ○ ○ ○ ○ ○

∀ y ∀ z ∀ w( icmp (y, z, w)

× ○ ○ × × × ○

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

∀ y ∀ z ∀ w( icmp (y, z, w)

× ○ × ○ × ○ ×

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

∃ x ∃ y ∃ z ∃ w( icmp (x, y, z) ∧ icmp (x, y, w)

× × × × ○ ○ ○

∧ (z = w))

∃x∃y∃z∃x

∃y

∃z

{icmp(x, y, z) ∧ icmp(x

, y

, z

)

○ × × × × × ×

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

∧(w ≤ x

) ∧ (w ≤ y

) ∧ (w ≤ z

))}

(3)

3. A = ∃ x ∀ y ∃ z {¬ [( ¬ P (y, z) ∧ ¬ Q(z, y)) ∨ P (x, y)] ∧ ∀ x ∀ y(Q(x, y ) → P (y, x)) }

とする.

(1) A

の冠頭連言標準形を求めよ.

A = ∃ x ∀ y ∃ z {¬ [( ¬ P (y, z) ∧ ¬ Q(z, y)) ∨ P (x, y)] ∧ ∀ x ∀ y(Q(x, y) → P (y, x)) }

≡ ∃ x ∀ y ∃ z {¬ [( ¬ P (y, z) ∧ ¬ Q(z, y)) ∨ P (x, y)] ∧ ∀ v ∀ w(Q(v, w) → P (w, v)) }

≡ ∃ x ∀ y ∃ z { [ ¬ ( ¬ P (y, z) ∧ ¬ Q(z, y)) ∧ ¬ P (x, y)] ∧ ∀ v ∀ w( ¬ Q(v, w) ∨ P (w, v)) }

≡ ∃ x ∀ y ∃ z { [(P (y, z) ∨ Q(z, y)) ∧ ¬ P (x, y )] ∧ ∀ v ∀ w( ¬ Q(v, w) ∨ P (w, v)) }

≡ ∃ x ∀ y ∃ z ∀ v ∀ w { (P (y, z) ∨ Q(z, y )) ∧ ¬ P (x, y) ∧ ( ¬ Q(v, w) ∨ P (w, v)) } (2) A

のスコーレム連言標準形を求めよ.

(1)

より,

A

のスコーレム連言標準形は以下のようになる.

∀ y ∀ v ∀ w { (P (y, f (y)) ∨ Q(f (y), y)) ∧ ¬ P (a, y) ∧ ( ¬ Q(v, w) ∨ P (w, v)) } (3) A

が充足不能であることを示せ.

(2)

より,

A

の節集合は以下のようになる.

{ P (y, f (y)) ∨ Q(f(y), y), ¬ P (a, y), ¬ Q(v, w) ∨ P (w, v) }

これから, 以下のような反駁を得ることができる.

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

{v := f(y),w := y}

¬Q(v,w)∨P(w,v)

¬P(a,z)

{y := a,z := f(a)}

P(y,f(y))

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

{y := a,z := f(a)}

¬Q(v,w)∨P(w,v)

¬ P(a,z)

{v := f(a),w := a}

Q(f(a),a)

P(a,f(a)) ¬P(a,z)

{z:=f(a)}

(4)

4.

以下の二つのアトムが単一化可能であれば最汎単一化代入

(mgu)

を, そうでなければ

×を空欄に記入せよ. ただし,

P

は述語記号,

f, g

は関数記号,

a, b

は定数記号,

x, y, z, v, w

は変数とする.

P (f (x, f (y, z)), f(x, f (x, y))) { u := y, v := y, z := y, x := y } P (f (u, f (v, v)), f (u, f(v, v)))

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

×

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

P (f (f(y, y), y), f(y, x)) { u := f(y, y), v := y, x := f (y, y) } P (f(u, v), f (v, u))

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(w, w), f (w, w)),

P (f (f (u, u), v), f (f(w, w), v)) y := f (w, w), z := f(w, w), u := w }

(5)

5.

以下の節集合

Σ

の反駁を木表現の形で求めよ.

Σ =

 

 

 

 



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