2014 年 6 月 24 日
情報論理学 第 9 回講義 復習問題
問題 1 述語論理式 A を A = ∀y (Q(x, y) ∧ ∃x R(x, y, z)) と おく と き ， A に おけ る 変
数の自由出現と 束縛出現を そ れぞれ (わかる よ う に 印を つけ て ) 示せ．
問題 2 以下の述語論理式 A に ついて ， 自由変数の集合 FV(A) を 求めよ ．
(1) A = ∀x P(x, y) ∧ ∀z P(y, z)
(2) A = ∀x P(x, y) ∧ ∀y P(y, z)
(3) A = ∀x (P(x, y) ∧ ∀y P(x, y))
問題 3 述語論理式 ∀y (∀x P(x, y) ∧ ∃x ∀y P(y, x)) に おけ る 束縛関係を 図示せよ ．
問題 4 代入 σ を σ = [x := g(z), y := a] と おく と き ， 以下を 求めよ ．
(1) σ(P(x, y))
(2) σ|x (P(x, y))
(3) σ(∃x P(x, y))
(4) σ(∀z P(x, z))
問題 5 代入 σ と 述語論理式 A を 以下のよ う に と る と き ， σ(A) を 計算せよ ．
(1) σ = [x := y]， A = ∀x P(x, y, z)
(2) σ = [y := z]， A = ∀x P(x, y, z)
(3) σ = [z := x]， A = ∀x P(x, y, z)
問題 6 代入 σ と 述語論理式 A を 以下のよ う に と る と き ， σ(A) を 計算せよ ．
(1) σ = [y := f(z)]， A = ∀x P(x, y, z)
(2) σ = [y := f(z)]， A = ∀y P(x, y, z)
(3) σ = [y := f(z)]， A = ∀z P(x, y, z)
問題 7
(1) 代入 σ を σ = [z := g(y)] と する と き ， 述語論理式 σ(∀x ∀y P(x, y, z)) を 求めよ ．
(2) 代入 σ を σ = [z := y] と する と き ， 述語論理式 σ(∃x (Q(x, y, z) ∧ ∃y Q(x, y, z)))
を 求めよ ．
問題 8
(1) [x := a](A) = ∃y P(a, a, y) を 満た す述語論理式 A を 全て 記せ．
(2) [x := a](A) = P(a, y) ∧ P(y, a) を 満た す述語論理式 A を 全て 記せ．
1
情報論理学 第 9 回講義 復習問題解答
問題 1
部が束縛出現，
部が自由出現： ∀y (Q(x, y) ∧ ∃x R(x, y, z))．
問題 2
(1) FV(A) = {y}
(2) FV(A) = {y, z}
(3) FV(A) = {y}
問題 3
∀y (∀x P(x, y) ∧ ∃x ∀y P(y, x))
問題 4
(1) P(g(z), a)
(2) P(x, a)
(3) ∃x P(x, a)
(4) ∀w P(g(z), w)
(4) の w は， x, z 以外の他の変数を 用いて も よ い．
問題 5
(1) ∀x P(x, y, z)
(2) ∀x P(x, z, z)
(3) ∀w P(w, y, x)
(3) の w は， x, y, z 以外の他の変数を 用いて も よ い．
問題 6
(1) ∀x P(x, f(z), z)
(2) ∀y P(x, y, z)
(3) ∀w P(x, f(z), w)
(3) の w は， x, y, z 以外の他の変数を 用いて も よ い．
問題 7
(1) ∀x ∀w P(x, w, g(y)) (2) ∃x (Q(x, y, y) ∧ ∃w Q(x, w, y))
問題 8
(1) ∃y P(a, a, y)， ∃y P(x, a, y)， ∃y P(a, x, y)， ∃y P(x, x, y)
(2) P(a, y) ∧ P(y, a)， P(x, y) ∧ P(y, a)， P(a, y) ∧ P(y, x)， P(x, y) ∧ P(y, x)
2
© Copyright 2024 ExpyDoc
