数理論理学
アルゴリズムは明日の数理論理学のテストが終わってから1限分の猶予があることに気付いたので数理論理学の過去問を解いてみた。(ホントはアルゴリズムやり始めるのが怖いから手をつけないってことはひみつ)。
何も確認せずパパっと解いたので間違いへのつっこみ大歓迎。
てか、こういうの日記にのせていいかどうかも微妙。
1.
1.全ての素数は、それより小さい数では割り切れない
∀x(Prime(x)⊃∀y(Lt(y,x)⊃¬＝(Zero,Mod(x,y))))
2.どの自然数よりも小さい自然数はない。
¬∃x(Natural(x)∧∀y(Natural(y)⊃Lt(x,y)))
3.fを実数関数、aを実数とする。任意のxと任意のεに対して、δが存在して、|x-a| < δならば、|f(x)-f(a)| < ε である。
∀x∀ε∃δ(Lt(Ab(Sub(x,a)),δ)⊃Lt(Ab(Minus(f(x),f(a)),ε)))
x,ε,δ∈Realの条件も入れるべきか迷ったんだけど、入れたほうがいいだろうか？
4.全ての非決定性有限オートマトンに対して、それと等価な決定性有限オートマトンが存在する。
∀x(NFA(x)⊃∃y(DFA(y)∧＝(x,y)))
=(x,y) xとyが等価。
5.無曖昧な文脈自由文法では生成できない文脈自由言語が存在する。
∃x(CFG(x)∧¬MuAimai(x))
テケトー。なにをxでなにがどうなのよ。。。
2.{A⊃B} |- NK ¬B⊃¬Aを示せ。
[3:A] 1:A⊃B
-------------
B [2:¬B]
---------------------------(⊃削除)
⊥
---------------------------(3. ⊃導入)
¬A
---------------------------(2. ⊃導入)
¬B⊃¬A
3.
1.恒真
(b)⇒∀x∃y(P(x)⊃P(y))
(c)⇒∃x∀y(P(x)⊃P(y))
(d)⇒∃x∃y(P(x)⊃P(y))
2.恒真のものの証明木を求めよ。
全部書くのは大変なので最後に出てくる一番上の形だけ
(b)
P(z)⇒P(z),∃y(P(z)⊃P(y))(c)
P(z),P(w)⇒P(w),P(u),∃x∀y(P(x)⊃P(y))(d)
P(z)⇒P(z),∃y(P(z)⊃P(y)),∃x∃y(P(x)⊃P(y))
4.
A(x) : xは動物である。
S(x) : xはカタツムリである。
P(x) : xは植物である。
L(x,y) : xはyを食べるのが好きである。
(a).すべてのカタツムリは動物である。
(b).カタツムリが少なくとも一匹は存在する。
(c).どのカタツムリも全ての植物を食べるのが好きである。
(d).すべての植物を食べるのが好きな動物が少なくとも1匹は存在する。
1.一階言語の論理式で表せ。
(a).
∀x(S(x)⊃A(x))
(b).
∃xS(x)
(c).
∀x(S(x)⊃∀y(P(y)⊃L(x,y)))
(d).
∃x(A(x)∧∀y(P(y)⊃L(x,y)))
2.(a)〜(c)および(d)の否定をそれぞれスコーレム連言標準形にせよ。
(a).
∀x(¬S(x)∨A(x))
(b).
S(a)
(c).
∀x∀y(¬S(x)∨¬P(y)∨L(x,y))
¬(d).
∀x((¬A(x)∨P(f(x)))∧(¬A(x)∨¬L(x,f(x))))
3.
К={
S(x)⇒A(x) ...(1)
⇒S(a) ...(2)
S(x),P(y)⇒L(x,y) ...(3)
A(x)⇒P(f(x)) ...(4)
A(x),L(x,f(x))⇒ ...(5)
}
4.Кが充足不能であることを分解証明系を用いて示せ。
(1) (2)
-------
⇒A(a) (4) (2) (3) (1) (2)
------------ -------- ---------------
⇒P(f(a)) P(y)⇒L(a,y) (5) ⇒A(a)
---------------------- ---------------
⇒L(a,f(a)) L(a,f(a))⇒
------------------------------
⇒
こんな感じ？
微妙！！
てかはてな記法がわからんし！！
日記に書くのに無駄に時間かかったね…しかも見にくい。。。
