习题
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(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用功。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)(R(x)∧Q(x)) 它的真值为：真。
(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) 不存在比所有火车都快的汽车。
解：设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)) 它的真值为：真。
(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)表示：x＞0，B(x)表示：x=5，C(x,y) 表示：x＋y=0
(1) (x)A(x)
解：正整数集合Z+。 (2) (x)A(x) 解：整数集合Z。 (3) (x)B(x) 解：集合｛5｝。 (4) (x)B(x) 解：整数集合Z。
(5) (x)(y)C(x,y) 解：整数集合Z。
4．分别在全总个体域和实数个体域中，将下列命题符号化。 (1) 对所有的实数x，都存着实数y，使得x－y=0 解：设R(x)：x是实数。B(x,y)：x－y=0。 在实数个体域符号化为：(x)(y)B(x,y)
在全总个体域符号化为：(x)(R(x)→(y)(R(y)∧B(x,y))) (2) 存在着实数x，对所有的实数y，都有x－y=0 解：设R(x)：x是实数。B(x,y)：x－y=0。 在实数个体域符号化为：(x)(y)B(x,y)
在全总个体域符号化为：(x)(R(x)∧(y)(R(y)→B(x,y))) (3) 对所有的实数x和所有的实数y，都有x＋y=y＋x 解：设R(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，使得x＋y=100 解：设R(x)：x是实数。B(x,y)：x＋y=100。 在实数个体域符号化为：(x)( y)B(x,y)
在全总个体域符号化为：(x)(R(x)∧(y)(R(y)∧B(x,y)))
习题
1. 指出下列公式中的约束变元和自由变元。 (1) (x)(P(x)→Q(y))
解：约束变元：x，自由变元：y
(2) (x)(P(x)∧R(x))→((x)P(x)∧Q(x)) 解：约束变元：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,v))∧R(x,y) (2) (x)(P(x)→(R(x)∨Q(x,y)))∧(x)R(x)→(z)S(x,z) 解：将前面的约束变元x换成u，后面的约束变元x换成v：
(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)→(3. 对下列谓词公式中的自由变元进行代入。
)S(x,w)w (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(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)：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) 所有的人都不一样高。
解：设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的自然数，则n＋1是n的后继数，n－1是n的先驱数。
解：设A(x)：x是数。B(x,y)：x是y后继数(根据定义，也可理解为y是x先驱数)。 a) “每个数都有惟一的一个数是它的后继数。”符号化为：
(x)(A(x)→(y)(A(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，使得对所有x，若|x－a|＜δ，则|f(x)－f(a)|＜ε。试把此定义用符号化的形式表达出来。
解：(ε) ((ε＞0)→(δ)( (δ＞0)∧(x) ((|x－a|＜δ)→(|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))
习题
1. 设个体域为D=1,2,3，试消去下列各式的量词。 (1) (x)P(x)
解：(x)P(x)P(1)∧P(2)∧P(3) (2) (x)P(x)→(y)Q(y)
解：(x)P(x)→(y)Q(y)(P(1)∧P(2)∧P(3))→(Q(1)∨Q(2)∨Q(3)) (3) (x)P(x)∨(y)Q(y)
解：(x)P(x)∨(y)Q(y)(P(1)∧P(2)∧P(3))∨(Q(1)∨Q(2)∨Q(3)) (4) (x)(P(x)?Q(x))
解：(x)(P(x)?Q(x))(P(1)?Q(1))∧(P(2)?Q(2))∧(P(3)?Q(3)) (5) (x)P(x)∨(y)Q(y)
解：(x)?P(x)∨(y)Q(y) (?P(1)∧?P(2)∧?P(3))∨(Q(1)∧Q(2)∧Q(3)) 2. 求下列各式的真值。
(1) (x)(y)H(x,y) 其中H(x,y)：x＞y，个体域为D=4,2 解：(x)(y)H(x,y)(y)H(2,y)∧(y)H(4,y)
(H(2,2)∨H(2,4))∧(H(4,2)∨H(4,4)) (0∨0)∧(1∨0)0∧10
(2) (x)(S(x)→Q(a))∧p 其中S(x)：x＞3，Q(x)：x=5，a：3，p：5＞3，个体域为D=-1,3,6
解：(x)(S(x)→Q(a))∧p((S(-1)→Q(3))∨(S(3)→Q(3))∨(S(6)→Q(3)))∧(5＞3)
((0→0)∨(0→0)∨(1→0))∧1 (1∨1∨0)∧11∧11
2
(3) (x)(x-2x+1=0) 其中个体域为D=-1,2
222
解：(x)(x-2x+1=0)(((－1)－2×(－1)＋1=0)∨(2－2×2＋1=0)
((4=0)∨(1=0)0∨00
3. 证明下列各式。其中：B是不含变元x的谓词公式。 (1) (x)(S(x)→R(x))(x)S(x)→(x)R(x) 证明：(x)(S(x)→R(x))(x)(?S(x)∨R(x))
(x)?S(x)∨(x)R(x) ?(x)S(x)∨(x R(x) (x)S(x)→(x)R(x)
(2) (x)(y)(S(x)→R(y))(x)S(x)→(y)R(y)
证明：(x)(y)(S(x)→R(y))(x)(y)(?S(x)∨R(y))
(x)?S(x)∨(y)R(y) ?(x)S(x)∨(y)R(y) (x)S(x)→(y)R(y)
(3) (x)(A(x)→B)(x)A(x)→B
离散数学第2章习题解答
