计算机科学与技术专业级第二学期离散数学试题一、单项选择题（每小题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 上是自反的。
