离散
说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。
一．填空 R是集合X上的关系,若 ,则称R是X上的等价关系。 R是集合X上的二元关系， 则关系R-1={ | }。 T是一连通图，若T满足 ，则T构成树。 G是一个图，若G可以 ,则称G为二部图。 已知谓词公式 x F(x,y)yH(x,y), 则 是自由变元。 已知谓词公式 xF(x,y)yG(x,y,z), 则 是约束变元。 图G存在悬挂顶点，则至少删去 条边，图变成两个连通分支。 T是一棵树，则T的树叶最少有 片。 G是一个连通图，若G有一个 ,则G为欧拉图。 图G存在悬挂顶点，则图G的边连通度λ（G）为 。 11．设p:小王走路,q:小王听音乐,在命题逻辑中，命题“小王边走路边听音乐”的符号化形式为___________________。 12. 设F(x)：x是人，H(x,y)：x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为_________________。 13. 命题公式r （ pq）的成真赋值为 _________________，对应的极小项为 ,成假赋值为 对应的极大项为 , 。 14．T是一棵具有n个顶点m条边的树，则n与m的关系是 。 15．G是一个图，若G含有与 的子图，则G一定是非平面图。 二．用一阶逻辑公式表示下列命题 1．集合AB 2．集合A = B 3．集合X = 4．集合A上的二元关系R是自反的 5．集合A上的二元关系R是反自反的 6．集合A上的二元关系R是对称的 7．集合A上的二元关系R是反对称的 8．集合A上的二元关系R是传递的 三．按要求完成下列各题 A={x，y，z}，R={,,,}，S={,,,}，求R◦S、S◦R及S的传递闭包t（R）。 已知集合E={1,2,{1,2}},S={1, {2}}，求ES, ES, (E－S)(S－E) 。 求命题公式（pqr）的主析取范式和主合取范式。 A={1，2，{2}}，求A×A，P（A）。 画一棵带权为2，2，3，3，4，5，8的最优二元树T，并计算它的权W（T）。 （1）在一棵有2个2度顶点，4个3度顶点，其余顶点都是树叶的无向树中，应该有几片树叶？（2）画出两棵非同构的满足（1）中顶点度数的无向树T1和T2。 一棵树有5片树叶，3个2度顶点，其余的顶点均为3度顶点，问T有几个顶点？ A={1，2,3,5,7,14,15,35},R是A上的整除关系:Rx|y(x整除y)，画出R的哈斯图，设 B={2,5,7,14,35}，求B关于R的极大元、极小元和最大元、最小元。 求出下列图的所有点割集和边割集。 10．已知一个有向图G=, 其中 V={v1,v2,v3 }， E={,,,,}， 求D的邻接矩阵A；（2）求顶点v1的入度、出度及次数（3）将G看成无向图，写出关联矩阵。 11．用二元树表示下面的表达式 ((x－2y)*3z－7x)÷(4z-2y)2 12．求下列图的最小生成树 四．证明下列命题 (14分) A，B，C是任意集合，证明(A-B)-C=(A-C)-(B-C) A，B，C是任意集合，证明若A⊕B= A⊕C，则B=C A，B是集合，若P(A)∩P(B)=P(A∩B)，其中P(A)表示集合A的幂集。 p，q，r是任意命题，证明p→(q∨r) (p∧┑q) →r p，q，r是任意命题，证明(p→q) ∧ (q→r) p→r 前提：(p∧q) → r ， ┐r ∨s, ┐s, p, 结论： ┐q 设A={1，2，3，4}，在A×A上定义二元关系R： ，y>,，v>A×A，，y>R，v>x+y=u+v，证明R为A×A上的等价关系。
1、使命题公式p∧(q∨┓r)成真的真值指派是 ( a )
A.110，111，100 B.110，101，011 C.所有指派 D.无
2、设G=为无向图(4,8)，则G一定是 ( d) A.完全图 B.赋权图 C.单图 D.重图 3、设G=为无向图(3,5)，则G一定是 ( d ) A.完全图 B.赋权图 C.单图 D.重图 4、若图G有一条路经过图中每条边恰好一次,则G ( a) A.有一条欧拉路径 B.是欧拉图
C.有一条哈密顿路 D.是哈密顿图
5、4、若图G有一条开路经过图中每个结点恰好一次,则G ( c ) A.有一条欧拉路径 B.是欧拉图 C.有一条哈密顿通路 D.是哈密顿图
6、平面连通图G有4个顶点，5条边，则其面数为 ( a ) A.3 B.4 C.5 D.不能确定
7、命题公式F <=> 0，则F是 ( b ) A.重言式 B.矛盾式 C.可满足式 D.不能断定
1、 下列句子中，那一个是命题?
A: X+Y>5 B. 请勿吸烟！C：火星上有生物 D：明天下午开会吗？ 2、 下面哪一个连接词不满足交换律？ A: → B: v C: ʌ D：↔
3、 设S：天下雨；R：我骑车上班，则命题“只要天不下雨，我就骑车上班”的符号化为 A: S→¬R B: ¬S→¬R C: ¬S¬R D: ¬Sʌ¬R 4、 下列哪一个命题是命题“2是偶数或-3是负数”的否定 A：2是偶数或-3不是负数 B：2是奇数或-3不是负数 C：2不是偶数且-3不是负数 D：2是奇数且-3不是负数
5、 当P的真值是1,Q的真值是1 R的真值是0， 下列复合命题中真值为0的是 A： （PvQ）→R B: R→(P ʌ Q) C: (PvR) →Q D: (P ʌR)↔ ¬Q
本文来源：https://www.wddqw.com/doc/8673561a76c66137ee061990.html