文档库

最新最全的文档下载
当前位置:文档库 > 计算机学院 离散数学(上)B卷和参考答案及评分标准

计算机学院 离散数学(上)B卷和参考答案及评分标准

《离散数学(上)》考试试卷(B 卷)

(时间120分钟)

院/系 专业 姓名 学号

计算机学院 离散数学(上)B卷和参考答案及评分标准

一、单选题(每小题2分,共20分)

计算机学院 离散数学(上)B卷和参考答案及评分标准

1. 若P :他聪明;Q :他用功;则“他虽聪明,但不用功”,可符号化为( )

A.P ∨Q

B.P ∧┐Q

C.P →┐Q

D.P ∨┐Q

2. 设个体域为{,}D a b =,(,)(,)0F a a F a b ==,(,)(,)1F b a F b b ==,则下列公式为真的是( )

A. (,)x yF x y ??;

B. (,)x yF x y ??;

C.(,)x yF x y ??;

D.(,)x yF x y ???。 3. 设B 是不含变元x 的公式,谓词公式(?x)(A(x)→B)等价于( )

A.(?x)A(x)→B

B.(?x)A(x)→B

C.A(x)→B

D.(?x)A(x)→(?x)B 4. 对任意集合C B A ,,,下列各式中一定成立的是( )

A.)()()(C A B A C B A ?⊕?=⊕?;

B. )()()(C A B A C B A ??⊕=?⊕;

C. )()()(C A B A C B A ???=??;

D. )()(C B A C B A ??=??。

5. 设A={a,b,c},A 上二元关系R={〈a,a 〉,〈b,b 〉,〈a,c 〉},则关系R 的对称闭包S(R)是( )

A.R ∪I A

B.R

C.R ∪{〈c,a 〉}

D.R ∩I A

6. 设X={a,b,c},I

x 是X 上恒等关系,要使I x ∪{〈a,b 〉,〈b,c 〉,〈c,a 〉,〈b,a 〉}∪R 为X 上的等

价关系,R 应取( )

A. {〈c,a 〉,〈a,c 〉}

B.{〈c,b 〉,〈b,a 〉}

C. {〈c,a 〉,〈b,a 〉}

D.{〈a,c 〉,〈c,b 〉} 7. 下列式子正确的是( )

A. ?∈?

B.???

C.{?}??

D.{?}∈?

8. 以下命题公式中,为永假式的是( )

计算机学院 离散数学(上)B卷和参考答案及评分标准

A.p →(p ∨q ∨r)

B.(p →┐p)→┐p

C.┐(q →q)∧p

D.┐(q ∨┐p)→(p ∧┐p) 9. 设1π和

2π是非空集合A 的划分,则下列集合一定是A 的划分的是( )

A.1

2ππ B.12ππ C.12ππ- D.1211()ππππ-

10. 设N 和R 分别为自然数和实数集合,则下列集合中与其他集合的基数不同的集合是( )

A.R

B.N

N C.()N ρ D.n

N (n N ∈)

二、判断题(每小题2分,共10分。对的打√,错的打×)

1.()命题联结词集合{?,∧,∨}是最小的全功能联结词集。

2.()((?P∨Q)∧(Q→R))→(P→R)为重言式。

3.()R是A上的二元关系,R是自反的,当且仅当r(R)=R。

4.()集合A上的等价关系确定了A的一个划分。

5.()R是集合A上的关系,R有传递性的充要条件是RoR?R。

三、填空题(每小空2分,共20分)

1. 设R是I上模2同余关系,则R对应的等价类有_________,___________。

2. 命题{{a}} ? {{a},3,4,1} 的真值 = __ __ 。

3. 公式

))

(

)

,

(

(

))

,

(

)

(

(x

S

z

y

R

z

y

x

Q

x

P

x→

?

?的自由变元是 , 约束变元

是。

4. n个命题变元的真值有___种不同的组合;n个命题变元可构造___个不同的

主析取范式。

5. 集合{1,2,3,4}

A=上有___个不同的二元关系,___个不同的等价关系。

6. 集合A上的关系{1,2,2,1,2,3}

<><><>的传递闭包为________________。

四、计算题(每小题10分,共30分)

1. 先化简含P、Q、R三个命题变元的命题公式G: ((P→Q)∧(P→R))→P,然后求G的主析取范式和主合取范式。

2. 设R是集合

{1,2,3,4,5}

A=上的关系

计算机学院 离散数学(上)B卷和参考答案及评分标准

计算机学院 离散数学(上)B卷和参考答案及评分标准

计算机学院 离散数学(上)B卷和参考答案及评分标准

{(1,1),(1,3),(2,2),(2,5),(3,1),(3,3),(4,4),(5,2),(5,5)}R =

(1)画出R 的关系图; (2)证明R 是等价关系; (3)写出R 的所有等价类。

3. 设,A R <>为偏序集,其中}20,,6,4,2{ =A ,R 是A 上整除关系。 (1) 画出,A R <>的哈斯图; (2) 求A 的极大元和极小元;

(3) 令}12,8,6{=B ,求B 的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界。

五、证明题(每小题10分,共20分)

计算机学院 离散数学(上)B卷和参考答案及评分标准

1. 设I 为整数集合,函数:f I I I I ?→?定义为: >-=<>

2. 用推理规则证明:{ P ∨Q, P →R, Q →S, R →(?P ∧?Q)}蕴涵S 。

安徽大学20 09 —20 10 学年第 1 学期

《离散数学(上)》考试试题(B 卷)参考答案及评分标准

一、单选题(每小题2分,共20分)

1.B ;

2.A ;

3.A ;

4.C ;

5.C ;

6.D ;

7.B ;

8.C ;

9.D ;10.D 。

二、判断题(每小题1分,共10分。对的打√,错的打×)

1.×;

2.√;

3.√;

4.√;

5.√。

三、填空题(每小空2分,共20分)

1. []20或{} ,2,0,2,-, []21或{} ,3,1,1,3,--;

2. T 或真或1;

3. y,x ; x,z ;

4.2n ;22n ;

5.162或65536;15;

6.{1,1,1,2,1,3,2,1,2,2,2,3}<><><><><><>。

四、计算题(每小题10分,共30分)

1. 化简命题公式

G ? ((P →Q) ∧ (P →R)) → P ? ? ((?P ∨Q) ∧ (?P ∨R)) ∨ P 2分 ? ((P ∧?Q) ∨ (P ∧?R)) ∨ P

2分

? (P ∧?Q) ∨ (P ∧?R) ∨ P ? ((P ∧?Q) ∨ P) ∨ (P ∧?R) ? P ∨ (P ∧ ?R)

? P

2分 G ? (P ∧?Q ∧?R)∨(P ∧?Q ∧R)∨(P ∧Q ∧?R)∨(P ∧Q ∧R)

(主析取范式)

2分

? m 4∨m 5∨m 6∨m 7

?()∑7,6,5,4

?()3,2,1,0π

? M 0∧M 1∧M 2∧M 3

? (P ∨Q ∨R)∧(P ∨Q ∨?R)∧(P ∨?Q ∨R)∧(P ∨?Q ∨?R)

(主合取范式) 2分

2. {(1,1),(1,3),(2,2),(2,5),(3,1),(3,3),(4,4),(5,2),(5,5)}R =.

(1) R 的关系图

计算机学院 离散数学(上)B卷和参考答案及评分标准

计算机学院 离散数学(上)B卷和参考答案及评分标准

计算机学院 离散数学(上)B卷和参考答案及评分标准

4分 (2) 因为 R 满足自反、对称和传递性,所以R 是等价关系;

3分 (3) 等价类:{1, 3}, {2, 5}, {4}。

3分

3. (1) ,A R <>的哈斯图为

计算机学院 离散数学(上)B卷和参考答案及评分标准

4分

(2) A 的极大元为:12,14,16,18,20,极小元为2; 2分 (3) B 的极大元为:8,12,极小元为6,8;B 的最大元和最小元都不存在; 2分

B 的上界不存在,下界为2;B 的上确界不存在,下确界为2。 2分

五、证明题(每小题10分,共20分)

1. (1)

1122,,,x y x y I I ?<><>∈?,若),(),(2211><=>

>->=<-<22221111*,*,y x y x y x y x ,则??

?=-=-221

12

211**y x y x y x y x , 3分 易得21

x x =且21y y =,因此1122,,x y x y <>=<>,所以f 是单射函数。 2分

(2)取I I q p ?>∈>=<<2,0,,对,x y ?<>,若>=<>

则有??

?====-2*0

q y x p y x ,易得???±=±=2

2y x ,但I I ?>?±±<2,2, 3分

所以对于,p q I I <>∈?,不存在,x y I I <>∈?,使得>=<>

所以f 不是满射的。 2分 2. 证:

(1) P ∨Q P (2) R →(?P ∧?Q) P (3) ?R ∨? (P ∨Q) T(2) (4) (P ∨Q)→?R T(3) 1分 (5) ?R T(1)(4) 2分 (6) P →R P (7) ?R →?P T (6) 1分 (8) ?P T(5)(7) 2分 (9) Q T(1)(8) 2分 (10) Q →S P (11) S T(9)(10) 2分 所以 { P ∨Q, P →R, Q →S, R →(?P ∧?Q)}蕴涵S .