离散数学习题解答-第3章谓词逻辑

习 题 3.1

1. 指出下列命题中哪些是简单命题？哪些是复合命题？

(1) 偶数和奇数都是整数。

(2) 今天是星期天。

(3) 朱方方与朱园园是姐妹。

(4) x 0，则x有平方根。

(5) 每个人都需要食物，电脑不需要食物，所以电脑不是人。

(6) 每个与会者都会说英语。每个既会说英语又会说德语的人都将在大会上发言，唐甜甜是会员并且会说德语，所以唐宁宁将在大会上发言。

(7) 无理数都不是循环小数。 (8) 3是无理数。

解：(2)、(3)和(8)是简单命题；(1)、(4)、(5)、(6)和(7)是复合命题。

2. 找出下列各复合命题中所包含的互不相同的简单命题。

(1) 有理数和无理数都是实数。

(2) 李丽媛既喜欢学习又喜欢锻炼身体。

(3) 乌鸦都是黑色的，天鹅不是黑色的，所以天鹅不是乌鸦。

(4) 有理数和无理数都是实数。虚数不是实数。因此，虚数既不是有理数，也不是无理数。

(5) 每个理科学生都要学高等数学，每个学高等数学而又勤奋的学生都能掌握微积分知识，王磊是理科生并且勤奋学习，所以王磊能掌握微积分知识。

(6) 命题公式A是重言式当且仅当A的每一组赋值都使A的真值为1 .

(7) 2009年6月6日是星期一或星期三，如果是星期三，那么我有英语课，我就不能去开会。如果是星期一，我就可以去开会。

解：(1) 包含2个简单命题：有理数是实数；无理数是实数。

(2) 包含2个简单命题：李丽媛既喜欢学习；李丽媛喜欢锻炼身体。

(3) 包含3个简单命题：乌鸦都是黑色的，天鹅不是黑色的，天鹅不是乌鸦。

(4) 包含5个简单命题：有理数是实数；无理数是实数；虚数不是实数；虚数不是有理数，虚数不是无理数。

(5) 包含7个简单命题：每个理科学生都要学高等数学；学高等数学的学生；勤奋的学生；能掌握微积分知识的学生；王磊是理科生；王磊勤奋学习，王磊能掌握微积分知识。

(6) 包含2个简单命题：命题公式A是重言式；A的每一组赋值都使A的真值为1 .

(7) 包含4个简单命题：2009年6月6日是星期一；2009年6月6日是星期三；我有英语课；我去开会。

3. 下列各命题中是否包含量词，如果包含，请指出是全称量词还是存在量词。

(1) 有理数是实数。

(2) 刘鸣是三好学生。

(3) 有人喜欢锻炼身体。

(4) 发光的东西不一定是金子。

(5) 星期一我去出差。

(6) 不能被2整除的整数称为奇数。

(7) 北京有外国人。

(8) 有些实数能表示成分数。

解：(1)包含全称量词；(3)包含存在量词；(4)包含全称量词；(6)包含全称量词；(7)包含存在量词；(8)包含存在量词；(2)和(5)不包含量词。

4. 指出下列命题中的个体词和谓词。

(1) 2是素数。

(2) 张丽丽与赵明辉是中学同学。

(3) 并不是所有汽车都比火车跑得慢。

(4) 8 3.

解：(1) 2是个体词，“ 是素数”是谓词；

(2) 张丽丽、赵明辉是个体词，“ 与 是中学同学”是谓词；

(3) 汽车、火车是个体词，“ 比 跑得快”是谓词；

(4) 8、3是个体词，“ 大于 ”是谓词。

习 题 3.2

1. 在下列符号串中，哪些是谓词公式，哪些不是谓词公式？

(1) p q r

(2) F(x,y) zG(y,z)

(3) x(p q) yF(y)

(4) xF(y,z) yG(z)

(5) xG(x) y zF(y,z) p(p q)

解：(2)和(4)是谓词公式；(1)、(3)和(5)不是谓词公式。

2. 指出下列公式的约束变元、自由变元及量词的辖域。

(1) x(F(x,y) yH(x,y,z))

(2) xF(x) G(x,c)

(3) x y(R(x,y) L(y,z)) xH(x,y)

(4) xF(x) yG(x,y)

(5) x yP(x,y,z) (L(y,z) xH(x,y))

(6) xF(x) yG(x,y) zQ(x,y,z)

解：(1) F(x,y)中的x是约束变元，y是自由变元；H(x,y,z)中的x和y是约束变元，z是自由变元； x的辖堿是F(x,y) yH(x,y,z)； y的辖堿是H(x,y,z).

(2) F(x)中的x是约束变元；G(x,c)中的x是自由变元； x的辖堿是F(x).

(3) R(x,y)中的x和y是约束变元；L(y,z)中的y是约束变元，z是自由变元；H(x,y)中的x是约束变元，y是自由变元； x的辖域是 y(R(x,y) L(y,z))； y的辖域是R(x,y) L(y,z)； x的辖域是H(x,y).

(4) F(x)中的x是约束变元；G(x,y)中的x是自由变元，y是约束变元； x的辖堿是F(x)； y的辖域是G(x,y).

(5) P(x,y,z)中的x和y是约束变元，z是自由变元；L(y,z)中的y和z是自由变元；H(x,y)中的x是约束变元，y是自由变元；公式最左边的 x的辖域是 yP(x,y,z)； y的辖域是P(x,y,z)；公式右边的 x的辖域是H(x,y).

(6) F(x)中的x是约束变元；G(x,y)中的x是自由变元，y是约束变元；Q(x,y,z)中的中的x和y是自由变元，z是约束变元； x的辖域是F(x)； y的辖域是G(x,y)； z的辖域是Q(x,y,z).

3. 判定下列公式是否为封闭公式。

(1) y x(G(x,y) zH(x,y,z)) xM(x)

(2) x(F(x) G(x,y)) yH(x,y)

(3) x y(R(x,y) zL(y,z)) xH(x,y)

(4) x(F(x) yG(x,y)) x zM(x,z)

(5) x y(R(x,y) zL(y,z)) x yH(x,y)

(6) x(L(x,a) yG(x,y)) x zM(x,z) H(a,b)

解：(1)、(4)、(5)和(6)是闭公式；

(2)不是闭公式，G(x,y)中的y是自由变元；

(3)不是闭公式，H(x,y)中的y是自由变元。

习 题 3.3

1. 在谓词逻辑系统中将下列命题符号化。

(1) 没有不需要吃饭的人。

(2) 所有无理数都是实数。

(3) 大牛与小马是同学。

(4) 高山和刘水都是大学生。