扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
电大离散数学期末考试试题(有几套带答案)
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
2014年中央电大离散数学(本科)考试试题小抄
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口中央电大离散数学(本科)考试试题_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
中央电大离散数学(本科)考试试题
阅读已结束，如果下载本文需要使用
想免费下载本文？
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢河南电大离散数学期末复习题2(历年考试题)_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
河南电大离散数学期末复习题2(历年考试题)
阅读已结束，如果下载本文需要使用
想免费下载本文？
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢计算机科学与技术专业2012 年 1 月级第二学期离散数学试题一、单项选择题（每小题 3 分，本题共 15 分）1．C 2．C 3．B 4．A 5．D 1．若集合 A 的元素个数为 10，则其幂集的元素个数为（ ） ． A．10 B．100 C．1024 D．1 2．设 A={a, b}，B={1, 2}，R1，R2，R
3 是 A 到 B 的二元关系，且 R1={&a，2&, &a，1&}，R2={&a，1&, &a，2&, &b，1&}，R3={&a，1&, &b，2&}，则（ ）是从 A 到 B 的函数． A．R1 和 R2 B．R2 C．R3 D．R1 和 R3 3．设 A={1, 2, 3, 4, 5, 6, 7, 8}，R 是 A 上的整除关系，B={2, 4, 6}，则集合 B 的最大元、最小元、上界、 下界依次为 ( )． A．8、2、8、2 B．无、2、无、2 C．6、2、6、2 D．8、1、6、1 4．若完全图 G 中有 n 个结点(n≥2)，m 条边，则当（ A．n 为奇数 B．n 为偶数 C．m 为奇数 5．已知图 G 的邻接矩阵为 ）时，图 G 中存在欧拉回路． D．m 为偶数则 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 中删去 变成树． 9．设连通平面图 G 的结点数为 5，边数为 6，则面数为 3 ． 110 ． 设 个 体 域 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，极小元不存在． b ? a ? ? c 图一 ? d错误． （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&} （2）关系图如图二：（3 分）图二 （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) }，试 (1) 画出 G 的图形表示； (2) 写出其邻接矩阵； (3) 求出每个结点的度数； v1 (4) 画出图 G 的补图的图形． ? 16． （1）关系图如图三： v2 ? ? v5v3? 图三?v4 （3 分）（2）邻接矩阵?0 ?1 ? ?1 ? ?0 ?0 ?（3）deg(v1)=2 deg(v2)=2 deg(v3)=2 deg(v4)=2 deg(v5)=2 （4）补图如图四1 1 0 0? 0 0 1 0? ? 0 0 0 1? ? 1 0 0 1? 0 1 1 0? ?（6 分）（9 分） v1 v2 ? v3 ? 图四 ? v4 （12 分） ? ? v517．求 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)∨(┐P∧Q∧R)∨ (P∧R∧Q) （主析取范式） 说明：此题解法步骤多样，若能按正确步骤求得结果，均可给分．（12 分）六、证明题（本题共 8 分）18．设连通无向图 G 有 14 条边，3 个 4 度顶点，4 个 3 度顶点，其它顶点的度数均小于 3，试说明 G 中可能有的顶点数． 证明： 可利用数列可图化及握手定理解答 顶点度数和为2?14=28， （2分） 28-（3?4+4?3）=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}?A B．{1，2}?A C．1?A D．2 ? A 2．设 G 为无向图，则下列结论成立的是 ( ) ． A．无向图 G 的结点的度数等于边数的两倍． B．无向图 G 的结点的度数等于边数． C．无向图 G 的结点的度数之和等于边数的两倍． D．无向图 G 的结点的度数之和等于边数． 3．图 G 如图一所示，以下说法正确的是( ) ． a? A．{(a，b)}是边割集 B．{ a，c}是点割集 C．{d}是点割集 b? D．{ (c，d)}是边割集 c ??e? d?f图一 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)) 6．命题公式 P ? ?P 的真值是 D．( ? x)( A(x)∧B(x)) 真（或 T，或 1） ． ． ， 二、填空题（每小题 3 分，本题共 15 分） 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．(?x)(P(x)→R(y)∨S(z)) 中的约束变元有 x ． 三、逻辑公式翻译（每小题 6 分，本题共 12 分） 11．将语句“雪是黑色的． ”翻译成命题公式． 设 P：雪是黑色的， （2 分） 则命题公式为：P． （6 分） 12．将语句“如果明天下雨，则我们就在室内上体育课． ”翻译成命题公式． 设 P：如果明天下雨， Q：我们在室内上体育课， 则命题公式为：P ?Q． 四、判断说明题（每小题 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 个面． 正确． 因 G 是一个连通平面图，满足欧拉定理，有 v-e+r=2， 所以 r=2-（v-e）=2-（5-9）=6 五．计算题（每小题 12 分，本题共 36 分） 15．试求出 P→（R∧Q）的合取范式． P→（R∧Q）?┐P∨（R∧Q） ? (┐P∨R) ∧（┐P∨Q） （合取范式） 16．设 A={{1}, {1, 2}，1}，B={ 1, 2, {2}}，试计算 （1）（A∩B） （2）（A∪B） （3）（A∩B）?A． （1） （A∩B）={1} （2） （A∪B）={1, 2, {1}, {2}, {1, 2}} （3） （A∩B）?A =? 17．试画一棵带权为 2, 3, 3, 4, 5,的最优二叉树,并计算该最优二叉树的权． 最优二叉树如图二所示． 17 ? 10 ? 5 ? ? 2 ? 3 ? ? 5 3 图二 ?7 ? 4 （10 分） （3 分） （7 分） （2 分） （6 分）（6 分） （12 分）（4 分） （8 分） （12 分）权为 2?3+3?3+3?2+4?2+5?2=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&?S即 &y, x&?R 且&y, x&?S 也即&y, x&? R∩S，故 R∩S 是对称的．（6 分） （8 分）中央广播电视大学
学年度第一学期“开放本科”期末考试 离散数学（本）试题2011 年 1 月 一、单项选择题（每小题 3 分，本题共 15 分）1．A 2．D 3．B 4．D 5．C1．若集合 A＝{ a，{1}}，则下列表述正确的是( )． A．{1}?A B．{1}?A C．{a}?A D．??A 2．设图 G＝&V, E&，v?V，则下列结论成立的是 ( )． A．deg(v)=2?E? B．deg(v)=?E? C．? deg(v) ? Ev?VD．? deg(v) ? 2 Ev?V3．如图一所示，以下说法正确的是 ( )． A．(e, c)是割边 B．(d, e)是割边 C．(b, a)是割边 D．(b, c)是割边 e ? a? b ? 图一 4．命题公式（P∨Q）的合取范式是 ( ) ． A．P B． （P∧Q） C． （P∨P） D． （P∨Q） 5．下列等价公式成立的为( )． A．P?Q?P?Q B．?Q?P?P?Q C．?P?P ??Q?Q D．?P?P ?Q 二、填空题（每小题 3 分，本题共 15 分） 6．设集合 A={0, 1, 2}，B={1,2, 3, 4,}，R 是 A 到 B 的二元关系， ? c ?dR ? {? x, y ? x ? A且y ? B且x, y ? 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}，则谓词公式 ?xA(x) 消去量词后的等值式为 A(1) ?A(2) ．三、逻辑公式翻译（每小题 6 分，本题共 12 分）11．将语句“如果小李学习努力，那么他就会取得好成绩． ”翻译成命题公式． 12．将语句“小张学习努力，小王取得好成绩． ”翻译成命题公式． 11．设 P：小李学习努力，Q：小李会取得好成绩， P?Q． 12．设 P：小张学习努力，Q：小王取得好成绩， P?Q． （2 分） （6 分） （2 分） （6 分）四、判断说明题（每小题 7 分，本题共 14 分） 判断下列各题正误，并说明理由．13．如果 R1 和 R2 是 A 上的自反关系，则 R1?R2 是自反的． 14．如图二所示的图中存在一条欧拉回路． ? ? ? 图二 13．正确． R1 和 R2 是自反的，?x ?A，&x, x& ? R1，&x, x& ?R2， 则&x, x& ? R1?R2， 所以 R1?R2 是自反的． 14．正确． 因为图 G 为连通的，且其中每个顶点的度数为偶数． （3 分） ? ?（7 分） （3 分） （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={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)}，试 （1）给出 G 的图形表示； （2）写出其邻接矩阵； （3）求出每个结点的度数； （4）画出其补图的图形． 17．设谓词公式 ?x( A( x, y) ? ?zB( x, y, z )) ? ?yC( y, z ) ，试 （1）写出量词的辖域； （2）指出该公式的自由变元和约束变元． 15．（1）A?B ={2,{2}} （2）A∩B ={1} （3）A× B={&{2},1&，&{2},{1,2}&，&1,1&，&1, {1,2}&， &2,1&，&2, {1,2}&} 16． （1）G 的图形表示如图三： v1 ? v2 ? ? 图三 ? ? v 5 v3 v4（4 分） （8 分） （12 分）（3 分） （2）邻接矩阵：?0 ?0 ? ?1 ? ?0 ?0 ?0 1 0 0? 0 1 1 0? ? 1 0 1 1? ? 1 1 0 0? 0 1 0 0? ?（6 分）（3）v1，v2，v3，v4，v5 结点的度数依次为 1，2，4，2，1（9 分）（4）补图如图四： v2 ? v3 ?v1? ? ?v 4 v5图四 17． （1）?x 量词的辖域为 ( A( x, y) ? ?zB( x, y, z )) ， ?z 量词的辖域为 B( x, y, z ) , ?y 量词的辖域为 C ( y, z ) ． （2）自由变元为 ( A( x, y) ? ?zB( x, y, z )) 中的 y，以及 C ( y, z ) 中的 z（12 分） （2 分） （4 分） （6 分） （9 分）约 束 变 元 为 ( A( x, y) ? ?zB( x, y, z )) 中 的 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 月一、单项选择题（每小题 3 分，本题共 15 分）1．D 1．若集合 A={a，b}，B={ a，{ a，b }}，则（ ） ． A．A?B B．A?B C．A?B D．A?B2．B3．C4．A5．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）仅为弱连通的 C． （c）仅为弱连通的 4．设图 G 的邻接矩阵为 ?0 ?1 ? ?1 ? ?0 ?0 ? 则 G 的边数为( A．5 5．下列公式 ( A．?P??Q?P?Q C．(Q?(P?Q)) ?(?Q?(P?Q)) )． B．6 )为永真式． B．(P?(?Q?P))?(?P?(P?Q)) D．(?P?(P?Q)) ?Q C．7 D．8 B． （b）仅为弱连通的 D． （d）仅为弱连通的1 1 0 0? 0 0 1 1? ? 0 0 0 0? ? 1 0 0 1? 1 0 1 0? ?二、填空题（每小题 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 的自反闭包为 9．无向连通图在结点数 v 与边数 e 满足 10．(?x)(A(x)→B(x))∨C(x，y)中的自由变元为 e=v-1 {&1,1&,&2,2&,&1,2&,&2,1&} ． 关系时是树． ．C(x，y )中的 x 与 y三、逻辑公式翻译（每小题 6 分，本题共 12 分）11．将语句“他们去旅游，仅当明天天晴． ”翻译成命题公式． 12．将语句“今天没有下雪． ”翻译成命题公式． 11．设 P：他们去旅游，Q：明天天晴， （2 分）P→Q． 12．设 P：今天下雪， ? P．（6 分） （2 分） （6 分）四、判断说明题（每小题 7 分，本题共 14 分） 判断下列各题正误，并说明理由．13．汉密尔顿图一定是欧拉图． 错误． 存在汉密尔顿图不是欧拉图． 反例见图二． ? （3 分） （5 分） ? ? 图二 14．下面的推理是否正确，试予以说明． (1) （?x）（F（x）→G（y）） 前提引入 (2) F（y）→G（y） ES（1） ． 1、错误． （2）应为 F（a）→G（y） ，换名时，约束变元与自由变元不能混淆． （3 分） （7 分） （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&} S={&0,0&,&0,1&,&0,2&,&0,3&,&1,0&,&1,1&,&1,2&,&2,0&,&2,1&,&3,0&} R?S={&0,0&,&0,1&,&0,2&,&0,3&} R-1={&0,0&} S-1= S r(R)=IA． 16．画一棵带权为 1, 2, 2, 3, 6 的最优二叉树,计算它们的权． 最优二叉树如图四： 14 8 ? 3 ? ? 1 ? 2 ? 2 ?6 ? 5 ? 3 （10 分） （12 分） （2 分） （4 分） （6 分） （8 分） （10 分） （12 分）图四 权为：1?3+2?3+2?3+3?3+6?1=30 注: 其他正确的最优二叉树参照给分． 17．求（P∨Q）→（R∨Q）的析取范式，合取范式． （P∨Q）→（R∨Q）??（P∨Q）∨（R∨Q） ?(?P∧?Q)∨（R∨Q） ?(?P∨R∨Q)∧(?Q∨R∨Q) ?(?P∨R∨Q) 析取、合取范式 注: 其他正确答案参照给分．（4 分）（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 1．若集合 A={1，{2}，{1，2}}，则下列表述正确的是( A．2?A B．{1}?A 2．D )． 3．B 4．C 5．B(C．1?A D．2 ? A 2．已知一棵无向树 T 中有 8 个顶点，4 度、3 度、2 度的分支点各一个，T 的树叶数为 )． A．6 B．4 3．设无向图 G 的邻接矩阵为 ?0 1 ?1 0 ? ?1 0 ? ?1 1 ?1 1 ? C．31 1 1? 0 1 1? ?, 0 0 0? ? 0 0 1? 0 1 0? ?D．5则 G 的边数为()． C．6 )． B．{a，{a}} D．{?，a} B．?A??B ? ?(A?B) D．?A??B ? ?(A?B) 假（或 F，或 0） ． D．14A．1 B．7 4．设集合 A={a}，则 A 的幂集为( A．{{a}} C．{?，{a}} 5．下列公式中 ( C．?A??B ? A?B 6．命题公式 P ? ?P 的真值是 )为永真式． A．?A??B ? ?A??B二、填空题（每小题 3 分，本题共 15 分）7．若无向树 T 有 5 个结点，则 T 的边数为 4 8．设正则 m 叉树的树叶数为 t，分支数为 i，则(m-1)i=． t-1 ． &2, 1& ，9．设集合 A={1，2}上的关系 R＝{&1, 1&,&1, 2&}，则在 R 中仅需加一个元素 就可使新得到的关系为对称的． 10．(?x)(A(x)→B(x，z)∨C(y))中的自由变元有 z，y ． 三、逻辑公式翻译（每小题 6 分，本题共 12 分） 11．将语句“今天上课．”翻译成命题公式． 设 P：今天上课， 则命题公式为：P． 12．将语句“他去操场锻炼，仅当他有时间．”翻译成命题公式． 设 P：他去操场锻炼，Q：他有时间， 则命题公式为：P ?Q． 四、判断说明题（每小题 7 分，本题共 14 分） 判断下列各题正误，并说明理由．（2 分） （6 分） （2 分） （6 分）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 （1）A∩B={1} （2）A∪B={1, 2, {1}, {2}} （3） A?（A∩B）={{1}, 2} （3）A ?（A∩B）． （4 分） （8 分） （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? 1 ? b 2 3 4 5 1 图一 ? c ?d（3 分） （2）邻接矩阵：?0 ?1 ? ?1 ? ?11 0 1 11 1 0 11? 1? ? 1? ? 0?（6 分） a? 1 ? b 2 3 4 5 1 图二 ? c ?d（3）最小的生成树如图二中的粗线所示：权为：1+1+3=5（10 分） （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 1．若集合 A＝{ a，{a}}，则下列表述正确的是( )． A．{a}?A B．{{{a}}}?A C．{a，{a}}?A D．??A 2．命题公式（P∨Q）的合取范式是 ( ) A． （P∧Q） B． （P∧Q）∨（P∨Q） C． （P∨Q） D．?（?P∧?Q） 3．无向树 T 有 8 个结点，则 T 的边数为( )． A．6 B．7 C．8 4．图 G 如图一所示，以下说法正确的是 ( )． A．a 是割点 B．{b, c}是点割集 C．{b, d}是点割集 D．{c}是点割集 3．B 4．B 5．DD．9图一 5．下列公式成立的为( A．?P∧?Q ? P∨Q)． B．P??Q ? ?P?QC．Q?P ? PD．?P∧(P∨Q)?Q二、填空题（每小题 3 分，本题共 15 分） 6．设集合 A={2, 3, 4}，B={1, 2, 3, 4}，R 是 A 到 B 的二元关系，R ? {? x, y ? x ? A且y ? B且x ? y}则 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：明天放假． 则命题公式为：P∧Q． 12．将语句“我去旅游，仅当我有时间． ”翻译成命题公式． 设 P：我去旅游，Q：我有时间， 则命题公式为：P?Q． 四、判断说明题（每小题 7 分，本题共 14 分） 判断下列各题正误，并说明理由． 13．如果图 G 是无向图，且其结点度数均为偶数，则图 G 是欧拉图． 错误． （3 分） 当图 G 不连通时图 G 不为欧拉图． （7 分） 14．若偏序集&A，R&的哈斯图如图二所示，则集合 A 的最大元为 a，最小元是 f． （2 分） （6 分）（2 分） （6 分）图二 错误． 集合 A 的最大元与最小元不存在， a 是极大元，f 是极小元， ． 五．计算题（每小题 12 分，本题共 36 分） 15．设谓词公式 (?x)( A( x, y) ? (?z ) B( y, x, z )) ，试 （1）写出量词的辖域； （2）指出该公式的自由变元和约束变元． （3 分） （7 分）（1）?x 量词的辖域为 ( A( x, y) ? (?z ) B( y, x, z )) ， ?z 量词的辖域为 B( y, x, z ) , （2）自由变元为 ( A( x, y) ? (?z ) B( y, x, z )) 中的 y，（3 分） （6 分） （9 分）约束变元为 x 与 z．16．设集合 A={{1},1,2}，B={1,{1,2}}，试计算（12 分）（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={ v1，v2，v3，v4 }，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4) }，试 （1）给出 G 的图形表示； （2）写出其邻接矩阵； （3）求出每个结点的度数； （4）画出其补图的图形． （1）G 的图形表示为(如图三)：（3 分） 图三 （2）邻接矩阵：?0 ?0 ? ?1 ? ?0 ? ?0 1 0 0 1 1 1 0 1 1 1 0? ? ? ? ? ? ? ?（6 分）（3）v1，v2，v3，v4 结点的度数依次为 1，2，3，2 （4）补图如图四所示：（9 分）（12 分） 图四 六、证明题（本题共 8 分） 18．设 A，B 是任意集合，试证明：若 A?A=B?B，则 A=B． 证明：设 x?A，则&x，x&?A?A， 因为 A?A=B?B，故&x，x&?B?B，则有 x?B，（1 分） （3 分）所以 A?B． 设 x?B，则&x，x&?B?B， 因为 A?A=B?B，故&x，x&?A?A，则有 x?A，所以 B?A． 故得 A=B． 2009 年 10 月 一、单项选择题（每小题 3 分，本题共 15 分）1．D 1．若 G 是一个汉密尔顿图，则 G 一定是( A．平面图 C．欧拉图 )． 2．C 3．B（5 分） （6 分） （7 分） （8 分）4．C5．AB．对偶图 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） 是人，B（x） 是工人，则命题“有人是工人”可符号化为（ ：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&,}，则复合函 {&1, 2&, &2, 3&, &3, 2&,} 数 g?f = ． 8． G 是一个图， 设 结点集合为 V， 边集合为 E， G 的结点度数之和为 则 9．无向连通图 G 的结点数为 v，边数为 e，则 G 当 v 与 e 满足 2|E| “边数的两倍” （或 ） e=v-1 关系时是树． ． ．10． 设个体域 D＝{1, 2, 3}，P(x)为 小于 2”则谓词公式(?x)P(x) 的真值为 假 “x ， （或 F， 0） 或 三、逻辑公式翻译（每小题 6 分，本题共 12 分） 11．将语句“他是学生． ”翻译成命题公式． 设 P：他是学生， 则命题公式为： P． （2 分） （6 分）12．将语句“如果明天不下雨，我们就去郊游． ”翻译成命题公式． 设 P：明天下雨，Q：我们就去郊游， 则命题公式为：? P? Q． 四、判断说明题（每小题 7 分，本题共 14 分） （2 分）判断下列各题正误，并说明理由． 13．下面的推理是否正确，试予以说明．(1) （?x）F（x）→G（x） (2) F（y）→G（y） 前提引入 US（1） ． （3 分） （7 分）错误． （2）应为 F（y）→G（x） ，换名时，约束变元与自由变元不能混淆． 14．如图二所示的图 G 存在一条欧拉回路．图二 错误． 因为图 G 为中包含度数为奇数的结点． 五．计算题（每小题 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 分） -1 S = S， （9 分） r(R)=IA={&0,0&,&1,1&,&2,2&,&3,3&}． （12 分） 17．画一棵带权为 1, 2, 2, 3, 4 的最优二叉树,计算它们的权． 最优二叉树如图三所示 12 ? 7 ?5 ? 3 ? ? 1 ? 2 图三 ? ? 4 2 ? 3 （10 分） （3 分） （7 分）权为 1?3+2?3+2?2+3?2+4?2=27（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 1．若集合 A={a，b}，B={ a，b，{ a，b }}，则（ ） ． A．A?B，且 A?B B．A?B，但 A?B C．A?B，但 A?B D．A?B，且 A?B 3．B 4．D 5．C2．集合 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．3 4．如图一所示，以下说法正确的是 ( ) ． A．{(a, e)}是割边 B．{(a, e)}是边割集 C．{(a, e) ,(b, c)}是边割集 D．{(d, e)}是边割集 ）个．） ．图一 5．设 A（x） 是人，B（x） 是学生，则命题“不是所有人都是学生”可符号化为（ ：x ：x ? x)(A(x)∧B(x)) A．( 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 的自反闭包为 9．结点数 v 与边数 e 满足 e=v-1 ． ． {&1,1&,&2,2&}） ．．关系的无向连通图就是树． A (a) ∧A (b)∧A （c） ．10． 设个体域 D＝{a, b, c}， 则谓词公式(?x)A(x)消去量词后的等值式为三、逻辑公式翻译（每小题 6 分，本题共 12 分）11．将语句“尽管他接受了这个任务，但他没有完成好． ”翻译成命题公式． 设 P：他接受了这个任务，Q：他完成好了这个任务， （2 分）P?? Q． 12．将语句“今天没有下雨． ”翻译成命题公式． 设 P：今天下雨， ? P．（6 分） （2 分） （6 分）四、判断说明题（每小题 7 分，本题共 14 分） 判断下列各题正误，并说明理由． 13．下面的推理是否正确，试予以说明．(1) （?x）F（x）→G（x） (2) F（y）→G（y） 前提引入 US（1） ． （3 分） （7 分）错误． （2）应为 F（y）→G（x） ，换名时，约束变元与自由变元不能混淆．14．若偏序集&A，R&的哈斯图如图二所示，则集合 A 的最大元为 a，最小元不存在．图二 错误． 集合 A 的最大元不存在，a 是极大元． （3 分） （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 分） -1 S = S， （10 分） r(R)=IA． （12 分） 17．画一棵带权为 1, 2, 2, 3, 4 的最优二叉树,计算它们的权． 12 ? 7 ? 3 ? ? 1 ? 2 ? ? 4 2 ?5 ? 3权为 1?3+2?3+2?2+3?2+4?2=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．D 1．设 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 和 R2 B．R2 C．R3 D．R1 和 R3 2．设 A={1, 2, 3, 4, 5, 6, 7, 8}，R 是 A 上的整除关系，B={2, 4, 6}，则集合 B 的最大元、最小元、上界、 下界依次为 ( )． A．8、2、8、2 B．无、2、无、2 C．6、2、6、2 D．8、1、6、1 3．若集合 A 的元素个数为 10，则其幂集的元素个数为（ A．1024 B．10 C．100 ） ． D．14．设完全图 K n 有 n 个结点(n≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． 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 中自反关系有 8．设图 G 是有 6 个结点的连通图，结点的总度数为 18，则可从 G 中删去 4 变成树． 9．设连通平面图 G 的结点数为 5，边数为 6，则面数为 3 ． 2 ． 个． 条边后使之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：今天有人来， ? P． 13．将语句“有人去上课． 翻译成谓词公式． ” 设 P(x)：x 是人，Q(x)：x 去上课， (?x)(P(x) ?Q(x))． （1 分） （4 分） （1 分）四、判断说明题（每小题 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?T 15．正确． （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&} （2）关系图为 2 4（3 分）?1 ??3?（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．求 P?Q?R 的析取范式，合取范式、主析取范式，主合取范式． 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) }，试 (3) 画出 G 的图形表示； (4) 写出其邻接矩阵； (3) 求出每个结点的度数； (4) 画出图 G 的补图的图形． （1）关系图 v1?v2? ? ?? v5v3 （2）邻接矩阵v4（3 分）?0 ?1 ? ?1 ? ?0 ?0 ?（3）deg(v1)=2 deg(v2)=3 deg(v3)=4 deg(v4)=3 deg(v5)=2 （4）补图 v1?1 1 0 0? 0 1 1 0? ? 1 0 1 1? ? 1 1 0 1? 0 1 1 0? ?（6 分）（9 分） v ? 5v2? ? ?v3v4（12 分）六、证明题（本题共 8 分）19．试证明（?x） （P（x）∧R（x） ）? （?x）P（x）∧（?x）R（x） ． 证明： （1） （?x） （P（x）∧R（x） ） P （2）P（a）∧R（a） ES(1) （2 分） （3）P（a） T(2)I （4） （?x）P（x） EG(3) （4 分） （5）R（a） T(2)I （6） （?x）R（x） EG(5) （6 分） （7） （?x）P（x）∧（?x）R（x） T(5)(6)I （2 分） 2008 年 9 月 一、单项选择题（每小题 3 分，本题共 15 分）1．C 2．C 3．D 1．若集合 A＝{ a，{a}，{1，2}}，则下列表述正确的是( )． A．{a，{a}}?A B．{2}?A C．{a}?A D．??A 2．设图 G＝&V, E&，v?V，则下列结论成立的是 ( ) ． A．deg(v)=2?E? B． deg(v)=?E? C． 4．A 5．B?deg(v) ? 2 Ev?VD．?deg(v) ? Ev?V3．命题公式（P∨Q）→R 的析取范式是 ( ) A．?（P∨Q）∨R B． （P∧Q）∨R C． （P∨Q）∨R D． （?P∧?Q）∨R 4．如图一所示，以下说法正确的是 ( )． A．e 是割点 B．{a, e}是点割集 C．{b, e}是点割集 D．{d}是点割集图一 5．下列等价公式成立的为( A．?P??Q?P?Q C．Q?(P?Q) ??Q?(P?Q))． B．P?(?Q?P) ??P?(P?Q) D．?P?(P?Q) ?Q二、填空题（每小题 3 分，本题共 15 分） 6．设集合 A={0, 1, 2, 3}，B={2, 3, 4, 5}，R 是 A 到 B 的二元关系，R ? {? x, y ? x ? A且y ? B且x, y ? 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}，则谓词公式 ?xA(x) 消去量词后的等值式为 A(1)?A(2) ．三、逻辑公式翻译（每小题 4 分，本题共 12 分）11．将语句“如果你去了，那么他就不去． ”翻译成命题公式． 设 P：你去，Q：他去， P??Q． 12．将语句“小王去旅游，小李也去旅游． ”翻译成命题公式． 设 P：小王去旅游，Q：小李去旅游， P?Q． 13．将语句“所有人都去工作． ”翻译成谓词公式． 设 P(x)：x 是人，Q(x)：x 去工作， (?x)(P(x)?Q(x))． （1 分） （4 分） （1 分） （4 分） （1 分） （4 分）四、判断说明题（每小题 7 分，本题共 14 分） 判断下列各题正误，并说明理由．14．如果 R1 和 R2 是 A 上的自反关系，则 R1∪R2 是自反的． 正确． R1 和 R2 是自反的，?x ?A，&x, x& ? R1，&x, x& ?R2， 则&x, x& ? R1?R2， 所以 R1∪R2 是自反的． 15．如图二所示的图 G 存在一条欧拉回路． v5 e v1 a v2 f h b 图二 正确． 因为图 G 为连通的，且其中每个顶点的度数为偶数． （3 分） （7 分） g n v3 c d v4 （3 分）（7 分）五．计算题（每小题 12 分，本题共 36 分）16．设谓词公式 ?x( P( x, y) ? ?zQ( y, x, z )) ? ?yR( y, z ) ? F ( y) ，试 （1）写出量词的辖域； （2）指出该公式的自由变元和约束变元．（1）?x 量词的辖域为 ( P( x, y) ? ?zQ( y, x, z )) ， ?z 量词的辖域为 Q( y, x, z ) , ?y 量词的辖域为 R ( y, z ) ．（2 分） （4 分） （6 分） （9 分）（2）自由变元为 ( P( x, y) ? ?zQ( y, x, z )) 与 F ( y ) 中的 y，以及 R ( y, z ) 中的 z 约束变元为 x 与 Q( y, x, z ) 中的 z，以及 R ( y, z ) 中的 y． 17．设 A={{1},{2},1,2}，B={1,2,{1,2}}，试计算（12 分）（1）（A?B）； （2）（A∩B）； （3）A×B． （1）A?B ={{1},{2}} （4 分） （2）A∩B ={1,2} （8 分） （3）A× B={&{1},1&，&{1},2&，&{1},{1,2}&，&{2},1&，&{2},2&， &{2},{1,2}&，&1,1&，&1,2&，&1, {1,2}&，&2,1&，&2,2&,&2, {1,2}&} （12 分） 18．设 G=&V，E&，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }， 试 （1）给出 G 的图形表示； （3）求出每个结点的度数； （1）G 的图形表示为： （2）写出其邻接矩阵； （4）画出其补图的图形．（3 分） （2）邻接矩阵：?0 ?0 ? ?1 ? ?0 ?0 ?0 1 0 0? 0 1 1 0? ? 1 0 1 1? ? 1 1 0 1? 0 1 1 0? ?（6 分）（3）v1，v2，v3，v4，v5 结点的度数依次为 1，2，4，3，2 （4）补图如下：（9 分）（12 分）六、证明题（本题共 8 分）19．试证明集合等式 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 年 1 月 一、单项选择题（每小题 3 分，本题共 15 分）1．A 2．D 3．B )． 4．A 5．C1．若集合 A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( A．A?B，且 A?B B．B?A，且 A?BC．A?B，且 A?B D．A?B，且 A?B 2．设有向图（a）（b）（c）与（d）如图一所示，则下列结论成立的是 ( 、 、)．图一 A． （a）是强连通的 C． （c）是强连通的 3．设图 G 的邻接矩阵为 ?0 ?1 ? ?1 ? ?0 ?0 ? 则 G 的边数为( )． C．4 D．3 )． B．G 连通且结点数比边数少 1 D．G 中没有回路． B．(Q?(P?Q)) ?(?Q?(P?Q)) B． （b）是强连通的 D． （d）是强连通的1 1 0 0? 0 0 1 1? ? 0 0 0 0? ? 1 0 0 1? 1 0 1 0? ?A．6 B．5 4．无向简单图 G 是棵树，当且仅当( A．G 连通且边数比结点数少 1 C．G 的边数比结点数少 1 5．下列公式 ( A．?P??Q?P?Q )为重言式．C．(P?(?Q?P))?(?P?(P?Q)) 6．命题公式 P ? (Q ? P) 的真值是D．(?P?(P?Q)) ?Q T （或 1） ． ． ，则该序列集合构 5 ．二、填空题（每小题 3 分，本题共 15 分） 7．若图 G=&V, E&中具有一条汉密尔顿回路，则对于结点集 V 的每个非空子集 S，在 G 中删除 S 中的 所有结点得到的连通分支数为 W，则 S 中结点数|S|与 W 满足的关系式为 8．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素 0 成前缀码． W?|S|9． 已知一棵无向树 T 中有 8 个结点， 度， 度， 度的分支点各一个， 的树叶数为 4 3 2 T 10．(?x)(P(x)→Q(x)∨R(x，y))中的自由变元为 R(x，y )中的 y ．三、逻辑公式翻译（每小题 4 分，本题共 12 分）11．将语句“他不去学校． ”翻译成命题公式． 设 P：他去学校， ? P． 12．将语句“他去旅游，仅当他有时间． ”翻译成命题公式． 设 P：他去旅游，Q：他有时间， P ?Q． 13．将语句“所有的人都学习努力． ”翻译成命题公式． 设 P(x)：x 是人，Q(x)：x 学习努力， （?x）(P(x)?Q(x))． （1 分） （4 分） （1 分） （4 分） （1 分） （3 分）四、判断说明题（每小题 7 分，本题共 14 分） 判断下列各题正误，并说明理由．14．设 N、R 分别为自然数集与实数集，f：N→R，f (x)=x+6，则 f 是单射． 正确． （3 分） 设 x1，x2 为自然数且 x1?x2，则有 f(x1)= x1+6? x2+6= f(x2)，故 f 为单射． （7 分） 15．设 G 是一个有 6 个结点 14 条边的连通图，则 G 为平面图． 错误． （3 分） 不满足“设 G 是一个有 v 个结点 e 条边的连通简单平面图，若 v≥3，则 e≤3v-6． ”五．计算题（每小题 12 分，本题共 36 分）16．试求出（P∨Q）→R 的析取范式，合取范式，主合取范式． （P∨Q）→R?┐(P∨Q)∨R? (┐P∧┐Q)∨R（析取范式） （3 分） ? (┐P∨R)∧ (┐Q∨R)（合取范式） （6 分） ? ((┐P∨R)∨(Q∧┐Q))∧ ((┐Q∨R)∨(P∧┐P)) ? (┐P∨R∨Q)∧(┐P∨R∨┐Q)∧ (┐Q∨R∨P) ∧(┐Q∨R∨┐P) ? (┐P∨Q∨R)∧(┐P∨┐Q∨R)∧ (P∨┐Q∨R) （主合取范式） （12 分） 17．设 A={{a, b}, 1, 2}，B={ a, b, {1}, 1}，试计算 （1）（A?B） （2）（A∪B） （1）（A?B）={{a, b}, 2} （3）（A∪B）?（A∩B）．（4 分）（2）（A∪B）={{a, b}, 1, 2, a, b, {1}} （8 分） （3）（A∪B）?（A∩B）={{a, b}, 2, a, b, {1}} （12 分） 18．图 G=&V, E&，其中 V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，对 应边的权值依次为 2、1、2、3、6、1、4 及 5，试 （1）画出 G 的图形； （2）写出 G 的邻接矩阵； （3）求出 G 权最小的生成树及其权值．（1）G 的图形表示为：（3 分） （2）邻接矩阵：?0 ?1 ? ?1 ? ?0 ?1 ?1 1 0 1? 0 0 1 1? ? 0 0 1 1? ? 1 1 0 1? 1 1 1 0? ?（6 分）（3）粗线表示最小的生成树，（10 分） 权为 7： （12 分）六、证明题（本题共 8 分）19．试证明集合等式 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
电大历年离散数学试题汇总―汇集和整理大量word文档,专业文献,应用文书,考试资料,教学教材,办公文档,教程攻略,文档搜索下载下载,拥有海量中文文档库,关注高价值的实用信息,我们一直在努力,争取提供更多下载资源。}