一.填空
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. 是哈密顿图
5、4、若图G 有一条开路经过图中每个结点恰好一次, 则G ( c )
离散
初三
散文
3088字
105人浏览
wangljlife