《离散数学 第2章 习题解答》由会员分享，可在线阅读，更多相关《离散数学 第2章 习题解答（10页珍藏版）》请在金锄头文库上搜索。
1、本文格式为Word版，下载可任意编辑离散数学 第2章 习题解答 第2章 习题解答 习题 2.1 1将以下命题符号化。 (1) 4不是奇数。 解：设A(x)：x是奇数。a：4。 “4不是奇数。”符号化为：?A(a) (2) 2是偶数且是质数。 解：设A(x)：x是偶数。B(x)：x是质数。a：2。 “2是偶数且是质数。”符号化为：A(a)B(a) (3) 老王是山东人或河北人。 解：设A(x)：x是山东人。B(x)：x是河北人。a：老王。 “老王是山东人或河北人。”符号化为：A(a)?B(a) (4) 2与3都是偶数。 解：设A(x)：x是偶数。a：2，b：3。 “2与3都是偶数。”符号化为：A
2、(a)A(b) (5) 5大于3。 解：设G(x,y)：x大于y。a：5。b：3。 “5大于3。”符号化为：G(a,b) (6) 若m是奇数，那么2m不是奇数。 解：设A(x)：x是奇数。a：m。b：2m。 “若m是奇数，那么2m不是奇数。”符号化为：A(a)A(b) (7) 直线A平行于直线B当且仅当直线A不相交于直线B。 解：设C(x,y)：直线x平行于直线y。设D(x,y)：直线x相交于直线y。a：直线A。b：直线B。 “直线A平行于直线B当且仅当直线A不相交于直线B。”符号化为：C(a,b)?D(x,y) (8) 小王既聪明又用功，但身体不好。 解：设A(x)：x聪明。B(x)：x用功
3、。C(x)：x身体好。a：小王。 “小王既聪明又用功，但身体不好。”符号化为：A(a)B(a)?C(a) (9) 秦岭隔开了渭水和汉水。 解：设A(x,y,z)：x隔开了y和z。a：秦岭。b：渭水。c：汉水。 “秦岭隔开了渭水和汉水。”符号化为：A(a,b,c) (10) 除非小李是东北人，否那么她确定怕冷。 解：设A(x)：x是东北人。B(x)：x怕冷。a：小李。 “除非小李是东北人，否那么她确定怕冷。”符号化为：B(a)?A(a) 2将以下命题符号化。并议论它们的真值。 (1) 有些实数是有理数。 解：设R(x)：x是实数。Q(x)：x是有理数。 “有些实数是有理数。”符号化为：(?x)(
4、R(x)Q(x) 1 第2章 习题解答 它的真值为：真。 (2) 只要人都要休息。 解：设R(x)：x是人。S(x)：x要休息。 “只要人都要休息。”符号化为：(?x)(R(x)S(x) 它的真值为：真。 (3) 每个自然数都有比它大的自然数。 解：设N(x)：x是自然数。G(x,y)：x比y大。 “每个自然数都有比它大的自然数。”符号化为：(?x)(N(x)(?y)(N(y)G(y,x) 它的真值为：真。 (4) 乌鸦都是黑的。 解：设A(x)：x是乌鸦。B(x)：是黑的。 “乌鸦都是黑的。”符号化为：(?x)(A(x)B(x) 它的真值为：真。 (5) 不存在比全体火车都快的汽车。 解：设
5、A(x)：x是汽车。B(x)：是火车。K(x,y)：x比y快。 “不存在比全体火车都快的汽车。”符号化为：?(?x)(A(x)(?y)(B(y)K(x,y) 它的真值为：真。 (6) 有些大学生不佩服运鼓动。 解：设S(x)：x是大学生。L(x)：是运鼓动。B(x,y)：x佩服y。 “有些大学生不佩服运鼓动。”符号化为：(?x)(S(x)L(y)?B(x,y) 它的真值为：真。 (7) 有些女同志既是教练员又是运鼓动。 解：设W(x)：x是女同志。J(x)：x是教练员。L(x)：x是运鼓动。 “有些女同志既是教练员又是运鼓动。”符号化为：(?x)(W(x)J(x)L(x) 它的真值为：真。 (
6、8) 除2以外的全体质数都是奇数。 解：设A(x)：x是质数。B(x)：x是奇数。C(x,y)：x不等于y。 “除2以外的全体质数都是奇数。”符号化为：(?x)(A(x)C(x,2)B(x) 它的真值为：真。 3指出一个个体域，使以下被量化谓词的真值为真，该个体域是整数集合的最大子集。在以下各题中，A(x)表示：x0，B(x)表示：x=5，C(x,y) 表示：xy=0 (1) (?x)A(x) 解：正整数集合Z+。 (2) (?x)A(x) 解：整数集合Z。 (3) (?x)B(x) 解：集合5。 (4) (?x)B(x) 解：整数集合Z。 2 第2章 习题解答 (5) (?x)(?y)C(x
7、,y) 解：整数集合Z。 4分别在全总个体域和实数个体域中，将以下命题符号化。 (1) 对全体的实数x，都存着实数y，使得xy=0 解：设R(x)：x是实数。B(x,y)：xy=0。 在实数个体域符号化为：(?x)(?y)B(x,y) 在全总个体域符号化为：(?x)(R(x)(?y)(R(y)B(x,y) (2) 存在着实数x，对全体的实数y，都有xy=0 解：设R(x)：x是实数。B(x,y)：xy=0。 在实数个体域符号化为：(?x)(?y)B(x,y) 在全总个体域符号化为：(?x)(R(x)(?y)(R(y)B(x,y) (3) 对全体的实数x和全体的实数y，都有xy=yx 解：设R(
8、x)：x是实数。B(x,y)：x=y。 在实数个体域符号化为：(?x)(?y)B(x+y,y+x) 在全总个体域符号化为：(?x)(R(x)(?y)(R(y)B(x+y,y+x) (4) 存在着实数x和存在着实数y，使得xy=100 解：设R(x)：x是实数。B(x,y)：xy=100。 在实数个体域符号化为：(?x)( ?y)B(x,y) 在全总个体域符号化为：(?x)(R(x)(?y)(R(y)B(x,y) 习题 2.2 1. 指出以下公式中的约束变元和自由变元。 (1) (?x)(P(x)Q(y) 解：约束变元：x，自由变元：y (2) (?x)(P(x)R(x)(?x)P(x)Q(x)
9、 解：约束变元：x，自由变元：x (3) (?x)(P(x)(?x)Q(x)(?x)R(x,y)Q(z) 解：约束变元：x，自由变元：y，z (4) (?x)(?y) (R(x,y)Q(z) 解：约束变元：x，y，自由变元：z (5) (?z) (P(x)(?x)R(x,z)(?y)Q(x,y)R(x,y) 解：约束变元：x，y，z，自由变元：x，y 2. 对以下谓词公式中的约束变元举行换名。 (1) (?x)(?y)(P(x,z)Q(x,y)R(x,y) 解：将约束变元x换成u：(?u)(?y)(P(u,z)Q(u,y)R(x,y) 将约束变元y换成v：(?x)(?v)(P(x,z)Q(x,
10、v)R(x,y) (2) (?x)(P(x)(R(x)Q(x,y)(?x)R(x)(?z)S(x,z) 解：将前面的约束变元x换成u，后面的约束变元x换成v： 3 第2章 习题解答 (?u)(P(u)(R(u)Q(u,y)(?v)R(v)(?z)S(x,z) 将约束变元z换成w：(?x)(P(x)(R(x)Q(x,y)(?x)R(x)(?w)S(x,w) 3. 对以下谓词公式中的自由变元举行代入。 (1) (?y)Q(z,y)(?x)R(x,y)(?x)S(x,y,z) 解：将自由变元z用u代入：(?y)Q(u,y)(?x)R(x,y)(?x)S(x,y,u) 将自由变元y用v代入：(?y)Q
11、(z,y)(?x)R(x,v)(?x)S(x,v,z) (2) (?y)P(x,y)(?z)Q(x,z)?(?x)R(x,y) 解：将自由变元x用u代入：(?y)P(u,y)(?z)Q(u,z)?(?x)R(x,y) 将自由变元y用v代入：(?y)P(x,y)(?z)Q(x,z)?(?x)R(x,v) 4. 利用谓词公式对以下命题符号化。 (1) 每列火车都比某些汽车快。 解：设A(x)：x是火车。B(x)：x是汽车。C(x,y)：x比y快。 “每列火车都比某些汽车快。”符号化为：(?x)(A(x)(?y)(B(y)C(x,y) (2) 某些汽车比全体火车慢。 解：设A(x)：x是火车。B(x
12、)：x是汽车。C(x,y)：x比y快。 “某些汽车比全体火车慢。”符号化为： (?x)(B(x)(?y)(A(y)C(y,x) (3) 对每一个实数x，存在一个更大的实数y。 解：设R(x)：x是实数。G(x,y)：x比y大。 “对每一个实数x，存在一个更大的实数y。”符号化为：(?x)(R(x)(?y)(R(y)G(y,x) (4) 存在实数x，y和z，使得x与y之和大于x与z之积。 解：设R(x)：x是实数。G(x,y)：x比y大。 “存在实数x，y和z，使得x与y之和大于x与z之积。”符号化为： (?x)(?y)(?z)(R(x)R(y)R(z)G(x+y,xz) (5) 全体的人都不一
13、样高。 解：设R(x)：x是人。G(x,y)：x和y一样高。 “全体的人都不一样高。”符号化为：(?x)(?y)(R(x)R(y)?G(x,y) 5. 自然数一共有下述三条公理： a) 每个数都有惟一的一个数是它的后继数。 b) 没有一个数使数1是它的后继数。 c) 每个不等于1的数都有惟一的一个数是它的直接先驱数。 用两个谓词表达上述三条公理。 注：设n是不等于1的自然数，那么n1是n的后继数，n1是n的先驱数。 解：设A(x)：x是数。B(x,y)：x是y后继数(根据定义，也可理解为y是x先驱数)。 a) “每个数都有惟一的一个数是它的后继数。”符号化为： (?x)(A(x)(?y)(A(
14、y)B(y,x)(?z)(A(z)B(z,x)(z=y) b) “没有一个数使数1是它的后继数。”符号化为：?(?x)(A(x)B(1,x) c) “每个不等于1的数都有惟一的一个数是它的直接先驱数。”符号化为： (?x)(A(x)?(x=1)(?y)(A(y)B(x,y)(?z)(A(z)B(x,z)(z=y) 6. 取个体域为实数集R，函数f在a点连续的定义是：对每个0，存在一个0，使得 4 第2章 习题解答 对全体x，若|xa|，那么|f(x)f(a)|。试把此定义用符号化的形式表达出来。 解：(?) (0)(?)( (0)(?x) (|xa|)(|f(x)f(a)|) 7.若定义惟一性量词(?!x)为“存在惟一的一个x”，那么(?!x)P(x)表示“存在惟一的一个x使P(x)为真”。试用量词，谓词及规律运算符表示(?!x)P(x)。 解：(?!x)P(x)?(?x)P(x)(?y)P(y)(y=x) 习题 2.3 1. 设个体域为D=?1,2,3?，试消
