《离散数学》练习题和参考答案.pdf
《《离散数学》练习题和参考答案.pdf》由会员分享,可在线阅读,更多相关《《离散数学》练习题和参考答案.pdf(55页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、 离散数学练习题和参考答案-、选择或填空(数理逻辑部分)1、下列哪些公式为永真蕴含式?()(1)-i Q=Q-P(2)-Q=P-Q(3)P=P-Q(4)PA(PV Q)=p 答:(1),(4)2、下列公式中哪些是永真式?()(1)(-1 P A Q)-(Q-r R)(2)P-(Q-Q)(3)(PA Q)-P(4)P-(PV Q)答:(2),(3),(4)3、设有下列公式,请问哪几个是永真蕴涵式?()P=PA Q(2)PA Q=p (3)PA Q=PV Q(4)PA (P-Q)=Q(5)(P-Q)=P(6)PA (PV Q)=-1P 答:(2),(3),(4),(5),(6)4 公式W x(A(
2、x)-B(y,X)A 3Z C(y,z)7D(x)中,自由变元是(),约束变元是()。答:x,y,x,z5、判断下列语句是不是命题。若是,给出命题的真值。()北京是中华人民共和国的首都。(2)陕西师大是一座工厂。(3)你喜欢唱歌吗?(4)若 7+8 18,则三角形有4条边。(5)前进!给我一杯水吧!答:(1)是,T (2)是,F(3)不是(4)是,T (5)不是(6)不是6、命 题“存在一些人是大学生”的否定是(),而命题“所有的人都是要死的”的否定是()。答:所有人都不是大学生,有些人不会死7、设 P:我生病,Q:我去学校,则 下 列 命 题 可 符 号 化 为()。(1)只有在生病时,我才
3、不去学校(2)若我生病,则我不去学校(3)当且仅当我生病时,我才不去学校(4)若我不生病,则我一定去学校答:(1)Q.P (2)(3)Q(4)P 8、设个体域为整数集,则下列公式的意义是()。(1)V x 3y(x+y=0)(2)3y V x(x+y=0)答:(1)对任一整数x 存在整数y 满足x+y=O(2)存在整数y 对任一整数x 满 足 x+y=O9、设全体域D是正整数集合,确定下列命题的真值:(1)V x 3y (x y=y)()(2)3x V y (x+y=y)()(3)3x V y(x+y-x)()(4)V x R(y=2x)()答:(1)F(2)F(3)F(4)T10、设谓词P(
4、x):x是奇数,Q(x):x是 偶 数,谓 词 公 式 七(P(x)v Q(x)在哪个个体域中为真?()自 然 数 实 数 (3)复数(4)(1)(3)均成立 答:11、命 题“2 是偶数或-3是负数”的否定是()。答:2 不是偶数且-3不是负数。12、永真式的否定是()(1)永 真 式(2)永 假 式(3)可 满 足 式(4)(1)(3)均有可能 答:(2)13、公式(PA Q)v (P人Q)化 简 为(),公式 Q (PV (P AQ)可化简为()。答:P,Q P14、谓词公式V x(P(x)v 力口丫)7式M 中量词 的辖域是()。答:P(x)v 3y R(y)15、令 R(x):x 是
5、实数,Q(x):x 是有理数。则命题”并非每个实数都是有理数”的符号化表示为()。答:-VX(R(X)T Q(X)(集合论部分)16、设人=匕,a,下列命题错误的是()。a e p(A)(2)a=P(A)(3)a e p(A)(4)a=P(A)答:(2)17、在 0()之间写上正确的符号。=(2)=(3)e (4)任 答:18、若集合S的基数|S|=5,则 S的幕集的基数1P(S)|=()。答:3219、设 =仅|6+1)2 W4且 x W R,Q=x|5x 2+16 且 x W R,则下列命题哪个正确()(1)Q U P (2)Q G P (3)P U Q (4)P=Q 答:(3)20、下列
6、各集合中,咖几个分别相等(),(1)A l=a,b (2)A 2=b,a (3)A 3=a,b,a(4)A 4=a,b,c(5)A 5=x|(x-a)(x-b)(x-c)=0(6)A 6=x|x 2-(a+b)x+a b=0答:A 1=A 2=A 3=A 6,A 4=A 521、若 A-B=,则下列哪个结论不可能正确?()(1)A=a (2)B=8 (3)A U B (4)B U A答:(4)22、判断下列命题哪个为真?()(1)A-B=B-A =A=B (2)空集是任何集合的真子集(3)空集只是非空集合的子集(4)若 A的一个元素属于B,则 A=B答:23、判断下列命题哪几个为正确?()(1
7、)W ,(2)=,(3)e 0(4)G 中(5)a,b e a,b,a,b 答:(2),(4)24、判断下列命题哪几个正确?()所有空集都不相等(2)H(4)若 A为非空集,则 AUA成立。答:(2)25、设 A C B=A C C,入 A B=A CC,则 B()C。答:=(等于)26、判断下列命题哪几个正确?()(1)若 A U B=A U C,则 B=C (2)a,b)=b,a P(AC B)W P(A)C P(B)(P(S)表示 S 的舞集)(4)若 A 为非空集,则 A。A U A 成立。答:(2)27、A,B,C是三个集合,则下列哪几个推理正确:(1)A B,BGC=A C (2)
8、A1B,B.C=AS B(3)Ae B,BGC=Ae C 答:(二元关系部分)28、设 人=1,2,3,4,5,6,B=1,2,3),从 A 到 B 的关系 R=x,y)|x=y 2,求 RR-l o答:答)R=,(2)R-1=,29、举出集合A 上的既是等价关系又是偏序关系的一个例子。()答:A的恒等关系3 0、集合A 上的等价关系的三个性质是什么?()答:自反性、对称性和传递性3 1、集合A 上的偏序关系的三个性质是什么?(答:自反性、反对称性和传递性3 2、设$=1 ,2,3,4,A 上的关系口=1,2,2,1,2,3 ,3,4 求 R o R答:R o R =1,1),1,3 ,2,2
9、,R-1=2,1,1,2,2,4,3 3 3、设 人=(1,2,3,4,5,6),R是 A 上的整除关系,求 R=()R-1。答:R=,3 4、设 人=1,2,3,4,5,6,B=1,2,3,从A 到 B 的关系 R=x,y|x=2y,求 RR-l答:(1)R=,(2)RT=,2,4 ,(3 6 3 5、设 人=1,2,3,4,5,6,B=1,2,3 ,从 A 到 B 的关系 R=(x,y)|x=y 2),求 R和 R-1的关系矩阵。答:R的关系矩阵=ooO1oOlooooOoooooORi的关系矩阵=3 6、集合A=1,2,,10上的关系R=x,y|x+y=10,x,y G A,则 R的性质
10、为()。100000000010000000(1)自反的(2)对称的(3)传递的,对 称 的(4)传递的(代数结构部分)3 7、设 4=2,4,6,A 上的二元运算*定义为:a*b=m a x a,b,则在独异点 A,*中,单位元是(),零元是()答:2,63 8、设八=3,6,9,A 上的二元运算*定义为:a*b=m i n a,b,则在独异点 A,*中,单位元是(),零元是();答:9,3(半群与群部分)3 9、设 G,*是一个群,则(1)若 a,b,x GG,a*x=b,贝 U x=();(2)若 a,b,x W G,a*x 二 a*b,贝 lj x=()。答:(1)a-*b (2)b4
11、 0、设 a 是 12阶群的生成元,则22是()阶元素,23 是()阶元素。6,44 1、代数系统 G,*是一个群,则G 的等幕元是()。单位元4 2、设 a是 10阶群的生成元,则 24 是()阶元素,3是()阶元素。5,104 3、群 G,*的等嘉元是(),有()个。单位元,14 4、素数阶群一定是()群,它的生成元是()0一非单位元4 5、设 G,*是一个群,a,b,c W G,则(1)若 c*a=b,则 c=();(2)若 c*a=b*a,则 c=()。b4 6、H,*是 3,*的子群的充分必要条件是()0答:H,*是群 或 W a,b WG,a*b H,a-l H 或 V a,b e
12、 G,a*b-l H4 7、群A,*的等金元有()个,是(),零元有()个。位元,04 8、在一个群 G,*中,若 G 中的元素a的阶是k,则 a-1的阶是()。4 9、在自然数集N 上,下列哪种运算是可结合的?()(1)a*b=a-b (2)a*b=m a x a,b (3)a*b=a+2b (4)a*b=|a-b|5 0、任意一个具有2 个或以上元的半群,它(1)不可能是群(2)不一定是群(3)定是群(4)是交换群5 1、6阶有限群的任何子群一定不是()。(1)2 阶(2)3阶 4阶(4)6阶(格与布尔代数部分)5 2、下列哪个偏序集构成有界格()(1)(N,)(2)(Z,2)(3)(2,
13、3,4,6,12,|(整除关系)(P(A),=)5 3、有限布尔代数的元素的个数一定等于(偶数奇数(3)4的倍数(4)2 的正整数次基答:答:答:答:答:循环群,任答:(1)1 3*/(2)答:1,单答:k(图论部分)5 4、设 G 是一个哈密尔顿图,则 G 一定是()。(1)欧 拉 图(2)树 平 面 图 (4)连通图5 5、下面给出的集合中,哪一个是前缀码?()(1)(0,10,110,101111)(2)01,001,000,1)(3)b,c,a a,a b,a b a (4)1,11,101,001,0011)5 6、一个图的哈密尔顿路是一条通过图中()的路。且恰好一次5 7、在有向图
14、中,结点v 的出度d e g+(v)表示(),入度d e g-(v)表示(),答:以 v 为起点的边的条数,以 v 为终点的边的条数5 8、设 G 是一棵树,则 G 的生成树有()棵。0 1 (3)2(4)不能确定5 9、n 阶无向完全图K n的边数是(),每个结点的度数是()。“(一1)答:2,n-l6 0、棵无向树的顶点数n与边数m关系是()。m=n-l6 1、个图的欧拉回路是一条通过图中()的回路。好一次6 2、有 n个结点的树,其结点度数之和是()。2n-26 3、下面给出的集合中,哪一个不是前缀码()。(1)a,a b,110,a l b l l (2)01,001,000,1(3)
15、1,2,00,01,0210(4)12,11,101,002,0011答:6 4、n个结点的有向完全图边数是(),每个结点的度数是()答:n (n-l),2n26 5、一个无向图有生成树的充分必要条件是()。答:它是连通图6 6、设 G 是 棵 树,n,m 分别表示顶点数和边数,则(1)n=m (2)m=n+l (3)n=m+l (4)不能确定。答:(3)6 7、设 T=(V,E)是一棵树,若|V|1,则 T中至少存在()片树叶。答:2答:所有结点一次答:答:所有边一次且恰答,68、任何连通无向图G至少有()棵生成树,当且仅当G是(),G的生成树只有一棵。答:1,树69、设 G是有n 个结点m
16、条边的连通平面图,且有k 个面,则 k 等于:(1)m-n+2 (2)n-m-2 (3)n+m-2 (4)m+n+2。答:70、设 T 是一棵树,则 T 是一个连通且()图。答:无简单回路71、设无向图G有 1 6条边且每个顶点的度数都是2,则图G有 X )个顶点。(1)1 0(2)4(3)8(4)1 6答:72、设无向图G有 1 8条边且每个顶点的度数都是3,则图0 有()个 顶 点。(1)1 0(2)4(3)8(4)1 2答:(4)73、设图设 V,E ,V=a,b,c,d,e ,E=,则 G 是有向图还是无向图?答:有向图74、任一有向图中,度数为奇数的结点有()个。答:偶数75、具有6
17、 个顶点,1 2 条边的连通简单平面图中,每个面都是由()条边围成?(1)2 (2)4(3)3 (4)5答:76、在有n 个顶点的连通图中,其 边 数()。(1)最多有n-1 条(2)至少有nT 条(3)最多有n条(4)至少有n条答:(2)77、棵树有2个 2 度顶点,1个 3 度顶点,3 个 4 度顶点,则其1 度顶点为()。(1)5(2)7(3)8(4)9答:78、若一棵完全二元(叉)树有2 n-l 个顶点,则 它()片树叶。(1)n (2)2 n (3)n-1 (4)2答:(1)79、下列哪一种图不一定是树()。(1)无简单回路的连通图(2)有 n个顶点n-1 条边的连通图(3)每对顶点
18、间都有通路的图(4)连通但删去一条边便不连通的图答:(3)80、连通图G是一棵树当且仅当G中()0(1)有些边是割边(2)每条边都是割边(3)所有边都不是割边(4)图中存在一条欧拉路径答:(2)(数理逻辑部分)二、求下列各公式的主析取范式和主合取范式:1、(P-Q R解:(P f Q)(-P V Q)ARQ (PAR)V(Q A R)(析取范式)=(PA(QV-nQ)AR)V(ip V p)A Q A R)=(P A Q A R)V(ipA iQ AR)V(ifA Q A R)V(P A Q A R)U (PAQAR)V(-npA -iQ AR)V(p A Q A R)(主析取范式)(P-Q)
19、人 R)=(-1P A-iQ A-iR)V(PAQA R)V(P A-i Q A R)V(PAQA-R)v(PA-QA-R)(原公式否定的主析取范式)(P f Q)AR (PVQVR)A(PV-1QVR)A(p V Q VR)A(-pV -Q VR)A(IP V Q V R)(主合取范式)2、(PAR)V(QAR)V-p解:(PAR)V(QAR)V-p(析取范式)=(PA(QV-Q)AR)V(pV -ip)人QAR)V(-,p A(QV-i Q)A(R V-(R)(PAQAR)V(pA-Q AR)V(pAQAR)V(-!P A Q A R)V(iPAQAR)V(ip A Q A-iR)V(ip
20、 A i Q A R)V(P A i Q A-i R)=(P Q人 R)V(P 人QAR)V(-1P A Q人 R)V(-)P A Q人一1R)V(-p A-i Q A R)V(-ip A-i Q A-i R)(主析取范式)(PAR)V(QAR)V-P)=(P AQ人R)V(P A Q AR)(原公式否定的主析取范式)(PAR)V(QAR)V-ip O (P VQ VR)人(一ipV -.Q V R)(主合取范式)3、(一 P-Q)人(Rvp)解:(P fQ)人(RVp)=(P V Q)A(RV p)(合取范式)=(PVQV(RA-nR)A(PV(Q A rQ)VR)=(PVQVR)A(PVQ
21、V-nR)A(pVQVR)A(p V-QVR)=(PVQVR)A(PVQV-nR)A(pV-.Q V R)(主合取范式)(-P f Q)A(RVp)(PV-QV-iR)A(-pVQ VR)A(-PV-nQVR)A(-ip V Q V -R)A(PV-iQ V -iR)(原公式否定的主合取范式)(r P f Q)A(RVp)(ip A Q A R)V(pA-.Q A iR)V(pAQA-iR)V(pA-nQAR)V(pAQAR)(主析取范式)4、Q-(P V rR)解:Q f(P V F)=-.Q V p v -,R(主合取范式)-1(Q-(P V iR)QVR)A(PVQV-,R)A(P V
22、Q V R)(原公式否定的主合取范式)Q f(pV-iR)(PAQAR)V(pAQA iR)V(pA-Q AR)V(pA-QA-iR)V(-.p A Q A -R)V(P A iQ A R)V(P A iQ A iR)(主析取范式)5、P-*(P人(Q f P)解:P-(P A (Q-P)0-pV(pA(-.Q V p)Q -p vp=T(主合取范式)=(PA-Q)v (-,PAQ)V(PA-iQ)V(P A Q)(主析取范式)6、-(P-*Q)V(RAP)解:(P f Q)V(R 人 P)=-1(rP V Q)V(R 人 P)=(PA-Q)V(RA P)(析取范式)=(PA-iQ A (R
23、V-iR)V(PA(-.Q VQ)AR)=(PA-.Q AR)V(pA iQ A -R)V(p A-Q AR)V(P A Q A R)Q (PA-QAR)V(P AQ AR)V(P A Q A R)(主析取范式)(-(P f Q)V(RAp)(PAQA-nR)V(-,pA Q A R)V(-.p A -nQAR)v(-iP A-iQ A-iR)V (-P A Q A-iR)(原公式否定的主析取范式)-1(P-Q)V(RAp)=(ip V -iQ VR)A(PV-QV-(R)A(pVQV-R)A(PVQVR)A(PV-Q V R)(主合取范式)7、PV(p-Q)解:PV(P-Q)=p V(F V
24、 Q)=(p V-,p)VQ=T(主合取范式)=(PA-Q)V(-.p A Q)V(pA iQ)V(P A Q)(主析取范式)8、(R-Q)人 P解:(Rf Q)/p=(-iRV Q )Ap(RA P)V(Q A P)(析取范式)=(-nRA(QV-Q)AP)V(-.RV R)AQ Ap)(-RAQ Ap)V(-nRA-IQAP)V(-RAQ Ap)V(RAQAP)=(PAQA-R)V(pA-QA-iR)V(P A Q A R)(主析取范式)(RQ)AP)(-PA-nQA-nR)V(-P A Q A _ 1R)V(p A-QAR)V(-,p A Q A R)V(-p A-Q A R)(原公式否
25、定的主析取范式)(R-Q)人 P=(PVQVR)A(pv-1QVR)A(-1PVQ V-.R)A(PV-.Q V -(R)A(PVQV-,R)(主合取范式)9、P fQ解:P f Q=PVQ(主合取范式)=(PA(QV iQ)V(-1PVp)AQ)(-PAQ)V(-ip A -Q)V(-pAQ)V(pAQ)=(P 人 Q)V(PA-iQ)V(p A Q)(主析取范式)10、PV-Q解:P V iQ (主合取范式)=(PA(-1QVQ)V(-)p v p)A r Q)=(PA-Q)V(PAQ)V(-1PA-nQ)V(p A-.Q)=(P AQ)V(pAQ)V(pA r Q)(主析取范式)11、P
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 练习题 参考答案
限制150内