二 谓词逻辑习题
1．设下面谓词的个体域都是{a, b ,c},试将下列谓词公式的量词消去, 写成与之等价的命题公式。
（1） ∀x R(x)∧∃x S (x)
（2） ∀x (P(x)→Q(x) )
(3) ∀x ┐P(x)∨ ∀x P(x)
２. 指出下列谓词公式在相应解释下的真值
（１）∀x （Ｐ→Ｑ（x ））∨Ｒ（e ）
其中个体域Ｄ＝{－２，３，６}, P ：“３＞２”,
Ｑ（x ）：“x ≤３”，Ｒ（Ｘ）：“x ＞５”，e ：３。
（２）∃x( P(x)→Q(x) )
其中Ｐ（x ）：“Ｘ＞３”，Ｑ（x ）：“x ＝４”，个体域Ｄ＝{2} 那么真值是（１） （２）
3. 设Ｐ（x ）：x 是素数，Ｑ（x ）：x 是偶数，E （x ，y ）：x 和y 相等。 命题“至多存在一个偶素数“可符号化为
命题“存在唯一的偶数”可符号化
4．命题“任意实数总能比较大小“可符号化为
5公式∀x(P(x)→Q(x , y)∨∃ zR(y, z))→S(x)中，自由变元为 约束变元为
6．试证明∀x A(x)→∃x B(x) ⇔∃x(A(x)→B(x))
7．设公式Ａ＝∀x ∃y(P(x)→Q(x, y)), 论域D={a, b}, 且 P(a) P(b) Q(a, a) Q(a, b) Q(b, a) Q(b, b) ０ １ １ ０ ０ １
求Ａ的真值
8．∀x A(x)→B 与 ∀x(A(x)→B) 是( )
（Ａ）等价的 （Ｂ）蕴含的 （Ｃ）重言蕴言的 9求谓词公式∀x P(x)→∀z Q(x, z)∨∀z R(x, y ,z)的前束范式。
10．求谓词公式∃x(┐∃y P(x, y)→(∃z Q(z)→R(x)))的前束范式
11．在谓词逻辑中，将下列命题符号化为：
（１） 有些人喜欢所有的花。
（２）没有不犯错误的人。
（３）在北京工作的人未必都是北京人。
（４）尽管有人聪明，但未必每个人都聪明。
12．对下面每个公式指出约束变元和自由变元。
(1)∀x P(x)→Q(y)
(2)∀x P(x)∧Q(x)∧∃x G(x)
(3)∃x ∀y(P(x)∧Q(y))→∀x R(x)
(4)∃x ∃y(P(x, y)∧Q(z))
13． 设个体域D={a, b, c}，试将下列各式化为不含量词的形式。
(1)∀x F(x)∧∃x G(x)
(2)∀x P(x)
(3)∀x(P(x)→Q(x))
14．求下列各式的前束范式
(1)∀x F(x)∨∃y G(y)
(2)∀z(∀y H(x, y)∃x G(x, y, z))
(3)∃x(┐(∃y P(x, y))→(∃z Q(z)→R(x)))
15． 构造下面推理的证明。 前提∃x P(x)→∀x Q(x) 结论∀x(P(x)→Q(x))
16．构造下面推理的证明。
前提∀x(P(x)∨Q(x)),∀x(Q(x)→┐R(x)), 结论∀x P(x)
∀x R(x)
二 谓词逻辑习题
1．设下面谓词的个体域都是{a, b ,c},试将下列谓词公式的量词消去, 写成与之等价的命题公式。
（1） ∀x R(x)∧∃x S (x)
（2） ∀x (P(x)→Q(x) )
(3) ∀x ┐P(x)∨ ∀x P(x)
２. 指出下列谓词公式在相应解释下的真值
（１）∀x （Ｐ→Ｑ（x ））∨Ｒ（e ）
其中个体域Ｄ＝{－２，３，６}, P ：“３＞２”,
Ｑ（x ）：“x ≤３”，Ｒ（Ｘ）：“x ＞５”，e ：３。
（２）∃x( P(x)→Q(x) )
其中Ｐ（x ）：“Ｘ＞３”，Ｑ（x ）：“x ＝４”，个体域Ｄ＝{2} 那么真值是（１） （２）
3. 设Ｐ（x ）：x 是素数，Ｑ（x ）：x 是偶数，E （x ，y ）：x 和y 相等。 命题“至多存在一个偶素数“可符号化为
命题“存在唯一的偶数”可符号化
4．命题“任意实数总能比较大小“可符号化为
5公式∀x(P(x)→Q(x , y)∨∃ zR(y, z))→S(x)中，自由变元为 约束变元为
6．试证明∀x A(x)→∃x B(x) ⇔∃x(A(x)→B(x))
7．设公式Ａ＝∀x ∃y(P(x)→Q(x, y)), 论域D={a, b}, 且 P(a) P(b) Q(a, a) Q(a, b) Q(b, a) Q(b, b) ０ １ １ ０ ０ １
求Ａ的真值
8．∀x A(x)→B 与 ∀x(A(x)→B) 是( )
（Ａ）等价的 （Ｂ）蕴含的 （Ｃ）重言蕴言的 9求谓词公式∀x P(x)→∀z Q(x, z)∨∀z R(x, y ,z)的前束范式。
10．求谓词公式∃x(┐∃y P(x, y)→(∃z Q(z)→R(x)))的前束范式
11．在谓词逻辑中，将下列命题符号化为：
（１） 有些人喜欢所有的花。
（２）没有不犯错误的人。
（３）在北京工作的人未必都是北京人。
（４）尽管有人聪明，但未必每个人都聪明。
12．对下面每个公式指出约束变元和自由变元。
(1)∀x P(x)→Q(y)
(2)∀x P(x)∧Q(x)∧∃x G(x)
(3)∃x ∀y(P(x)∧Q(y))→∀x R(x)
(4)∃x ∃y(P(x, y)∧Q(z))
13． 设个体域D={a, b, c}，试将下列各式化为不含量词的形式。
(1)∀x F(x)∧∃x G(x)
(2)∀x P(x)
(3)∀x(P(x)→Q(x))
14．求下列各式的前束范式
(1)∀x F(x)∨∃y G(y)
(2)∀z(∀y H(x, y)∃x G(x, y, z))
(3)∃x(┐(∃y P(x, y))→(∃z Q(z)→R(x)))
15． 构造下面推理的证明。 前提∃x P(x)→∀x Q(x) 结论∀x(P(x)→Q(x))
16．构造下面推理的证明。
前提∀x(P(x)∨Q(x)),∀x(Q(x)→┐R(x)), 结论∀x P(x)
∀x R(x)