离散数学作业.docx

1、离散数学作业命题逻辑的基本概念一、单项选择题1下列语句中不是命题的有（ ）.A 9+512 B. 1+3=5 C. 我用的电脑CPU主频是1G吗D.我要努力学习。2. 下列语句是真命题为( )A. 1+2=5当且仅当2是偶数 B.如果1+2=3，则2是奇数C. 如果1+2=5，则2是奇数 D. 你上网了吗3. 设命题公式,则使公式取真值为1的p，q，r赋值分别是 ( )4. 命题公式为 ( )(A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式5. 设p:我将去市里,q：我有时间命题“我将去市里，仅当我有时间时”符号化为为( ) 6设P：我听课,Q：我看小说. “我不能一边听课

2、，一边看小说”的符号为（ ）A. ； B. ； C. ； D. 二、判断下列语句是否是命题，若是命题是复合命题则请将其符号化（1）中国有四大发明。（2）2是有理数。（3）“请进！”（4）刘红和魏新是同学。（5）a+b（6）如果买不到飞机票，我哪儿也不去。（8）侈而惰者贫，而力而俭者富。（韩非：韩非子 显学）（9）火星上有生命。（10）这朵玫瑰花多美丽啊！二、将下列命题符号化，其中p:21,q:32（1）只要21，就有32。（2）如果21，则3 2。（3）只有21，才有3 2。（4）除非21，才有3 2。（5）除非21，否则3 2。（6）21仅当32。三、将下列命题符号化(1)小丽只能从筐里拿一

3、个苹果或一个梨。(2)王栋生于1992年或1993年。四、设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p(qr) （2）（pr）(qs) （3）（pqr）(pqr) (4)（rs）(pq) 五、用真值表判断下列公式的类型：(1) p(pq)(pq) (2) (pr) (pq)(2)(pq) (qr) (pr)命题逻辑等值演算一、填空（1）给定两个命题公式A，B，若 ，则称A和B时等值的，记作A B（2）德摩根律为： 。（3）蕴涵等值式为 。 （4）由已知的等值式推演出另外一些等值式的过程称为 。二、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求

4、出成真赋值.(1) (pqq)(2)(p(pq)(pr)(3)(pq)(pr)三、用等值演算法证明下面等值式(1)(pq)(pr)(p(qr)(2)(pq)(pq)(pq) (pq)三、用等值演算求下列公式的析取范式与合取范式。(1)( pq)(qp)(2) (pq)qr(3)(p(qr)(pqr)命题逻辑的推理理论填空1.数理逻辑的的主要任务是 。推理是指 ， 前提是 ，结论是 。2.推理正确是指： 3.命题公式A1，A,2， ，A,k推B的推理正确当且仅当 二、先把下列命题符号化，再写出前提、结论、推理的形式结构，然后用真值表法、等值演算法证明下列推理是正确的。若今天是星期一，则明天是星期

5、三。明天不是星期三，所以今天不是星期一。自然推理系统下用直接法或用附加前提法或用归谬法构造推理证明(1)前提：pq,(qr),r结论：p (2)前提：qp,qs,st,tr结论：pq（3）前提：p(qr),sp,q （4）前提：pq,rq,rs结论：sr 结论：p 在自然推理系统下构造下列推理的证明1.如果我学习，那么我数学不会不及格。如果不热衷于玩游戏，那么我将学习。但我数学不及格。因此我热衷于玩游戏。2.只要A曾到过受害者房间并且11点以前没离开，A就是谋杀嫌犯。A曾到过受害者房间。如果A在11点以前离开，看门人就会看见他。看门人没看见他。所以A是谋杀嫌犯。第五章一、1.设个体域D是正整数

6、集合，确定下列命题为真的是（ ）A x y (xy=y)B. x y(x+y=y)C. x y(x+y=x) D. x y(y=2x) 2. 设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式 x(P(x) Q(x)在哪个个体域中为真( )A.自然数B. 实数 C.复数D. (1)-(3)均成立3. 令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为 二、在一阶逻辑中将下列命题符号化:(1) 没有不能表示成分数的有理数。(2) 在北京卖菜的人不全是外地人。(3)乌鸦都是黑的。(4)有的人天天锻炼身体。三、设个体域D=a,b,c,消去下列各式的量词(1

7、) x y(F(x) G(y)(2) x y(F(x) G(y)(3) x F(x) y G(y)四、设个体域D=1,2,3,4，F(x):x是2的倍数，G(x):x是奇数。将命题 x (F(x) G(y)中的量词消去，并讨论命题的真值。五、在自然推理系统用直接法或用附加前提法或用归谬法构造下列推理的证明（1）前提： x (F(x) G(x), x F(x) 结论： x G(x) (2) 前提： x(F(x)G(x)结论： xF(x) x G(x)(3) 前提： x(F(x)G(x)， x G(x)结论： x F(x)第六章 集合论一、单项选择题1若集合A=a，b，B= a，b， a，b ，则

8、（ ） AA B，且A B BA B，但A B CA B，但A B DA B，且A B2若集合A2，a， a ，4，则下列表述正确的是( ) Aa， a A B a A C2 A D A3若集合A a，a，1，2，则下列表述正确的是( ) Aa，a A B2 ACa A D A4若集合A=a，b， 1，2 ，B= 1，2，则（ ） AB A，且B A BB A，但B A CB A，但B A DB A，且B A 5设集合A = 1, a ，则P(A) = ( ) A1, a B,1, a C,1, a, 1, a D1, a, 1, a 6若集合A的元素个数为10，则其幂集的元素个数为（ ） A

9、1024 B10 C100 D1二、1设集合A有n个元素，那么A的幂集合P(A)的元素个数为 2设集合Aa，b，那么集合A的幂集是 3.设A, B代表集合，命题A B 的真值为 4. 设A, B为任意集合，命题A B 的真值为 5. 设集合A= ,a，则A的幂集P(A)= 6. 设集合A=a,b,c, B=c,d, 那么AB 三、（1）B、C为任意的三个集合，如果AB=AC，判断结论B=C 是否成立并说明理由（2）B、C为任意的三个集合，如果AB=AC，判断结论B=C 是否成立并说明理由四、 1设集合Aa, b, c，B=b, d, e，求（1）B A； （2）A B； （3）AB； （4）B

10、 A2设A=a, b, 1, 2，B= a, b, 1, 1，试计算（1）（A B） （2）（AB） （3）（AB） （AB）五证明集合等式：A B=A B六、某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都会打篮球或排球。求不会打球的人数。第七章 二元关系（1）一、单项选择题1集合A=1, 2, 3, 4, 5, 6, 7, 8上的关系R=|x+y=10且x, yA，则R的性质为（ ） A自反的 B对称的 C传递且对称的 D反自反且传递的2设集合A = 1，2，3，4，5，6 上的二元关系R =a ,

11、b a , bA , 且a +b = 8，则R具有的性质为（ ）A自反的 B对称的C对称和传递的 D反自反和传递的3集合Aa,b,c上二元关系R的关系矩阵MR， R( )， (A) , (B) , (C) , (D) ,4.设A=a，b，c，R=，则R具有性质（ ）(A) 自反的 (B) 反自反的 (C) 反对称的 (D) 等价的二、填空题1设集合A=0, 1, 2, 3，B=2, 3, 4, 5，R是A到B的二元关系， 则R的有序对集合为 2设集合A=0, 1, 2，B=0, 2, 4,R是A到B的二元关系，则R的关系矩阵MR 3设集合A=a,b,c，A上的二元关系R=,，S=,则(R S)

12、1=4设集合A=a,b,c，A上的二元关系R=, , , ，则二元关系R具有的性质是三、设A=a，b，构成集合（A）A。四、(1)列出集合A=2,3,4上的恒等关系I A,全域关系EA,小于或等于关系LA,整除关系DA.(2)设A=a,b,c,d，为A上的关系，其中= 求。五、设集合Aa, b, c, d上的二元关系R的关系图如图1所示（1）写出R的表达式； （2）写出R的关系矩阵； （3）求出R2 六、设集合A=1，2，3，4，R=|x, y A；|x y|=1或x y=0，试（1）写出R的集合表示； （2）画出R的关系图；（3）说明R满足自反性，不满足传递性第七章 二元关系（2）一、选择题

13、1. 设集合A=a,b上的二元关系R=,，则R ( ) A. 是等价关系但不是偏序关系 B是偏序关系但不是等价关系C. 既是是等价关系又是偏序关系 D. 既不是等价关系又不是偏序关系2. A=1、2、3，则A上不同等价关系有( ) A. 5 C. 15 3. 设A为有限集，元素个数为n个，P(A)为A的幂集，则P(A)的元素个数及的元素个数为( ) A B 及 C 及 D以上全不对4. 设A是非空集合，则A上的空关系不具有( )A反自反性 B自反性 C对称性 D传递性5设，R是A上相等关系“=”，由R产生等价类有( ) A10个 B50个 C100个 D1个6.集合A的一个划分，确定A的元素间

14、的关系为( ). A全序关系B等价关系C偏序关系D拟序关系7集合A=1，2，3上的下列关系矩阵中符合等价关系条件的是（）A B C D8.给定A=1、2、3上的关系R=, , , , 则( )A R是自反的且传递 B R不反自反且不对称C R是反对称且不对称 D R不自反且传递9.设A=，1，1，3，1，2，3则A上包含关系“”哈斯图为（ ）二、设A=1，2，3，4,R=,是A上的等价关系吗如果是,给出给出每个元素的等价类；如果不是,请说明理由。三、设A=1，2，3，4，S=1，2，3，4为A的一个分划，求由S导出的等价关系.四、设集合A=1，2，3，6，8，12，24，36，R为A上整除关系

15、，画出R的哈斯图，并指出B=2，6，8的极大元，极小元、最大元，最小元、及上确界和下确界。五、设A=1，2，3，4，在AA上定义二元关系R， ,AA ，u,v R u + y = x + v.证明R 是AA上的等价关系.(2)确定由R 引起的对AA的划分.第八章 函数一、选择题1设A=a, b，B=1, 2，R1，R2，R3是A到B的二元关系，且R1=, ，R2=, , ，R3=, ，则（ ）不是从A到B的函数 AR1和R2 BR2 CR3 DR1和R32.设A=a，b，c，B=1，2，作f：AB，则不同的函数个数为( )A 6 C. 9 3.下列函数中为双射的是( ). A B C D4.设

16、Z是整数集，E=,-4,-2,0,2,4，f：ZE，f（x）=2x，则f是( )A仅是满射 B仅是单射 C是双射 D无逆函数二、判断下列函数中哪些是满射的哪些是单射的哪些是双射的 (1) f:NN, f(x)=x2+2 (2) f:NN,f(x)=(x)mod 3, x除以3的余数 (3) f:NN,f(x)= (4) f:N0,1,f(x)= (5) f:N-0R,f(x)=lgx (6) f:RR,f(x)=x2-2x-15 三、设X=a,b,c,d,Y=1,2,3,f=,判断以下命题的真假: (1)f是从X到Y的二元关系,但不是从X到Y的函数; (2)f是从X到Y的函数,但不是满射,也不

17、是单射的; (3)f是从X到Y的满射,但不是单射; (4)f是从X到Y的双射.四、设A=1,2，B=a,b,c,写出所有A到B的函数，并说明所具有的性质。五、已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少A到B的函数数是多少 六、设N是自然数集合，定义 N 上的二元关系R：R=(x,y): x N, y N, x+y 是偶数证明R是等价关系。 求 关系R的等价类。第十四、十五章 一、单项选择题1一个无向图有4个结点，其中3个的度数为2，3，3，则第4个结点的度数不可能是（ ） B. 1 C. 2 D. 42无向完全图有( )条边A. nB. n2 C.n(n-1)D. n(

18、n-1)/23整数列（1，3，3，5，4）（ ）A可以简单图化 B. 不可图化 C. 可图化，不可简单图化4若答案中的数值表示一个简单图中各个顶点的度，能画出图的是( ). A. (1,2,2,3,4,5) B. (1,2,3,4,5,5) C. (1,1,1,2,3) D. (2,3,3,4,5,6).5设简单图G所有结点的度之和为12，则G一定有( ). A3条边 B4条边 C5条边 D6条边6设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是（）A3 B4 C5 D67下列各图中既是欧拉图，又是汉密尔顿图的是（）A B C D8.设G为完全二部图K2,3，

19、下面命题中为真的是( )为欧拉图 为哈密尔顿图为平面图 为正则图二、填空1简单无向图有21条边,3个4度结点,其余均为3度结点,则G有_个结点.2无向图G=,V=a,b,c,d,E=(a,b),(a,c),(a,d),(b,c),则它的邻接矩阵为 ，该图的补图有 条边。3.设K6是有6个点的完全图，则K6共有_条边。4. .已知n阶无向简单图G有m条边，则G的补图G有_条边。5. 若一条路中，所有边均不相同，则此路称作_；若一条路中所有的结点均不相同，则称此路为_。6设无向图G有18条边且每个顶点的度数都是3，则图G有 个顶点。 7任一有向图中，度数为奇数的结点有()个。 8. 无向连通图G含

20、有欧拉回路的充分必要条件是 9.已知n阶无向图G中有m条边，各顶点的度数均为3。又已知2n-3=m，则m= .三、（1）已知无向图G有12条边，1度顶点有2个，2度、3度、5度顶点各1个，其余顶点度数均为4，求4度顶点的个数。（2）假设在图G(有向图或无向图)中，有10条边，4个3度的结点，其余结点的度数不大于2。问G中至少有几个结点四、判断下图是否欧拉图，若是，找出一个欧拉回路。五设简单无向图G有n个结点,n+1条边，证明G中至少有一上结点的度3。六、画出彼德森图，K5，K3,3，并判断他们是否是欧拉图，是否是哈密顿图。第十六、十七章一、选择题1设G是有6个结点的无向完全图，从G中删去( )

21、条边，则得到树 (A) 6 (B) 9 (C) 10 (D) 152设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ）A2 B3 C4 D53.下列编码是前缀码的是( ).A.1,11,101 B.1,001,0011 C.1,01,001,000D.0,00,0004.下图所示的二叉树中序遍历的结果是（ ）Aabcde Bedcba Cbdeca Dbadce5. 若连通图G=,其中=n，=m则要删去G中( )条边,才能确定G的一棵生成树. A. nm1 B. nm+1 C. mn+1 D. mn1.6.关于含有n片树叶的最优二叉树描述,不正确的是( ).A. 含有n片树叶的最优

22、二叉树每个分支点都有两个孩子；B. 含有n片树叶的最优二叉树分支点的个数是n-1；C.W(T)等于个分支点的权重（构造最优二叉树时产生）之和；D. 在权重一定的前提下，含有n片树叶的最优二叉树是惟一的。7. 若一棵完全二叉树有2n-1个顶点，则它（ ）片树叶。A nB. 2n D. 2二、1.一棵二叉树先序遍历得ABDECF，中序遍历得DBEACF,则后序遍历的结果是_。2. 在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有 个4度结点。3.最优二叉树有n片树叶，则它有 分支点。4. 设T=V,E是一棵树，若|V|1，则T中至少存在 片树叶。三、1.(1)在一棵有2个2度顶点，4个3度顶点，其余顶点都是树叶的无向树中应该有几片树叶(2)画出两棵非同构的满足上述条件的无向树。2. 画一棵带权为2，2，2，3，3，4，5，8的最优二叉树T，并计算它的权W（T）。3. 求下2图的最小生成树。 4.已知连通的平面图G的阶数n=6，边数m=8，面数r=4。求G的对偶图G*的阶数n*，边数m*，面数r*。四、证明若图G是自对偶的，则m=2n2。其中n为G的结点数，m为G的边数。