論理数学 A 期末試験 (2007 年 8 月 7 日実施 )
学生番号 氏名
1. S
を以下のような命題論理式の集合とする.S =
p ∨ q, p ∧ q, q ∨ r, q ∧ r, p ∨ q ∨ r, p ∧ q ∧ r, p ∧ (q ∨ r), (p ∨ q) ∧ r
. (a)
以下の表を埋めることで,S
の論理式の真理値表を完成させよ.p q r p ∨ q p ∧ q q ∨ r q ∧ r p ∨ q ∨ r p ∧ q ∧ r p ∧ (q ∨ r) (p ∨ q) ∧ r
0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 1 0 1 0 0 0
0 1 0 1 0 1 0 1 0 0 0
0 1 1 1 0 1 1 1 0 0 1
1 0 0 1 0 0 0 1 0 0 0
1 0 1 1 0 1 0 1 0 1 1
1 1 0 1 1 1 0 1 0 1 0
1 1 1 1 1 1 1 1 1 1 1
(b)
論理的帰結| =
は, 反対称律の=
を論理的同値≡
とみなすと半順序となる. 半順序集合S, | =
をハッセの図式で表せ.(a)
より,S
の論理式には以下のような関係が分かる.p ∧ q ∧ r | = A ( ∀ A ∈ S) A | = p ∨ q ∨ r ( ∀ A ∈ S) p ∧ q | = p ∧ (q ∨ r) q ∧ r | = (p ∨ q) ∧ r (p ∨ q) ∧ r | = p ∨ q (p ∨ q) ∧ r | = q ∨ r p ∧ (q ∨ r) | = p ∨ q p ∧ (q ∨ r) | = q ∨ r
これをハッセの図式で表すと, 以下のようになる.+ 1 / 1 0
/ 1 0 . 1 /
+ 1 ,/ 2 0-
*+ 2 /- 1 0
+ 2 / 2 0
/ 2 0 + 2 /
2.
半順序≤
に対して, 以下のハッセの図式で与えられる半順序集合P
i(1 ≤ i ≤ 8)
を考 える.P
1P
2P
3P
4P
5P
6P
7P
8さらに,
<, #,
および,
述語P
を以下のように定義する.1. x < y ⇐⇒ (x ≤ y) ∧ ¬ (y ≤ x), 2. x # y ⇐⇒ ¬ ((x ≤ y) ∨ (y ≤ x)),
3. P (x, y, z, w) ⇐⇒ (x < y) ∧ (y < z) ∧ (z < w).
このとき,解答欄の上の半順序集合のもとで解答欄の左に与えられた論理式が真となると きには解答欄の空欄に○を, 偽となるときには解答欄の空欄に×を記入せよ. ただし
,
論 理式A
に対して∀ (A)
は,A
に出現する自由変数をすべて全称記号で束縛した式を表す.論理式
P
1P
2P
3P
4P
5P
6P
7P
8∀ (P (x, y, z, w) → ∀ v(x ≤ v))
○ ○ ○ × × ○ ○ ×∀ (P (x, y, z, w) → ∀ v(v ≤ w))
○ ○ × ○ × ○ × ○∀ ((P (x, y, z, w) ∧ P (x
, y
, z
, w
)
○ × ○ ○ ○ ○ ○ ×∧ (y # y
)) → (z # z
)) * * * * *
∀ ((P (x, y, z, w) ∧ P (x
, y
, z
, w
)
× ○ ○ ○ ○ ○ × ○∧ (z # z
)) → (y # y
)) * * * * *
∀ ((P (x, y, z, w) ∧ P (x
, y
, z
, w
)
○ ○ ○ × × ○ ○ ×∧ (x # x
)) → (w # w
)) * * * * *
∀ ((P (x, y, z, w) ∧ P (x
, y
, z
, w
)
○ ○ × ○ ○ ○ × ○∧ (w # w
)) → (x # x
)) * * * * *
∀ ((P (x, y, z, w) ∧ P (x
, y
, z
, w
)
× ○ ○ ○ ○ × ○ ○∧ (z # z
)) → (w # w
)) * * * * *
∀ ((P (x, y, z, w) ∧ P (x
, y
, z
, w
)
○ × ○ ○ ○ × ○ ○∧ (y # y
)) → (x # x
)) * * * * *
*は前提が偽なので全体として真
3.
論理式A
に対して,以下の問いに答えよ.A = ∃ x ∀ y ∃ z ¬ (P (x, y) → (P (y, z) ∧ Q(z, y))) ∧ ∀ x ∀ y(P (x, y) → Q(x, y)).
(a) A
の冠頭連言標準形を求めよ.A ≡ ∃ x ∀ y ∃ z ¬ (P (x, y) → (P (y, z) ∧ Q(z, y ))) ∧ ∀ x ∀ y(P (x, y ) → Q(x, y))
≡ ∃ x ∀ y ∃ z ¬ (P (x, y) → (P (y, z) ∧ Q(z, y ))) ∧ ∀ v ∀ w(P (v, w) → Q(w, v))
≡ ∃ x ∀ y ∃ z ¬ ( ¬ P (x, y ) ∨ (P (y, z) ∧ Q(z, y ))) ∧ ∀ v ∀ w( ¬ P (v, w) ∨ Q(w, v))
≡ ∃ x ∀ y ∃ z( ¬¬ P (x, y ) ∧ ¬ (P (y, z) ∧ Q(z, y))) ∧ ∀ v ∀ w( ¬ P (v, w) ∨ Q(w, v))
≡ ∃ x ∀ y ∃ z(P (x, y) ∧ ( ¬ P (y, z) ∨ ¬ Q(z, y))) ∧ ∀ v ∀ w( ¬ P (v, w) ∨ Q(w, v))
≡ ∃ x ∀ y ∃ z ∀ v ∀ w { (P (x, y) ∧ ( ¬ P (y, z) ∨ ¬ Q(z, y))) ∧ ( ¬ P (v, w) ∨ Q(w, v)) }
≡ ∃ x ∀ y ∃ z ∀ v ∀ w { P (x, y) ∧ ( ¬ P (y, z) ∨ ¬ Q(z, y)) ∧ ( ¬ P (v, w) ∨ Q(w, v)) } (b) A
のスコーレム標準形を求めよ.(1)
よりスコーレム標準形は以下のようになる.∀ y ∀ v ∀ w { P (a, y) ∧ ( ¬ P (y, f (y)) ∨ ¬ Q(f(y), y )) ∧ ( ¬ P (v, w) ∨ Q(w, v)) }
(c) A
が充足不能であることを示せ. (出題ミス)4. P
を述語記号,f, g
を関数記号,a, b
を定数記号,x, y, z, w, u, v
を変数とする. このとき, 表の左の欄に与えられた二つのアトムが単一化可能な場合はそのときのmgu
を,そうでな い場合は×を表の右の欄に記入せよ.P (f(x, y), f (y, f (z, x))) y := f (z, x), w := f(z, x), v := f (z, x), u := x P (f(u, v), f (w, y))
P (f (x, y), f(y, f (z, f (b, v)))) x := b, y := a, z := f(b, a), w := f(b, z), v := a P (w, f (a, f (w, w)))
P (f(x, y), f (y, f (z, x))) x := a, y := f(a, b), z := f(a, f (a, b)), P (z, f (f(a, b), f (w, a))) w := f (a, f (a, b))
P (f(x, y), f (y, f (z, x)))
×P (z, f (f (u, v), v))
P (f(x, y), f (z, f (y, x))) x := a, y := b, z := f(a, b), v := b, w := a P (z, f (f(a, b), f (v, w)))
P (f(x, y), f (f(x, y), f (a, b))) u := a, v := b, x := g(a), y := g(b),
P (f (g(u), g (v )), f (z, f (u, v))) z := f (g (a), g (b))
5. f
を関数記号,x, y
を変数とする. 以下の節集合Σ
の線形入力反駁を木の形で求めよ.ただし,用いた
mgu
を明記すること.Σ =
⎧ ⎪
⎪ ⎪
⎪ ⎪
⎨
⎪ ⎪
⎪ ⎪
⎪ ⎩
P (x, f (y)) ∨ ¬ Q(f (x), y ) Q(x, f (y)) ∨ ¬ P (f (x), y) Q(f(f (f(x))), f(x))
¬ P (f(x), f(f (f(f (f(x))))))
⎫ ⎪
⎪ ⎪
⎪ ⎪
⎬
⎪ ⎪
⎪ ⎪
⎪ ⎭
2*>,4*6++?@ 3*4*5+,6+
59014*5+,6014*69+
5/015,6.014*5+
3*>9,4*69++?@2*4*59+,69+
2*>,4*4*6-+++?@2*4*4*5++,6-+ 2*>:,4*6:++?@ 3*4*5:+,6:+ 5:014*4*5++,69014*6:+ 2*>,4*4*4*6.++++?@ 3*4*4*4*5+++,6.+ 3*4*4*4*>;+++,4*5;++
2*>,4*4*4*4*5+++++ @2*=7><8,4*4*4*4*4*><++++++
5014*><+
