第2章谓词逻辑习题及答案

⇔(T∧F)∧(T∧F)∧(F∧T) ⇔F (2)∀x(R(x)→F(x))∨G(5)⇔((R(－2)→F(－2))∧(R(3)→F(3))∧(R(6)→F(6)))∨G(5)
⇔((T→T)∧(T→T)∧(T→F))∨F ⇔(T∧T∧F)∨F ⇔F (3)∃x(F(x)∨G(x))⇔(F(－2)∨G(－2))∨(F(3)∨G(3))∨(F(6)∨G(6)) ⇔(T∨F)∨(T∨F)∨(F∨T) ⇔T 11.完成定理 2.3 中未给出的证明。 证明 (1)∀x(A(x)∨B)为假⇔∃a 使(A(a)∨B)为假⇔∃a 使 A(a)为假且 B 为假⇔∀xA(x)为假且 B 为 假⇔∀xA(x)∧B 为假，故∀x(A(x)∧B)⇔∀xA(x)∧B。 (2)∀x(A(x)∧B)为假⇔∃a 使(A(a)∧B)为假⇔∃a 使 A(a)为假或 B 为假⇔∀xA(x)为假或 B 为假 ⇔∀xA(x)∧B 为假，故∀x(A(x)∧B)⇔∀xA(x)∧B。 (4)∀x(B→A(x))⇔∀x(¬B∨A(x)) ⇔¬B∨∀x A(x) ⇔B→∀xA(x)
3
第 2 章 谓词逻辑
⇔T (4)∀x∃yF(x，f(f(x，y)，y))⇔∀x∃y(x＜f(f(x，y)，y))
⇔∀x∃y(x＜(f(x，y)－y)) ⇔∀x∃y(x＜(x－y－y)) ⇔∀x∃y(x＜x－2y) ⇔T 8.判断下列公式的类型： (1)¬∃xP(x)→∀xP(x)。 (2)¬∀xA(x)↔∃x(¬A(x))。 (3)∃x(P(x)∧Q(x))→(∃xP(x)→¬Q(x))。 (4)∃x∀y(F(x，y)→F(y，x))。 解 (1)设论域为{1，2}。 若 P(1)＝P(2)＝T，则 ¬∃xP(x)→∀xP(x)⇔¬( P(1)∨P(2))→( P(1)∧P(2)) ⇔¬(T∨T)→(T∧T) ⇔F→T ⇔T 若 P(1)＝P(2)＝F，则 ¬∃xP(x)→∀xP(x)⇔¬( P(1)∨P(2))→( P(1)∧P(2)) ⇔¬(F∨F)→(F∧F) ⇔T→F ⇔F 所以，¬∃xP(x)→∀xP(x)为可满足式。 (2)¬∀xA(x)↔∃x(¬A(x))⇔∃x(¬A(x))↔∃x(¬A(x))⇔T，所以¬∀xA(x)↔∃x(¬A(x))为永真式。 (3)设论域为{1，2}。 若 P(1)＝P(2)＝Q(1)＝Q(2)＝F，则 ∃x(P(x)∧Q(x))→(∃xP(x)→¬Q(x)) ⇔((P(1)∧Q(1))∨(P(2)∧Q(2)))→(( P(1)∨P(2))→¬Q(x)) ⇔((F∧F)∨(F∧F))→((F∨F)→¬Q(x)) ⇔T 若 P(1)＝Q(1)＝Q(2)＝T，P(2)＝F，则 ∃x(P(x)∧Q(x))→(∃xP(x)→¬Q(x)) ⇔((P(1)∧Q(1))∨(P(2)∧Q(2)))→(( P(1)∨P(2))→¬Q(x)) ⇔((T∧T)∨(F∧T))→((T∨F)→¬Q(x))

谓词逻辑练习及答案第二章谓词逻辑练习一1、指出下列谓词公式中的量词及其辖域，指出各自由变元和约束变元，并回答它们是否是命题：（1）∀x(P(x)∨Q(x))∧R （R为命题常元）（2）∀x(P(x)∧Q(x))∧∃xS(x)→T(x)（3）∀x(P(x)→∃y(B(x,y)∧Q(y))∨T(y))（4）P(x)→(∀y∃x(P(x)∧B(x,y))→P(x))解（1）全称量词∀，辖域 P(x)∨Q(x)，其中x为约束变元，∀x(P(x)∨Q(x))∧R是命题。

（2）全称量词∀，辖域 P(x)∨Q(x)，其中 x为约束变元。

存在量词∃，辖域 S(x) ，其中 x为约束变元。

T(x)中x为自由变元。

∀x(P(x)∧Q(x))∧∃xS(x)→T(x)不是命题。

（3）全称量词∀，辖域 P(x)→∃y(B(x,y)∧Q(y))∨T(y)，其中 x为约束变元，T(y)中y为自由变元。

存在量词∃，辖域B(x,y)∧Q(y)，其中y为约束变元。

∀x(P(x)→∃y(B(x,y)∧Q(y))∨T(y))是命题。

（4）全称量词∀，辖域∃x(P(x)∧B(x,y))，其中 y为约束变元。

存在量词∃，辖域P(x)∧B(x,y)，其中 x为约束变元。

不在量词辖域中的P(x)中的x为自由变元。

P(x)→(∀y∃x(P(x)∧B(x,y))→P(x))不是命题。

2、对个体域{0，1}判定下列公式的真值, E(x)表示“x是偶数”：（1）∀x(E(x)→┐x=1)（2）∀x(E(x)∧┐x=1)（3）∃x(E(x)∧x=1)（4）∃x(E(x)→x=1)再将它们的量词消去,表示成合取或析取命题公式，鉴别你所确定的真值是否正确。

解（1）∀x(E(x)→┐x=1) 真∀x(E(x)→┐x=1) 可表示成命题公式（E(0)→┐0=1）∧（E(1)→┐1=1）其中E(0)→┐0=1真，E(1)→┐1=1也真，故（E(0)→┐0=1）∧（E(1)→┐1=1）真。

谓词的概念和表示
2-1、谓词的概念和表示
命题是反映判断的句子，一般有主语和谓语两部 分组成。 例如：电子计算机是科学技术的工具。 其中：“电 子计算机”是主语，“是科学技术的工具”是谓语。 主语一般是客体，客体可以独立存在。 用以刻划客体的性质或关系的即是谓词。 例如（1）他是三好学生。 （2）7 是质数。
例如，简单而有名的苏格拉底三段论： 所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。 这个显然成立的推理在第一章中是不能进行推证的，比如令P表示： 所有的人都是要死的，Q表示：苏格拉底是人，R表示：苏格拉底是要 死的。于是该推理可以表示为： P∧Q R 但是，用第一章命题逻辑的方法并不能证明该推理成立，因为P∧Q→R 不是重言式。比如当P、Q为T，R为F时，P∧Q→R的真值为F。 苏格拉底三段论在命题逻辑中不能推证的原因是命题公式描述能力的 局限性。比如：“所有的人都是要死的”和“苏格拉底是要死的”这两 个命题所表述的性质都为：“是要死的”，但在命题逻辑中需用两个不 同的命题符号P和R来表示，两个不同的符号显然掩盖了两个命题描述 性质的共同性。这样必须要对命题的内部关系进行深入地研究。
例4： 用 存 在 量 词 表 述 “ 些 人 是 聪 明 的 ” 一 解 ： 设 （x） ：X是 人 。 （x） ：X是 聪 M R 明 的 。 则 上 述 命 题 表为 ： 述 （x） （M（x） R（x） ）
例：发光的不都是金子。
解：L(X):x是发光的。B(x):x是金子。
(x )(L( x ) B( x ))
例：有些人早饭吃面。 包 解 : M ( x ) : x是 人 。 E ( x ) : x早 饭 吃 面 包 ( x )( M ( X ) E ( x ))

习题21．在一阶逻辑中将下面命题符号化。

(1)所有的有理数均可表成分数。

Q(x)：x是有理数，F(x)：x可表成分数∀x(Q(x) →F(x))(2)有的有理数是整数。

Q(x)：x是有理数，Z(x)：x是整数∃x(Q(x) ∧Z(x))(3)凡偶数均能被2整除F(x)：x是偶数，G(x)：x能被2整除∀x(F(x) →G(x))(4)存在着偶素数F(x)：x是偶数，G(x)：x是素数∃x(F(x) ∧G(x))(5)没有不犯错误的人M(x)：x是人，G(x)：x犯错误﹁∃x(M(x)∧﹁G(x))∀x(M(x) →G(x))（所有的人都犯错误）(6)在北京工作的人未必都是北京人F(x)：x在北京工作，G(x)：x是北京人﹁∀x(F(x) →G(x))∃x(F(x)∧﹁G(x))（存在着在北京工作的非北京人）(7) 尽管有些人聪明，但未必一切人都聪明。

同课本p36例2.2.2(1)令C(x)：x聪明；M(x)：x是人。

则命题(7)可符号化为xCx))Mx→∃∧∧⌝∀Mxx()())(((xC)((8) 每列火车都比某些汽车快。

T(x)：x是火车，B(x)：x是汽车，F(x,y)：x比y快。

∀x(T(x) →∃y (B(y)∧F(x,y)))(9)某些汽车比所有的火车慢。

T (x )：x 是火车，B (x )：x 是汽车，F(x,y)：x 比y 快。

∃x(B(x) ∧∀y (T (y) →F (y ,x )) )2．指出下列各合式公式中的指导变项，量词的辖域，个体变项的自由出现和约束出现。

(1)),())((y x yH x F x ∃→∀(2)),()(y x G x xF ∧∃(3)),()),(),((y x xH z y L y x R y x ∃∧∨∀∀解：(1) ∃yH (x,y )中，y 为指导变项，∃的辖域为H (x,y )，其中y 是约束出现，x 是自由出现，∀x (F (x ))中，x 是指导变项，∀的辖域为F (x )，x 是约束出现。

高等数学第二章谓词逻辑练习题一、选择题1．下列四个公式正确的是①)()())()((x xB x xA x B x A x ?∧??∧? ②)()())()((x xB x xA x B x A x ?∨??∨?③)()())()((x xB x xA x B x A x ?∨??∨? ④))()(()()(x B x A x x xB x xA ∧∧?A.①③B.①④C.③④D.②④2. 谓词公式)())()((x Q y yR x P x →?∨?中量词?x 的辖域是( )(A) ))()((y yR x P x ?∨? (B) P (x ) (C) )()(y yR x P ?∨ (D) )(x Q3. 谓词公式))()(()(x xQ x Q x x xP ??→??→?的类型是（）(A) 永真式 (B) 矛盾式(C) 非永真式的可满足式 (D) 蕴涵式4. 设个体域为整数集，下列公式中其真值为1的是( )(A) )0(=+??y x y x (B) )0(=+??y x x y(C))0(=+??y x y x (D) )0(=+y x y x5. 设个体域{,}A a b =，公式()()xP x xS x ?∧?在中消去量词后应为( )(A) ()()P x S x ∧ (B) ()()(()())P a P b S a S b ∧∧∨(C) ()()P a S b ∧ (D) ()()()()P a P b S a S b ∧∧∨6. 在谓词演算中，下列各式正确的是( )(A) (,)(,)x yA x y y xA x y (B) (,)(,)x yA x y y xA x y(C) (,)(,)x yA x y x yA x y (D) (,)(,)x yA x y y xA x y7.下列各式不正确的是( )(A) (()())()()x P x Q x xP x xQ x ?∨??∨?(B) (()())()()x P x Q x xP x xQ x ?∧??∧?(C) (()())()()x P x Q x xP x xQ x ?∨??∨?(D) (())()x P x Q xP x Q ?∧??∧8. 设I 是如下一个解释：D ＝{a,b}, 01 0 1b) P(b,a) P(b,b) P(a,),(a a P 则在解释I 下取真值为1的公式是( ).(A) ?x ?yP(x,y) (B)?x ?yP(x,y) (C)?xP(x,x) (D)?x ?yP(x,y).9. 设个体变元z y x ,,的论域都为自然数集合，(,,):,P x y z x y z +=(,,),(,):Q x y z x y z R x y x y ?=<：，则以下命题中（）是假命题.A ．),0,(x x xP ?B ．),,(y y x yP x ??C ．),,(x x y yQ x ??D ．)0,(x xR ?10. 下面不是命题的是（）A ．()xP x ?B ．()()x P x ?C ．()()()x P x P y ?∨D ．()()(()())x y P x R y ??→11公式()()()()x P x x Q x ?→?的前束范式为（）A ．()()(()())x y P x Q y ??→B ．()()(()())x y P x Q y ??→C ．()()(()())x y P x Q y ??→D ．()()(()())x y P x Q y ??→12. 公式()(())x P x Q （）A ．(()())(()())x P x Q Q x P x ?→∧→?B ．(()())(()())x P x Q Q x P x ?→∧→?C (()())(()())x P x Q Q x P x ?→∧→?D ．(()())(()())x P x Q Q x P x ?→∧→?13. ()()(,)x y P x y ??的否定是（）A ．()()(,)x y P x yB ．()()(,)x y P x yC ．()()(,)x y P x yD ．()()(,)x y P x y14.下列谓词公式与()(()())x A x B x ?↓等价的是（）A ．()()()()x A x xB x ?↓? B ．()()()()x A x x B x ?↑?C ．()()()()x A x x B x ?↓?D ．()()()()x A x x B x ?↑?15.在谓词演算中，()P a 是()xP x ?的有效结论，其理论依据是（）A ．USB ．UGC ．ESD ．EG16. 设个体域是整数集合，P 代表?x ?y ((x <="" )→(x="" -y=""(A) P 是真命题 (B) P 是假命题(C) P 是一阶逻辑公式，但不是命题 (D) P 不是一阶逻辑公式二、填空题1. 设全体域D 是正整数集合，确定下列命题的真值：(1) ()x y xy y ??= ( ) (2) ()+x y x y y ??= ( )(3) ()+x y x y x ??= ( ) (4) (2)x y y x ??= ( )2. 谓词公式()((,)())()((,)()())x P x y Q z y R x y z Q z ?∨∧?→?中量词?x 的辖域是3. 公式()(()(,)()(,))()x P x Q x y z R y z S x ?→∨?→中量的自由变量为约束变量为4. 设个体域D ＝{1,2},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 .5. 设个体域D ＝{a ,b },公式)),()((y x yH x G x ?→?消去量词化为6. 设N (x )：x 是自然数，Z (y )；y 是整数，则命题“每个自然数都是整数，而有些整数不是自然数”符号化为7. 谓词公式?x (F (x )→G (x ))∧??y (F (y )→G (y ))的类型是．8. 设个体域{1,2},谓词P (1)=1,P(2)=0，Q(1)=0，Q (2)=1，则?x (P (x )∨Q (x ))的真值是9.只用联结词,,??→表示以下公式()(()())x P x Q x ?∧=()(()()())x P x y Q y =()(()()())y x P x Q y ??∨?=三、计算及证明1. 求谓词公式))(())((a f R x Q P x ∧→?的真值．其中P ：4>3，Q （x ）：x >1，R （x ）：x ≤ 2．f （-3）=1，f （1）=5，f （5）= -3．a ：5．个体域D =（-3，1，5）．2. 说明公式))(),(()(x xP y x yG x xP ?→?→?是逻辑有效式(永真式)．3. 通过等值演算说明下列等值式成立： )()())()((x xQ x xP x Q x P x ?→??→?4. 求谓词公式),,()),(),((z y x zH y x yG y x xF ?∧?→?的前束范式5. 前提：?xF (x ), ?x (F (x )→G (x )∧H (x ))结论：?x (F (x )∧H (x ))6. 构造推理证明))()(()()(x Q x P x x xQ x xP →→?．。

例1 把下面命题符号化:
第2章
谓词逻辑
1) 凡人要死。 解 设 H: ……是人。 M: ……要死。 则原命题可以表示为x(H(x)→M(x))。 2) 所有的自然数都是实数。 解 设 N: ……是自然数。 R: ……是实数。
则原命题可以表示为x(N(x)→R(x))。
第2章
谓词逻辑
3) 对每一个x, x是偶数当且仅当2整除x。
我们将例２中的“…＞…”和“……位于……和……之间” 也称为谓词, 系。 它们表示了两个和两个以上个体之间的关
第2章
谓词逻辑
定义 2.1―2 用于刻画个体的性质或个体间关系的
词称为谓词。 谓词常用大写字母Ｐ, Ｑ, Ｒ等表示。 如用Ｑ表示 谓词“是共青团员”, a 表示个体“张三”, b表示个体 “李四”, 则命题“张三是共青团员”和“李四是共青 团员”可分别用Ｑ(a)和Ｑ(b) 表示。 又如用Ｎ表示谓 词“是自然数”, c表示个体“100”, 则命题“100 是自 然数”可用Ｎ(c)表示。 这里Ｑ和Ｎ是只与一个个体相 联系的谓词, 我们称之为一元谓词。 一元谓词刻画了个 体的性质。
Q: ……读……。 a: 李涛。 则命题可表示为x(P(x)→Q(a,x))。 2) 有些人聪明, 但不是所有的人都聪明。
解 设 H: ……是人。
B: ……聪明。 则命题可表示为x(H(x)∧B(x))∧┐(x(H(x)→B(x)))。
2) 100 是自然数。
3) 马列主义是真理。
第2章
谓词逻辑
原子命题 1) 可以分解为“张三”和“是共青团员” 两部分; 原子命题 2) 可以分解为“100”和“是自然数” 两部分; 原子命题 3)可以分解为“马列主义”和“是真 理”两部分。 我们将例1中的“张三”、 “100 ”、 “马列主义”

第2章习题答案1. 解 (1)设F(x)表示“x犯错误”，N(x)表示“x为人”，则此语句符号化为：⌝∃x(N(x)∧⌝F(x))。

(2)设F(x)表示“x是推理”，M(x)表示“x是计算机”，H(x，y)表示“x能由y完成”，则此语句符号化为：⌝∀x(F(x)→∃ y M(y)∧H(x，y))。

(3)设C(x)表示“x是计算机系的学生”，D(x)表示“x学习离散数学”，则此语句符号化为：∀x(C(x)→D(x))。

(4)因原语句与“一切自然数x，都有一个自然数y，使得y是x的后继数；并且对任意自然数x，当y 和z都是x的后继时，则有y＝z”的意思相同，所以原语句可符号化为：∀x(N(x)→∃ y(N(y)∧M(x，y)))∧∀x∀y∀z(N(x)∧N(y)∧N(z)→(M(x，y)∧M(x，z)→( y＝z))) 其中N(x)表示x是自然数，M(x，y)表示y是x的后继数。

(5)设S(x，y，z)表示“x＋y＝z”，则此语句符号化为：∀x∀y∃z S(x，y，z)。

(6)设Z(x)表示“x是整数”，S(x，y)表示“xy＝0”，T(x，y)表示“x＝y”，则此语句符号化为：∀x∀y(Z(x)∧Z(y)→(S(x，y)→ T(x，0)∨T(y，0)))。

(7)设E(x)表示“x是偶数”，P(x)表示“x是素数”，S(x，y)表示“x＝y”，则此语句符号化为：∀x(E(x)∧P(x)→∀y(E(y)∧P(y)→ S(x，y)))。

(8)设E(x)表示“x是偶数”，O(x)表示“x是奇数”，N(x)表示“x是自然数”，则此语句符号化为：⌝∃x(E(x)∧O(x)∧N(x))。

(9)设R(x)表示“x是实数”，Q(x)表示“x是有理数”，Z(x)表示“x是整数”，则此语句符号化为：∃x(R(x)∧Q(x)∧⌝Z(x))。

(10)设R(x)表示“x是实数”，Q(x，y)表示“y大于x”，则此语句符号化为：∀x(R(x)→∃⌝y(R(y)∧Q(x，y)))。

数理逻辑习题解二1.设个体域是整数集合，请利用给出的谓词将下列命题符号化。

N(e)：e是自然数（不包括0）。

P(e)：e是素数。

Q(e)：e是偶数。

E(e1,e2)：e1=e2。

L(e1,e2)：e1≤e2。

D(e1,e2)：e1|e2。

（即e1整除e2）a)凡素数均为自然数。

b)没有最大的素数。

c)有些自然数不是素数。

d)并非所有的素数都不是偶数。

e)偶素数只有2。

f)一个自然数是素数的充要条件是除1之外，该数不能被其它任何小于它的自然数整除。

[解]a)∀x(P(x)→N(x))。

b)⌝∃x(P(x)∧∀y(P(y)→L(y,x)))。

c)∃x(N(x)∧⌝P(x))。

d)⌝∀x(P(x)→⌝Q(x))。

e)∀x(P(x)∧Q(x)→E(x,2))。

f)∀x(N(x)→(P(x)↔⌝∃y(N(y)∧⌝E(y,1)∧⌝E(y,x)∧L(y,x)∧D(y,x))))。

2.利用上题给出的各谓词，用自然语言表达下述命题。

a)∀x(Q(x)→D(2,x))b)∃x(N(x)∧D(x,9))c)∀x∀y(N(x)∧N(y)∧D(x,y)∧D(y,x)→E(x,y))d)⌝∃x(N(x)∧∀y(N(y)→L(y,x))e)∀x(P(x)→∀y(N(y)∧D(y,x)→E(y,x)∨E(y,1)))f)∀x(N(x)∧⌝P(x)→∃y(⌝E(y,x)∧⌝E(y,1)∧D(y,x)))[解]a)凡偶数都能被2整除。

b)存在着能整除9的自然数。

c)两个能互相整除的自然数相等。

d)没有最大的自然数。

e)凡素数的因数只有1和自身。

g)凡合数必有不是1和自身的因数。

3.符号∃!称为唯一性量词，即∃!x A(x)为真当且仅当存在唯一的x，使得A(x)为真。

请用量词∀，∃和相等=来表达∃!x A(x)。

[解]1)∃!x A(x)=Df∃x(A(x)∧∀y(A(y)→y=x))。

2)∃!x A(x)=Df∃x A(x)∧∀x∀y(A(x)∧A(y)→x=y)3)∃!x A(x)=Df∃x∀y(A(y)↔y=x)注:可以证明上述三种表达式是等价的。

第二章 谓词逻辑习题2.11 指出下列命题的个体、谓词或量词：⑪离散数学是一门计算机基础课程。

⑫田亮是一名优秀的跳水运动员。

⑬所有大学生都要好好学习计算机课程。

⑭并非一切推理都能够由计算机来完成的。

解 ⑪个体：离散数学；谓词：…是一门计算机基础课程。

⑫个体：田亮；谓词：…是一名优秀的跳水运动员。

⑬个体：大学生；谓词：…要好好学习计算机课程；量词：所有。

⑭个体：推理；谓词：…是能够由计算机来完成的；量词：一切。

2 用谓词符号化下列命题：⑪小芳是舞蹈演员。

⑫苏格拉底是一位有名的哲学家。

⑬张三作完了他的作业。

⑭我身体很好。

解 ⑪设)(x F ：x 是舞蹈演员；a ：小芳。

命题符号化：)(a F 。

⑫设)(x F ：x 是一位有名的哲学家；a ：苏格拉底。

命题符号化：)(a F 。

⑬设)(x F ：x 作完了他的作业家；a ：张三。

命题符号化：)(a F 。

⑭设)(x F ：x 身体很好；a ：我。

命题符号化：)(a F 。

3 选择合适的个体域符号化下列命题。

⑪如果一个整数的平方是奇数，那么这个整数是奇数。

⑫有些国家在南半球，而有些国家在北半球。

⑬并非所有不在中国居住的人都不是中国人。

⑭有些艺术家既是导演又是演员。

⑮有的猫不捉耗子，会捉耗子的猫才是好猫。

解 ⑪选取个体域为整数集合。

设)(x F ：x 的平方是奇数；)(x G ：x 是奇数。

命题符号化：)()(x G x F 。

⑫选取个体域为所有国家的集合。

设)(x F ：x 在南半球；)(x G ：x 在北半球。

命题符号化：)()(x xG x xF ∃∧∃。

⑬选取个体域为所有人的集合。

设)(x F ：x 在中国居住；)(x G ：x 是中国人。

命题符号化：))()((x G x F x ⌝→⌝⌝∀⑭选取个体域为所有人的集合。

设)(x M ：x 是艺术家；)(x F ：x 是导演；)(x G ：x 是演员。

命题符号化：∃x (M (x )∧F (x )∧G (x ))。

谓词逻辑习题1. 将下列命题用谓词符号化。

（1）小王学过英语和法语。

（2）2大于3仅当2大于4。

（3）3不是偶数。

（4）2或3是质数。

（5）除非李键是东北人，否则他一定怕冷。

解：(1) 令)(x P ：x 学过英语，Q(x)：x 学过法语，c ：小王，命题符号化为)()(c Q c P ∧ (2) 令),(y x P ：x 大于y, 命题符号化为)3,2()4,2(P P → (3) 令)(x P ：x 是偶数，命题符号化为)3(P ⌝ (4) 令)(x P ：x 是质数，命题符号化为)3()2(P P ∨(5) 令)(x P ：x 是北方人；)(x Q ：x 怕冷；c ：李键；命题符号化为)()(x P c Q ⌝→ 2. 设个体域}{c b a D ，，=，消去下列各式的量词。

（1）))()((y Q x P y x ∧∃∀ （2）))()((y Q x P y x ∨∀∀（3）)()(y yQ x xP ∀→∀（4）))()((y yQ y x P x ∃→∀，解：(1) 中))()(()(y Q x P y x A ∧∃=，显然)(x A 对y 是自由的，故可使用UE 规则，得到 ))()(()(y Q y P y y A ∧∃=，因此))()(())()((y Q y P y y Q x P y x ∧∃∧∃∀α，再用ES 规则， )()())()((z Q z P y Q y P y ∧∧∃α，D z ∈，所以)()())()((z Q z P y Q x P y x ∧∧∃∀α（2）中))()(()(y Q x P y x A ∨∀=，它对y 不是自由的，故不能用UI 规则，然而，对)(x A 中约束变元y 改名z ，得到))()((z Q x P z ∨∀，这时用UI 规则，可得：))()((y Q x P y x ∨∀∀ ))()((z Q x P z x ∨∀∀⇔ ))()((z Q x P z ∨∀α （3）略 （4）略3. 设谓词)(y x P ，表示“x 等于y ”，个体变元x 和y 的个体域都是}321{，，=D 。

离散数学答案第二章习题解答第二章谓词逻辑习题与解答1、将下列命题符号化:(1) 所有的火车都比某些汽车快。

(2) 任何金属都可以溶解在某种液体中。

(3) 至少有一种金属可以溶解在所有液体中。

(4) 每个人都有自己喜欢的职业。

(5) 有些职业就是所有的人都喜欢的。

解 (1) 取论域为所有交通工具的集合。

令x x T :)(就是火车, x x C :)(就是汽车, x y x F :),(比y 跑得快。

“所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧?→?。

(2) 取论域为所有物质的集合。

令x x M :)(就是金属, x x L :)(就是液体, x y x D :),(可以溶解在y 中。

“任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y xD y L y x M x ∧?→?。

(3) 论域与谓词与(2)同。

“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →?∧?。

(4) 取论域为所有事物的集合。

令x x M :)(就是人, x x J :)(就是职业, x y x L :),(喜欢y 。

“每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧?→?(5)论域与谓词与(4)同。

“有些职业就是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →?∧?。

2、取论域为正整数集,用函数+(加法),?(乘法)与谓词<,=将下列命题符号化:(1) 没有既就是奇数,又就是偶数的正整数。

(2) 任何两个正整数都有最小公倍数。

(3) 没有最大的素数。

(4) 并非所有的素数都不就是偶数。

解先引进一些谓词如下:x y x D :),(能被y 整除,),(y x D 可表示为)(x y v v =??。

第二章谓词逻辑2—1基本概念例题１. 所有的自然数都是整数。

设N(x)：x是自然数。

I(x)：x是整数。

此命题可以写成∀x(N(x)→I(x))例题２. 有些自然数是偶数。

设E(x)：x是偶数。

此命题可以写成∃x(N(x)∧E(x))例题3. 每个人都有一个生母。

设P(x):x是个人。

M(x,y):y是x的生母。

此命题可以写成：∀x(P(x)→∃y(P(y)∧M(x,y))) 2-2 谓词公式及命题符号化例题1. 如果x是奇数，则2x是偶数。

其中客体x与客体2x之间就有函数关系，可以设客体函数g(x)=2x，谓词O(x)：x是奇数，E(x)：x是偶数，则此命题可以表示为：∀x(O(x)→E(g(x)))例题2 小王的父亲是个医生。

设函数f(x)=x的父亲，谓词D(x):x是个医生，a:小王，此命题可以表示为D(f(a))。

例题3 如果x和y都是奇数，则x+y是偶数。

设h(x,y)=x+y ，此命题可以表示为:∀x∀y((O(x)∧O(y))→E(h(x,y))命题的符号表达式与论域有关系两个公式：一般地，设论域为{a1,a2,....,an}，则有(1). ∀xA(x)⇔A(a1)∧A(a2)∧......∧A(an)(2). ∃xB(x)⇔B(a1)∨B(a2)∨......∨B(an)1.每个自然数都是整数。

该命题的真值是真的。

表达式∀x(N(x)→I(x))在全总个体域的真值是真的,因∀x(N(x)→I(x))⇔(N(a1)→I(a1))∧(N(a2)→I(a2))∧…∧(N(an)→I(an))式中的x不论用自然数客体代入，还是用非自然数客体代入均为真。

例如(N(0.1)→I(0.1))也为真。

而∀x(N(x)∧I(x))在全总个体域却不是永真式。

∀x(N(x)∧I(x))⇔(N(a1)∧I(a1))∧(N(a2)∧I(a2)) ∧…∧(N(an)∧I(an))比如x用0.2代入(N(0.2)∧I(0.2))就为假。

第二章 习题课
一. 命题符号化 60页(2) a) x(J(x)→L(x)) b) x(L(x)∧S(x)) c) x(J(x)∧O(x)∧V(x)) d) J(j)∧O(j)∧V(j) e) x(L(x)→J(x)) 或者 x(L(x)∧J(x)) f) x(S(x)∧L(x)∧C(x)) g) x(C(x)∧V(x)) 或者 x(C(x)→V(x)) h) x((C(x)∧O(x))→L(x)) i) x(W(x)∧C(x)∧H(x)) j) x(W(x)∧J(x)∧C(x)) k) x(L(x)→y(J(y)∧A(x,y))) l) x(S(x)∧y(L(y)→A(x,y)))
x(Y(x)→(((D(4,x)∧D(100,x))→R(x))∨(D(400,x) →R(x)))) 此式有些问题，因为它等价于 x(Y(x)→(((D(4,x)∧D(100,x))∧D(400,x))→R(x))) 正确答案： 1)x(Y(x)→((D(4,x)∧D(100,x))→R(x)))∧ x(Y(x)→(D(400,x) →R(x))) 2)x(Y(x)→(((D(4,x)∧D(100,x))∨D(400,x)) →R(x)))
x(A(x)→(B(x)→C(x))),x(A(x)∧D(x)) C(a)∧D(a) A(a)→B(a)
⑴ A(a) ⑵ x(A(x)→(B(x)→C(x))) ⑶ A(a)→(B(a)→C(a)) ⑷ B(a)→C(a) ⑸ C(a)∧D(a) ⑹ C(a) ⑺ B(a) ⑻ B(a) ⑼ A(a)→B(a)
72页(2)d)论域为{1,2} P(1) P(2) Q(1,1) Q(1,2) Q(2,1) Q(2,2) F T T T F F xy(P(x)∧Q(x,y)) y(P(1)∧Q(1,y))∧y(P(2)∧Q(2,y)) ((P(1)∧Q(1,1))∨(P(1)∧Q(1,2)))∧ ((P(2)∧Q(2,1))∨(P(2)∧Q(2,2))) ((F∧T)∨(F∧T))∧((T∧F)∨(T∧F)) (F∨F)∧(F∨F)F

第二章谓词逻辑1.什么叫做客体和客体变元？如何表示客体和客体变元？2.么叫做谓词？3.什么叫做论域？我们定义一个“最大”的论域叫做什么？4.填空题：1．存在量词：记作( )，表示( )或者( )或者( )。

2．全称量词：记作( )，表示( )或者( )或者( )。

5.什么叫做量词的作用域？指出下面两个谓词公式中各个量词的作用域。

∀x(F(x,y)→∃yP(y))∧Q(z)∧∃xA(x)∀x∃y∀z(A(x,y)→B(x,y,z))∧C(t)6.什么叫做约束变元？什么叫做自由变元？指出下面公式中哪些客体变元是约束变元？哪些客体变元是自由变元？∀x(F(x,y)→∃yP(y))∧Q(z)∧∃xA(x)7.填空：一个谓词公式如果无自由变元，它就表示一个( )。

8.给出的谓词J(x)：x是教练员，L(x) ：x是运动员，S(x) ：x是大学生，O(x) ：x是年老的，V(x) ：x是健壮的，C(x) ：x是国家选手，W(x) ：x是女同志，H(x) ：x是家庭妇女，A(x,y)：x钦佩y。

客体j：金某人。

用上面给出的符号将下面命题符号化。

1．所有教练员是运动员。

2．某些运动员是大学生。

3．某些教练是年老的，但是健壮的。

4．金教练既不老，但也不是健壮的。

5．不是所有运动员都是教练。

6．某些大学生运动员是国家选手。

7．没有一个国家选手不是健壮的。

8．所有老的国家选手都是运动员。

9．没有一位女同志既是国家选手又是家庭妇女。

10．有些女同志既是教练又是国家选手。

11．所有运动员都钦佩某些教练。

12．有些大学生不钦佩运动员。

9.将下面命题符号化1．金子闪光,但闪光的不一定都是金子。

2．没有大学生不懂外语。

3．有些液体可以溶解所有固体。

4．每个大学生都爱好一些文体活动。

5．每个自然数都有唯一的后继数。

10.令P表示天气好。

Q表示考试准时进行。

A(x)表示x是考生。

B(x)表示x提前进入考场。

C(x)表示x取得良好成绩。

第2章人工智能与知识工程初步1. 设有如下语句，请用相应的谓词公式分别把他们表示出来：s(1)有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。

解：定义谓词dP(x)：x是人L(x,y)：x喜欢y其中，y的个体域是{梅花，菊花}。

将知识用谓词表示为：(∃x )(P(x)→L(x, 梅花)∨L(x, 菊花)∨L(x, 梅花)∧L(x, 菊花))(2)有人每天下午都去打篮球。

解：定义谓词P(x)：x是人B(x)：x打篮球A(y)：y是下午将知识用谓词表示为：a(∃x )(∀y) (A(y)→B(x)∧P(x))(3)新型计算机速度又快，存储容量又大。

解：定义谓词NC(x)：x是新型计算机F(x)：x速度快B(x)：x容量大将知识用谓词表示为：(∀x) (NC(x)→F(x)∧B(x))(4)不是每个计算机系的学生都喜欢在计算机上编程序。

解：定义谓词S(x)：x是计算机系学生L(x, pragramming)：x喜欢编程序U(x,computer)：x使用计算机将知识用谓词表示为：¬(∀x) (S(x)→L(x, pragramming)∧U(x,computer))(5)凡是喜欢编程序的人都喜欢计算机。

解：定义谓词P(x)：x是人L(x, y)：x喜欢y将知识用谓词表示为：(∀x) (P(x)∧L(x,pragramming)→L(x, computer))2请对下列命题分别写出它们的语义网络： (1) 每个学生都有一台计算机。

解：(2) 高老师从3月到7月给计算机系学生讲《计算机网络》课。

解：(3) 学习班的学员有男、有女、有研究生、有本科生。

解：参例2.14(4) 创新公司在科海大街56号，刘洋是该公司的经理，他32岁、硕士学位。

解：参例2.10(5) 红队与蓝队进行足球比赛，最后以3：2的比分结束。

解：2.19 请把下列命题用一个语义网络表示出来： (1) 树和草都是植物； 解：(2) 树和草都有叶和根； 解：(3) 水草是草，且生长在水中； 解：(4) 果树是树，且会结果； 解：(5) 梨树是果树中的一种，它会结梨。

谓词逻辑习题1. 将下列命题用谓词符号化。

（1）小王学过英语和法语。

（2）2大于3仅当2大于4。

（3）3不是偶数。

（4）2或3是质数。

（5）除非李键是东北人，否则他一定怕冷。

解：(1) 令)(x P ：x 学过英语，Q(x)：x 学过法语，c ：小王，命题符号化为)()(c Q c P ∧ (2) 令),(y x P ：x 大于y, 命题符号化为)3,2()4,2(P P → (3) 令)(x P ：x 是偶数，命题符号化为)3(P ⌝ (4) 令)(x P ：x 是质数，命题符号化为)3()2(P P ∨(5) 令)(x P ：x 是北方人；)(x Q ：x 怕冷；c ：李键；命题符号化为)()(x P c Q ⌝→ 2. 设个体域}{c b a D ，，=，消去下列各式的量词。

（1）))()((y Q x P y x ∧∃∀ （2）))()((y Q x P y x ∨∀∀（3）)()(y yQ x xP ∀→∀（4）))()((y yQ y x P x ∃→∀，解：(1) 中))()(()(y Q x P y x A ∧∃=，显然)(x A 对y 是自由的，故可使用UE 规则，得到 ))()(()(y Q y P y y A ∧∃=，因此))()(())()((y Q y P y y Q x P y x ∧∃∧∃∀ ，再用ES 规则， )()())()((z Q z P y Q y P y ∧∧∃ ，D z ∈，所以)()())()((z Q z P y Q x P y x ∧∧∃∀（2）中))()(()(y Q x P y x A ∨∀=，它对y 不是自由的，故不能用UI 规则，然而，对)(x A 中约束变元y 改名z ，得到))()((z Q x P z ∨∀，这时用UI 规则，可得：))()((y Q x P y x ∨∀∀ ))()((z Q x P z x ∨∀∀⇔ ))()((z Q x P z ∨∀ （3）略 （4）略3. 设谓词)(y x P ，表示“x 等于y ”，个体变元x 和y 的个体域都是}321{，，=D 。

谓词逻辑习题参考答案与提示1.（1）设W(x)：x是工人；c：小张。

原命题可符号化为：⌝W(c)。

（2）设S(x)：x是田径运动员；B(x)：x是球类运动员；h：他。

原命题可符号化为：S(h)∨B(h)。

（3）设C(x)：x是聪明的；B(x)：x是美丽的；l：小莉。

原命题可符号化为：C(l)∧B(l)。

（4）设O(x)：x是奇数。

原命题可符号化为：O(m)→⌝O(2m)（5）设P(x，y)：直线x平行于直线y；G(x，y)：直线x相交于直线y。

原命题可符号化为：P(x，y)→⌝G(x，y)。

（6）设O(x)：x是老的；V(x)：x是健壮的；j：王教练。

原命题可符号化为：⌝O(j)∧⌝V(j)。

（7）设L(x, y)：x大于y。

原命题可符号化为：L(5,4)→L(4,6)。

2.（1）存在自然数x，对任意自然数y满足xy=1；a)0 b)0 c)0 d)0（2）对每个自然数x，存在自然数y满足xy=1；a)0 b)0 c)0 d)1（3）对每个自然数x，存在自然数y满足xy=0；a)1 b)1 c)0 d)0（4）存在自然数x，对任意自然数y满足xy=1；a)1 b)1 c)0 d)0（5）对每个自然数x，存在自然数y满足xy=x；a)1 b)1 c)1 d)1（6）存在自然数x，对任意自然数y满足xy=x；a)1 b)1 c)0 d)0（7）对任意自然数x,y，存在自然数z满足x-y=z。

a)1 b)1 c)0 d)03.（1）⌝∃xL(x,0)（2）∀x∀y∀z((L(x,y)∧L(y,z))→L(x,z))（3）∀x∀y((L(x,y)→∃z(L(z,0)∧G(xz,yz)))（4）∃x∀yM(x,y,y)（5）∀x∃yA(x,y,x)4. ∃!xP(x)可用以下具有相同的意义的谓词公式表示∃x(P(x)∧∀y(P(y)→E(y,x)))E(y,x)表示y等于x5. 设R(x)：x是兔子；T(x)：x是乌龟。