一．填空
R 是集合X 上的关系, 若 , 则称R 是X 上的等价关系。 R 是集合X 上的二元关系， 则关系R-1={ <x,y>| }。 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={<x,x>,<x,y>,<y,z>,<z,z>}，S={<x,y>,<y,z>,<z,y>,<z,z>}，求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 上的整除关系:<x,y>Rx|y(x整除y) ，画出R 的哈斯图，设 B={2,5,7,14,35}，求B 关于R 的极大元、极小元和最大元、最小元。
求出下列图的所有点割集和边割集。
10．已知一个有向图G=<V, E>, 其中
V={v1,v2,v3 }，
E={<v1,v2>,<v2,v1>,<v2,v3>,<v3,v2>,<v3,v1>}，
求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 ： <x，y>,<u，v>A×A ，<x，y>R<u，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=<V,E>为无向图(4,8)，则G 一定是 ( d)
A. 完全图 B. 赋权图 C. 单图 D. 重图
3、设G=<V,E>为无向图(3,5)，则G 一定是 ( d )
A. 完全图 B. 赋权图 C. 单图 D. 重图
4、若图G 有一条路经过图中每条边恰好一次, 则G ( a)
A. 有一条欧拉路径 B. 是欧拉图
C. 有一条哈密顿路 D. 是哈密顿图
离散
初三
散文
3088字
105人浏览
wangljlife