离散数学1—6

★ 形成性考核作业 ★

1

离散数学作业6

离散数学数理逻辑部分形成性考核书面作业

本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业．

要求：学生提交作业有以下三种方式可供选择：

1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅．

2. 在线提交word文档

3. 自备答题纸张，将答题过程手工书写，并拍照上传．

一、填空题

1．命题公式()PQP的真值是 1或T ．

2．设P：他生病了，Q：他出差了．R：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 P∨Q→R

．

3．含有三个命题变项P，Q，R的命题公式PQ的主析取范式是 (PQ┐R) ∨(PQR)

4．设P(x)：x是人，Q(x)：x去上课，则命题“有人去上课．” 可符号化为

∃ x ( P ( x) ∧ Q ( x)) ．

5．设个体域D＝{a, b},那么谓词公式)()(yyBxxA消去量词后的等值式为

(A(a) ∨A(b)) ∨ (B(a) ∧B(b)) ．

6．设个体域D＝{1, 2, 3}，A(x)为“x大于3”，则谓词公式(x)A(x) 的真值为 0 ．

7．谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为 y ．

离散数学练习题

第一章

一．填空

1.公式)()(qpqp的成真赋值为 01；10

2.设p, r为真命题，q, s 为假命题，则复合命题)()(srqp的真值为 0

3.公式)()()(qpqpqp与共同的成真赋值为 01；10

4.设A为任意的公式，B为重言式，则BA的类型为 重言式

5．设p, q均为命题，在 不能同时为真 条件下，p与q的排斥也可以写成p与q的相容或。

二．将下列命题符合化

1. 7不是无理数是不对的。

解：)(p，其中p: 7是无理数； 或p，其中p: 7是无理数。

2.小刘既不怕吃苦，又很爱钻研。

解：其中,qpp: 小刘怕吃苦，q：小刘很爱钻研

3.只有不怕困难，才能战胜困难。

解：pq，其中p: 怕困难，q: 战胜困难

或qp，其中p: 怕困难， q: 战胜困难

4.只要别人有困难，老王就帮助别人，除非困难解决了。

解：)(qpr，其中p: 别人有困难，q:老王帮助别人 ，r: 困难解决了

或：qpr)(，其中p:别人有困难，q: 老王帮助别人，r: 困难解决了

5.整数n是整数当且仅当n能被2整除。

解：qp，其中p: 整数n是偶数，q: 整数n能被2整除

三、求复合命题的真值

P：2能整除5， q：旧金山是美国的首都， r：在中国一年分四季

1. ))(())((qprrqp

2.rqpprpq)(())()((

解：p, q 为假命题，r为真命题

1.))(())((qprrqp的真值为0

2. rqpprpq)(())()((的真值为1

四、判断推理是否正确

设xy2为实数，推理如下： 若y在x=0可导，则y在x=0连续。y 在x=0连续，所以y在x=0可导。

解：xy2，x为实数，令p: ｙ在ｘ=0可导，q: y在x=0连续。P为假命题，q为真命题，推理符号化为：pqqp)(，由p，q得真值可知，推理的真值为0，所以推理不正确。

《离散数学》习题一参考答案

第一节 集合的基数

1.证明两个可数集的并是可数集。

证明：设A，B是两可数集，},,,,,{321naaaaA，},,,,,{321nbbbbB

jbiaNBAfji212: ，f是一一对应关系，所以|A∪B|=|N|=0。

2．证明有限可数集的并是可数集

证：设kAAAA321,,是有限个可数集，kiaaaaAiniiii,,3,2,1),,,,,(321

ikjaNAAfijkii)1(:1，f是一一对应关系，所以|A|=|kiiA1|=|N|=0。

3.证明可数个可数集的并是可数集。

证：设kAAAA321,,是无限个可数集，,3,2,1),,,,,(321iaaaaAiniiii

ijijiaNAAfijii)2)(1(21:1，

所以f是一一对应关系，所以|A|=|1iiA|=|N|=0。

4.证明整系数多项式所构成的集合是可数集。

证明：设整系数n次多项式的全体记为

}|{1110ZaaxaxaxaAinnnnn

则整系数多项式所构成的集合1NnAA；

由于kx的系数ka是整数，那么所有kx的系数的全体所构成的集合是可数集，由习题2“有限个可数集的并是可数集”可得nA是可数集，再又习题4“可数个可数集的并是可数集”得出整系数多项式所构成的集合1NnAA也是可数集。 5.证明不存在与自己的真子集等势的有限集合.

证明：设集合A 是有限集，则|A|=n，若B是A的真子集，则|B|≤|A|=n，A-B≠φ，即|A-B|=|A|-|AB|＞0；又A=（A-B）∪B，（A-B）B=φ，所以，，就是|A|＞|B|，即得结论。

6．证明正有理数集合是可数集，从而能证明有理数集是可数集。

证明：因为},|{NnmnmQ，是正分数集，

离散数学练习题

第一章

一．填空

1.公式)()(qpqp的成真赋值为 01；10

2.设p, r为真命题，q, s 为假命题，则复合命题)()(srqp的真值为 0

3.公式)()()(qpqpqp与共同的成真赋值为 01；10

4.设A为任意的公式，B为重言式，则BA的类型为 重言式

5．设p, q均为命题，在 不能同时为真 条件下，p与q的排斥也可以写成p与q的相容或。

二．将下列命题符合化

1. 7不是无理数是不对的。

解：)(p，其中p: 7是无理数； 或p，其中p: 7是无理数。

2.小刘既不怕吃苦，又很爱钻研。

解：其中,qpp: 小刘怕吃苦，q：小刘很爱钻研

3.只有不怕困难，才能战胜困难。

解：pq，其中p: 怕困难，q: 战胜困难

或qp，其中p: 怕困难， q: 战胜困难

4.只要别人有困难，老王就帮助别人，除非困难解决了。

解：)(qpr，其中p: 别人有困难，q:老王帮助别人 ，r: 困难解决了

或：qpr)(，其中p:别人有困难，q: 老王帮助别人，r: 困难解决了

5.整数n是整数当且仅当n能被2整除。

解：qp，其中p: 整数n是偶数，q: 整数n能被2整除

三、求复合命题的真值

P：2能整除5， q：旧金山是美国的首都， r：在中国一年分四季

1. ))(())((qprrqp

2.rqpprpq)(())()((

解：p, q 为假命题，r为真命题

1.))(())((qprrqp的真值为0

2. rqpprpq)(())()((的真值为1

四、判断推理是否正确

设xy2为实数，推理如下：

若y在x=0可导，则y在x=0连续。y 在x=0连续，所以y在x=0可导。

解：xy2，x为实数，令p: ｙ在ｘ=0可导，q: y在x=0连续。P为假命题，q为真命题，推理符号化为：pqqp)(，由p，q得真值可知，推理的真值为0，所以推理不正确。