为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

《离散数学》题库大全及答案

2011-08-10 50页 doc 3MB 448阅读

用户头像

is_807823

暂无简介

举报
《离散数学》题库大全及答案《离散数学》试题一 课程内容涉及   1.集合论部分:集合及其运算、二元关系与函数、自然数及自然数集、集合的基数   2.图论部分:图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配集、覆盖集、独立集与匹配、带权图及其应用   3.代数结构部分:代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数   4.组合数学部分:组合存在性定理、基本的计数公式、组合计数方法、组合计数定理   5.数理逻辑部分:命题逻辑、一阶谓词演算、消解原理   离散数学被分成三门课程进行教学,即集合论与图论、代数结构与组合数...
《离散数学》题库大全及答案
《离散数学》试题一 课程内容涉及   1.集合论部分:集合及其运算、二元关系与数、自然数及自然数集、集合的基数   2.图论部分:图的基本概念、欧拉图与哈密顿图、树、图的矩阵示、平面图、图着色、支配集、覆盖集、独立集与匹配、带权图及其应用   3.代数结构部分:代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数   4.组合数学部分:组合存在性定理、基本的计数公式、组合计数方法、组合计数定理   5.数理逻辑部分:命题逻辑、一阶谓词演算、消解原理   离散数学被分成三门课程进行教学,即集合论与图论、代数结构与组合数学、数理逻辑。教学方式以课堂讲授为主, 课后有书面作业、通过学校网络教学平台发布课件并进行师生交流。 编辑本段相关文献   【1】 耿素云,屈婉玲.离散数学(国家十五规划教材).高教出版社,2004。   【2】 袁崇义,屈婉玲,王捍贫,刘田.离散数学及其应用(第4版,译著).机械工业出版社,2002。   【3】 陆钟万.计算机科学中的数理逻辑.科学出版社,2002。   【4】 哈密尔顿,朱水林译.数理逻辑.华东师大出版社,1987。   【5】 耿素云.离散数学习题集--数理逻辑与集合论分册.北大出版社,1993。   【6】 张立昂.离散数学习题集--抽象代数分册.北大出版社,1990。   【7】 耿素云.离散数学习题集--图论分册.北大出版社,1990。   【8】 离散数学习题辅导软件   【9】 命题逻辑教学软件   【10】离散数学教程,耿素云,屈婉玲, 王捍贫,北京大学出版社,2002。   【11】Discrete Mathematics and Its Applications,Sixth Edition,Kenneth H.Rosen   Discrete Mathematics and Its Applications此书的价值已经被全世界几百所大学所证实,作为离散数学领域的经典教材,全世界几乎所有知名的院校都曾经使用本书作为教材.以我个人观点看来,这本书可以称之为离散数学百科.书中不但介绍了离散数学的理论和方法,还有丰富的历史资料和相关学习网站资源.更为令人激动的便是这本书少有的将离散数学理论与应用结合得如此的好.你可以看到离散数学理论在逻辑电路,程序设计,商业和互联网等诸多领域的应用实例.本书的英文版(第六版)当中更增添了相当多的数学和计算机科学家的传记,是计算机科学历史不可多得的参考资料.作为教材这本书配有相当数量的练习.每一章后面还有一组课题,把学生已经学到的计算和离散数学的内容结合在一起进行训练.这本书也是我个人在学习离散数学时读的唯一的英文教材,实为一本值得推荐的好书。 《离散数学》题库答案 一、选择或填空 (数理逻辑部分) 1、下列哪些公式为永真蕴含式?(   ) (1) Q=>Q→P (2) Q=>P→Q (3)P=>P→Q (4) P (P Q)=> P 答:(1),(4) 2、下列公式中哪些是永真式?( ) (1)(┐P Q)→(Q→ R) (2)P→(Q→Q) (3)(P Q)→P (4)P→(P Q) 答:(2),(3),(4) 3、设有下列公式,请问哪几个是永真蕴涵式?( ) (1)P=>P Q (2) P Q=>P (3) P Q=>P Q (4)P (P→Q)=>Q (5) (P→Q)=>P (6) P (P Q)=> P 答:(2),(3),(4),(5),(6) 4、公式x((A(x)B(y,x)) z C(y,z))D(x)中,自由变元是( ),约束变元是( )。 答:x,y, x,z 5、判断下列语句是不是命题。若是,给出命题的真值。( ) (1)​ 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。  (3) 你喜欢唱歌吗? (4) 若7+8>18,则三角形有4条边。  (5) 前进! (6) 给我一杯水吧! 答:(1) 是,T (2) 是,F (3) 不是 (4) 是,T (5) 不是 (6) 不是 6、命题“存在一些人是大学生”的否定是( ),而命题“所有的人都是要死的”的否定是( )。 答:所有人都不是大学生,有些人不会死 7、设P:我生病,Q:我去学校,则下列命题可符号化为( )。 (1) 只有在生病时,我才不去学校 (2) 若我生病,则我不去学校 (3) 当且仅当我生病时,我才不去学校(4) 若我不生病,则我一定去学校 答:(1) (2) (3) (4) 8、设个体域为整数集,则下列公式的意义是( )。 (1) xy(x+y=0) (2) yx(x+y=0) 答:(1)对任一整数x存在整数 y满足x+y=0(2)存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合,确定下列命题的真值: (1) xy (xy=y)  (  )  (2) xy(x+y=y)  (  ) (3) xy(x+y=x)  (  )  (4) xy(y=2x)   (  ) 答:(1) F (2) F (3)F (4)T 10、设谓词P(x):x是奇数,Q(x):x是偶数,谓词公式 x(P(x)Q(x))在哪个个体域中为真?( ) (1) 自然数  (2) 实数   (3) 复数  (4) (1)--(3)均成立 答:(1) 11、命题“2是偶数或-3是负数”的否定是( )。 答:2不是偶数且-3不是负数。 12、永真式的否定是( ) (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 答:(2) 13、公式( P Q) ( P Q)化简为( ),公式 Q (P (P Q))可化简为( )。 答: P ,Q P 14、谓词公式x(P(x) yR(y)) Q(x)中量词x的辖域是( )。 答:P(x) yR(y) 15、令R(x):x是实数,Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为( )。 答: x(R(x) Q(x)) (集合论部分) 16、设A={a,{a}},下列命题错误的是( )。 (1) {a} P(A) (2) {a} P(A) (3) {{a}} P(A) (4) {{a}} P(A) 答:(2) 17、在0( ) 之间写上正确的符号。 (1) = (2)  (3)  (4) 答:(4) 18、若集合S的基数|S|=5,则S的幂集的基数|P(S)|=( )。 答:32 19、设P={x|(x+1) 4且x R},Q={x|5 x +16且x R},则下列命题哪个正确( ) (1) Q P  (2) Q P (3) P Q (4) P=Q 答:(3) 20、下列各集合中,哪几个分别相等( )。 (1) A1={a,b} (2) A2={b,a} (3) A3={a,b,a} (4) A4={a,b,c} (5) A5={x|(x-a)(x-b)(x-c)=0} (6) A6={x|x2-(a+b)x+ab=0} 答:A1=A2=A3=A6, A4=A5 21、若A-B=Ф,则下列哪个结论不可能正确?( ) (1) A=Ф (2) B=Ф (3) A B (4) B A 答:(4) 22、判断下列命题哪个为真?( ) (1) A-B=B-A => A=B (2) 空集是任何集合的真子集 (3) 空集只是非空集合的子集 (4) 若A的一个元素属于B,则A=B 答:(1) 23、判断下列命题哪几个为正确?(   )  (1) {Ф}∈{Ф,{{Ф}}} (2) {Ф} {Ф,{{Ф}}} (3) Ф∈{{Ф}} (4) Ф {Ф} (5) {a,b}∈{a,b,{a},{b}} 答:(2),(4) 24、判断下列命题哪几个正确?(     ) (1) 所有空集都不相等 (2) {Ф} Ф (4) 若A为非空集,则A A成立。 答:(2) 25、设 A∩B=A∩C, ∩B= ∩C,则B( )C。 答:=(等于) 26、判断下列命题哪几个正确?(     ) (1) 若A∪B=A∪C,则B=C (2) {a,b}={b,a} (3) P(A∩B) P(A)∩P(B) (P(S)表示S的幂集) (4) 若A为非空集,则A A∪A成立。 答:(2) 27、A,B,C是三个集合,则下列哪几个推理正确: (1) A B,B C=> A C (2) A B,B C=> A∈B (3) A∈B,B∈C=> A∈C 答:(1) (二元关系部分) 28、设A={1,2,3,4,5,6},B={1,2,3},从A到B的关系R={〈x,y〉|x=y2},求(1)R (2) R-1 。 答:(1)R={<1,1>,<4,2>} (2) R ={<1,1>,<2,4>} 29、举出集合A上的既是等价关系又是偏序关系的一个例子。(    ) 答:A上的恒等关系 30、集合A上的等价关系的三个性质是什么?( ) 答:自反性、对称性和传递性 31、集合A上的偏序关系的三个性质是什么?( ) 答:自反性、反对称性和传递性 32、设S={1,2,3,4},A上的关系R={〈1,2〉,〈2,1〉,〈2,3〉,〈3,4〉} 求(1)R R (2) R-1 。 答:R R ={〈1,1〉,〈1,3〉,〈2,2〉,〈2,4〉} R-1 ={〈2,1〉,〈1,2〉,〈3,2〉,〈4,3〉} 33、设A={1,2,3,4,5,6},R是A上的整除关系,求R= {(     )}。 答:R={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<1,2>,<1,3>,<1,4>, <1,5>,<1,6>,<2,4>,<2,6>,<3,6>} 34、设A={1,2,3,4,5,6},B={1,2,3},从A到B的关系R={〈x,y〉|x=2y},求(1)R (2) R-1 。 答:(1)R={<1,1>,<4,2>,<6,3>} (2) R ={<1,1>,<2,4>,(36>} 35、设A={1,2,3,4,5,6},B={1,2,3},从A到B的关系R={〈x,y〉|x=y2},求R和R-1的关系矩阵。 答:R的关系矩阵= R 的关系矩阵= 36、集合A={1,2,…,10}上的关系R={|x+y=10,x,y A},则R 的性质为( )。 (1) 自反的  (2) 对称的   (3) 传递的,对称的 (4) 传递的 答:(2) (代数结构部分) 37、设A={2,4,6},A上的二元运算*定义为:a*b=max{a,b},则在独异点中,单位元是( ),零元是( )。 答:2,6 38、设A={3,6,9},A上的二元运算*定义为:a*b=min{a,b},则在独异点中,单位元是( ),零元是( ); 答:9,3 (半群与群部分) 39、设〈G,*〉是一个群,则 (1) 若a,b,x∈G,a x=b,则x=( ); (2) 若a,b,x∈G,a x=a b,则x=( )。 答: (1) a b (2) b 40、设a是12阶群的生成元, 则a2是( )阶元素,a3是( )阶元素。 答: 6,4 41、代数系统是一个群,则G的等幂元是(    )。 答:单位元 42、设a是10阶群的生成元, 则a4是( )阶元素,a3是( )阶元素。 答:5,10 43、群的等幂元是(  ),有(   )个。 答:单位元,1 44、素数阶群一定是( )群, 它的生成元是( )。 答:循环群,任一非单位元 45、设〈G,*〉是一个群,a,b,c∈G,则 (1) 若c a=b,则c=( );(2) 若c a=b a,则c=( )。 答:(1) b (2) b 46、的子群的充分必要条件是( )。 答:是群 或 a,b G, a b H,a-1 H 或 a,b G,a b-1 H 47、群<A,*>的等幂元有(   )个,是(   ),零元有(   )个。 答:1,单位元,0 48、在一个群〈G,*〉中,若G中的元素a的阶是k,则a-1的阶是( )。 答:k 49、在自然数集N上,下列哪种运算是可结合的?( ) (1) a*b=a-b  (2) a*b=max{a,b} (3) a*b=a+2b (4) a*b=|a-b| 答:(2) 50、任意一个具有2个或以上元的半群,它( )。 (1) 不可能是群  (2) 不一定是群  (3) 一定是群  (4) 是交换群 答:(1) 51、6阶有限群的任何子群一定不是( )。 (1) 2阶  (2) 3 阶 (3) 4 阶  (4) 6 阶 答:(3) (格与布尔代数部分) 52、下列哪个偏序集构成有界格( ) (1) (N, ) (2) (Z, ) (3) ({2,3,4,6,12},|(整除关系))  (4) (P(A), ) 答:(4) 53、有限布尔代数的元素的个数一定等于( )。 (1) 偶数 (2) 奇数 (3) 4的倍数  (4) 2的正整数次幂 答:(4) (图论部分) 54、设G是一个哈密尔顿图,则G一定是( )。 (1) 欧拉图 (2) 树  (3) 平面图 (4) 连通图 答:(4) 55、下面给出的集合中,哪一个是前缀码?(      ) (1) {0,10,110,101111}   (2) {01,001,000,1} (3) {b,c,aa,ab,aba}    (4) {1,11,101,001,0011} 答:(2) 56、一个图的哈密尔顿路是一条通过图中( )的路。 答:所有结点一次且恰好一次 57、在有向图中,结点v的出度deg+(v)表示( ),入度deg-(v)表示( )。 答:以v为起点的边的条数, 以v为终点的边的条数 58、设G是一棵树,则G 的生成树有( )棵。 (1) 0  (2) 1  (3) 2  (4) 不能确定 答:1 59、n阶无向完全图Kn 的边数是( ),每个结点的度数是( )。 答: , n-1 60、一棵无向树的顶点数n与边数m关系是(    )。 答:m=n-1 61、一个图的欧拉回路是一条通过图中( )的回路。 答:所有边一次且恰好一次 62、有n个结点的树,其结点度数之和是(    )。 答:2n-2 63、下面给出的集合中,哪一个不是前缀码( )。 (1) {a,ab,110,a1b11} (2) {01,001,000,1} (3) {1,2,00,01,0210} (4) {12,11,101,002,0011} 答:(1) 64、n个结点的有向完全图边数是( ),每个结点的度数是( )。 答:n(n-1),2n-2 65、一个无向图有生成树的充分必要条件是( )。 答:它是连通图 66、设G是一棵树,n,m分别表示顶点数和边数,则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。 答:(3) 67、设T=〈V,E〉是一棵树,若|V|>1,则T中至少存在( )片树叶。 答:2 68、任何连通无向图G至少有( )棵生成树,当且仅当G 是( ),G的生成树只有一棵。 答:1,树 69、设G是有n个结点m条边的连通平面图,且有k个面,则k等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。 答:(1) 70、设T是一棵树,则T是一个连通且( )图。 答:无简单回路 71、设无向图G有16条边且每个顶点的度数都是2,则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16 答:(4) 72、设无向图G有18条边且每个顶点的度数都是3,则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 12 答:(4) 73、设图G=,V={a,b,c,d,e},E={,,,,},则G是有向图还是无向图? 答:有向图 74、任一有向图中,度数为奇数的结点有(   )个。 答:偶数 75、具有6 个顶点,12条边的连通简单平面图中,每个面都是由(  )条边围成? (1) 2  (2) 4  (3) 3  (4) 5 答:(3) 76、在有n个顶点的连通图中,其边数( )。 (1) 最多有n-1条  (2) 至少有n-1 条 (3) 最多有n条   (4) 至少有n 条 答:(2) 77、一棵树有2个2度顶点,1 个3度顶点,3个4度顶点,则其1度顶点为( )。 (1) 5  (2) 7 (3) 8  (4) 9 答:(4) 78、若一棵完全二元(叉)树有2n-1个顶点,则它( )片树叶。 (1) n  (2) 2n (3) n-1  (4) 2 答:(1) 79、下列哪一种图不一定是树( )。 (1) 无简单回路的连通图  (2) 有n个顶点n-1条边的连通图 (3) 每对顶点间都有通路的图  (4) 连通但删去一条边便不连通的图 答:(3) 80、连通图G是一棵树当且仅当G中( )。 (1) 有些边是割边  (2) 每条边都是割边 (3) 所有边都不是割边  (4) 图中存在一条欧拉路径 答:(2) (数理逻辑部分) 二、求下列各公式的主析取范式和主合取范式: 1、(P→Q) R  解:(P→Q) R ( P Q ) R ( P R) (Q R) (析取范式) ( P (Q Q) R) (( P P) Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) ( P Q R) ( P Q R) (P Q R)(主析取范式) ((P→Q) R) ( P Q R) ( P Q R) (P Q R) (P Q R) ( P Q R)(原公式否定的主析取范式) (P→Q) R (P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R)(主合取范式) 2、(P R) (Q R) P 解: (P R) (Q R) P(析取范式) (P (Q Q) R) ((P P) Q R) ( P (Q Q) (R R)) (P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) (主析取范式) ((P R) (Q R) P) (P Q R) (P Q R)(原公式否定的主析取范式) (P R) (Q R) P ( P Q R) ( P Q R)(主合取范式) 3、( P→Q) (R P) 解:( P→Q) (R P)  (P Q) (R P)(合取范式) (P Q (R R)) (P (Q Q)) R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R)(主合取范式) (( P→Q) (R P)) (P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R)(原公式否定的主合取范式) ( P→Q) (R P)  ( P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (主析取范式) 4、Q→(P R) 解:Q→(P R) Q P R(主合取范式) (Q→(P R)) ( P Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) (P Q R) (P Q R)(原公式否定的主合取范式) Q→(P R) (P Q R) (P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R)(主析取范式) 5、P→(P (Q→P)) 解:P→(P (Q→P)) P (P ( Q P)) P P T (主合取范式) ( P Q) ( P Q) (P Q) (P Q)(主析取范式) 6、 (P→Q) (R P) 解: (P→Q) (R P) ( P Q) (R P) (P Q) (R P)(析取范式) (P Q (R R)) (P ( Q Q) R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R)(主析取范式) ( (P→Q) (R P)) (P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R)(原公式否定的主析取范式) (P→Q) (R P) ( P Q R) (P Q R) (P Q R) (P Q R) (P Q R)(主合取范式) 7、P (P→Q)      解:P (P→Q) P ( P Q) (P P) Q T(主合取范式) ( P Q) ( P Q) (P Q) (P Q)(主析取范式) 8、(R→Q) P 解:(R→Q) P ( R Q ) P ( R P) (Q P) (析取范式) ( R (Q Q) P) (( R R) Q P) ( R Q P) ( R Q P) ( R Q P) (R Q P) (P Q R) (P Q R) (P Q R)(主析取范式) ((R→Q) P) ( P Q R) ( P Q R) (P Q R) ( P Q R) ( P Q R)(原公式否定的主析取范式) (R→Q) P (P Q R) (P Q R) ( P Q R) (P Q R) (P Q R)(主合取范式) 9、P→Q 解:P→Q P Q(主合取范式) ( P (Q Q)) (( P P) Q) ( P Q) ( P Q) ( P Q) (P Q) ( P Q) ( P Q) (P Q)(主析取范式) 10、 P Q  解: P Q (主合取范式) (P ( Q Q)) (( P P) Q) (P Q) (P Q) ( P Q) (P Q) (P Q) (P Q) ( P Q)(主析取范式) 11、P Q 解:P Q(主析取范式) (P (Q Q)) ((P P) Q) (P Q) (P Q) (P Q) ( P Q) (P Q) (P Q) ( P Q)(主合取范式) 12、(P R) Q 解:(P R) Q (P R) Q ( P R) Q ( P Q) ( R Q)(合取范式) ( P Q (R R)) (( P P) Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) ( P Q R) ( P Q R) (P Q R)(主合取范式) (P R) Q ( P Q R) ( P Q R) (P Q R) (P Q R) (P Q R) (原公式否定的主析取范式) (P R) Q (P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R)(主析取范式) 13、(P Q) R 解:(P Q) R ( P Q) R (P Q) R(析取范式) (P Q (R R)) ((P P) (Q Q) R) (P Q R) (P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R) (P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R)(主析取范式) (P Q) R ( P Q) R (P Q) R(析取范式) (P R) ( Q R)(合取范式) (P (Q Q) R) ((P P) Q R) (P Q R) (P Q R) (P Q R) ( P Q R) (P Q R) (P Q R) ( P Q R)(主合取范式) 14、(P (Q R)) ( P ( Q R)) 解:(P (Q R)) ( P ( Q R)) ( P (Q R)) (P ( Q R)) ( P Q) ( P R) (P Q) (P R)(合取范式) ( P Q (R R)) ( P (Q Q) R) (P Q (R R)) (P (Q Q) R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) (P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) (P Q R) (P Q R)(主合取范式) (P (Q R)) ( P ( Q R)) ( P Q R) (P Q R)(原公式否定的主合取范式) (P (Q R)) ( P ( Q R)) (P Q R) ( P Q R)(主析取范式) 15、P ( P (Q ( Q R))) 解:P ( P (Q ( Q R))) P (P (Q (Q R))) P Q R(主合取范式) (P Q R) (P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) (原公式否定的主合取范式) (P Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) (P Q R) (P Q R) (P Q R)(主析取范式) 16、(P Q) (P R) 解、(P Q) (P R) ( P Q) ( P R) (合取范式) ( P Q (R R) ( P ( Q Q) R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R)(主合取范式) (P Q) (P R) ( P Q) ( P R) P (Q R)(合取范式) ( P (Q Q) (R R)) (( P P) Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) (主析取范式) 三、证明: 1、P→Q, Q R, R, S P=> S 证明: (1) R 前提 (2) Q R 前提 (3)​  Q (1),(2) (4)​  P→Q 前提 (5)​  P (3),(4) (6)​  S P 前提 (7) S (5),(6) 2、A→(B→C),C→( D E), F→(D E),A=>B→F 证明: (1) A 前提 (2) A→(B→C) 前提 (3) B→C (1),(2) (4) B 附加前提 (5)​  C (3),(4) (6)​  C→( D E) 前提 (7)​  D E (5),(6) (8)​  F→(D E) 前提 (9)​  F (7),(8) (10)​  B→F CP 3、P Q, P→R, Q→S => R S 证明: (1) R 附加前提 (2) P→R 前提 (3) P (1),(2) (4) P Q 前提 (5) Q (3),(4) (6) Q→S 前提 (7) S (5),(6) (8) R S CP,(1),(8) 4、(P→Q) (R→S),(Q→W) (S→X), (W X),P→R => P 证明: (1) P 假设前提 (2) P→R 前提 (3) R (1),(2) (4) (P→Q) (R→S) 前提 (5) P→Q (4) (6) R→S (5) (7) Q (1),(5) (8) S (3),(6) (9) (Q→W) (S→X) 前提 (10) Q→W (9) (11) S→X (10) (12) W (7),(10) (13) X (8),(11) (14) W X (12),(13) (15) (W X) 前提 (16) (W X) (W X) (14),(15) 5、(U V)→(M N), U P, P→(Q S), Q S =>M 证明: (1) Q S 附加前提 (2)​ P→(Q S) 前提 (3)​  P (1),(2) (4)​  U P 前提 (5)​  U (3),(4) (6)​  U V (5) (7)​ (U V)→(M N) 前提 (8)​  M N (6),(7) (9)​  M (8) 6、 B D,(E→ F)→ D, E=> B 证明: (1) B 附加前提 (2) B D 前提 (3) D (1),(2) (4) (E→ F)→ D 前提 (5) (E→ F) (3),(4) (6) E F (5) (7) E (6) (8) E 前提 (9) E E (7),(8) 7、P→(Q→R),R→(Q→S) => P→(Q→S) 证明: (1) P 附加前提 (2) Q 附加前提 (3) P→(Q→R) 前提 (4) Q→R (1),(3) (5) R (2),(4) (6) R→(Q→S) 前提 (7) Q→S (5),(6) (8) S (2),(7) (9) Q→S CP,(2),(8) (10) P→(Q→S) CP,(1),(9) 8、P→ Q, P→R,R→ S =>S→ Q 证明: (1) S 附加前提 (2) R→ S 前提 (3) R (1),(2) (4) P→R 前提 (5) P (3),(4) (6) P→ Q 前提 (7) Q (5),(6) (8) S→ Q CP,(1),(7) 9、P→(Q→R) => (P→Q)→(P→R) 证明: (1) P→Q 附加前提 (2) P 附加前提 (3) Q (1),(2) (4) P→(Q→R) 前提 (5) Q→R (2),(4) (6) R (3),(5) (7) P→R CP,(2),(6) (8) (P→Q) →(P→R) CP,(1),(7) 10、P→( Q→ R),Q→ P,S→R,P => S 证明: (1) P 前提 (2) P→( Q→ R) 前提 (3) Q→ R (1),(2) (4) Q→ P 前提 (5) Q (1),(4) (6) R (3),(5) (7) S→R 前提 (8) S (6),(7) 11、A,A→B, A→C, B→(D→ C) => D 证明: (1) A 前提 (2) A→B 前提 (3) B (1),(2) (4) A→C 前提 (5) C (1),(4) (6) B→(D→ C) 前提 (7) D→ C (3),(6) (8) D (5),(7) 12、A→(C B),B→ A,D→ C => A→ D 证明: (1) A 附加前提 (2) A→(C B) 前提 (3) C B (1),(2) (4)​  B→ A 前提 (5)​  B (1),(4) (6)​  C (3),(5) (7)​  D→ C 前提 (8)​  D (6),(7) (9)​  A→ D CP,(1),(8) 13、(P Q) (R Q) (P R) Q 证明、 (P Q) (R Q) ( P Q) ( R Q) ( P R) Q (P R) Q (P R) Q 14、P (Q P) P (P Q) 证明、 P (Q P) P ( Q P) ( P) ( P Q) P (P Q) 15、(P Q) (P R), (Q R),S P S 证明、 (1) (P Q) (P R) 前提 (2) P (Q R) (1) (3) (Q R) 前提 (4) P (2),(3) (5) S P 前提 (6) S (4),(5) 16、P Q,Q R,R S P 证明、 (1) P 附加前提 (2) P Q 前提 (3) Q (1),(2) (4) Q R 前提 (5) R (3),(4) (6 ) R S 前提 (7) R (6) (8) R R (5),(7) 17、用真值表法证明P Q (P Q) (Q P) 证明、 列出两个公式的真值表: P Q P Q (P Q) (Q P) F F F T T F T T T T F F F F T T 由定义可知,这两个公式是等价的。 18、P→Q P→(P Q) 证明、 设P→(P Q)为F,则P为T,P Q为F。所以P为T,Q为F ,从而P→Q也为F。所以P→Q P→(P Q)。 19、用先求主范式的方法证明(P→Q) (P→R) (P→(Q R) 证明、 先求出左右两个公式 的主合取范式 (P→Q) (P→R) ( P Q) ( P R) ( P Q (R R))) ( P (Q Q) R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) (P→(Q R)) ( P (Q R)) ( P Q) ( P R) ( P Q (R R)) ( P (Q Q) R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) 它们有一样的主合取范式,所以它们等价。 20、(P→Q) (Q R) P 证明、 设(P→Q) (Q R)为T,则P→Q和 (Q R)都为T。即P→Q和 Q R都为T。故P→Q, Q和 R)都为T,即P→Q为T,Q和R都为F。从而P也为F,即 P为T。从而(P→Q) (Q R) P 21、为庆祝九七香港回归祖国,四支足球队进行比赛,已知情况如下,问结论是否有效? 前提: (1) 若A队得第一,则B队或C队获亚军; (2)​ 若C队获亚军,则A队不能获冠军; (3)​ 若D队获亚军,则B队不能获亚军; (4)​ A 队获第一; 结论: (5) D队不是亚军。 证明、 设A:A队得第一;B: B队获亚军;C: C队获亚军;D: D队获亚军;则前提符号化为A (B C),C A,D B,A;结论符号化为 D。 本题即证明 A (B C),C A,D B,A D。 (1) A 前提 (2) A (B C)前提 (3) B C (1),(2) (4) C A 前提 (5) C (1),(4) (6) B (3),(5) (7) D B 前提 (8) D (6),(7) 22、用推理规则证明P Q, (Q R),P R不能同时为真。 证明、 (1) P R 前提 (2) P (1) (3) P Q 前提 (4) Q (2),(3) (5) (Q R) 前提 (6) Q R (5) (7) Q (6) (8) Q Q (4),(7) (集合论部分) 四、设A,B,C是三个集合,证明: 1、A (B-C)=(A B)-(A C) 证明: (A B)-(A C)= (A B) =(A B) ( ) =(A B ) (A B )= A B =A (B ) =A (B-C) 2、(A-B) (A-C)=A-(B C) 证明: (A-B) (A-C)=(A ) (A ) =A ( ) =A = A-(B C) 3、A B=A C, B= C,则C=B   证明: B=B ( A)=(B ) (B A) =(C ) (C A)=C ( A)=C 4、A B=A (B-A) 证明: A (B-A)=A (B )=(A B) (A ) =(A B) U= A B 5、A=B A B=    证明: 设A=B,则A B=(A-B) (B-A)= = 。 设A B= ,则A B=(A-B) (B-A)= 。故A-B= ,B-A= ,从而A B,B A,故A=B。 6、A B = A C,A B=A C,则C=B 证明: B=B (A B)= B (A C)= (B A) (B C) = (A C) (B∩C)= C (A B) = C (A C) =C 7、A B=A C, B= C,则C=B 证明: B=B (A )=(B A) (B ) =(C A) (C )=C (A ) =C 8、A-(B C)=(A-B)-C   证明: A-(B C)= A =A ( )=(A ) =(A-B) =(A-B)-C 9、(A-B) (A-C)=A-(B C)  证明: (A-B) (A-C) =(A ) (A ) =(A A) ( ) =A =A-(B C) 10、A-B=B,则A=B= 证明: 因为B=A-B,所以B=B B=(A-B) B= 。从而A=A-B=B= 。 11、A=(A-B) (A-C) A B C= 证明: 因为(A-B) (A-C) =(A ) (A ) =A ( ) =A = A-(B C),且A=(A-B) (A-C), 所以A= A-(B C),故A B C= 。 因为A B C= ,所以A-(B C)=A。而A-(B C)= (A-B) (A-C), 所以A=(A-B) (A-C)。 12、(A-B) (A-C)= A B C 证明: 因为(A-B) (A-C) =(A ) (A ) =A ( ) =A = A-(B C),且(A-B) (A-C)= , 所以 = A-(B C),故A B C。 因为A B C,所以A-(B C)=A。而A-(B C)= (A-B) (A-C), 所以A=(A-B) (A-C)。 13、(A-B) (B-A)=A B= 证明: 因为(A-B) (B-A)=A,所以B-A A。但(B-A) A= ,故B-A= 。 即B A,从而B= (否则A-B A,从而与(A-B) (B-A)=A矛盾)。 因为B= ,所以A-B=A且B-A= 。从而(A-B) (B-A)=A。 14、(A-B)-C A-(B-C) 证明: x (A-B)-C,有 A-B且x C,即 A,x B且x C。 从而 A,x B-C,故x A-(B-C)。从而(A-B)-C A-(B-C) 15、P(A) P(B) P(A B) (P(S)表示S的幂集) 证明: S P(A) P(B),有S P(A)或S P(B),所以S A或S B。 从而S A B,故S P(A B)。即P(A) P(B) P(A B) 16、P(A) P(B)=P(A B) (P(S)表示S的幂集) 证明: S P(A) P(B),有S P(A)且S P(B),所以S A且S B。 从而S A B,故S P(A B)。即P(A) P(B) P(A B)。 S P(A B),有S A B,所以S A且S B。 从而S P(A)且S P(B),故S P(A) P(B)。即P(A B) P(A) P(B)。 故P(A B)=P(A) P(B) 17、(A-B) B=(A B)-B当且仅当B= 。 证明: 当B= 时,因为(A-B) B=(A- ) =A,(A B)-B=(A )- =A,所以(A-B) B=(A B)-B。 用反证法证明。假设B ,则存在b B。因为b B且b A B,所以b (A B)-B。而显然b (A-B) B。故这与已知(A-B) B=(A B)-B矛盾。 五、证明或解答: (数理逻辑、集合论与二元关系部分) 1、设个体域是自然数,将下列各式翻译成自然语言: (1) x y(xy=1); (2) x y(xy=1); (3) x y (xy=0); (4) x y(xy=0); (5) x y (xy=x); (6) x y(xy=x); (7) x y z (x-y=z) 答: (1)存在自然数x,对任意自然数y满足xy=1; (2)对每个自然数x,存在自然数y满足xy=1; (3)对每个自然数x,存在自然数y满足xy=0; (4)存在自然数x,对任意自然数y满足xy=1; (5)对每个自然数x,存在自然数y满足xy=x; (6)存在自然数x,对任意自然数y满足xy=x; (7)对任意自然数x,y,存在自然数z满足x-y=z。 2、设A(x,y,z): x+y=z, M(x,y,z): xy=z, L(x,y): xy, 个体域为自然数。将下列命题符号化: (1)没有小于0的自然数; (2)xyz; (4)存在x,对任意y 使得xy=y; (5)对任意x,存在y使x+y=x。 答: (1) x(G(x,0) M(0,0,x)) 或 x L(x,0) (2) x y z ((L(x,y) L(y,z)) L(x,z)) (3) x y ((L(x,y) z(L(z,0) G(xz,yz))) (4) x yM(x,y,y) (5) x yA(x,y,x) 3、列出下列二元关系的所有元素: (1)A={0,1,2},B={0,2,4},R={|x,y }; (2)A={1,2,3,4,5},B={1,2},R={|2 x+y 4且x 且y B}; (3)A={1,2,3},B={-3,-2,-1,0,1},R={||x|=|y|且x 且y B}; 解: (1) R={<0,0>,<0,2>,<2,0>,<2,2>} (2) R={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>}; (3) R={<1,1>,<1,-1>,<2,-2>,<3,-3>}。 4、对任意集合A,B,证明:若A A=B B,则B=B。 证明: 若B= ,则B B= 。从而A A = 。故A= 。从而B=A。 若B ,则B B 。从而A A 。 对 , B B。因为A A=B B,则 A。从而x A。故B A。 同理可证,A B。 故B=A。 5、对任意集合A,B,证明:若A ,A B=A C,则B=C。 证明: 若B= ,则A B= 。从而A C = 。因为A ,所以C= 。即B=C。 若B ,则A B 。从而A C 。 对 ,因为A ,所以存在y A, 使 B。因为A B=A C,则 C。从而x C。故B C。 同理可证,C B。 故B=C。 6、设A={a,b}, B={c}。求下列集合: (1) A {0,1} B; (2) B2 A; (3) (A B)2; (4) P(A) A。 解: (1) A {0,1} B={,,,}; (2) B2 A={,}; (3) (A B)2={,,,}; (4) P(A) A={< ,a>,< ,b>,<{a},a>,<{a},b>,<{b},a>,<{b},b> ,,}。 7、设全集U={a,b,c,d,e}, A={a,d}, B={a,b,c}, C={b,d}。求下列各集合: (1)A B ; (2) ;(3)(A ) C; (4)P(A)-P(B); (5)(A-B) (B-C); (6)(A B) C; 解 : (1) A B ={a}; (2) ={a,b,c,d,e}; (3) (A ) C={b,d}; (4) P(A)-P(B)={{d},{a,d}}; (5) (A-B) (B-C)={d,c,a}; (6) (A B) C={b,d}。 8、设A,B,C是任意集合,证明或否定下列断言: (1)若A B,且B C,则A C; (2)若A B,且B C,则A C; (3)若A B,且B C,则A C; (4)若A B,且B C,则A C; 证明: (1) 成立。 对 x A, 因为A B,所以x B。又因为B C,所以x C。即A C。 (2) 不成立。反例如下:A={a}, B={a,b},C={a,b,c}。虽然A B,且B C,但A C。 (3) 不成立。反例如下:A={a}, B={{a},b},C={{{a},b},c}。虽然A B,且B C,但A C。 (4) 成立。因为A B, 且B C,所以A C。 9、A上的任一良序关系一定是A上的全序关系。 证明: a,b∈A,则{a,b}是A的一个非空子集。 ≤是A上的良序关系, {a,b}有最小元。若最小元为a,则a≤b;否则b≤a。从而≤为A上的的全序关系。 10、若R和S都是非空集A上的等价关系,则R S是A上的等价关系。  证明: a∈A,因为R和S都是A上的等价关系,所以xRx且xSx。故xR Sx。从而R S是自反的。 a,b∈A,aR Sb,即aRb且aSb。因为R和S都是A上的等价关系,所以bRa且bSa。故bR Sa。从而R S是对称的。 a,b,c∈A,aR Sb且bR Sc,即aRb,aSb,bRc且bSc。因为R和S都是A上的等价关系,所以aRc且aSc。故aR Sc。从而R S是传递的。 故R S是A上的等价关系。 11、设R A×A,则R自反 IA R。 证明: x A, R是自反的, xRx。即 R,故IA R。 x A, IA R, R。即xRx,故R是自反的。 12、设A是集合,R A×A,则R是对称的 R=R-1。 证明: R , R是对称的, yRx。即 R,故 R_1 。从而R R-1。 反之 R-1,即 R 。 R是对称的, yRx。即 R, R_1 R。 故R=R-1。 x,y A,若 R ,即 R-1。 R=R-1, R。即yRx,故R是对称的。 13、设A,B,C和D均是集合,R A×B,S B×C,T C×D,则 (1)  R (S T)=(R S) (R T); (2)  R (S T) (R S) (R T); 证明: (1) R (S T),则由合成关系的定义知 y B,使得 R且 S T。从而 R且 S或 R且 T,即 R S或 R T。故 (R S) (R T) 。从而R (S T) (R S) (R T)。 同理可证(R S) (R T) R (S T)。 故R (S T)=(R S) (R T)。 (2) R (S T),则由合成关系的定义知 y B,使得 R且 S T。从而 R且 S且 T,即 R S且 R T。故 (R S) (R T) 。从而R (S T) (R S) (R T)。 14、设〈A,≤〉为偏序集, B A,若B有最大(小)元、上(下)确界,则它们是惟一的。 证明: 设a,b都是B的最大元,则由最大元的定义a b,b a。 是A上的偏序关系, a=b。即B如果有最大元则它是惟一的。 15、设A={1,2,3},写出下列图示关系的关系矩阵,并讨论它们的性质: 1 1 1 2 3 2 3 2 3 解: (1)R={<2,1>,<3,1>,<2,3>};MR= ;它是反自反的、反对称的、传递的; (2)R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>};MR= ;它是反自反的、对称的; (3)R={<1,2>,<2,1>,<1,3>,<3,3>};MR= ;它既不是自反的、反自反的、也不是对称的、反对称的、传递的。 16、设A={1,2,…,10}。下列哪个是A的划分?若是划分,则它们诱导的等价关系是什么? (1)B={{1,3,6},{2,8,10},{4,5,7}}; (2)C={{1,5,7},{2,4,8,9},{3,5,6,10}}; (3)D={{1,2,7},{3,5,10},{4,6,8},{9}} 解: (1)和(2)都不是A的划分。 (3)是A的划分。其诱导的等价关系是 I {<1,2>,<2,1>,<1,7>,<7,1>,<2,7>,<7,2>,<3,5>,<5,3>,<3,10>, <10,3>,<10,5>,<5,10>,<4,6>,<6,4>,<4,8>,<8,4>,<6,8>,<8,6>}。 17、R是A={1,2,3,4,5,6}上的等价关系, R=I {<1,5>,<5,1>,<2,4>,<4,2>,<3,6>,<6,3>} 求R诱导的划分。 解: R诱导的划分为{{1,5},{2,4},{3,6}}。 18、A上的偏序关系 的Hasse图如下。 (1)​ 下列哪些关系式成立:a b,b a,c e,e f,d f,c f; (2)​ 分别求出下列
/
本文档为【《离散数学》题库大全及答案】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索