西南科技大学离散数学07-08参考答案及评分细则(B卷)

参考答案及评分细则

西南科技大学2007——20008学年第 2 学期

《 离散数学 》期末考试试卷（B卷）

一、 (10分) 符号化下列命题：

（1)

（2)

（3)

（4)

（5) W→V (2分) (P∨Q)→┐R (2分) (P∨Q) R (2分) ┐ x(P(x)∧Q(x)) (2分) ( x)（R（x）→ ( y)（R（y）∧L（y，x））。 (2分)

二、 (7分)化简命题公式： （P∧（P→Q））→Q

解：（P ∧（P→Q））→Q

（P ∧（┐P∨Q））→Q (2分)

（P ∧┐P）∨（P∧Q））→Q (2分)

（P ∧Q）→Q (1分)

┐（P ∧Q）∨Q (1分)

┐P∨┐Q∨Q

┐P∨T

T (1分)

三、 (10分)已知命题公式A的真值表如下表，求公式A的主析取范式和主合

取范式。

解：由公式的真值表可得，该公式的极小项m为：(2分)

┒A∧┒B∧┒C，┒A∧┒B∧C，┒A∧B∧C，A∧┒B∧┒C，A∧┒B∧C。 极大项M为：(2分)

参考答案及评分细则

西南科技大学2007——20008学年第 2 学期

《 离散数学 》期末考试试卷（B卷）

A∨┒B∨C，┒A∨┒B∨C，┒A∨┒B∨┒C。

故，该命题公式的主析取范式为： (0,1,3,4,5)。(3分)

主合取范式为： (2,6,7)。(3分)

四、 (16分)用推理规则证明：

（1） (8分)S→┒Q，┒Q R，S∨P，┒R P

证明： ① ┒Q R P，前提引入

(┒Q→R)∧(R→┒Q)

② ┒Q→R T，①化简

③ S→┒Q P，前提引入

④ S→R T，②③前提三段论

⑤ ┒R P，前提引入

⑥ ┒S T，④⑤拒取式

⑦ S∨P P，前提引入

⑧ P T，⑥⑦析取三段论

故，原命题成立，证毕。 （评分参考：每步1分）

（2） (8分) x(P(x)→Q(x))， x(Q(x)→R(x)) x(P(x)→R(x))

证明： ① x(P(x)→Q(x)) P，前提引入

② P(y)→Q(y) T，①, US (2分)

③ x(Q(x)→R(x)) P，前提引入

④ Q(y)→R(y) T，③， US (2分)

⑤ P(y)→R(y) T，②④，前提三段论 (2分)

参考答案及评分细则

西南科技大学2007——20008学年第 2 学期

《 离散数学 》期末考试试卷（B卷）

⑥ x(P(x)→R(x)) T，⑤，UG (2分)

五、 (10分)对谓词公式： x y(H(x)∨G(y,x)))先消去量词后再求真值。其中，

对任意的x,y属于个体域D={2，3}，

F,x 2 F,x y G(x,y) 。 H(x) T,x 3 T,x y

解： x y(H(x)∨G(y,x))

x((H(x)∨G(2,x))∧(H(x)∨G(3,x)) (3分)

((H(2)∨G(2,2))∧(H(2)∨G(3,2))) ∨((H(3)∨G(2,3))∧(H(3)∨

G(3,3)) (3分)

((F∨F)∧(F∨T))∨((T∨T)∧(T∨F)) (2分)

(F∧T) ∨(T∧T)

F∨T

T (2分)

六、 (7分) 设A、B和C是论述域U中的任意集合，证明：

A-(B∪C)=(A-B)∩(A-C)

证明：A-(B∪C)

=A∩～(B∪C) (2分)

=A∩(～B∩～C) (2分)

= A∩(～B) ∩A∩(～C) (2分)

=(A-B)∩(A-C) (1分)

证毕。

参考答案及评分细则

西南科技大学2007——20008学年第 2 学期

《 离散数学 》期末考试试卷（B卷）

七、 (设A={a,b,c}，求

(1). (5分)A的所有划分。

解：A的所有划分有：

π1={{a,b,c}}； π2={{a},{b,c}}；

π3={{b},{a,c}}； π4={{c},{a,b}}；

π5={{a},{b},{c}}；（每个1分）

(2). (5分)所有划分所诱导出的等价关系的序偶。

解：π1所诱导出的等价关系的序偶为：(1分)

R1={<a,a>,<b,b>,<c,c>,<a,b>,<a,c>,<b,c>,<b,a>,<c,a>,<c,b>}

π2所诱导出的等价关系的序偶为：(1分)

R2={<a,a>,<b,b>,<c,c>,<b,c>,<c,b>}

π3所诱导出的等价关系的序偶为：(1分)

R1={<a,a>,<b,b>,<c,c>,<a,c>,<c,a>}

π4所诱导出的等价关系的序偶为：(1分)

R1={<a,a>,<b,b>,<c,c>,<a,b>,<b,a>}

π5所诱导出的等价关系的序偶为：(1分)

R5={<a,a>,<b,b>,<c,c>}

八、 (10分)设A={1,2,3,4}，R是A上的二元关系，

R={<1,2>,<4,3>,<2,2>,<2,1>,<3,1>}，求：MR2、Ms(R)、st(R)。

参考答案及评分细则

西南科技大学2007——20008学年第 2 学期

《 离散数学 》期末考试试卷（B卷）

0 1解：因为MR 1 011000001

1

1

1

00 0 (2分) 0 0 00000 0 (2分) 0 0 MR2=MR

0 1Ms(R)= 1 01100 1 1 MR= 0 110010 0 (3分) 1 0

1

1

1

111011 1 1 0 1 1由Mt(R)可知,Mst(R)= 1 1

所以, st(R)={<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,<2,3>,<2,4>,<3,1>,<3,2>,<3,4>,<4,1

>,<4,2>,<4,3>} (3分)

九、 (10分)图G是偏序集合<A,≤>的哈斯图，求：

参考答案及评分细则

西南科技大学2007——20008学年第 2 学期

《 离散数学 》期末考试试卷（B卷）

(1) (4分)A和偏序关系≤的集合表达式。

解：(1).A={a,b,c,d,e,f} (2分)

≤={<a,b>,<a,e>,<a,c>,<a,f>,<a,d>,<b,e>,<c,e>,<c,f>,<d,f>}∪IA (2分)

(2) (6分)求该偏序集的极大元、极小元、最大元、最小元。

解：该偏序集的极大元为e和f (2分)，极小元为a (2分)，最小元为a,最大元不存在(2分)。

十、 （10分）有向图D如下图所示。

（1） 写出D的邻接矩阵。

参考答案及评分细则

西南科技大学2007——20008学年第 2 学期 《 离散数学 》期末考试试卷（B卷）

解：MR=（3分）

（2） 求v1结点的出度和入度。

解：deg＋(v1)=4，deg－(v1)=1 （2分）

（3） 利用邻接矩阵求D中长度为2的路径的总数，并写出v1至v2长度

为2的路径。

解：A2

= （3分）

从v2到v4长度为2的路径有1条v2 v3 v4长度为2的路有13条（1分），

（1分）。