离散数学第2章习题解答

第2章习题解答1习题2.11．将下列命题符号化。(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章习题解答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)不存在比所有火车都快的汽车。解：设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。第2章习题解答3(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)))习题2.21.指出下列公式中的约束变元和自由变元。(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，y2.对下列谓词公式中的约束变元进行换名。(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：第2章习题解答4(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(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，使得第2章习题解答5对所有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))习题2.31.设个体域为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∧10(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)∧11∧11(3)(x)(x2-2x+1=0)其中个体域为D=-1,2解：(x)(x2-2x+1=0)(((－1)2－2×(－1)＋1=0)∨(22－2×2＋1=0)((4=