离散数学习题讲解.docVIP

求公式（p?q）?r对应的主析取范式和主合取范式。

解：1、真值表法：

pqrp?q(p?q)?r极小项：m1,m3,m4,m5,m7

00010极大项：M0，M2，M6

00111公式主析取范式为：

01010（púq）?r?m1úm3úm4úm5úm7

01111?(?pù?qùr)ú(?pùqùr)ú(pù?qù?r)

10001ú(pù?qùr)ú(pùqùr)

10101公式的主合取范式为：

11010（púq）?r?M0ùM2ùM6

11111?(púqúr)ù(pú?qúr)ù(?pú?qúr)

(2、等值演算法也可，略)

2、在自然推理系统P中构造下面推理的证明：(要求有符号化、前提、结论、推理及理由)

如果乙不参加篮球赛，那么甲就不参加；如果乙参加篮球赛，那么甲和丙就参加。因此，如果甲参加篮球赛，那么丙就参加。

解：设：p：乙队参加比赛；q：甲队参加比赛；r：丙队参加比赛。

前提：?p??q，p?(qùr),

结论：q?r

证明

q附加前提引入

?p??q前提引入

p①②拒取式规则

p?(qùr)前提引入

qùr③④假言推理

r化简

推理成立。

3、自然推理系统F中，证明下面推理：(要求有符号化、前提、结论、推理及理由)

所有的舞蹈者都很有风度；李霞是个学生并且是个舞蹈者。因此，有些学生很有风度。

解：设F(x)：x是舞蹈者；G(x)：x是学生；H(x)：x很有风度；a：李霞。

前提：x(F(x)?H(x)),G(a)ùF(a)

结论：$x(G(x)ùH(x))

证明：

G(a)ùF(a)前提引入

G(a)①化简

F(a)①化简

x(F(x)?H(x))前提引入

F(a)?H(a)④UI规则

H(a)③⑤假言推理

G(a)ùH(a)②⑥合取引入

$x(G(x)ùH(x))⑦EG规则

所以推理成立。

4、A={1，2，3，4}，R1,R2都是A上的二元关系，其中R1={1,2，2,1，2,3，3,4}，R2={1,2，4,4}。试给出R1的关系矩阵和关系图，并求：

dom(R1èR2)，ran(R1?R2)，fld(R1-R2)，R1?R2，R12，R1-1

解：

MR1GR1

MR1：见上

GR1：见上

dom(R1èR2)={1,2,3,4}

ran(R1?R2)={2}

fld(R1-R2)={1,2,3,4}

R1?R2={2,2，3,4}

R12={1,1,1,3,2,2,2,4}

R1-1={2,1,1,2,3,2,4,3}

5.偏序集A，R?的哈斯图下图所示，写出集合A和偏序关系R?的集合表达式，并分别写出集合B={a,b,c}的极大元，极小元，最大元，最小元，最小上界，最大下界。

五题六题

解：

A={a,b,c,d,e}R?={a,c,a,d,a,e,b,c,b,d,b,e,c,d,c,e}èIA

B的极大元：cB的极小元：a,b

B的最大元：cB的最小元：无

B的最小上界：cB的最大下界：无

6.设有向图D如图所示，

1、写出D的邻接矩阵；

2、求D中v1到v3长度为4的通路有几条？

3、求D中v1到自己的长度为3的回路有几条？

4、求D中长度为3的通路(不含回路)有多少条？

5、求D中长度为3的回路有多少条？

解：

1、D中v1到v3长度为4的通路有4条

2、D中v1到自己的