离散
初三 散文 3088字 88人浏览 wangljlife

一.填空

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 )

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