2_计算机学院_离散数学期末考试_2011年春季_试卷B1

计算机科学与技术专业级第二学期离散数学试题一、单项选择题（每小题3分，本题共15分）1．C 2．C 3．B 4．A 5．D1．若集合A的元素个数为10，则其幂集的元素个数为（）．A．10 B．100 C．1024 D．12．设A={a, b}，B={1, 2}，R1，R2，R3是A到B的二元关系，且R1={<a，2>, <a，1>}，R2={<a，1>, <a，2>, <b，1>}，R3={<a，1>, <b，2>}，则（）是从A到B的函数．A．R1和R2B．R2C．R3D．R1和R33．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为( )．A．8、2、8、2 B．无、2、无、2C．6、2、6、2 D．8、1、6、14．若完全图G中有n个结点(n≥2)，m条边，则当（）时，图G中存在欧拉回路．A．n为奇数B．n为偶数C．m为奇数D．m为偶数5．已知图G的邻接矩阵为则G有（）．A．6点，8边B．6点，6边C．5点，8边D．5点，6边二、填空题（每小题3分，本题共15分）6．设集合A＝{a}，那么集合A的幂集是{,{a}} ．7．若R1和R2是A上的对称关系，则R1∪R2，R1∩R2，R1-R2，R2-R1中对称关系有 4 个．8．设图G是有5个结点的连通图，结点度数总和为10，则可从G中删去 1 条边后使之变成树．9．设连通平面图G的结点数为5，边数为6，则面数为 3 ．10．设个体域D＝{a, b}，则谓词公式( x)(A(x)∧B（x））消去量词后的等值式为(A (a)∧B (b))∧(A（a）∧B（b））．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“今天有联欢活动，明天有文艺晚会．”翻译成命题公式．设P：今天有联欢活动，Q：明天有文艺晚会，（2分）P∧Q．（6分）12．将语句“如果小王来，则小李去．”翻译成命题公式．设P：小王来，Q：小李去（2分）P → Q ． （6分）四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．若偏序集<A ，R >的哈斯图如图一所示，则集合A 的最大元为a ，极小元不存在． 错误． （3分）对于集合A 的任意元素x ，均有<x , a >R （或xRa ），所以a 是集合A 中的最大元．（5分）但按照极小元的定义，在集合A 中b ,c ,d 均是极小元． （7分）14．┐P ∧（P →┐Q ）∨P 为永假式．错误． （3分）┐P ∧（P →┐Q ）∨P 是由┐P ∧（P →┐Q ）与P 组成的析取式，如果P 的值为真，则┐P ∧（P →┐Q ）∨P 为真， （5分）如果P 的值为假，则┐P 与P →┐Q 为真，即┐P ∧（P →┐Q ）为真，也即┐P ∧（P →┐Q ）∨P 为真，所以┐P ∧（P →┐Q ）∨P 是永真式． （7分）另种说明：┐P ∧（P →┐Q ）∨P 是由┐P ∧（P →┐Q ）与P 组成的析取式，只要其中一项为真，则整个公式为真． （5分）可以看到，不论P 的值为真或为假，┐P ∧（P →┐Q ）与P 总有一个为真，所以┐P ∧（P →┐Q ）∨P 是永真式． （7分）或用等价演算┐P ∧（P →┐Q ）∨P ⇔T 五．计算题（每小题12分，本题共36分）15．设集合A ={1，2，3，4}，R ={<x , y >|x , y ∈A ；|x y |=1或x y =0}，试（1）写出R 的有序对表示；（2）画出R 的关系图；（3）说明R 满足自反性，不满足传递性．15．（1）R ={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>} （3分）（2）关系图如图二：图二 （6分）（3）因为<1,1>,<2,2>,<3,3>,<4,4>均属于R ，即A 的每个元素构成的有序对均在R 中，故R 在A 上是自反的． （9分）因有<2,3>与<3,4>属于R ，但<2,4>不属于R ，所以R 在A 上不是传递的．（12分） abcd 图一16．设图G =<V ，E >，V ={ v 1，v 2，v 3，v 4，v 5}，E ={ (v 1, v 2)，(v 1, v 3)，(v 2, v 4)，(v 3, v 5)，(v 4, v 5) }，试(1) 画出G 的图形表示；(2) 写出其邻接矩阵；(3) 求出每个结点的度数；(4) 画出图G 的补图的图形． 16．（1）关系图如图三：（3分）（2）邻接矩阵⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0110010010100010100100110 （6分） （3）deg(v 1)=2deg(v 2)=2deg(v 3)=2deg(v 4)=2deg(v 5)=2 （9分）（4）补图如图四（12分）17．求P →Q ∧R 的合取范式与主析取范式．P →（R ∧Q ）⇔┐P ∨(R ∧Q ) （4分）⇔ （┐P ∨Q ）∧（┐P ∨R ） （合取范式） （6分）P →（R ∧Q ）⇔┐P ∨(R ∧Q )⇔(┐P ∧(┐Q ∨Q) )∨(R ∧Q ) （7分）⇔(┐P ∧┐Q )∨(┐P ∧Q)∨(R ∧Q ) （8分）⇔((┐P ∧┐Q )∧ (┐R ∨R ))∨(┐P ∧Q )∨(R ∧Q ) （9分）⇔(┐P ∧┐Q ∧┐R )∨(┐P ∧┐Q ∧R )∨(┐P ∧Q )∨(R ∧Q ) （10分）⇔(┐P ∧┐Q ∧┐R )∨(┐P ∧┐Q ∧R )∨((┐P ∧Q )∧(┐R ∨R ))∨(R ∧Q )⇔(┐P ∧┐Q ∧┐R )∨(┐P ∧┐Q ∧R )∨(┐P ∧Q ∧┐R )∨(┐P ∧Q ∧R )∨(R ∧Q )⇔(┐P ∧┐Q ∧┐R )∨(┐P ∧┐Q ∧R )∨(┐P ∧Q ∧┐R )∨(┐P ∧Q ∧R )∨((┐P ∨P )∧(R ∧Q ))⇔(┐P ∧┐Q ∧┐R )∨(┐P ∧┐Q ∧R )∨(┐P ∧Q ∧┐R )∨ v 1 v 2 v 3 v 4 图三 v 5 v 1 v 2 v 3 v 4 图四 v 5(┐P ∧Q ∧R )∨ (P ∧R ∧Q ) （主析取范式） （12分）说明：此题解法步骤多样，若能按正确步骤求得结果，均可给分．六、证明题（本题共8分）18．设连通无向图G 有14条边，3个4度顶点，4个3度顶点，其它顶点的度数均小于3，试说明G 中可能有的顶点数．证明： 可利用数列可图化及握手定理解答顶点度数和为214=28， （2分）28-（34+43）=4，则知其他顶点度数和为4， （4分）对于有限图，若无零度顶点，则除4度及3度顶点外，可能的顶点情况有：2个2度点；1个2度点和2个1度点；4个1度点， （6分）即对应图的顶点数分别至少为9、10、11． （8分）2011年 7月一、单项选择题（每小题3分，本题共15分）1．A 2．C 3．C 4．D 5．B1．若集合A ={1，{1}，{2}，{1，2}}，则下列表述正确的是( )．A ．{2}AB ．{1，2}AC ．1AD ． 2 A2．设G 为无向图，则下列结论成立的是 ( ) ．A ．无向图G 的结点的度数等于边数的两倍．B ．无向图G 的结点的度数等于边数．C ．无向图G 的结点的度数之和等于边数的两倍．D ．无向图G 的结点的度数之和等于边数．3．图G 如图一所示，以下说法正确的是( ) ． A ．{(a ，b )}是边割集B ．{ a ，c }是点割集C ．{d }是点割集D ．{ (c ，d )}是边割集 图一4．设集合A ={1}，则A 的幂集为( )．A ．{{1}}B ．{1，{1}}C ．{，1}D ．{，{1}}5．设A (x )：x 是人，B (x )：x 犯错误，则命题“没有不犯错误的人”可符号化为（ ）．A ．┐(∃x )( A (x ) → ┐B(x))B ．┐(∃x )( A (x )∧┐B (x ))C ．┐(∃x )( A (x )∧B (x ))D ．(∀x )( A (x )∧B (x ))二、填空题（每小题3分，本题共15分）6．命题公式P P ⌝∨的真值是 真（或T ，或1） ．7．若无向图T 是连通的，则T 的结点数v 与边数e 满足关系v= e +1 时，T 是树．8．无向图G 是欧拉图的充分必要条件是 G 是连通的且结点度数都是偶数 ．9．设集合A ={1，2}上的关系R ＝{<2,2>,<1,2>}，则在R 中仅需加入一个元素 <1, 1> ， a b c de f就可使新得到的关系为自反的．10．( x )(P (x )→R (y )∨S (z )) 中的约束变元有 x ．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“雪是黑色的．”翻译成命题公式．设P ：雪是黑色的， （2分）则命题公式为：P ． （6分）12．将语句“如果明天下雨，则我们就在室内上体育课．”翻译成命题公式．设 P ：如果明天下雨， Q ：我们在室内上体育课， （2分）则命题公式为：P Q ． （6分）四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．设集合A ={1，2}，B ={3，4}，从A 到B 的关系为f ={<1, 3>，<1, 4>}，则f 是A 到B 的函数． 错误． （3分）因为A 中元素1有B 中两个不同的元素与之对应，故f 不是A 到B 的函数． （7分）14．设G 是一个连通平面图，有5个结点9条边，则G 有6个面．正确． （3分）因G 是一个连通平面图，满足欧拉定理，有v -e +r =2，所以r =2-（v -e ）=2-（5-9）=6 （7分）五．计算题（每小题12分，本题共36分）15．试求出P →（R ∧Q ）的合取范式．P →（R ∧Q ）┐P ∨（R ∧Q ） （6分）(┐P ∨R ) ∧（┐P ∨Q ）（合取范式） （12分）16．设A ={{1}, {1, 2}，1}，B ={ 1, 2, {2}}，试计算（1）（A ∩B ） （2）（A ∪B ） （3）（A ∩B ）A ．（1）（A ∩B ）={1} （4分）（2）（A ∪B ）={1, 2, {1}, {2}, {1, 2}} （8分）（3）（A ∩B ）A = （12分）17．试画一棵带权为2, 3, 3, 4, 5,的最优二叉树,并计算该最优二叉树的权．最优二叉树如图二所示．（10分） 图二权为23+33+32+42+52=39 （12分）六、证明题（本题共8分）18．试证明：若R 与S 是集合A 上的对称关系，则R ∩S 也是集合A 上的对称关系．证明：设x ，y A ，因为R 对称，所以若<x , y >R ，则<y , x >R ． （2分）因为S 对称，所以若<x , y >S ，则<y , x >S ． （4分）于是若<x , y >R ∩S 则<x , y >R 且<x , y >S2 3 3 4 5 5 10 7 17即 <y , x >R 且<y , x >S （6分）也即<y , x > R ∩S ，故R ∩S 是对称的． （8分）中央广播电视大学2010—2011学年度第一学期“开放本科”期末考试离散数学（本）试题2011年1月一、单项选择题（每小题3分，本题共15分）1．A 2．D 3．B 4．D 5．C1．若集合A ＝{ a ，{1}}，则下列表述正确的是( )．A ．{1}∈AB ．{1}⊆AC ．{a }∈AD ．∅∈A2．设图G ＝<V , E >，v ∈V ，则下列结论成立的是 ( )．A ．deg(v )=2EB ．deg(v )=EC ．E v V v =∑∈)deg( D ．E v Vv 2)deg(=∑∈ 3．如图一所示，以下说法正确的是 ( )． A ．(e , c )是割边 B ．(d, e )是割边 C ．(b , a )是割边 D ．(b, c )是割边4．命题公式（P ∨Q ）的合取范式是 ( ) ．A ．PB ．（P ∧Q ）C ．（P ∨P ）D ．（P ∨Q ）5．下列等价公式成立的为( )．A ．P ∧Q P ∨QB ．Q →P P →QC ．⌝P ∧P ⌝Q ∧QD ．⌝P ∨P Q二、填空题（每小题3分，本题共15分）6．设集合A ={0, 1, 2}，B ={1,2, 3, 4,}，R 是A 到B 的二元关系，},,{B A y x B y A x y x R ⋂∈∈∈><=且且则R 的有序对集合为 {<1, 1>，<1, 2>，<2, 1>，<2, 2>} ．7．设G 是连通平面图，v , e , r 分别表示G 的结点数，边数和面数，则v ，e 和r 满足的关系式 v -e +r =2 ．8．设G ＝<V , E >是有20个结点，25条边的连通图，则从G 中删去 6 条边，可以确定图G 的一棵生成树．9．无向图G 存在欧拉回路，当且仅当G 所有结点的度数全为偶数且 连通 ．10．设个体域D ＝{1,2}，则谓词公式)(x xA ∀消去量词后的等值式为 A (1) ∧A (2) ．a b c d 图一 e三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“如果小李学习努力，那么他就会取得好成绩．”翻译成命题公式．12．将语句“小张学习努力，小王取得好成绩．”翻译成命题公式．11．设P ：小李学习努力，Q ：小李会取得好成绩， （2分） P Q ． （6分）12．设P ：小张学习努力，Q ：小王取得好成绩， （2分） P Q ． （6分）四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．如果R 1和R 2是A 上的自反关系，则R 1R 2是自反的． 14．如图二所示的图中存在一条欧拉回路．13．正确． （3分）R 1和R 2是自反的，x ∈A ，<x , x > ∈ R 1，<x , x > ∈R 2，则<x , x > ∈ R 1R 2，所以R 1R 2是自反的． （7分）14．正确． （3分）因为图G 为连通的，且其中每个顶点的度数为偶数． （7分） 五．计算题（每小题12分，本题共36分）15．设A ={{2},1,2}，B ={1,{1,2}}，试计算（1）（A B ）； （2）（A ∩B ）； （3）A ×B ．16．设G =<V ，E >，V ={ v 1，v 2，v 3，v 4，v 5}，E ={ (v 1,v 3)，(v 2,v 3)，(v 2,v 4)，(v 3,v 4)，(v 3,v 5)}，试（1）给出G 的图形表示； （2）写出其邻接矩阵；（3）求出每个结点的度数； （4）画出其补图的图形．17．设谓词公式),()),,(),((z y yC z y x zB y x A x ∀∧∀∧∃，试（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元．15．（1）A B ={2,{2}} （4分）（2）A ∩B ={1} （8分）（3）A ×B={<{2},1>，<{2},{1,2}>，<1,1>，<1, {1,2}>，<2,1>，<2, {1,2}>} （12分）16．（1）G 的图形表示如图三：图二v 1 v 2 v 3 v 4 图三 v 5（3分）（2）邻接矩阵：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0010000110110110110000100 （6分） （3）v 1，v 2，v 3，v 4，v 5结点的度数依次为1，2，4，2，1 （9分） （4）补图如图四：（12分）17．（1）x 量词的辖域为)),,(),((z y x zB y x A ∀∧， （2分） z 量词的辖域为),,(z y x B , （4分）y 量词的辖域为),(z y C ． （6分）（2）自由变元为)),,(),((z y x zB y x A ∀∧中的y ，以及),(z y C 中的z （9分）约束变元为)),,(),((z y x zB y x A ∀∧中的x 与(,,)B x y z 中的z ，以及(,)C y z 中的y ． （12分）六、证明题（本题共8分）18．试证明集合等式A ⋃ (B ⋂C )=(A ⋃B ) ⋂ (A ⋃C ) ．18．证明：设S = A ⋃ (B ⋂C )，T =(A ⋃B ) ⋂ (A ⋃C )，若x ∈S ，则x ∈A 或x ∈B ⋂C ，（1分）即 x ∈A 或x ∈B 且 x ∈A 或x ∈C ． （2分）也即x ∈A ⋃B 且 x ∈A ⋃C ， （3分）即 x ∈T ，所以S ⊆T ． （4分）反之，若x ∈T ，则x ∈A ⋃B 且 x ∈A ⋃C ， （5分）即x ∈A 或x ∈B 且 x ∈A 或x ∈C ， （6分）也即x ∈A 或x ∈B ⋂C ，即x ∈S ，所以T ⊆S ． （7分）因此T =S ． （8分）2011年1月v 1 v 2 v 3 v 4图四 v 5一、单项选择题（每小题3分，本题共15分）1．D 2．B 3．C 4．A 5．B1．若集合A ={a ，b }，B ={ a ，{ a ，b }}，则（ ）．A ．A ∉B B ．A BC ．A BD ．A B2．集合A ={x |x 为小于10的自然数}，集合A 上的关系R ={<x ，y >|x +y =10且x , y ∈A }，则R 的性质为（ ）．A ．自反的B ．对称的C ．传递且对称的D ．反自反且传递的3．设有向图（a ）、（b ）、（c ）与（d ）如图一所示，则下列结论成立的是 ( )．图一A ．（a ）仅为弱连通的B ．（b ）仅为弱连通的C ．（c ）仅为弱连通的D ．（d ）仅为弱连通的4．设图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100100110 则G 的边数为( )．A ．5B ．6C ．7D ．8 5．下列公式 ( )为永真式．A ．⌝P ∧⌝QP ∨Q B ．(P →(Q →P ))(⌝P →(P →Q )) C ．(Q →(P ∨Q )) (⌝Q ∧(P ∨Q )) D ．(⌝P ∨(P ∧Q )) Q 二、填空题（每小题3分，本题共15分）6．设集合A ＝{1，2，3}，那么集合A 的幂集是 {,{1},{2 },{3 },{1,2},{1,3},{2,3},{1,2,3}} ． 7．设A ={a ，b }，B ={1，2}，作f ：A →B ，则不同的函数个数为 4 ．8．若A ={1,2}，R ={<x , y >|x A , y A , x +y <4}，则R 的自反闭包为 {<1,1>,<2,2>,<1,2>,<2,1>} ．9．无向连通图在结点数v 与边数e 满足 e=v -1 关系时是树．10．(∀x )(A (x )→B (x ))∨C (x ，y )中的自由变元为 C (x ，y )中的x 与y ．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“他们去旅游，仅当明天天晴．”翻译成命题公式．12．将语句“今天没有下雪．”翻译成命题公式．11．设P ：他们去旅游，Q ：明天天晴， （2分）P →Q ． （6分）12．设P ：今天下雪， （2分）P ． （6分）四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．汉密尔顿图一定是欧拉图．错误． （3分）存在汉密尔顿图不是欧拉图．（5分）反例见图二． （7分）14．下面的推理是否正确，试予以说明．(1) （x ）（F （x ）→G （y ）） 前提引入(2) F （y ）→G （y ） ES （1）．1、错误． （3分）（2）应为F （a ）→G （y ），换名时，约束变元与自由变元不能混淆． （7分）五．计算题（每小题12分，本题共36分）15．设A ={0，1，2，3，4，5，6}，R ={<x ，y >|x ∈A ，y ∈A 且x +y <1}，S ={<x ，y >|x ∈A ，y ∈A 且x +y ≤3}，试求R ，S ，R •S ，R -1，S -1，r (R )．R ={<0,0>} （2分）S ={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>} （4分）R S ={<0,0>,<0,1>,<0,2>,<0,3>} （6分）R -1={<0,0>} （8分）S -1= S （10分）r (R )=I A ． （12分）16．画一棵带权为1, 2, 2, 3, 6的最优二叉树,计算它们的权．最优二叉树如图四：图四 （10分）权为：13+23+23+33+61=30 （12分）注: 其他正确的最优二叉树参照给分．17．求（P ∨Q ）→（R ∨Q ）的析取范式，合取范式．（P ∨Q ）→（R ∨Q ） 1 2 2 3 3 6 8 5 14图二（P ∨Q ）∨（R ∨Q ） （4分） (P ∧Q )∨（R ∨Q ） (P ∨R ∨Q )∧(Q ∨R ∨Q ) (P ∨R ∨Q ) 析取、合取范式 （12分）注: 其他正确答案参照给分．六、证明题（本题共8分）18．试证明集合等式A ⋂ (B ⋃C )=(A ⋂B ) ⋃ (A ⋂C )．证明：设S =A ∩(B ∪C )，T =(A ∩B )∪(A ∩C )， 若x ∈S ，则x ∈A 且x ∈B ∪C ，即 x ∈A 且x ∈B 或 x ∈A 且x ∈C ，也即x ∈A ∩B 或 x ∈A ∩C ，即 x ∈T ，所以S ⊆T ． （4分）反之，若x ∈T ，则x ∈A ∩B 或 x ∈A ∩C ，即x ∈A 且x ∈B 或 x ∈A 且x ∈C也即x ∈A 且x ∈B ∪C ，即x ∈S ，所以T ⊆S ．因此T =S ． （8分）2010年 7月一、单项选择题（每小题3分，本题共15分）1．B 2．D 3．B 4．C 5．B1．若集合A ={1，{2}，{1，2}}，则下列表述正确的是( )．A ．2AB ．{1}AC ．1AD ． 2 A2．已知一棵无向树T 中有8个顶点，4度、3度、2度的分支点各一个，T 的树叶数为( )．A ．6B ．4C ．3D ．5 3．设无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101110011000011100111110, 则G 的边数为( )． A ．1 B ．7 C ．6 D ．144．设集合A ={a }，则A 的幂集为( )．A ．{{a }}B ．{a ，{a }}C ．{，{a }}D ．{，a }5．下列公式中 ( )为永真式．A ．⌝A ∧⌝ B⌝A ∨⌝B B ．⌝A ∧⌝ B ⌝(A ∨B ) C ．⌝A ∧⌝ BA ∨B D ．⌝A ∧⌝ B ⌝(A ∧B ) 二、填空题（每小题3分，本题共15分）6．命题公式P P ⌝∧的真值是 假（或F ，或0） ．7．若无向树T 有5个结点，则T 的边数为 4 ．8．设正则m 叉树的树叶数为t ，分支数为i ，则(m -1)i = t -1 ．9．设集合A ={1，2}上的关系R ＝{<1, 1>,<1, 2>}，则在R 中仅需加一个元素 <2, 1> ，就可使新得到的关系为对称的．10．( x )(A (x )→B (x ，z )∨C (y ))中的自由变元有 z ，y ．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“今天上课．”翻译成命题公式．设P ：今天上课， （2分）则命题公式为：P ． （6分）12．将语句“他去操场锻炼，仅当他有时间．”翻译成命题公式．设 P ：他去操场锻炼，Q ：他有时间， （2分）则命题公式为：P Q ． （6分）四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．设集合A ={1，2}，B ={3，4}，从A 到B 的关系为f ={<1, 3>}，则f 是A 到B 的函数．14．设G 是一个有4个结点10条边的连通图，则G 为平面图．13．错误． （3分）因为A 中元素2没有B 中元素与之对应，故f 不是A 到B 的函数． （7分）14．错误． （3分）不满足“设G 是一个有v 个结点e 条边的连通简单平面图，若v ≥3，则e ≤3v -6．”（7分）五．计算题（每小题12分，本题共36分）15．试求出（P ∨Q ）→（R ∨Q ）的析取范式．（P ∨Q ）→（R ∨Q ） ┐(P ∨Q )∨（R ∨Q ） （4分）(┐P ∧┐Q )∨（R ∨Q ） （8分）(┐P ∧┐Q )∨R ∨Q （析取范式） （12分）16．设A ={{1}, 1, 2}，B ={ 1, {2}}，试计算（1）A ∩B （2）A ∪B （3）A （A ∩B ）．（1）A ∩B ={1} （4分）（2）A ∪B ={1, 2, {1}, {2}} （8分）（3） A （A ∩B ）={{1}, 2} （12分）17．图G =<V , E >，其中V ={ a , b , c , d }，E ={ (a , b ), (a , c ) , (a , d ), (b , c ), (b , d ), (c , d )}，对应边的权值依次为1、2、3、1、4及5，试（1）画出G 的图形；（2）写出G 的邻接矩阵；（3）求出G 权最小的生成树及其权值．（1）G 的图形表示如图一所示：图一a b c d 112 4 5 3（3分）（2）邻接矩阵：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0111101111011110 （6分） （3）最小的生成树如图二中的粗线所示：（10分）权为：1+1+3=5 （12分）六、证明题（本题共8分）18．试证明：若R 与S 是集合A 上的自反关系，则R ∩S 也是集合A 上的自反关系．证明：设x A ，因为R 自反，所以x R x ，即< x , x >R ；又因为S 自反，所以x R x ，即< x , x >S ． （4分）即< x , x >R ∩S （6分）故R ∩S 自反． （8分）2010年1月一、单项选择题（每小题3分，本题共15分）1．A 2．C 3．B 4．B5．D 1．若集合A ＝{ a ，{a }}，则下列表述正确的是( )．A ．{a }⊆AB ．{{{a }}}⊆AC ．{a ，{a }}∈AD ．∅∈A2．命题公式（P ∨Q ）的合取范式是 ( )A ．（P ∧Q ）B ．（P ∧Q ）∨（P ∨Q ）C ．（P ∨Q ）D ．（P ∧Q ）3．无向树T 有8个结点，则T 的边数为( )．A ．6B ．7C ．8D ．94．图G 如图一所示，以下说法正确的是 ( )．A ．a 是割点B ．{b, c }是点割集C ．{b , d }是点割集D ．{c }是点割集图一5．下列公式成立的为( )．A ．⌝P ∧⌝Q P ∨QB ．P →Q ⌝P →Q 图二ab c d 1 1 2 453C ．Q →P PD ．⌝P ∧(P ∨Q )Q二、填空题（每小题3分，本题共15分）6．设集合A ={2, 3, 4}，B ={1, 2, 3, 4}，R 是A 到B 的二元关系，},{y x B y A x y x R ≤∈∈><=且且则R 的有序对集合为 {<2, 2>，<2, 3>，<2, 4>，<3, 3>}，<3, 4>，<4, 4>} ．7．如果R 是非空集合A 上的等价关系，a ∈A ，b ∈A ，则可推知R 中至少包含<a , a >，< b , b > 等元素．8．设G ＝<V , E >是有4个结点，8条边的无向连通图，则从G 中删去 5 条边，可以确定图G 的一棵生成树．9．设G 是具有n 个结点m 条边k 个面的连通平面图，则m 等于 n +k 2 ．10．设个体域D ＝{1, 2}，A (x )为“x 大于1”，则谓词公式()()x A x ∃的真值为 真（或T ，或1） ．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“今天考试，明天放假．”翻译成命题公式．设P ：今天考试，Q ：明天放假． （2分）则命题公式为：P ∧Q ． （6分）12．将语句“我去旅游，仅当我有时间．”翻译成命题公式．设P ：我去旅游，Q ：我有时间， （2分）则命题公式为：P Q ． （6分）四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．如果图G 是无向图，且其结点度数均为偶数，则图G 是欧拉图．错误． （3分）当图G 不连通时图G 不为欧拉图． （7分）14．若偏序集<A ，R >的哈斯图如图二所示，则集合A 的最大元为a ，最小元是f ．图二错误． （3分）集合A 的最大元与最小元不存在，a 是极大元，f 是极小元，． （7分）五．计算题（每小题12分，本题共36分）15．设谓词公式)),,()(),()((z x y B z y x A x ∀→∃，试（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元．（1）x 量词的辖域为)),,()(),((z x y B z y x A ∀→， （3分）z 量词的辖域为),,(z x y B , （6分）（2）自由变元为)),,()(),((z x y B z y x A ∀→中的y ， （9分）约束变元为x 与z ． （12分）16．设集合A ={{1},1,2}，B ={1,{1,2}}，试计算（1）（A B ）； （2）（A ∩B ）； （3）A ×B ．（1）A B ={{1},2} （4分）（2）A ∩B ={1} （8分）（3）A ×B={<{1},1>，<{1},{1,2}>，<1,1>，<1, {1,2}>，<2,1>，<2, {1,2}>} （12分）17．设G =<V ，E >，V ={ v 1，v 2，v 3，v 4 }，E ={ (v 1,v 3)，(v 2,v 3)，(v 2,v 4)，(v 3,v 4) }，试（1）给出G 的图形表示； （2）写出其邻接矩阵；（3）求出每个结点的度数； （4）画出其补图的图形．（1）G 的图形表示为(如图三)：（3分）图三（2）邻接矩阵：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0110101111000100 （6分） （3）v 1，v 2，v 3，v 4结点的度数依次为1，2，3，2 （9分）（4）补图如图四所示：（12分）图四六、证明题（本题共8分）18．设A ，B 是任意集合，试证明：若A A=B B ，则A=B ．证明：设x A ，则<x ，x >A A ， （1分）因为A A=B B ，故<x ，x >B B ，则有x B ， （3分）所以A B．（5分）设x B，则<x，x>B B，（6分）因为A A=B B，故<x，x>A A，则有x A，所以B A．（7分）故得A=B．（8分）2009年10月一、单项选择题（每小题3分，本题共15分）1．D 2．C 3．B 4．C 5．A1．若G是一个汉密尔顿图，则G一定是( )．A．平面图B．对偶图C．欧拉图D．连通图2．集合A={1, 2, 3, 4}上的关系R={<x，y>|x=y且x, y∈A}，则R的性质为（）．A．不是自反的B．不是对称的C．传递的D．反自反3．设集合A={1，2，3，4，5}，偏序关系是A上的整除关系，则偏序集<A，>上的元素5是集合A的（）．A．最大元B．极大元C．最小元D．极小元4．图G如图一所示，以下说法正确的是( ) ．A．{(a, d)}是割边B．{(a, d)}是边割集C．{(a, d) ,(b, d)}是边割集D．{(b, d)}是边割集图一5．设A（x）：x是人，B（x）：x是工人，则命题“有人是工人”可符号化为（）．A．(∃x)(A(x)∧B(x)) B．(∀x)(A(x)∧B(x))C．┐(∀x)(A(x) →B(x)) D．┐(∃x)(A(x)∧┐B(x))二、填空题（每小题3分，本题共15分）6．若集合A={1，3，5，7}，B={2，4，6，8}，则A∩B=空集（或）．7．设集合A={1，2，3}上的函数分别为：f={<1,2>,<2,1>,<3,3>,}，g={<1,3>,<2,2>,<3,2>,}，则复合函数g f = {<1, 2>, <2, 3>, <3, 2>,} ．8．设G是一个图，结点集合为V，边集合为E，则G的结点度数之和为2|E|（或“边数的两倍”）．9．无向连通图G的结点数为v，边数为e，则G当v与e满足e=v-1 关系时是树．10．设个体域D＝{1, 2, 3}，P(x)为“x小于2”，则谓词公式(∀x)P(x) 的真值为假（或F，或0）．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“他是学生．”翻译成命题公式．设P：他是学生，（2分）则命题公式为：P．（6分）12．将语句“如果明天不下雨，我们就去郊游．”翻译成命题公式．设P ：明天下雨，Q ：我们就去郊游， （2分）则命题公式为： P Q ．四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．下面的推理是否正确，试予以说明．(1) （x ）F （x ）→G （x ） 前提引入(2) F （y ）→G （y ） US （1）．错误． （3分）（2）应为F （y ）→G （x ），换名时，约束变元与自由变元不能混淆． （7分）14．如图二所示的图G 存在一条欧拉回路．图二错误． （3分）因为图G 为中包含度数为奇数的结点． （7分）五．计算题（每小题12分，本题共36分）15．求（P ∨Q ）→R 的析取范式与合取范式．（P ∨Q ）→R （P ∨Q ）∨R （4分）(P ∧Q )∨R （析取范式） （8分）(P ∨R )∧(Q ∨R) （合取范式） （12分）16．设A ={0，1，2，3}，R ={<x ，y >|x ∈A ，y ∈A 且x +y <0}，S ={<x ，y >|x ∈A ，y ∈A 且x +y ≤2}，试求R ，S ，R •S ，S -1，r (R )．R =, S ={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<2,0>} （3分）R S =， （6分）S -1= S ， （9分）r (R )=I A ={<0,0>,<1,1>,<2,2>,<3,3>}． （12分）17．画一棵带权为1, 2, 2, 3, 4的最优二叉树,计算它们的权．最优二叉树如图三所示（10分） 图三权为13+23+22+32+42=27 （12分）1 22 3 3 4 7 5 12六、证明题（本题共8分）18．试证明集合等式A⋃ (B⋂C)=(A⋃B) ⋂ (A⋃C) ．证明：设S= A⋃ (B⋂C)，T=(A⋃B) ⋂ (A⋃C)，若x∈S，则x∈A或x∈B⋂C，即x∈A或x∈B且x∈A 或x∈C．也即x∈A⋃B且x∈A⋃C，即x∈T，所以S⊆T．（4分）反之，若x∈T，则x∈A⋃B且x∈A⋃C，即x∈A或x∈B且x∈A或x∈C，也即x∈A或x∈B⋂C，即x∈S，所以T⊆S．因此T=S．2009年7月一、单项选择题（每小题3分，本题共15分）1．A 2．B 3．B 4．D 5．C1．若集合A={a，b}，B={ a，b，{ a，b }}，则（）．A．A B，且A B B．A B，但A BC．A B，但A∉B D．A B，且A∉B2．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={<x，y>|x+y=10且x, y∈A}，则R的性质为（）．A．自反的B．对称的C．传递且对称的D．反自反且传递的3．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个．A．0 B．2 C．1 D．34．如图一所示，以下说法正确的是( ) ．A．{(a, e)}是割边B．{(a, e)}是边割集C．{(a, e) ,(b, c)}是边割集D．{(d, e)}是边割集图一5．设A（x）：x是人，B（x）：x是学生，则命题“不是所有人都是学生”可符号化为（）．A．(∀x)(A(x)∧B(x)) B．┐(∃x)(A(x)∧B(x))C．┐(∀x)(A(x) →B(x)) D．┐(∃x)(A(x)∧┐B(x))二、填空题（每小题3分，本题共15分）6．若集合A的元素个数为10，则其幂集的元素个数为1024 ．7．设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为8 ．8．若A={1,2}，R={<x, y>|x A, y A, x+y=10}，则R的自反闭包为{<1,1>,<2,2>} ．9．结点数v与边数e满足e=v-1 关系的无向连通图就是树．10．设个体域D＝{a, b, c}，则谓词公式(∀x)A(x)消去量词后的等值式为A (a) ∧A (b)∧A（c）．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“尽管他接受了这个任务，但他没有完成好．”翻译成命题公式．设P：他接受了这个任务，Q：他完成好了这个任务，（2分）P Q ． （6分）12．将语句“今天没有下雨．”翻译成命题公式．设P ：今天下雨， （2分）P ． （6分）四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．下面的推理是否正确，试予以说明．(1) （x ）F （x ）→G （x ） 前提引入(2) F （y ）→G （y ） US （1）．错误． （3分）（2）应为F （y ）→G （x ），换名时，约束变元与自由变元不能混淆． （7分）14．若偏序集<A ，R >的哈斯图如图二所示，则集合A 的最大元为a ，最小元不存在．图二错误． （3分）集合A 的最大元不存在，a 是极大元． （7分）五．计算题（每小题12分，本题共36分）15．求（P ∨Q ）→（R ∨Q ）的合取范式．（P ∨Q ）→（R ∨Q ）（P ∨Q ）∨（R ∨Q ） （4分）(P ∧Q )∨（R ∨Q ）(P ∨R ∨Q )∧(Q ∨R ∨Q ) (P ∨R ∨Q ) ∧R 合取范式 （12分）16．设A ={0，1，2，3，4}，R ={<x ，y >|x ∈A ，y ∈A 且x +y <0}，S ={<x ，y >|x ∈A ，y ∈A 且x +y ≤3}，试求R ，S ，R •S ，R -1，S -1，r (R )．R =, （2分）S ={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>} （4分）R S =， （6分）R -1=， （8分）S -1= S ， （10分）r (R )=I A ． （12分）17．画一棵带权为1, 2, 2, 3, 4的最优二叉树,计算它们的权．1 2 2 3 3 4 7 5 12权为13+23+22+32+42=27 （12分）六、证明题（本题共8分）18．设G是一个n阶无向简单图，n是大于等于2的奇数．证明G与G中的奇数度顶点个数相等(G 是G的补图)．证明：因为n是奇数，所以n阶完全图每个顶点度数为偶数，（3分）因此，若G中顶点v的度数为奇数，则在G中v的度数一定也是奇数，（6分）所以G与G中的奇数度顶点个数相等．（8分）2008年7月一、单项选择题（每小题3分，本题共15分）1．B 2．B 3．A 4．C 5．D1．设A={a, b}，B={1, 2}，R1，R2，R3是A到B的二元关系，且R1={<a，2>, <b，2>}，R2={<a，1>, <a，2>, <b，1>}，R3={<a，1>, <b，2>}，则（）不是从A到B的函数．A．R1和R2B．R2C．R3D．R1和R32．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为( )．A．8、2、8、2 B．无、2、无、2C．6、2、6、2 D．8、1、6、13．若集合A的元素个数为10，则其幂集的元素个数为（）．A．1024 B．10 C．100 D．14．设完全图Kn 有n个结点(n≥2)，m条边，当（）时，Kn中存在欧拉回路．A．m为奇数B．n为偶数C．n为奇数D．m为偶数5．已知图G的邻接矩阵为，则G有（）．A．5点，8边B．6点，7边C．6点，8边D．5点，7边二、填空题（每小题3分，本题共15分）6．设集合A＝{a，b}，那么集合A的幂集是{,{a,b},{a},{b }} ．7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 2 个．8．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去 4 条边后使之变成树．9．设连通平面图G的结点数为5，边数为6，则面数为 3 ．10．设个体域D＝{a, b}，则谓词公式(∀x)A(x)∧（∃x）B（x）消去量词后的等值式为(A (a)∧A (b))∧(B（a）∨B（b）) ．三、逻辑公式翻译（每小题4分，本题共12分）11．将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公式．设P：所有人今天都去参加活动，Q：明天的会议取消，（1分）P Q．（4分）12．将语句“今天没有人来．”翻译成命题公式．设P：今天有人来，（1分）P．（4分）13．将语句“有人去上课．”翻译成谓词公式．设P(x)：x是人，Q(x)：x去上课，（1分）(x)(P(x)Q(x))．四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．14．┐P∧（P→┐Q）∨P为永真式．15．若偏序集<A，R>的哈斯图如图一所示，则集合A的最大元为a，最小元不存在．图一14．正确．（3分）┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式，如果P的值为真，则┐P∧（P→┐Q）∨P为真，（5分）如果P的值为假，则┐P与P→┐Q为真，即┐P∧（P→┐Q）为真，也即┐P∧（P→┐Q）∨P为真，所以┐P∧（P→┐Q）∨P是永真式．（7分）另种说明：┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式，只要其中一项为真，则整个公式为真．（5分）可以看到，不论P的值为真或为假，┐P∧（P→┐Q）与P总有一个为真，所以┐P∧（P→┐Q）∨P是永真式．（7分）或用等价演算┐P∧（P→┐Q）∨P⇔T15．正确．（3分）对于集合A的任意元素x，均有<x, a>R（或xRa），所以a是集合A中的最大元．（5分）按照最小元的定义，在集合A中不存在最小元．（7分）五．计算题（每小题12分，本题共36分）16．设集合A={1，2，3，4}，R={<x, y>|x, y∈A；|x y|=1或x y=0}，试（1）写出R 的有序对表示；（2）画出R 的关系图；（3）说明R 满足自反性，不满足传递性．（1）R ={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>} （3分）（2）关系图为（6分）（3）因为<1,1>,<2,2>,<3,3>,<4,4>均属于R ，即A 的每个元素构成的有序对均在R 中，故R 在A 上是自反的。

2020-2021《离散数学》期末课程考试试卷B1专业：考试日期： 所需时间：120分钟 总分：100 分 闭卷一、选择题（每小题2分，共20分） 1．下列语句中是命题的只有（ ）A ．1+8==30B ．5x+6==30C ．5y+1<30D ．x mod 20==3。

2．设命题公式G ：)(R Q P ∧→⌝,则使公式G 取真值为1的P ，Q ，R 赋值分别是 ( )1,1,1.0,1,0.1,0,0.0,0,0.D C B A3．设A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中（ ）是错的。

A 、A ⊆Φ； B 、{6，7，8}∈A ；C 、{{4，5}}⊂A ；D 、{1，2，3}⊂A 。

4．给定下列序列，（ ）可以构成无向简单图的结点度数序列。

A 、 2,3,4,5,6,7；B 、 1,2,2,3,4；C 、 2,1,1,1,2；D 、 3,3,5,6,0。

5．给定无向图>=<E V G ,，如下图所示，下面哪个边集不是其边割集（ ）。

A 、{<V1,V2>,<V7,V8>}；B 、{<V1,V4>,<V3,V4>}；C 、{<V4,V7>,<V4,V8>}；D 、{<V1,V4>,<V2,V3>}。

6．设P 表示“天下大雨”， Q 表示“他在室内运动”，则命题“除非天下大雨，否则他不在室内运动”符号化为（ ）。

A 、 P Q →； B 、P Q ∧； C 、P Q ⌝→⌝； D 、P Q ⌝∨．7．集合A 上的关系R 为一个等价关系，当且仅当R 具有（ ）。

A 、自反性、对称性和传递性； B 、自反性、反对称性和传递性； C 、反自反性、对称性和传递性； D 、反自反性、反对称性和传递性 8．设Q 为有理数集，〈Q ，•〉（其中•为普通乘法）不能构成（ ）。

《离散数学》期末考试复习题及答案第一部分、考试形式和时间答题时限：120 分钟考试形式：闭卷笔试第二部分、考试题型和得分构成一、选择题：对每一道小题，从其4个备选答案中选择最适合的一项，每小题2分，共10道小题，20分。

二、填空题：每空1分，共5道小题，10个空白处待填，10分。

三、判断题：每一道小题均以陈述语句描述，对的打√，错的打х。

每小题1分，共10道小题，10分。

四、综合题：每小题10分，共6道小题，60分。

第三部分、考试复习范围一、选择题1．含n个元素的集合A的幂集的元素个数为多少？答案：2n个。

2．数理逻辑的创始人是谁？答案：莱布里茨。

3．设(R,+,⋅)是环，它有哪些特性？答案：1.(R,+)是阿贝尔群。

2.(R,•)是半群。

3.•对+可分配。

4．排中律满足哪些性质？答案：A ∧ 不成立。

（不应同时否认一个命题（A ）及其否定（非A ））x （F （x ）∨F （x ））对任何个体x 而言，x 有性质F 或没有性质F 。

5．什么是真命题？命题“如果雪是黑的，则1+1=0”是真命题吗？答案：真值为真的命题为真命题。

命题“如果雪是黑的，则1+1=0”是真命题！解析：p:雪是黑的；q:1+1=0;如果雪是黑的，则1+1=0:p →q 。

由于p 为假，所以无论的真值如何，“p →q ”的真值都为真。

6. 下列哪个等价公式有错？A ．P Q Q P →⇔→；B ．P Q P Q →⇔⌝∨；C ．P Q Q P →⇔⌝∨；答案：A7. 设G 为4阶有向图，度数列为（3,4,2,3），若它的入度列为（1,2,2,1），则出度列为哪项？A ．（1,2,1,2）；B ．（2,2,0,2）；C ．（2,1,1,2）．答案：B解析：有向图中：度数=出度数+入度数。

8. 设{}{},3,4,S a φ=,则表示空元素属于S 怎样写？答案:Ø∈S9. 什么是前束范式？下面哪个是前束范式？A ．(,)()()(,,)Q x z x y R x y z →∃∀ ；B ．()()(,)x y Q x y ∀∃．A答案：前束范式：如果量词均在全式的开头，它们的作用域延伸到整个公式的末端，则该公式叫做前束范式。

离散数学期末考试试题(配答案)1. 谓词公式)()(x xQ x xP ∃→∀的前束范式是___________。

2. 设全集{}{}{},5,2,3,2,1,5,4,3,2,1===B A E 则A ∩B =____；=A _____；=B A Y __ _____3. 设{}{}b a B c b a A ,,,,==；则=-)()(B A ρρ__ __________；=-)()(A B ρρ_____ ______。

二．选择题（每小题2分；共10分）1. 与命题公式)(R Q P →→等价的公式是（ ）（A ）R Q P →∨)( （B ）R Q P →∧)( （C ）)(R Q P ∧→ （D ）)(R Q P ∨→ 2. 设集合{}c b a A ,,=；A 上的二元关系{}><><=b b a a R ,,,不具备关系( )性质 （A ） (A)传递性 (B)反对称性 (C)对称性 (D)自反性 三．计算题（共43分）1. 求命题公式r q p ∨∧的主合取范式与主析取范式。

（6分）2. 设集合{}d c b a A ,,,=上的二元关系R 的关系矩阵为⎪⎪⎪⎪⎪⎭⎫⎝⎛=1000000011010001R M ；求)(),(),(R t R s R r 的关系矩阵；并画出R ；)(),(),(R t R s R r 的关系图。

（10分）5. 试判断),(≤z 是否为格？说明理由。

（5分）（注：什么是格？Z 是整数；格：任两个元素；有最小上界和最大下界的偏序）四．证明题（共37分）1. 用推理规则证明D D A C C B B A ⌝⇒∧⌝⌝⌝∧∨⌝→)(,)(,。

（10分）2. 设R 是实数集；b a b a f R R R f +=→⨯),(,:；ab b a g R R R g =→⨯),(,:。

求证：g f 和都是满射；但不是单射。

（10分）一；1； _ ∃x ∃y¬P(x)∨Q(y)2； {2} {4；5} {1；3；4；5}3； {{c}；{a ；c}；{b ；c}；{a ；b ；c}} Φ_ 二；B D三；解：主合取方式：p ∧q ∨r ⇔(p ∨q ∨r)∧(p ∨¬q ∨r)∧(¬p ∨q ∨r)= ∏0.2.4主析取范式：p ∧q ∨r ⇔(p ∧q ∧r) ∨(p ∧q ∧¬r) ∨(¬p ∧q ∧r) ∨(¬p ∧¬q ∧r) ∨(p ∧¬q ∧r)= ∑1.3.5.6.7 四；1；证明：编号 公式 依据 （1） （¬B∨C ）∧¬C 前提 （2） ¬B∨C ；¬C （1） （3） ¬B （2） （4） A →B （3） （5） ¬A （3）（4） （6） ¬（¬A∧D ） 前提 （7） A ∨¬D （6） （8）¬D （5）（6）2；证明：要证f 是满射；即∀y ∈R ；都存在（x1；x2）∈R ×R ；使f （x1；x2）=y ；而f （x1；x2）=x1+x2；可取x1=0；x2=y ；即证得；再证g 是满射；即∀y ∈R ；；都存在（x1；x2）∈R ×R ；使g （x1；x2）=y ；而g （x1；x2）=x1x2；可取x1=1；x2=y ；即证得；最后证f 不是单射；f （x1；x2）=f （x2；x1）取x1≠x2；即证得；同理：g （x1；x2）=g （x2；x1）；取x1≠x2；即证得。

离散数学期末考试试题及答案离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。

下面是小编整理的离散数学期末考试试题及答案，欢迎阅读参考！一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。

1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。

[A] 3 [B] 8 [C]9 [D]272、设A1,2,3,5,8,B1,2,5,7,则AB( )。

[A] 3,8 [B]3 [C]8 [D]3,83、若X是Y的子集，则一定有( )。

[A]X不属于Y [B]X∈Y[C]X真包含于Y [D]X∩Y=X4、下列关系中是等价关系的'是( )。

[A]不等关系 [B]空关系[C]全关系 [D]偏序关系5、对于一个从集合A到集合B的映射，下列表述中错误的是( )。

[A]对A的每个元素都要有象 [B] 对A的每个元素都只有一个象[C]对B的每个元素都有原象 [D] 对B的元素可以有不止一个原象6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为( )。

[A]p→q [B]q→p [C]┐q→┐p [D]┐p→q7、设A={a,b,c},则A到A的双射共有( )。

[A]3个 [B]6个 [C]8个 [D]9个8、一个连通G具有以下何种条件时，能一笔画出：即从某结点出发，经过中每边仅一次回到该结点( )。

[A] G没有奇数度结点 [B] G有1个奇数度结点[C] G有2个奇数度结点 [D] G没有或有2个奇数度结点9、设〈G,*〉是群，且|G|>1，则下列命题不成立的是( )。

[A] G中有幺元 [B] G中么元是唯一的[C] G中任一元素有逆元 [D] G中除了幺元外无其他幂等元10、令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为( )[A] p→┐q [B] p∨┐q[C] p∧q [D] p∧┐q11、设G=的结点集为V={v1,v2,v3},边集为E={,}.则G的割(点)集是( )。

离散数学期末考试试题离散数学期末考试试题离散数学作为一门重要的数学基础课程，对于计算机科学、信息科学等学科具有重要的意义。

期末考试是对学生在这门课程中的学习成果进行综合评价的重要环节。

本文将通过讨论离散数学期末考试试题，探讨离散数学的基本概念和应用。

第一部分：命题逻辑命题逻辑是离散数学的基础，它研究的是命题之间的逻辑关系。

考试中的命题逻辑部分通常包括命题的合取、析取、否定等逻辑运算，以及命题的真值表和逻辑等价的判断。

第一题是关于命题的合取和析取的运算。

考生需要根据给定的命题，使用逻辑运算符将其进行合取或析取运算，并给出结果。

这个题目考察了考生对于逻辑运算的理解和操作能力。

第二题是关于命题的真值表。

考生需要根据给定的命题和逻辑运算符，填写真值表，并根据真值表判断命题之间的逻辑关系。

这个题目考察了考生对于真值表的理解和应用能力。

第二部分：集合论集合论是离散数学的另一个重要分支，它研究的是集合之间的关系和运算。

考试中的集合论部分通常包括集合的基本运算、集合的关系和集合的证明等内容。

第三题是关于集合的基本运算。

考生需要根据给定的集合和集合运算符，求解集合的并、交、差等运算，并给出结果。

这个题目考察了考生对于集合运算的理解和操作能力。

第四题是关于集合的关系。

考生需要根据给定的集合和集合关系，判断两个集合之间的包含关系、相等关系等，并给出证明。

这个题目考察了考生对于集合关系的理解和应用能力。

第三部分：图论图论是离散数学的重要分支之一，它研究的是图的性质和图的应用。

考试中的图论部分通常包括图的表示、图的遍历和图的连通性等内容。

第五题是关于图的表示。

考生需要根据给定的图，使用邻接矩阵或邻接表的方式表示图，并给出图的基本信息。

这个题目考察了考生对于图的表示方法的理解和应用能力。

第六题是关于图的遍历。

考生需要根据给定的图和遍历算法，求解图的深度优先遍历或广度优先遍历，并给出遍历结果。

这个题目考察了考生对于图的遍历算法的理解和操作能力。

离散数学期末考试题及答案一、选择题（每题2分，共20分）1. 以下哪个选项是图的边数与顶点数的关系？A. 边数小于顶点数B. 边数等于顶点数C. 边数大于顶点数D. 边数与顶点数无固定关系答案：D2. 有限自动机的英文缩写是什么？A. FAB. PDAC. TMAD. NFA答案：A3. 布尔代数中，德摩根定律是指什么？A. ¬(A ∧ B) 等于¬ A ∨ ¬ BB. ¬(A ∨ B) 等于¬ A ∧ ¬ BC. A ∧ B 等于¬(A ∨ B)D. A ∨ B 等于¬(¬ A ∧ ¬B)答案：B4. 在命题逻辑中，以下哪个符号表示蕴含？A. ∧B. ∨C. →D. ↔答案：C5. 集合A = {1, 2, 3}，B = {2, 3, 4}，则A ∪ B等于：A. {1, 2, 3, 4}B. {1, 2, 3}C. {2, 3, 4}D. {1, 3, 4}答案：A6. 以下哪个选项是正确的递归定义？A. 一个数是偶数当且仅当它是2的倍数B. 一个数是偶数当且仅当它不是2的倍数C. 一个数是偶数当且仅当它是另一个偶数加1D. 以上都是正确的递归定义答案：A7. 有向图和无向图的主要区别是什么？A. 有向图的边有方向，无向图的边没有方向B. 有向图的顶点有方向，无向图的顶点没有方向C. 有向图的边可以相交，无向图的边不可以相交D. 有向图可以有环，无向图不可以有环答案：A8. 在命题逻辑中，以下哪个公式是矛盾的？A. A ∧ ¬ AB. A ∨ ¬ AC. A → BD. A ∧ B ∧ ¬ A答案：A9. 以下哪个是图的同义术语？A. 网络B. 矩阵C. 树D. 以上全部答案：A10. 以下哪个命题逻辑公式是有效的？A. (A → B) ∧ (B → A)B. (A ∧ B) → AC. (A ∨ B) → AD. (A ∧ B) → B答案：B二、填空题（每题2分，共20分）11. 在命题逻辑中，_________ 表示一个命题是真的，而 _________ 表示一个命题是假的。

安徽大学20 10 — 20 11 学年第 1 学期 《离散数学（上）》考试试卷（B 卷）（时间120分钟）院/系 专业 姓名 学号一、单选题（每小题2分，共20分）1. 设:P 天下雨，:Q 小王乘汽车上班，则命题“仅当天下雨，小王才乘汽车上班”可符号化为（ ）A.P Q →；B.Q P →；C.P Q ∧；D.P Q ∨。

2. 设个体域为{,}D a b =,(,)(,)0F a a F a b ==,(,)(,)1F b a F b b ==,则下列公式为真的是( ）A. (,)x yF x y ∃∀；B. (,)x yF x y ∀∃；C.(,)x yF x y ∀∀；D.(,)x yF x y ∃∃¬。

3. 设B 是不含变元x 的公式，谓词公式(∀x)(A(x)→B)等价于( )A.(∃x)A(x)→BB.(∀x)A(x)→BC.A(x)→BD.(∀x)A(x)→(∀x)B 4. 对任意集合C B A ,,，下列各式中一定成立的是（ ）A.)()()(C A B A C B A ⋃⊕⋃=⊕⋃；B. )()()(C A B A C B A ⋃⋂⊕=⋂⊕；C. )()()(C A B A C B A ⋃⊗⋃=⊗⋃；D. )()(C B A C B A ⨯⨯=⨯⨯。

5. 设A={a,b,c}，A 上二元关系R={〈a,a 〉，〈b,b 〉,〈a,c 〉}，则关系R 的对称闭包S(R)是( )A.R ∪I AB.RC.R ∪{〈c,a 〉}D.R ∩I A6. 设X={a,b,c},I x 是X 上恒等关系，要使I x ∪{〈a,b 〉，〈b,c 〉，〈c,a 〉，〈b,a 〉}∪R 为X 上的等价关系，R 应取( )A. ｛〈c,a 〉，〈a,c 〉｝B.{〈c,b 〉，〈b,a 〉}C. {〈c,a 〉，〈b,a 〉}D.{〈a,c 〉，〈c,b 〉} 7. 下列式子正确的是( )A. ∅∈∅B.∅⊆∅C.{∅}⊆∅D.{∅}∈∅ 8. 以下命题公式中，为永假式的是( )A.p →(p ∨q ∨r)B.(p →┐p)→┐pC.┐(q →q)∧pD.┐(q ∨┐p)→(p ∧┐p) 9. 设1π和2π是非空集合A 的划分，则下列集合一定是A 的划分的是（ ）A.12ππB.12ππC.12ππ-D.1211()ππππ-10. 设N 和R 分别为自然数和实数集合，则下列集合中与其他集合的基数不同的集合是（ ）A.RB.NN C.()N ρ D.nN （n N ∈）二、判断题（每小题2分，共10分。

大学《离散数学》期末考试试卷及答案(1)一、选择题1. 离散数学的主要研究对象是（）。

A. 连续的数学结构B. 有限的数学结构C. 数学的综合应用D. 数学的哲学思考2. 命题逻辑是离散数学的一个重要组成部分，它主要研究（）。

A. 命题之间的真假关系B. 变量之间的关系C. 函数之间的关系D. 集合之间的关系3. 集合的基本运算包括（）。

A. 并、交、差、补B. 加、减、乘、除C. 包含、相等、不等、自反D. 大于、小于、等于、不等于二、填空题1. 若集合A={m|2m-1>3}，则A中的元素为______。

2. 有一个集合A={1，2，3}，则集合A的幂集为______。

3. 若命题p为真，命题q为假，则复合命题“p∧q”的真值为______。

三、解答题1. 请写出离散数学中常用的数学符号及其含义。

2. 请解释命题逻辑中的充分必要条件及其符号表示，并给出一个例子。

3. 请定义集合的笛卡尔积，并给出两个集合进行笛卡尔积运算的例子。

四、问答题1. 离散数学在计算机科学中有着重要的应用，请列举三个与计算机科学相关的离散数学应用领域并简要介绍。

2. 请简要解释归纳法在离散数学中的作用，并给出一个使用归纳法证明的例子。

3. 什么是有向图？请给出一个有向图的例子，并解释该图中的关系。

参考答案：一、选择题1. B2. A3. A二、填空题1. A={m|2m-1>3}2. {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}3. 假三、解答题1. 常用数学符号及含义：- ∪：并，表示集合的合并操作。

- ∩：交，表示集合的交集操作。

- ∖：差，表示减去一个集合中的元素。

- ⊆：包含，表示一个集合包含于另一个集合。

- =：相等，表示两个集合具有相同的元素。

2. 充分必要条件是指一个命题的成立与另一个命题的成立互为必要条件，若A是B的充分必要条件，那么当A成立时B一定成立，且当A不成立时B也一定不成立。

离散数学期末考试题及答案一、选择题（每题2分，共20分）1. 在集合论中，表示两个集合A和B的并集的符号是：A. ∩B. ∪C. ⊂D. ⊆2. 以下哪个命题逻辑表达式是真命题，当P为真，Q为假时？A. ¬PB. P ∧ QC. P ∨ QD. P → Q3. 如果函数f: A → B是一个单射，那么它不能是：A. 满射B. 双射C. 恒等函数D. 逆函数4. 在图论中，一个图G是连通的，当且仅当：A. G是无向图B. G是简单图C. G是完全图D. 对于任意两个顶点，都存在一条路径5. 以下哪个不是组合数学中的计数原理？A. 加法原理B. 乘法原理C. 排列D. 组合二、简答题（每题10分，共30分）6. 解释什么是二元关系，并给出一个例子。

7. 描述什么是有向图和无向图的区别。

8. 什么是等价关系，它有哪些性质？三、计算题（每题15分，共30分）9. 给定集合A = {1, 2, 3, 4}，B = {a, b, c}，定义函数f: A → B，其中f(1) = a, f(2) = b, f(3) = c, f(4) = a。

判断f是否是单射、满射或双射，并给出理由。

10. 计算以下命题逻辑表达式的真值表：(P ∧ Q) → (¬P ∨ R)，其中P、Q、R是命题变量。

四、证明题（每题20分，共20分）11. 证明：如果一个图G是连通的，那么它的任意子图也是连通的。

答案一、选择题1. B2. C3. A4. D5. D二、简答题6. 二元关系是定义在两个集合上的一个关系，它将第一个集合中的每个元素与第二个集合中的元素相关联。

例如，如果A是人名的集合，B是年龄的集合，关系R可以是“比...年长”，那么(Alice, 30) ∈ R表示Alice比30岁年长。

7. 有向图由顶点和有向边组成，每条边都有一个方向，表示从一个顶点指向另一个顶点。

无向图由顶点和无向边组成，边没有方向。

离散数学期末考试题及答案1. 题目描述：以下是离散数学期末考试的题目。

请仔细阅读每个问题，并在题后给出相应的答案。

请注意，答案应尽量详细和准确，以确保得分。

1.1 命题与谓词逻辑（20分）1.1.1 什么是命题逻辑？它可以用于解决哪些问题？1.1.2 简要解释谓词逻辑的概念和其在离散数学中的应用。

1.2 集合和图论（30分）1.2.1 定义两个集合的并、交和差的概念。

1.2.2 解释有向图和无向图的区别，并给出一个实际应用中的例子。

1.3 关系和函数（40分）1.3.1 什么是关系？请给出一个实际应用中关系的例子。

1.3.2 定义函数的概念，并解释函数与关系的区别。

1.4 计数原理（20分）1.4.1 简要阐述乘法原理和加法原理的概念，并给出一个应用实例。

1.4.2 什么是排列和组合？请说明它们的应用场景，并给出一个例子。

2. 答案解析：2.1 命题与谓词逻辑1.1.1 命题逻辑是一种数学分支，用于研究命题之间的关系和推理规则。

其应用范围广泛，包括数学、计算机科学、哲学等领域。

1.1.2 谓词逻辑是一种扩展了命题逻辑的逻辑体系，它考虑了命题中的变量、谓词和量词等元素。

在离散数学中，谓词逻辑常用于描述集合、函数和关系等概念。

2.2 集合和图论1.2.1 集合的并（∪）是指将两个或多个集合中的所有元素取出形成一个新的集合；交（∩）指仅包含两个或多个集合中共有的元素；差（-）是指从一个集合中去除另一个集合中的元素。

1.2.2 有向图中，边是具有方向性的；而在无向图中，边是没有方向性的。

例如，在社交网络中，有向图可以表示人与人之间的关注关系，而无向图可以表示人与人之间的好友关系。

2.3 关系和函数1.3.1 关系是集合之间的一种特殊的子集，它描述了元素之间的某种联系。

例如，家族中的血亲关系可以看作是一个关系。

关系可以用图、矩阵等方式表示。

1.3.2 函数是一种特殊的关系，它将一个集合中的每个元素映射到另一个集合中的唯一元素。

2011级离散数学(B) 计科、软件、网络一、填空题（每小题2分，共30分）1 设():M x x 偶数， ():F x x 素数。

将命题“存在偶素数”符号化为： ))()((x F x M x ∧∃ 。

2 集合A={2,2,2,3}的幂集合P(A)={}3,2{},3{},2{,φ }。

3 设A={1,2,3}，B={a,b}，则=⨯B A 6 。

4 已知命题公式A 含有2个命题变项，其成真赋值为00、10、11，则其主合取范式为 1M 。

5 设p ：北京比大连人口多，q ：2+2=4，r ：乌鸦是白色的。

则命题公式)()(r p r p ⌝∧↔∨⌝的真值为 0 。

6 无向图G 具有欧拉通路，当且仅当G 是 连通 图且无奇度顶点或有两个奇度顶点。

7 6阶无向树的总度数为 10 。

8设A={1,2,3}，B={a, b}，A 1={2}，f={<1,a>,<2,a>,<3,b>}，则=-))((11A f f { 1，2 }。

9 设B A f →:，若ran B f )(=，则称B A f →:是满射的。

10 设群>⊕=<}),.({b a P G ，其中⊕为对称差。

群方程φ=⊕}{b Y 的解=Y {b} 。

11 设p：我去自习，q：我去看电影，r：我有课。

则命题“如果我去自习或看电影，我就没有课”的符号化形式为r qp⌝→∨)(。

12 画出3阶有向完全图的2条边的2个非同构的生成子图。

13 下面运算表中的=-1a c 。

14 写出模4乘法<Z4,⊗ >的运算表⊗0 1 2 31230 0 0 00 1 2 30 2 0 20 3 2 115 设A（x）是任意的含自由出现个体变项x的公式，则⇔⌝∀)(xxA )(xAx⌝∃。

二、试解下列各题（每小题5分，共25分）1. 设A = {a , b , c , d }, R = {<a ,b >,<b ,a >,<b ,c >,<c ,d >}, 求3R 的的矩阵表示和关系图表示。