离散数学课后习题+答案

1、离散数学习题答案离散数学习题答案习题一习题一1. 判断下列句子是否为命题？若是命题说明是真命题还是假命题。 （1）3 是正数吗？ （2）x1=0。 （3）请穿上外衣。 （4）210。 （5）任一个实数的平方都是正实数。 （6）不存在最大素数。 （7）明天我去看电影。 （8）9512。 （9）实践出真知。 （10）如果我掌握了英语、法语，那么学习其他欧洲语言就容易多了。 解：解：（1） 、 （2） 、 （3）不是命题。 （4） 、 （8）是假命题。 （5） 、 （6） 、 （9） 、 （10）是真命题。 （7）是命题，只是现在无法确定真值。 2. 设 P 表示命题“天下雪” ，Q 表示命题“我将去书店” ，R 表示命题“我有时间” ，以符 号形式写出下列命题。 （1）如果天不下雪并且我有时间，那么我将去书店。 （2）我将去书店，仅当我有时间。 （3）天不下雪。 （4）天下雪，我将不去书店。 解：解： （1） （PR）Q。 （2）QR。 （3）P。 （4）PQ。 3. 将下列命题符号化。 （1）王皓球打得好，歌也唱得好。 （2）我一边看书，一边听音乐。 （3）老张和老李都是球迷。 （4）只

2、要努力学习，成绩会好的。 （5）只有休息好，才能工作好。 （6）如果 a 和 b 是偶数，那么 a+b 也是偶数。 （7）我们不能既游泳又跑步。 （8）我反悔，仅当太阳从西边出来。 （9）如果f(x)在点x0处可导，则f(x)在点x0处可微。反之亦然。 （10）如果张老师和李老师都不讲这门课，那么王老师就讲这门课。 （11）四边形 ABCD 是平行四边形，当且仅当 ABCD 的对边平行。 （12）或者你没有给我写信，或者信在途中丢失了。 解：解：（1）P：王皓球打得好，Q：王皓歌唱得好。原命题可符号化：PQ。 （2）P：我看书，Q：我听音乐。原命题可符号化：PQ。 （3）P：老张是球迷，Q：老李是球迷。原命题可符号化：PQ。 （4）P：努力学习，Q：成绩会好。原命题可符号化：PQ。 （5）P：休息好，Q：工作好。原命题可符号化：QP。 （6）P：a 是偶数，Q：b 是偶数，R：a+b 是偶数。原命题可符号化：（PQ）R。 （7）P：我们游泳，Q：我们跑步。原命题可符号化：（PQ） 。 （8）P：我反悔，Q：太阳从西边出来。原命题可符号化：PQ。 （9）P：f(x)在点x0处可导， Q：

3、f(x)在点x0处可微。原命题可符号化：P Q。 （10）P：张老师讲这门课，Q：李老师讲这门课，R：王老师讲这门课。原命题可符号化： （PQ）R。 （11）P：四边形 ABCD 是平行四边形，Q：四边形 ABCD 的对边平行。原命题可符号化： P Q。 （12）P：你给我写信，Q：信在途中丢失了。原命题可符号化：P （PQ） 。 4. 判断下列公式哪些是合式公式，哪些不是合式公式。 （1）(QRS) （2）(P (RS) （3）(PQ) (QP) （4）(RSF) （5）(P(QR)(PQ) (PR) 解：解： （1） 、 （2） 、 （5）是合式公式， （3） 、 （4）不是合式公式。 5. 否定下列命题： （1） 桂林处处山清水秀。 （2） 每一个自然数都是偶数。 解：解： （1）桂林并非处处山清水秀。 （2）并不是每一个自然数都是偶数。或：有些自然数不是偶数。 6. 给出下述每一个命题的逆命题、否命题和逆否命题。 （1） 如果天下雨，我将不去。 （2） 仅当你去我才不去。 （3） 如果=b24ac1，Q(x)：x3，R(x)：x5，a：5，论域是- 2，3，6。 解：解： （1

4、）(x)(P(x)Q(x) (P(1)Q(1) (P(2)Q(2) (TF) (FT) T TT （2）(x) (PQ(x)R(a)(PQ(-2)(PQ(3)(PQ(6)R(a) (TT)(TT)(TF)F TTFFF 9. 对下列谓词公式中的约束变元进行换名。 （1）(x)(y)(P(x，z)Q(y) S(x，y) （2）(x)(P(x)(R(x)Q(x)(x)R(x)(z)S(x，z) 解：解： （1）(u)(v)(P(u，z)Q(v) S(x，y) （2）(u)(P(u)(R(u)Q(u)(v)R(v)(z)S(x，z) 10. 对下列谓词公式中的自由变元进行代入。 （1）(y)A(x，y)(x)B(x，z)(x)(z)C(x，y，z) （2）(y)P(x，y)(z)Q(x，z)(x)R(x，y) 解：解： （1）(y)A(u，y)(x)B(x，v)(x)(z)C(x，w，z) （2）(y)P(u，y)(z)Q(v，z)(x)R(x，w) 11. 考虑以下赋值。 论域D=1，2 指定常数 a：1，b：2 指定函数 f：f (1)=2，f (2)=1 指定谓词 P：P(1，1)T，

5、P(1，2)T，P(2，1)F，P(2，2)F 求以下各式的真值。 （1）P(a，f(a)P(b，f(b) （2）(x)(y)P(y，x) （3）(x)( y)(P(x，y)P(f (x)，f (y) 解：解： （1）P(a，f(a)P(b，f(b) P(1，f(1)P(2，f(2) P(1，2)P(2，1) TFF （2）(x)(y)P(y，x) (x)(P(1，x)P(2，x)(P(1，1)P(2，1)(P(1，2)P(2，2)( TF)(TF) TTT （3）(x)(y)(P(x，y)P(f (x)，f (y)(x)(P(x，1)P(f (x)，f (1)(P(x，2)P(f (x)，f (2) (P(1，1)P(f (1)，f (1)(P(1，2)P(f (1)，f (2)(P(2，1)P(f (2)，f (1)(P(2，2)P(f (2)，f (2) (TF)(TF)(FF)(FT)(FF)(TT) FTF 12. 将下面各式翻译成自然语言，然后在不同的个体域中确定它们的真值。 （1）(x) (y)(xy=0) （2）(x) (y)( xy=0) （3）(x) (y)( xy

6、=1) （4）(x) (y)( xy=1) （5）(x) (y)( xy=x) （6）(x) (y)( xy=x) （7）(x) (y) (z)(x-y=z) 个体域分为 （a）实数集合 R （b）整数集合 Z （c）正整数集合 Z+ （d）非零实数集合 R-0 解：解：（1）对于任意的 x，存在 y，使得 xy=0。 （2）存在 x，对于任意的 y，都有 xy=0。 （3）对于任意的 x，存在 y，使得 xy=1。 （4）存在 x，对于任意的 y，都有 xy=1。 （5）对于任意的 x，存在 y，使得 xy=x。 （6）存在 x，对于任意的 y，都有 xy=x。 （7）对于任意的 x，任意的 y，存在 z，使得 x-y=z。 个体域分为 （a）实数集合 R （1）真（2）真（3）假（4）假（5）真（6）真（7）真 （b）整数集合 Z （1）真（2）真（3）假（4）假（5）真（6）真（7）真 （c）正整数集合 Z+ （1）假（2）假（3）假（4）假（5）真（6）假（7）假 （d）非零实数集合 R-0 （1）假（2）假（3）真（4）假（5）真（6）假（7）假 13. 判断下面公式的真假，

7、如果是真，请证明之；如果为假，请给出 P 和 Q 的解释，以说 明公式为假 （1）(x)(P(x)Q(x) (x)P(x)(x)Q(x) （2）(x)P(x)(x)Q(x) (x)(P(x)Q(x) 解：解：（1）(x)(P(x)Q(x)(x)(P(x)Q(x)(x)(P(x)Q(x)(x)(P(x)Q(x) (x)P(x)(x)Q(x)(x)P(x)(x)Q(x)(x)P(x)(x)Q(x) (x)P(x)(x)Q(x) (x)P(x)(x)Q(x) (x)P(x)(x)Q(x) （2）(x)P(x)(x)Q(x) (x)(P(x)Q(x)不成立。 P(x)：x 成绩优秀。Q(x)：x 获得奖学金。论域为所有学生。(x)P(x)(x)Q(x)表示：若所有学生成绩都优秀，则所有学生都获得奖学金。 (x)(P(x)Q(x)表示：任何一个学生，只要成绩优秀，他就获得奖学金。 显然“任何一个学生，只要成绩优秀，他就获得奖学金。 ”可以推出“若所有学生成绩都优秀，则所有学生都获得奖学金。 ”反之未必成立。 14. 求证：(x)(P(x)Q(x)(x)P(x)(x)Q(x) 证明：证明：(x)(

8、P(x)Q(x) (x)( P(x)Q(x) (x)P(x)(x)Q(x) (x) P(x)(x)Q(x) (x)P(x)(x)Q(x) 15. 求证：(x)(y)(P(x)Q(y)(x)P(x)(y)Q(y) 证明：证明：(x)(y)(P(x)Q(y) (x)(y)( P(x)Q(y) (x) P(x)(y)Q(y) (x)P(x)(y)Q(y)(x)P(x)(y)Q(y) 16. 下列推导过程中有何错误？ （1）(x)(P(x)Q(x)P （2）P(a)Q(a)US(1) （3）(x)P(x)P （4）P(a)ES(3) （5）Q(a)T(2),(4) I （6）(x)Q(x)EG(5) 解：解：应先消去存在量词。 17. 把以下各式化为前束范式。 （1）(x)(P(x)(y)Q(x，y) （2）(x)(y)P(x，y)(z)Q(z)R(x) （3）(x)(y)(z)P(x，y，z)(u)Q(x，u)(v)Q(y，v) 解：解： （1）(x)(P(x)(y)Q(x，y) (x)(P(x)(y)Q(x，y) (x)(y)(P(x)Q(x，y) （2）(x)(y)P(x，y)(z)Q(z)R(x) (x)(y)P(x，y)(z)Q(z)R(x) (x)(y)P(x，y)(z)Q(z)R(x) (x)(y)P(x，y)(z) Q(z)R(x) (x)(y)(z)(P(x，y)Q(z)R(x) （3）(x)(y)(z)P(x，y，z)(u)Q(x，u)(v)Q(y，v) (x)(y)(z)P(x，y，z)(u)Q(x，u)(v)Q(y，v) (x)(y)(z) P(x，y，z)(u) Q(x，u)(v) Q(y，v) (x)(y)(z)(u)(v)(P(x，y，z)Q(x，u)Q(y，v) 18. 求等价于下面各式的前束析取范式和前束合取范式。 （1）(x)P(x)(x)Q(x) (x)(P(x)Q(x) （2）(x)(P(x)(y)(z)Q(x，y)(z)R(y，x) （3）(x)P(x)(x)(z)Q(x

《离散数学课后习题+答案》由会员mg****85分享，可在线阅读，更多相关《离散数学课后习题+答案》请在金锄头文库上搜索。