当前位置: 首页 > 电大 >

电大离散数学填空题参考题

二、填空题

1.已知图 G 中有 1 个 1 度结点,2 个 2 度结点,3 个 3 度结点,4 个 4 度结点,则 G 的边数是 15

讨论:已知图 G 中有 15 条边,3 个 3 度结点,4 个 4 度结点,其它结点的度数小于等于 2,讨论图 G 可能

的结点数. 2.设给定图 G (如右图所示),则图 G 的点割集是{f}、{c, e}

a?

?b

f?

?c

3.无向图 G 存在欧拉回路,当且仅当 G 连通且结点度数都是偶数. 由定理 4.1.1 的推论

e? ?d

4.若图 G=<V,E>中具有一条汉密尔顿回路,则对于结点集 V 的每个非空子集 S,在 G 中删除 S 中的

所有结点得到的连通分支数为 W,则 S 中结点数|S|与 W 满足的关系式为 W(G-S)? |S

5.设图 G 是有 6 个结点的连通图,结点的总度数为 18,则可从 G 中删去 4 条边后使之变成树.(……边后,可以确定图 G 的一棵生成树)
6.设集合 A={a},那么集合 A 的幂集是{?,{a}}.

1.设集合 A={0, 1, 2, 3},B={2, 3, 4, 5},R 是 A 到 B 的二元关系,R ? {? x, y ? x ? A且y ? B且x, y ? A ? B}
则 R 的有序对集合为 R = { ? 2 , 2 ? , ? 2 , 3 ? , ? 3 , 2 ? , ? 3 , 3 ? . 2.设集合 A={1, 2, 3, 4 },B={6, 8, 12},A 到 B 的二元关系 R={? x, y ? y ? 2x, x ? A, y ? B}
那么 R-1= {<6,3>,<8,4>} 3.设集合 A={a,b,c,d},A 上的二元关系 R={<a, a >, <b, b>, <b, c>, <c, d>},若在 R 中再增加两个元素
<c, b>, <d, c>,则新得到的关系就具有对称性. 4.设 A={1,2}上的二元关系为 R={<x,y>|x?A,y?A,x+y=10},则 R 的自反闭包为 IA。
因为满足条件 x?A,y?A,x+y=10 的关系只有空关系,空关系的闭包是 IA. 5.设 R 是集合 A 上的等价关系,且 1 , 2 , 3 是 A 中的元素,则 R 中至少包含<1, 1>, <2, 2>, <3, 3>等元素.
6.设集合 A={1, 2},B={a, b},那么集合 A 到 B 的双射函数是{<1, a >, <2, b >},{<1, b >, <2, a >}
1.命题公式 P ? (Q ? P) 的真值是 1.
2.设 P:他生病了,Q:他出差了.R:我同意他不参加学习.则命题“如果他生病或出差了,我就同意他 不参加学习”符号化的结果为 (P?Q)?R. 3.含有三个命题变项 P,Q,R 的命题公式 P?Q 的主析取范式是(P?Q?R)? (P?Q??R) .
4.设个体域 D={a, b},那么谓词公式 ?xA(x) ? ?yB(y) 消去量词后的等值式为(A(a)? A(b))? (B(a)? B(b)).
5.设个体域 D={1, 2, 3},A(x)为“x 小于 3”,则谓词公式(?x)A(x)的真值为 1. 6.谓词命题公式(?x)((A(x)?B(x)) ?C(y))中的自由变元为 y.

1/2

三、判断说明题

1.如果图 G 是无向图,且其结点度数均为偶数,则图 G 存在一条欧拉回路.a (错) ?

问:“如果图 G 是无向连通图,则图 G 存在一条欧拉回路”

b ? c?

2.如右图所示的图 G 不是欧拉图而是汉密尔顿图.(对) 注意:汉密尔顿图不一定是欧拉图,为什么?.

e?

f?

3.设 G 是一个有 7 个结点 16 条边的连通图,则 G 为平面图.(错)

图G

?d ?g

4.“完全图 K6 是平面图”是否正确?(错) 不正确.

因为完全图 K6 有 6 个结点 15 条边,且 15?3?6-6=12,即 e ? 3v-6 对 K6 不成立,所以 K6 不是平面图.

a?

1.若偏序集<A,R>的哈斯图如右图所示, 2.则集合 A 的最大元为 a,最小元不存在.(错)

b?

?c ?g

d?

?h

e?

?f

问:是否存在一个元素 a,它既是偏序集<A,R>的最大元,也是<A,R>的最小元?

1.命题公式 ?P ? P 的真值是 1.(错) 2.命题公式?P∧(P??Q)∨P 为永真式.正确 解:正确 因为,由真值表
P Q ?P ?Q 0011 0110 1001 1100 可知,该命题公式为永真式. 3.下面的推理是否正确,请给予说明.(错)

P??Q 1 1 1 0

?P∧(P→?Q)∨P 1 1 1 1

2/2




友情链接: 高中资料网 职业教育网 成人教育网 理学 大学工学资料