論理数学 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
.
このとき, 半順序集合S, | =
をハッセの図式で表せ.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
の冠頭連言標準形を求めよ.(b) A
のスコーレム標準形を求めよ.(c) A
が充足不能であることを示せ.4. P
を述語記号,f, g
を関数記号,a, b
を定数記号,x, y, z, w, u, v
を変数とする. このとき, 表の左の欄に与えられた二つのアトムが単一化可能な場合はそのときのmgu
を,そうでな い場合は×を表の右の欄に記入せよ.P (f(x, y), f (y, f (z, x))) P (f(u, v), f (w, y))
P (f (x, y), f(y, f (z, f (b, v)))) P (w, f (a, f (w, w)))
P (f(x, y), f (y, f (z, x))) P (z, f (f(a, b), f (w, a)))
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))) P (z, f (f(a, b), f (v, w)))
P (f(x, y), f (f(x, y), f (a, b)))
P (f (g(u), g (v )), f (z, f (u, v)))
5. f
を関数記号,x, y
を変数とする. 以下の節集合Σ
の線形入力反駁を木の形で求めよ.ただし,用いた
