一.填空R-11 R是集合X上的关系,若 ,则称R是X上的等价关系.2 R是集合X上的二元关系,则关系1/R={ | }.3 T是一连通图,若T满足 ,则T构成树.4 G是一个图,若G可以 ,则称G为二部图.5 已知谓词公式 x F(x,y)y
来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/25 12:22:56
一.填空R-11 R是集合X上的关系,若 ,则称R是X上的等价关系.2 R是集合X上的二元关系,则关系1/R={ | }.3 T是一连通图,若T满足 ,则T构成树.4 G是一个图,若G可以 ,则称G为二部图.5 已知谓词公式 x F(x,y)y
一.填空R-1
1 R是集合X上的关系,若 ,则称R是X上的等价关系.
2 R是集合X上的二元关系,则关系1/R={ | }.
3 T是一连通图,若T满足 ,则T构成树.
4 G是一个图,若G可以 ,则称G为二部图.
5 已知谓词公式 x F(x,y)yH(x,y),则 是自由变元.
6 已知谓词公式 xF(x,y)yG(x,y,z),则 是约束变元.
7 图G存在悬挂顶点,则至少删去 条边,图变成两个连通分支.
8 T是一棵树,则T的树叶最少有 片.
9 G是一个连通图,若G有一个 ,则G为欧拉图.
10 图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 集合A属于集合B,
2 集合A等于集合B
3 集合X=空集
4.集合A上的二元关系R是自反的
5.集合A上的二元关系R是反自反的
6.集合A上的二元关系R是对称的
7.集合A上的二元关系R是反对称的
8.集合A上的二元关系R是传递的
三.按要求完成下列各题
1 A={x,y,z},R={,,,},S={,,,},求R◦S、S◦R及S的传递闭包t(R).
2 已知集合E={1,2,{1,2}},S={1,{2}},求ES,ES,(E-S)(S-E) .求命题公式(pqr)的主析取范式和主合取范式.
3 A={1,2,{2}},求A×A,P(A).
4 画一棵带权为2,2,3,3,4,5,8的最优二元树T,并计算它的权W(T).
5 (1)在一棵有2个2度顶点,4个3度顶点,其余顶点都是树叶的无向树中,应该有几片树叶?(2)画出两棵非同构的满足(1)中顶点度数的无向树T1和T2.
6 一棵树有5片树叶,3个2度顶点,其余的顶点均为3度顶点,问T有几个顶点?
7 A={1,2,3,5,7,14,15,35},R是A上的整除关系:Rx|y(x整除y),画出R的哈斯图,设 B={2,5,7,14,35},求B关于R的极大元、极小元和最大元、最小元.
9 求出下列图的所有点割集和边割集.
10.已知一个有向图G=,其中
V={v1,v2,v3 },
E={,,,,},
求D的邻接矩阵A;(2)求顶点v1的入度、出度及次数(3)将G看成无向图,写出关联矩阵.
11.用二元树表示下面的表达式
((x-2y)*3z-7x)÷(4z-2y)2
12.求下列图的最小生成树
四.证明下列命题 (14分)
1 A,B,C是任意集合,证明(A-B)-C=(A-C)-(B-C)
2 A,B,C是任意集合,证明若A⊕B= A⊕C,则B=C
3 A,B是集合,若P(A)∩P(B)=P(A∩B),其中P(A)表示集合A的幂集.
4 p,q,r是任意命题,证明p→(q∨r) (p∧┑q) →r
5 p,q,r是任意命题,证明(p→q) ∧ (q→r) p→r
6 前提:(p∧q) → r ,┐r ∨s,┐s,p,
结论:┐q
7 设A={1,2,3,4},在A×A上定义二元关系R:,A×A,Rx+y=u+v,证明R为A×A上的等价关系.
一.填空R-11 R是集合X上的关系,若 ,则称R是X上的等价关系.2 R是集合X上的二元关系,则关系1/R={ | }.3 T是一连通图,若T满足 ,则T构成树.4 G是一个图,若G可以 ,则称G为二部图.5 已知谓词公式 x F(x,y)y
因为版本不同,所以有些我也不会.
一、(1)a∈X,b∈X且aRb=bRa(3)无回路(8)2(9)欧拉回路(11)p ∨ q(12)「(∨x) (∨y)(F(x)∧ F(y)→H(x,y))(14)m=n-1
二、(1)(Vx)(x∈A →x∈B)(4)(Vx)(x ∈A → ∈R) 其他的自己写吧
三、(1)R◦S={={,,,,,}(3)A×A=={,,,,,,,,}
四、(1) (A-B)-C
= (A-B) ∩ C
= (A∩~B) ∩ C
= A∩(~B ∩ C)
= A∩(~B ∩ C)∪(C C)
= A∩(~C ∩(~B ∪C))
= (A∩~C) ∩(~B ∪C)
= (A∩~C) (B C)
= (A-C)∩~(B-C)
= (A-C)-(B-C)
疯了,这么多题!