电大历年离散数学试题汇总

-.z.计算机科学与技术专业级第二学期离散数学试题2012年1月一、单项选择题（每小题3分，本题共15分）1．C2．C3．B4．A5．D1．若集合A的元素个数为10，则其幂集的元素个数为（）．A．10B．100C．1024D2．设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和R3．设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，B={2,4,6}，则集合B的最大元、最小元、上界、下界依次为()．A．8、2、8、2B．无、2、无、2C．6、2、6、2D．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}，则谓词公式(*)(A(*)∧B（*））消去量词后的等值式为(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分）abcd图一13．若偏序集<A，R>的哈斯图如图一所示，则集合A的最大元为a，极小元不存在．错误．（3分）对于集合A的任意元素*，均有<*,a>R（或*Ra），所以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）∨PT五．计算题（每小题12分，本题共36分）15．设集合A={1，2，3，4}，R={<*,y>|*,yA；|*y|=1或*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分）16．设图G=<V，E>，V={v1，v2，v3，v4，v5}，E={(v1,v2)，(v1,v3)，(v2,v4)，(v3,v5)，(v4,v5)}，试画出G的图形表示；写出其邻接矩阵；v1v2v3v4图三v5(4)画出图G的补图的图形．16．（1）关系图如图三：（3分）（2）邻接矩阵（6分）（3）deg(v1)=2deg(v2)=2deg(v3)=2deg(v4)=2v1v1v2v3v4图四v5（4）补图如图四（12分）17．求PQ∧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)∨(┐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．A2．C3．C4．D5．B1．若集合A={1，{1}，{2}，{1，2}}，则下列表述正确的是()．A．{2}AB．{1，2}AC．1AD．22．设G为无向图，则下列结论成立的是()．A．无向图G的结点的度数等于边数的两倍．B．无向图G的结点的度数等于边数．C．无向图G的结点的度数之和等于边数的两倍．D．无向图G的结点的度数之和等于边数．ababcdefA．{(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(*)：*是人，B(*)：*犯错误，则命题“没有不犯错误的人”可符号化为（）．A．┐(*)(A(*)→┐B(*))B．┐(*)(A(*)∧┐B(*))C．┐(*)(A(*)∧B(*))D．(*)(A(*)∧B(*))二、填空题（每小题3分，本题共15分）6．命题公式的真值是真（或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>，就可使新得到的关系为自反的．10．(*)(P(*)→R(y)∨S(z))中的约束变元有*．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“雪是黑色的．”翻译成命题公式．设P：雪是黑色的，（2分）则命题公式为：P．（6分）12．将语句“如果明天下雨，则我们就在室内上体育课．”翻译成命题公式．设P：如果明天下雨，Q：我们在室内上体育课，（2分）则命题公式为：PQ．（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,的最优二叉树,并计算该最优二叉树的权．最优二叉树如图二所示．23345510717（10分）图二权为23+33+32+42+52=39（12分）六、证明题（本题共8分）18．试证明：若R与S是集合A上的对称关系，则R∩S也是集合A上的对称关系．证明：设*，yA，因为R对称，所以若<*,y>R，则<y,*>R．（2分）因为S对称，所以若<*,y>S，则<y,*>S．（4分）于是若<*,y>R∩S则<*,y>R且<*,y>S即<y,*>R且<y,*>S（6分）也即<y,*>R∩S，故R∩S是对称的．（8分）中央广播电视大学2010—2011学年度第一学期“开放本科”期末考试离散数学（本）试题2011年1月一、单项选择题（每小题3分，本题共15分）1．A2．D3．B4．D5．C1．若集合A＝{a，{1}}，则下列表述正确的是()．A．{1}AB．{1}AC．{a}AD．A2．设图G＝<V,E>，vV，则下列结论成立的是()．A．deg(v)=2EB．deg(v)=EC．D．3．如图一所示，以下说法正确的是()．A．(e,c)是割边B．(d,e)是割边abcdabcd图一e4．命题公式（P∨Q）的合取*式是()．A．PB．（P∧Q）C．（P∨P）D．（P∨Q）5．下列等价公式成立的为()．A．PQPQB．QPPQC．PPQQD．PPQ二、填空题（每小题3分，本题共15分）6．设集合A={0,1,2}，B={1,2,3,4,}，R是A到B的二元关系，则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}，则谓词公式消去量词后的等值式为A(1)A(2)．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“如果小李学习努力，则他就会取得好成绩．”翻译成命题公式．12．将语句“小*学习努力，小王取得好成绩．”翻译成命题公式．11．设P：小李学习努力，Q：小李会取得好成绩，（2分）PQ．（6分）12．设P：小*学习努力，Q：小王取得好成绩，（2分）PQ．（6分）四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．如果R1和R2是A上的自反关系，则R1R2是自反的．14．如图二所示的图中存在一条欧拉回路．图二13．正确．（3分）R1和R2是自反的，*A，<*,*>R1，<*,*>R2，则<*,*>R1R2，所以R1R2是自反的．（7分）14．正确．（3分）因为图G为连通的，且其中每个顶点的度数为偶数．（7分）五．计算题（每小题12分，本题共36分）15．设A={{2},1,2}，B={1,{1,2}}，试计算（1）（AB）；（2）（A∩B）；（3）A×B．16．设G=<V，E>，V={v1，v2，v3，v4，v5}，E={(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)}，试（1）给出G的图形表示；（2）写出其邻接矩阵；（3）求出每个结点的度数；（4）画出其补图的图形．17．设谓词公式，试（1）写出量词的辖域；（2）指出该公式的自由变元和约束变元．15．（1）AB={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分）v1v2v3v4图三v5（3分）（2）邻接矩阵：（6分）（3）v1，v2，v3，v4，v5结点的度数依次为1，2，4，2，1（9分）v1v2v3v4图四v5（12分）17．（1）*量词的辖域为，（2分）z量词的辖域为,（4分）y量词的辖域为．（6分）（2）自由变元为中的y，以及中的z（9分）约束变元为中的*与中的z，以及中的y．（12分）六、证明题（本题共8分）18．试证明集合等式A(BC)=(AB)(AC)．18．证明：设S=A(BC)，T=(AB)(AC)，若*∈S，则*∈A或*∈BC，（1分）即*∈A或*∈B且*∈A或*∈C．（2分）也即*∈AB且*∈AC，（3分）即*∈T，所以ST．（4分）反之，若*∈T，则*∈AB且*∈AC，（5分）即*∈A或*∈B且*∈A或*∈C，（6分）也即*∈A或*∈BC，即*∈S，所以TS．（7分）因此T=S．（8分）2011年1月一、单项选择题（每小题3分，本题共15分）1．D2．B3．C4．A5．B1．若集合A={a，b}，B={a，{a，b}}，则（）．A．ABB．ABC．ABD．AB 2．集合A={*|*为小于10的自然数}，集合A上的关系R={<*，y>|*+y=10且*,yA}，则R的性质为（）．A．自反的B．对称的C．传递且对称的D．反自反且传递的3．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是()．图一A．（a）仅为弱连通的B．（b）仅为弱连通的C．（c）仅为弱连通的D．（d）仅为弱连通的4．设图G的邻接矩阵为则G的边数为()． A．5B．6C．7D．5．下列公式()为永真式．A．PQPQB．(P(QP))(P(PQ))C．(Q(PQ))(Q(PQ))D．(P(PQ))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={<*,y>|*A,yA,*+y<4}，则R的自反闭包为{<1,1>,<2,2>,<1,2>,<2,1>}．9．无向连通图在结点数v与边数e满足e=v-1关系时是树．10．(*)(A(*)→B(*))∨C(*，y)中的自由变元为C(*，y)中的*与y．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“他们去旅游，仅当明天天晴．”翻译成命题公式．12．将语句“今天没有下雪．”翻译成命题公式．11．设P：他们去旅游，Q：明天天晴，（2分）P→Q．（6分）12．设P：今天下雪，（2分）P．（6分）四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．汉密尔顿图一定是欧拉图．图二存在汉密尔顿图不是欧拉图．（5分）反例见图二．（7分）14．下面的推理是否正确，试予以说明．(1)（*）（F（*）→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={<*，y>|*A，yA且*+y<1}，S={<*，y>|*A，yA且*+y3}，试求R，S，RS，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分）RS={<0,0>,<0,1>,<0,2>,<0,3>}（6分）R-1={<0,0>}（8分）S-1=S（10分）r(R)=IA．（12分）16．画一棵带权为1,2,2,3,6的最优二叉树,计算它们的权．14最优二叉树如图四：148866535332322121图四（10分）权为：13+23+23+33+61=30（12分）注:其他正确的最优二叉树参照给分．17．求（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)析取、合取*式（12分）注:其他正确答案参照给分．六、证明题（本题共8分）18．试证明集合等式A(BC)=(AB)(AC)．证明：设S=A∩(B∪C)，T=(A∩B)∪(A∩C)，若*∈S，则*∈A且*∈B∪C，即*∈A且*∈B或*∈A且*∈C，也即*∈A∩B或*∈A∩C，即*∈T，所以ST．（4分）反之，若*∈T，则*∈A∩B或*∈A∩C，即*∈A且*∈B或*∈A且*∈C也即*∈A且*∈B∪C，即*∈S，所以TS．因此T=S．（8分）2010年7月一、单项选择题（每小题3分，本题共15分）1．B2．D3．B4．C5．B1．若集合A={1，{2}，{1，2}}，则下列表述正确的是()．A．2AB．{1}C．1AD．22．已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为()．A．6B．4C．3D．53．设无向图G的邻接矩阵为,则G的边数为()． A．1B．7C．6D．4．设集合A={a}，则A的幂集为()．A．{{a}}B．{a，{a}}C．{，{a}}D．{，a}5．下列公式中()为永真式．A．ABABB．AB(AB)C．ABABD．AB(AB)二、填空题（每小题3分，本题共15分）6．命题公式的真值是假（或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．(*)(A(*)→B(*，z)∨C(y))中的自由变元有z，y．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“今天上课．”翻译成命题公式．设P：今天上课，（2分）则命题公式为：P．（6分）12．将语句“他去操场锻炼，仅当他有时间．”翻译成命题公式．设P：他去操场锻炼，Q：他有时间，（2分）则命题公式为：PQ．（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权最小的生成树及其权值．图一a图一abcd112453（3分）（2）邻接矩阵：图二图二abcd112453（3）最小的生成树如图二中的粗线所示：（10分）权为：1+1+3=5（12分）六、证明题（本题共8分）18．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．证明：设*A，因为R自反，所以*R*，即<*,*>R；又因为S自反，所以*R*，即<*,*>S．（4分）即<*,*>R∩S（6分）故R∩S自反．（8分）2010年1月一、单项选择题（每小题3分，本题共15分）1．A2．C3．B4．B5．D1．若集合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．7 C．8 D．94．图G如图一所示，以下说法正确的是()．A．a是割点B．{b,c}是点割集C．{b,d}是点割集D．{c}是点割集图一5．下列公式成立的为()．A．P∧QP∨QB．PQPQC．QPPD．P∧(P∨Q)Q二、填空题（每小题3分，本题共15分）6．设集合A={2,3,4}，B={1,2,3,4}，R是A到B的二元关系，则R的有序对集合为{<2,2>，<2,3>，<2,4>，<3,3>}，<3,4>，<4,4>}．7．如果R是非空集合A上的等价关系，aA，bA，则可推知R中至少包含<a,a>，<b,b>等元素．8．设G＝<V,E>是有4个结点，8条边的无向连通图，则从G中删去5条边，可以确定图G的一棵生成树．9．设G是具有n个结点m条边k个面的连通平面图，则m等于n+k2．10．设个体域D＝{1,2}，A(*)为“*大于1”，则谓词公式的真值为真（或T，或1）．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“今天考试，明天放假．”翻译成命题公式．设P：今天考试，Q：明天放假．（2分）则命题公式为：P∧Q．（6分）12．将语句“我去旅游，仅当我有时间．”翻译成命题公式．设P：我去旅游，Q：我有时间，（2分）则命题公式为：PQ．（6分）四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．如果图G是无向图，且其结点度数均为偶数，则图G是欧拉图．错误．（3分）当图G不连通时图G不为欧拉图．（7分）14．若偏序集<A，R>的哈斯图如图二所示，则集合A的最大元为a，最小元是f．图二错误．（3分）集合A的最大元与最小元不存在，a是极大元，f是极小元，．（7分）五．计算题（每小题12分，本题共36分）15．设谓词公式，试（1）写出量词的辖域；（2）指出该公式的自由变元和约束变元．（1）*量词的辖域为，（3分）z量词的辖域为,（6分）（2）自由变元为中的y，（9分）约束变元为*与z．（12分）16．设集合A={{1},1,2}，B={1,{1,2}}，试计算（1）（AB）；（2）（A∩B）；（3）A×B．（1）AB={{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={v1，v2，v3，v4}，E={(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)}，试（1）给出G的图形表示；（2）写出其邻接矩阵；（3）求出每个结点的度数；（4）画出其补图的图形．（1）G的图形表示为(如图三)：（3分）图三（2）邻接矩阵：（6分）（3）v1，v2，v3，v4结点的度数依次为1，2，3，2（9分）（4）补图如图四所示：（12分）图四六、证明题（本题共8分）18．设A，B是任意集合，试证明：若AA=BB，则A=B．证明：设*A，则<*，*>AA，（1分）因为AA=BB，故<*，*>BB，则有*B，（3分）所以AB．（5分）设*B，则<*，*>BB，（6分）因为AA=BB，故<*，*>AA，则有*A，所以BA．（7分）故得A=B．（8分）2009年10月一、单项选择题（每小题3分，本题共15分）1．D2．C3．B4．C5．A1．若G是一个汉密尔顿图，则G一定是()．A．平面图B．对偶图C．欧拉图D．连通图 2．集合A={1,2,3,4}上的关系R={<*，y>|*=y且*,yA}，则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（*）：*是人，B（*）：*是工人，则命题“有人是工人”可符号化为（）．A．(*)(A(*)∧B(*))B．(*)(A(*)∧B(*))C．┐(*)(A(*)→B(*))D．┐(*)(A(*)∧┐B(*)) 二、填空题（每小题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>,}，则复合函数gf={<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(*)为“*小于2”，则谓词公式(*)P(*)的真值为假（或F，或0）三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“他是学生．”翻译成命题公式．设P：他是学生，（2分）则命题公式为：P．（6分）12．将语句“如果明天不下雨，我们就去郊游．”翻译成命题公式．设P：明天下雨，Q：我们就去郊游，（2分）则命题公式为：PQ．四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．下面的推理是否正确，试予以说明．(1)（*）F（*）→G（*）前提引入(2)F（y）→G（y）US（1）．错误．（3分）（2）应为F（y）→G（*），换名时，约束变元与自由变元不能混淆．（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={<*，y>|*A，yA且*+y<0}，S={<*，y>|*A，yA且*+y2}，试求R，S，RS，S-1，r(R)．R=,S={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<2,0>}（3分）RS=，（6分）S-1=S，（9分）r(R)=IA={<0,0>,<1,1>,<2,2>,<3,3>}．（12分）17．画一棵带权为1,2,2,3,4的最优二叉树,计算它们的权．1223347512（10分）图三权为13+23+22+32+42=27（12分）六、证明题（本题共8分）18．试证明集合等式A(BC)=(AB)(AC)．证明：设S=A(BC)，T=(AB)(AC)，若*∈S，则*∈A或*∈BC，即*∈A或*∈B且*∈A或*∈C．也即*∈AB且*∈AC，即*∈T，所以ST．（4分）反之，若*∈T，则*∈AB且*∈AC，即*∈A或*∈B且*∈A或*∈C，也即*∈A或*∈BC，即*∈S，所以TS．因此T=S．2009年7月一、单项选择题（每小题3分，本题共15分）1．A2．B3．B4．D5．C1．若集合A={a，b}，B={a，b，{a，b}}，则（）．A．AB，且ABB．AB，但ABC．AB，但ABD．AB，且AB 2．集合A={1,2,3,4,5,6,7,8}上的关系R={<*，y>|*+y=10且*,yA}，则R的性质为（）．A．自反的B．对称的C．传递且对称的D．反自反且传递的 3．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个．A．0B．2C．1D．4．如图一所示，以下说法正确的是()．A．{(a,e)}是割边 B．{(a,e)}是边割集C．{(a,e),(b,c)}是边割集D．{(d,e)}是边割集图一5．设A（*）：*是人，B（*）：*是学生，则命题“不是所有人都是学生”可符号化为（）．A．(*)(A(*)∧B(*))B．┐(*)(A(*)∧B(*))C．┐(*)(A(*)→B(*))D．┐(*)(A(*)∧┐B(*))二、填空题（每小题3分，本题共15分）6．若集合A的元素个数为10，则其幂集的元素个数为1024．7．设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为8．8．若A={1,2}，R={<*,y>|*A,yA,*+y=10}，则R的自反闭包为{<1,1>,<2,2>}．9．结点数v与边数e满足e=v-1关系的无向连通图就是树．10．设个体域D＝{a,b,c}，则谓词公式(*)A(*)消去量词后的等值式为A(a)∧A(b)∧A（c）．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“尽管他接受了这个任务，但他没有完成好．”翻译成命题公式．设P：他接受了这个任务，Q：他完成好了这个任务，（2分）PQ．（6分）12．将语句“今天没有下雨．”翻译成命题公式．设P：今天下雨，（2分）P．（6分）四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．下面的推理是否正确，试予以说明．(1)（*）F（*）→G（*）前提引入(2)F（y）→G（y）US（1）．错误．（3分）（2）应为F（y）→G（*），换名时，约束变元与自由变元不能混淆．（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={<*，y>|*A，yA且*+y<0}，S={<*，y>|*A，yA且*+y3}，试求R，S，RS，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分）RS=，（6分）R-1=，（8分）S-1=S，（10分）r(R)=IA．（12分）17．画一棵带权为1,2,2,3,4的最优二叉树,计算它们的权．1223347512权为13+23+22+32+42=27（12分）六、证明题（本题共8分）18．设G是一个n阶无向简单图，n是大于等于2的奇数．证明G与中的奇数度顶点个数相等(是G的补图)．证明：因为n是奇数，所以n阶完全图每个顶点度数为偶数，（3分）因此，若G中顶点v的度数为奇数，则在中v的度数一定也是奇数，（6分）所以G与中的奇数度顶点个数相等．（8分）2008年7月一、单项选择题（每小题3分，本题共15分）1．B2．B3．A4．C5．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和R2．设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，B={2,4,6}，则集合B的最大元、最小元、上界、下界依次为()．A．8、2、8、2B．无、2、无、2C．6、2、6、2D．8、1、6、13．若集合A的元素个数为10，则其幂集的元素个数为（）．A．1024B．10C．100D．14．设完全图K有n个结点(n≥2)，m条边，当（）时，K中存在欧拉回路．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}，则谓词公式(*)A(*)∧（*）B（*）消去量词后的等值式为(A(a)∧A(b))∧(B（a）∨B（b）)．三、逻辑公式翻译（每小题4分，本题共12分）11．将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公式．设P：所有人今天都去参加活动，Q：明天的会议取消，（1分）PQ．（4分）12．将语句“今天没有人来．”翻译成命题公式．设P：今天有人来，（1分）P．（4分）13．将语句“有人去上课．”翻译成谓词公式．设P(*)：*是人，Q(*)：*去上课，（1分）(*)(P(*)Q(*))．四、判断说明题（每小题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）∨PT15．正确．（3分）对于集合A的任意元素*，均有<*,a>R（或*Ra），所以a是集合A中的最大元．（5分）按照最小元的定义，在集合A中不存在最小元．（7分）五．计算题（每小题12分，本题共36分）16．设集合A={1，2，3，4}，R={<*,y>|*,yA；|*y|=1或*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分）1234（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分）17．求PQR的析取*式，合取*式、主析取*式，主合取*式．P→（R∨Q）┐P∨(R∨Q)┐P∨Q∨R（析取、合取、主合取*式）（9分）(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧R)∨(P∧┐Q∧┐R)∨(P∧┐Q∧R)∨(P∧Q∧┐R)∨(P∧Q∧R)（主析取*式）（12分）18．设图G=<V，E>，V={v1，v2，v3，v4，v5}，E={(v1,v2)，(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}，试画出G的图形表示；写出其邻接矩阵；(3)求出每个结点的度数；v1v2v1v2v3v4v5（1）关系图（3分）（2）邻接矩阵（6分）（3）deg(v1)=2deg(v2)=3deg(v3)=4deg(v4)=3v1v2v3v4v1v2v3v4v5（4）补图（12分）六、证明题（本题共8分）19．试证明（*）（P（*）∧R（*））（*）P（*）∧（*）R（*）．证明：（1）（*）（P（*）∧R（*））P（2）P（a）∧R（a）ES(1)（2分）（3）P（a）T(2)I（4）（*）P（*）EG(3)（4分）（5）R（a）T(2)I（6）（*）R（*）EG(5)（6分）（7）（*）P（*）∧（*）R（*）T(5)(6)I（2分）2008年9月一、单项选择题（每小题3分，本题共15分）1．C2．C3．D4．A5．B1．若集合A＝{a，{a}，{1，2}}，则下列表述正确的是()．A．{a，{a}}AB．{2}AC．{a}AD．A2．设图G＝<V,E>，vV，则下列结论成立的是()．A．deg(v)=2EB．deg(v)=EC．D．3．命题公式（P∨Q）→R的析取*式是()A．（P∨Q）∨RB．（P∧Q）∨RC．（P∨Q）∨RD．（P∧Q）∨R4．如图一所示，以下说法正确的是()．A．e是割点B．{a,e}是点割集C．{b,e}是点割集D．{d}是点割集图一5．下列等价公式成立的为()．A．PQPQB．P(QP)P(PQ)C．Q(PQ)Q(PQ)D．P(PQ)Q二、填空题（每小题3分，本题共15分）6．设集合A={0,1,2,3}，B={2,3,4,5}，R是A到B的二元关系，则R的有序对集合为{<2,2>，<2,3>，<3,2>}，<3,3>．7．设G是连通平面图，v,e,r分别表示G的结点数，边数和面数，则v，e和r满足的关系式v-e+r=2．8．设G＝<V,E>是有6个结点，8条边的连通图，则从G中删去3条边，可以确定图G的一棵生成树．9．无向图G存在欧拉回路，当且仅当G连通且所有结点的度数全为偶数．10．设个体域D＝{1,2}，则谓词公式消去量词后的等值式为A(1)A(2)．三、逻辑公式翻译（每小题4分，本题共12分）11．将语句“如果你去了，则他就不去．”翻译成命题公式．设P：你去，Q：他去，（1分）PQ．（4分）12．将语句“小王去旅游，小李也去旅游．”翻译成命题公式．设P：小王去旅游，Q：小李去旅游，（1分）PQ．（4分）13．将语句“所有人都去工作．”翻译成谓词公式．设P(*)：*是人，Q(*)：*去工作，（1分）(*)(P(*)Q(*))．（4分）四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．14．如果R1和R2是A上的自反关系，则R1∪R2是自反的．正确．（3分）R1和R2是自反的，*A，<*,*>R1，<*,*>R2，则<*,*>R1R2，所以R1∪R2是自反的．（7分）15．如图二所示的图G存在一条欧拉回路．vv1v2v3v5v4dbacefghn图二正确．（3分）因为图G为连通的，且其中每个顶点的度数为偶数．（7分）五．计算题（每小题12分，本题共36分）16．设谓词公式，试（1）写出量词的辖域；（2）指出该公式的自由变元和约束变元．（1）*量词的辖域为，