离散数学复习题(13页).doc

《离散数学复习题(13页).doc》由会员分享，可在线阅读，更多相关《离散数学复习题(13页).doc（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、-离散数学复习题-第 13 页一、单项选择题1对任意集合A、B、C，下述论断正确的是 【 A 】（A）若AB，BC，则 AC （B）若AB，BC，则 AC （C）若AB，BC，则 AC （D）若AB，BC，则 AC2设，则下列选项错误的是 【 B 】（A） （B） （C） （D）3设上的关系如下，有传递关系的有 【 D 】（A） （B）（C） （D）4R是A上的自反关系，则 【 B 】（A） （B） （C） （D）5中含3条边的不同构生成子图有 【 C 】（A）1个 （B）2个 （C）3个 （D）4个6设为无向图，,若连通，则 【 D 】（A） （B） （C） （D）7欧拉回路是 【 B 】（

2、A）路径 （B）简单回路 （C）既是基本回路也是简单回路 （D）既非基本回路也非简单回路85阶无向完全图的边数是 【 B 】：（A）5 （B）10 （C）15 （D）209设A ，B ，C，则（AB） C为 【 C 】（A） （B） （C） （D）10设，则下列选项错误的是 【 D 】（A） （B） （C） （D）11集合上的关系, 则R的性质为 【 B 】（A）自反的 （B）对称的 （C）传递的、对称的 （D）反自反的、传递的12设R是非空集A上的二元关系，则R的对称闭包s(R) 【 B 】（A） （B） （C） （D）13若简单图G与其补图同构，称G为自补图，则含有5个结点不同构的无向自补

3、图的个数为 【 C 】（A）0 （B）1 （C）2 （D）314设为无向图，,若连通，则 【 D 】（A） （B） （C） （D）15欧拉回路是 【 B 】（A）路径 （B）简单回路 （C）既是基本回路也是简单回路 （D）既非基本回路也非简单回路16个结点的无向完全图的边数是 【 D 】：（A） （B） （C） （D）17设P:我将去镇上,Q:我有时间。命题“我将去镇上,仅当我有时间时”符号化为【 A 】 (A) PQ, (B) QP , (C) QP , (D) QP18下面哪个命题是命题“2是偶数或3是负数”的否定？ 【 C 】(A) 2是偶数或3不是负数, (B) 2是奇数或3不是负数,

4、(C) 2不是偶数且3不是负数, (D) 2是奇数且3是不负数,19下面哪个联结词运算不可交换 : 【 B 】(A) , (B) , (C) , (D) 20 命题公式(P(PQ)Q 是 ; 【 C 】(A) 矛盾式, (B) 蕴含式, (C) 重言式 , (D) 等值式21下列命题联结词集合中,哪个是最小联结词组; 【 C 】(A) , (B) (C) (D) 22下面那一个命题是假命题; 【 A 】(A) 如果2是偶数,那么一个公式的析取范式唯一, (B) 如果2是偶数,那么一个公式的析取范式不唯一,(C) 如果2是奇数,那么一个公式的析取范式唯一,(D) 如果2是奇数,那么一个公式的析取

5、范式不唯一23谓词公式中变元是; 【 D 】（A）自由变元, (B) 约束变元, (C) 既不是自由变元也不是约束变元, (D) 既是自由变元也是约束变元24设:x是人, :x犯错误,命题“没有不犯错误的人”符号化为; 【 D 】(A), (B), (C) , (D) 25命题公式 (PQ)R的成真赋值为; 【 B 】(A)000, 001,110 (B) 001, 011, 101,110,111(C)全体赋值 (D) 无26下面语句中哪个是真命题； 【 D 】(A) 我在说谎, (B) 严禁吸烟 ,(C) 如果1+2=3,那么雪是黑的, (D) 如果1+2=5,那么雪是黑的27设P:我们划

6、船,Q:我们跑步。命题“我们不能既划船又跑步”符号化为【 B 】 (A) PQ, (B) PQ , (C) （PQ）, (D) PQ 28下面哪个命题是命题“2是偶数或3是负数”的否定？【 C 】。(B) 2是偶数或3不是负数, (B) 2是奇数或3不是负数,(C) 2不是偶数且3不是负数, (D) 2是奇数且3是不负数,29下面哪个联结词运算不可交换【 C 】。(A) , (B) , (C) , (D) 30 下面哪个命题公式是重言式 【 B 】。(A) (PQ)(QP), (B) (PQ)P, (C) (PQ)(PQ) , (D) （PQ）31下列命题联结词集合中,哪个不是最小联结词组【

7、C 】。(A) , (B) (C) (D) 32命题公式PQR的对偶式是【 D 】。(C) P（QR）, （B）P（QR）， （C）P（QR）， （D）P（QR）33谓词公式中变元是【 D 】。 （A）自由变元, (B) 约束变元, (C) 既不是自由变元也不是约束变元, (D) 既是自由变元也是约束变元34设:x是运动员, :x是强壮的,命题“没有一个运动员不是强壮的”符号化为【 C 】。(A), (B), (C) , (D) 35的否定是【 B 】。(A) ， (B) ，(C) ， (D) 36在谓词演算中，下列各式正确的是【 A 】：(A) , (B) ,(C) , (D) 二、填空题1

8、.若集合A的基数，则其幂集的基数 1024 。 2.设，则 15 。3.设N表示非负整数集，R：NN，xRy定义为x+2y10，则Dom(R)0,2,4,6,8,10 Ran(R)5,4,3,2,1,0 4.A=,R是A上的整除关系，那么A的极大元是 10，24 ,极小元是 2，3，5 ,。5.设A=上的关系，则R具备 反对称性 、传递性，R不具备 自反性、反自反性和对称性。6.设G=（n,m）是简单图,v是G中度数为k的结点，e是G中的一条边，则Ge中有n个结点，m1 条边。7. 3个结点可构成 4 个不同构的简单无向图。8.具有p个顶点的完全图K有个生成树，p2。9.设G是一个有k个支的图

9、，如果S是G的割集，则G-S恰有 k+1 个支。10.设A= ，则AA= ， 2 。 11.集合的幂集 。12.设R是集合上的模7同余关系，则. 。13. A=,R是A上的整除关系，那么A的极大元是 10，24 ,极小元是 2，3，5 ,。14.整数集上的小于关系“”具有 反自反 、 反对称 和 传递 性。15.设G=（n,m）是简单图,v是G中度数为k的结点，e是G中的一条边，则Gv中有n1个结点，mk 条边。16.3个结点可构成 4 个不同构的简单无向图。17.具有p个顶点的完全图K有个生成树，p2。18.设S是连通图G=（V，E）的割集，则G-S恰有 2 个支。19.设P:我生病,Q:我

10、去学校看电影 (1) 命题“我虽然生病但我仍去学校”符号化为 PQ 。(2) 命题“只有在生病的时候，我才不去学校”符号化为PQ 。20. 设P、Q为两个命题，德摩根律可表示为，（或）， 吸收律可表示为 （或）。21.公式的主析取范式为, 主合取范式的编码表示为。22.中,的作用域为, 的作用域为, 的作用域为。23.谓词公式的前束范式为。24.设P:我有钱,Q:我去看电影 (1) 命题“如果我有钱, 那么我就去看电影”符号化为。(2) 命题“虽然我有钱, 但我不去看电影”符号化为。25.命题公式的成真赋值为 010， 100， 101， 110，111 , 成假赋值为 000，001，011

11、。26. 公式的主析取范式为, 主合取范式的编码表示为。27. 中,的作用域为, 的作用域为, 的作用域为。28.谓词公式的前束范式为。三、计算题1、用等值演算法化简并判断下列公式的类型(P(QR)(QR)(PQ)解：原式(P(QR)(QP)R) (PQ)R)(QP)R) (PQ)R)(QP)R) (PQ)(QP)R) (PQ)(PQ)R) TR R 故原式为可满足式 2、求命题公式(pq)（pq）的合取范式、析取范式、主合取范式和主析取范式。解：合取范式：(pq)（pq）=(pq)（pq）（qp） =(pq)（pq）（pq） = (pq)（pq）（pq） = pq析取范式：(pq)（pq）=

12、(pq)（pq）（pq） = (pq)（pq）（pq）主合取范式：(pq)（pq）= pq（=）主析取范式：(pq)（pq）=(pq)（pq）（pq）=得分阅卷人3、给定集合A，且A中有关系：R= S=，计算RS4、在120名学生参加考试，这次考试有A，B，C共3道题，考试结果如下：有12人3道题都做对了，20人做对了A题和B题，16人做对了A题和C题，28人做对了B题和C题，做对了A题的有48人，做对了B题的有56人，还有16人一道题也没做对，求做对了C题的有多少人？解：设A,B,C分别为做对A题、B题、C题的人构成的集合， 故由题意有：根据包含排斥原理可知： 20+16+ 28+104 1

13、24856 52 故做对C题的有52人。 5、在1000名大学毕业生的调查中，有804人掌握了英语，205人掌握了日语，190人掌握了俄语，125人既掌握了英语又掌握了日语，57人既掌握了日语又掌握了俄语，85人既掌握了英语又掌握了俄语，求这1000名大学生中，英语、日语、俄语全掌握的有多少人。解：设A,B,C分别为掌握了英语、日语、俄语的人的集合， 则， 为既掌握英语又掌握日语的集；为掌握英语和俄语，为掌握日语和俄语的人的集合，为三种都掌握的人的集合， 故由题意得： 1000804 250190 1258557 23 于是，英语、日语、俄语全掌握的只有23人。6、设集合A=上的二元关系为,

14、R= （1）写出R的关系矩阵。（2）验证（A，R）是偏续集。（3）画出Hasse图。7、（1）设集合A=,是集合A的幂集，画出（，）的Hasse图。 V4（2）设X=，R=，写出R的关系矩阵，画出关系图。8、e6e4V1已知有向图D ，如图所示, 求e7e2e3 :（1）D的邻接矩阵；V3e5V2（2）D中到长度为4的通路数为多少？（3）D中长度小于等于4的通路有多少？其中有多少条是回路？9、已知图G ，Va,b,c,d,e,E, , , 求G的可达性矩阵P。10、用真值表法求命题公式(p(pq) (qr) (pr）的主析取范式和主合取范式。四、证明题1、设A，B，C为任意三个集合，证明A（B

15、C）（AB）（AC） 证： ，则且 即而且但， 于是但，即。从而 反之，有但，即且但。于是且，即， 从而 。由集合相等的定义得： 2、设A，B，C为任意三个集合，证明： A（BC）=（AB）（AC）证：对任意的x A（BC） ABC A A A （ AAB （AB） 所以 A（BC）=（AB）（AC） 3、写出下面推理的形式证明：如果数a是实数，则它不是有理数就是无理数。如果a不能表示成分数，则它不是有理数。a是实数且它不能表示成分数，所以a是无理数。解 设命题，p：a是实数， q：a是有理数， r：a是无理数，s： a能表示成分数。 前提：, 结论：r 证明： 前提引入 p 化简 化简 前提

16、引入 假言推理 前提引入 假言推理 r 析取三段论 4、写出下面推理的形式证明：如果今天是星期一，则要进行英语或离散数学考试。如果今天英语老师有会，则不考英语。今天是星期一，英语老师有会。所以今天进行离散数学考试。解 符号化题目中的命题，设p：今天是星期一，q：进行英语考试，r：进行离散数学考试，s：英语老师有会。 前提：, p, s结论：r 证明： 前提引入p 前提引入 假言推理 前提引入 s 前提引入 假言推理 r 析取三段论 5、在自然推理系统P中，用附加前提引入法构造下面的推理证明：前提：P(QS)，RP , Q 结论：RS 证明： (1)RP 前提引人 (2) RP (1)置换 (3

17、)R 附加前提引人 (4)P (2)(3)分离 (5)P(QS) 前提引入 (6)QS (4)(5)分离 (7)Q 前提引人 (8)S (6)(7)分离 (9)RS 条件证明规则6、在自然推理系统P中，构造下面的推理证明：前提：PQ ，PR，QS， 结论：SR 证明: (1) PQ 前提引入 (2)PQ (1)置换 (3) QS 前提引入 (4) S (2)(3)三段论 (5)SP (4)置换 (6) PR 前提引入 (7)SR (5)(6)三段论 (8)SR (7)置换7、书上114页定理7.9及证明过程。8、设无向图G中只有两个奇度顶点u与v，试证明u与v必连通。证明：用反证法。假设u与v

18、不连通，即u与v之间无通路，则u与v处于G的不同连通分支中。不妨设u在G1，v在G2中。于是，G1与G2作为G的子图，他们中均只含有一个奇度顶点，这与握手定理的推论矛盾。9、设n阶无向简单图G有m条边，已知m(n-1)(n-2)+1，证明G必连通。证明： （1）任何n阶简单图的 边数m均小于等于完全图Kn的边数n(n-1)。 （2）若G中无孤立点，则(G)1。用归纳法。 n=1时，G为平凡图，显然G连通。 n=2时，m(n-1)(n-2)+1=1，此时G为K2，当然连通。 设n=k(k2)，m(k-1)(k-2)+1时结论成立，要证明当n=k+1,mk(k-1)+1时结 论也成立。(i) 若G

19、为Kk+1，G当然连通。(ii) 若G中含孤立点，一定推出矛盾。删去G中的孤立点，记作G1。则G1的边数m k(k-1)+1，这与G1为阶数小于等于k的简单图矛盾，故G中不可能含孤立点。 (iii) 由(i)、(ii)可知，只需对G不为完全图、又不含孤立点的情况加以证明。 G中存在v0，使1d(v0)k-1（G中无孤立点，又不是k+1阶完全图）， 令G=G-v0，则G为k阶简单图，且G的边数 m k(k-1)+1-(k-1) =( k(k-1)-(k-1)+1 =(k-1)(k-2)+1 由归纳假设可知，G是连通图，而G为G的子图，故G也连通。 10、设G为n阶无向简单图，证明以下题目： （1

20、）当(G)时，证明G连通。证明（1）用反证法。假设G至少有两个连通分支，设G1,G2为其中的两个，并设G1,G2的阶数分别为n1和n2，则n1+n2n，且minn1,n2 。于是，对任意的 vV(G1)， dG1(V)= dG(V) -1 ，这与(G)矛盾，所以G连通。 （2）当(G)(n+k-1)时，证明G是k-连通图。证明：设V为V(G)的任意子集，且|V|=k-1。令 G=G-V，则G为n-(k-1)=n-k+1=n阶无向简单图，而 (G)(G)-(k-1) (n+k-1)-(k-1) = (n+k-1-2k+2) = (n-k+1) =n 由当(G)时，G连通可知，G连通，故G为k-连通图。