离散复习

1．设P表示“我将去书店”， Q表示“我有时间”，则命题“我将去书店，仅当我有时间”

符号化为 。PQ

2．设P表示“天下雨”， Q表示“我骑自行车上班”，则命题“除非下雨，否则我骑自行车上班”符号化为 。PQ3．写出下表中各列所定义的命题联结词

P Q 0 0 0 1 1 0 1 1 Q PQ PQ P→Q PQ P ∧ Q Pc

1 1 0 0 0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 0 1 0 0 1

3．设命题公式A的真值表为 P Q R A 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 0

则命题公式A的主析取范式为 ， 主合取范式为 。

(PQR)(PQR)(PQR)

(PQR)(PQR)(PQR)(PQR)(PQR)

4．设G(x)表示“x是金子”， F(x)表示“x是闪光的”，则命题“金子是闪光的，但闪光的不一定是金子”符号化为 。

(x)(G(x)F(x))(x)(F(x)G(x))

或(x)(G(x)F(x))(y)(F(y)G(y))

5．设S为非空集合，P(S)为集合S的幂集。代数系统〈P(S),,〉中，P(S)关于“”

的幺元为 ，零元为 ，P(S)关于“”的幺元为 ，零元为 。

,S,S,(换成布尔代数也要懂)

6. 10．设A，B是任意两个集合，f是A到B的一个关系, 如果

Zwy

计算机1班离散期末复习

， 称关系f为函数(或映射), 记为f：A→B。若 ，则称f为入射（或单射）；若 则称f为满射，若 ，则称f为双射。当f为 时，f是B到A的函数，且ff11= ，f1f= 。（对xA，都有唯一的yB使得x,yf； 对x1,x2A,x1x2，都有f(x1)f(x2)； ran(f)B； 既是单射又是满射； 双射，IB； IA）

8．在一棵根树中，有且只有一个结点的入度为__0___，其余所有结点的入度均为_1__。

在一棵根树中，入度为__0___的结点称为树根，出度为__0___的结点称为树叶。 9.设A={1，2，3}，A上的二元关系R={1,1,1,2,1,3,3,3}，则关系R具有 性，不具有 性 。反对称，传递；自反、对称、反自反。 10．将下面运算表中的空白处填入适当的元素符号，使{a,b,c},构成群．

 a b c a a b a c c c11． 设R是集合A上的二元关系，则r(R)= ，s(R)= ，

t(R)= 。

RIA,RR1，i1Ri

12.设有33盏灯，拟公用一个电源，求至少需要5插头的接线板的数目。

解：设至少需要5插头的接线板i个，则有

（5-1）i=33-1 （2分）

故 i=8

即至少需要8个5插头的接线板。 （1分）

12.知道平面图也满足欧拉公式点-边+面=2;

13.证明x(P(x)Q(x))，x(Q(x)R(x)S(x))，P(a)R(a)S(a)

（1）x(P(x)Q(x)) P （2）P(a)Q(a) US(1) （2分）

Zwy

计算机1班离散期末复习

（3）P(a)R(a) P （4）Q(a) T(2)(3)I （2分） （5）x(Q(x)R(x)S(x)) P

（6）Q(a)R(a)S(a) US(5) （2分） （7）R(a) T(3) I （1分） （8）Q(a)R(a) T(4)(7)I （1分）

（9）S(a) T(6)(8)I （2分）

13．用CP规则证明P(QR),Q(RS),PQS；

1. 2.

P P 6. (RS) T(4,5) I （2分）

P 7.

RP(QR) QR T(3,4) I（1分） T(6,7) I（1分）

3. 4.

T(1, 2) I （3分） 8.

SQ P(附加前提) 9. (QS) CP （2分）

5. Q(RS) P

14.设

A,,,为一布尔代数，在A上定运算如下：a，bA，

ab=(ab)(ab)． 证明〈A，〉是一个交换群．

证明：(1) 因为A,,,“”封闭。

为一布尔代数，所以ab=(ab)(ab)A，即A关于

（2）对a,b,cA，

(ab)c[(ab)(ab)]c ((ab)(ab))c)(((ab)(ab))c) (abc)(abc)((ab)(ab)c) (abc)(abc)(abc)(abc)

同理

a(bc)a[(bc)(bc)] (abc)(abc)(abc)(abc)

Zwy

计算机1班离散期末复习

所以“”是可结合的。

（3）对aA，a0(a0)(a0)(a1)0a 0a(0a)(0a)0(1a)a 所以0是〈A，〉的幺元。

（4）对aA，aa(aa)(aa)000，所以a（5）a,bA，a1a。

b(ab)(ab)(ba)(ba)ba

综上，〈A，〉是一个交换群．

15.关于最有二叉树的题大家看习题册的86页第6题;

16. 设集合A{a,b,c,d,e}上的偏序关系“”={c,a,c,c,d,a,d,b， a,a,b,a,b,b,d,c,d,d,e,a,e,c,e,e}，画出偏序关系“”的哈斯图。 解：偏序关系“”的哈斯图为:

对上题中的偏序集A,，求下表所列集合的上（下）界，上（下）确界，并将结果填入表

中。

子 集 {a,b,c} {c,d,e} A 上 界 上 界 a a,c 下 界 下 界 d 上 确 界 上 确 界 a c a 下 确 界 下 确 界 d

子 集 {a,b,c} {c,d,e} A 无 无 无 无 a

Zwy

计算机1班离散期末复习

17. 9．设f,g,h是集合A上的任意函数，下列哪个命题是真命题（ ）．（3）

(1)． fggf ； (2)．fff； (3)．f(gh)(fg)h； (4)．fgh． 18.懂得在群的运算表上寻找子群(需要满足两个条件:有幺元,满足封闭性) 19. 下列等价式不成立的是（ 2 ）.

(1)．x(F(x)G(x))xF(x)xG(x); (2)．x(F(x)G(x))xF(x)xG(x) (3)．x(F(x)G)xF(x)G (4)．x(F(x)G)xF(x)G

20. 谓词公式

(x)P(x)(x) , (x)P(x)(x) 。

P(x),P(x)

21.设A{a,b,c}，集合A上的等价关系R所确定的A的划分的是{{a},{ b, c }} ，则

R=( 1 )

（1）． {< a, a>,,,,} （2）．{< a ,b>,,,} （3）．{< a ,b>,,} （4）．{< a, a>,< a ,b>,,,,} 22. N个命题变元可以构成互不等价的命题公式（ 4 ）个。

(1)．N； (2)．2； (3)．2N； (4)．223. 19．下面的偏序集，哪个不是格（ ）．

N2N．

24.下面所示的偏序集中，哪一个是格：（ ）．(B)

Zwy

计算机1班离散期末复习

】

25．设f,g,h是集合A上的任意函数，下列哪个命题是真命题（ ）．（3） (1)． fggf ； (2)．fff； (3)．f(gh)(fg)h； (4)．fgh．

R26.设R是正实数集，Ｒ是实数集，ｆ：

R,xR,ｆ(x)lnx，则ｆ是（ ）．（4）

(1)．是入射不是满射； (2)．是满射不是入射； (3)．既非入射也非满射； (4)．是双射． 27．下面哪个偏序集构成有界格（ 4 ）．

(1)．N,； (2)．2,3,4,6,12,／，其中／为整除关系；

(3)．Z,； (4)．P(A),；其中A{a,b,c}，P(A)为A的幂集． 28.判断是否是平面图（子图中不能有k5，或者k33） 29。下图中是哈密尔顿图的是( 2 )

1．下面给出的四个图中，哪个不是汉密尔顿图（ （4） ）．

1．下列是欧拉图的是( 2 )

Zwy

计算机1班离散期末复习

1. 下列各图不是欧拉图的是（ 4 ）

17．下面哪个哈斯图构成分配格（ ）．

Zwy