5/9演習

1.意味論的同値が同値関係であることを証明せよ

• 反射的であるのは定義から自明
• 対称的であるのは定義から自明
• 推移的であるのは定義から自明

よって意味論的同値は同値関係である。

2.AとBが意味論的同値であってもα等価でない例を挙げよ。

解答例）AとA∨A（形が違うが意味論的同値）

3.次の一階述語論理の論理式が恒真か否かを答えよ。解釈は台集合が{0,1}であるとする。

(a)

(b)

4.以下の論理式集合において、左の論理式が意味論的帰結になっているか否かを答えよ。

Φ	{P,Q}	{P∧Q}	{P⊃Q}
P	○	○	×
Q	○	○	×
P∨Q	○	○	×
¬P∧Q	×	×	×
¬P⊃Q	○	○	×

5.以下の論理式が恒真か、恒偽か、どちらでもないかを答えよ。

(a) A∧¬A

恒偽

(b) A∨¬A

恒真

(c) (A⊃B)∨(B⊃A)

恒真

(d) (A⊃B)∧(¬B∧A)

恒偽

(e) ∀xP⊃∀xP(f(x))

恒真

(f) ∀xP(f(x))⊃∀xP

どちらでもない

(g) P(f(x))⊃∃xP

恒真
注意：fの値域と定義域は同じ