离散数学习题答案.docx

离散数学习题答案.docx

《离散数学习题答案.docx》由会员分享，可在线阅读，更多相关《离散数学习题答案.docx（71页珍藏版）》请在冰点文库上搜索。

离散数学习题答案

离散数学习题参考答案

习题一

1、构造公式（p∧q）∨（¬p∧¬q）、p↔q的真值表。

2、构造公式¬（p∨q）与¬p∧¬q的真值表。

3、构造公式p、p∧p、p∨p的真值表。

4、构造公式p∨（q∧r）、（p∨q）∧（p∨r）的真值表。

5、构造公式p∨（p∧r）、p的真值表。

6、构造公式p∧（p∨r）、p的真值表。

7、构造公式p↔q、¬q↔¬p的真值表。

8、构造公式（p→q）∧（p→¬q）、¬p的真值表。

9、构造公式p、¬¬p的真值表。

10、构造公式p∨¬p、p∧¬p的真值表

略

习题二

一、分别用等算演算与真值表法，判断以下公式是否存在主析取式或主合取式，假设有，请写出来。

（1）（¬p→q）→（¬q∨p）

（2）（¬p→q）→（q∧r）

（3）（p∨（q∧r））→（p∨q∨r）

（4）¬（q→¬p）∧¬p

（5）（p∧q）∨（¬p∨r）

（6）（p→（p∨q））∨r

（7）（p∧q）∨r

（8）（p→q）∧（q→r）

（9）（p∧q）→q

（10）¬（r↔p）∧p∧q

解：

（1）

p

q

¬p

（¬p→q）

¬q

（¬q∨p）

（¬p→q）→（¬q∨p）

0

0

1

0

1

1

1

0

1

1

1

0

0

0

1

0

0

1

1

1

1

1

1

0

1

0

1

1

存在主析取式=成真赋值对应的小项的析取

=m00∨m10∨m11=（¬p∧¬q）∨（p∧¬q）∨（p∧q）

主析取式=成假赋值对应的大项的合取

=M01=p∨¬q

等值演算：

（¬p→q）→（¬q∨p）

⇔¬（¬¬p∨q）∨（p∨¬q）

⇔¬（p∨q）∨（p∨¬q）

⇔（¬p∧¬q）∨（p∨¬q）

⇔（¬p∨（p∨¬q））∧（¬q∨（p∨¬q））

⇔（¬p∨p∨¬q）∧（¬q∨p∨¬q）

⇔（1∨¬q）∧（p∨¬q）

⇔（p∨¬q）

这是大项，故为大项的合取，称为主合取式

（¬p→q）→（¬q∨p）

⇔（p∨¬q）

⇔（p）∨（¬q）

⇔（p∧1）∨（1∧¬q）

⇔（p∧（q∨¬q））∨（（p∨¬p）∧¬q）

⇔（p∧q）∨（p∧¬q）∨（p∧¬q）∨（¬p∧¬q）

⇔（p∧q）∨（p∧¬q）∨（¬p∧¬q）

因为一个公式的值不是真，就是假，因此当我们得到一个公的取值为真的情况时，剩下的组合是取值为假，因此当得到小项的析取组成的主析取式后，可以针对剩下的组合写出主合取式。

如当我们得到（¬p→q）→（¬q∨p）的大项之合取（p∨¬q）后，使（p∨¬q）为假时（p,q）的值为（0,1），故其标记为M01，剩余的取值为（0,0）,（1,0）,（1,1），故小项之析取为m00∨m10∨m11。

反之，假设先得到其小项的析取，也可得到其大项的合取。

反正这两者将其所有组合瓜分完毕。

（2）（¬p→q）→（q∧r）

p

q

r

¬p

¬p→q

（q∧r）

结果

0

0

0

1

0

0

1

0

0

1

1

0

0

1

0

1

0

1

1

0

0

0

1

1

1

1

1

1

1

0

0

0

1

0

0

1

0

1

0

1

0

0

1

1

0

0

1

0

0

1

1

1

0

1

1

1

主析取式=m000∨m001∨m011∨m111=（¬p∧¬q∧¬r）∨（¬p∧¬q∧r）∨（¬p∧q∧r）∨（p∧q∧r）

主合取式=M010∧M100∧M101∧M110=（p∨¬q∨r）∧（¬p∨q∨r）∧（¬p∨q∨¬r）∧（¬p∨¬q∨r）

（3）（p∨（q∧r））→（p∨q∨r）

p

q

r

（q∧r）

（p∨（q∧r））

（p∨q∨r）

（p∨（q∧r））

→（p∨q∨r）

0

0

0

0

0

0

1

0

0

1

0

0

0

1

0

1

0

0

0

1

1

0

1

1

0

0

1

1

1

0

0

0

1

1

1

1

0

1

0

1

1

1

1

1

0

1

1

1

1

1

1

1

1

1

1

1

永真式，所有小项的析取得到其主析取式

=（¬p∧¬q∧¬r）∨（¬p∧¬q∧r）∨（¬p∧q∧¬r）∨（¬p∧q∧r）∨（p∧¬q∧¬r）∨（p∧¬q∧r）∨（p∧q∧¬r）∨（p∧q∧r）

由于没为假的指派，所以没有为假赋值，所对应的大项合取构成的合取，即没有主合取式。

¬（p∨（q∧r））∨（p∨q∨r）=（¬p∧¬（q∧r））∨（p∨q∨r）=（（¬p∧¬q）∨（¬p∧¬r））∨（p∨q∨r）=

（¬p∧¬q）∨（¬p∧¬r）∨p∨q∨r=¬（p∨q）∨（¬p∧¬r）∨p∨q∨r=1永真

（4）¬（q→¬p）∧¬p

p

q

¬p

（q→¬p）

¬（q→¬p）

结果

0

0

1

1

0

0

0

1

1

1

0

0

1

0

0

1

0

0

1

1

0

0

1

0

没有成真的赋值，从而没有对应的小项，因此没有小项构成的主析取式

永假式即矛盾式，为假指派对应的大项合取=（p∨q）∧（p∨¬q）∧（¬p∨q）∧（¬p∨¬q）

原式=¬（¬q∨¬p）∧¬p=（q∧p）∧¬p=0

（5）（p∧q）∨（¬p∨r）

p

q

r

（p∧q）

¬p

（¬p∨r）

（p∧q）∨（¬p∨r）

0

0

0

0

1

1

1

0

0

1

0

1

1

1

0

1

0

0

1

1

1

0

1

1

0

1

1

1

1

0

0

0

0

0

0

1

0

1

0

0

1

1

1

1

0

1

0

0

1

1

1

1

1

0

1

1

主析取式

（¬p∧¬q∧¬r）∨（¬p∧¬q∧r）∨（¬p∧q∧¬r）∨（¬p∧q∧r）∨（p∧¬q∧r）∨（p∧q∧¬r）∨（p∧q∧r）

主合取式

M100=¬p∨q∨r

原式=（（p∧q）∨¬p）∨r=（（p∨¬p）∧（¬p∨q））∨r=（1∧（¬p∨q））∨r=¬p∨q∨r这就是大项也

剩下的赋值对应的就是小项

（6）（p→（p∨q））∨r

p

q

r

（p∨q）

（p→（p∨q））

（p→（p∨q））∨r

0

0

0

0

1

1

0

0

1

0

1

1

0

1

0

1

1

1

0

1

1

1

1

1

1

0

0

1

1

1

1

0

1

1

1

1

1

1

0

1

1

1

1

1

1

1

1

1

永真式，只有小项组成的主析取式。

没有为假的赋值，所以没有成假赋值对应的大项的合取，即没有主合取式。

原式=（¬p∨（p∨q））∨r=（1∨q）∨r=1

（7）（p∧q）∨r

p

q

r

（p∧q）

（p∧q）∨r

0

0

0

0

0

0

0

1

0

1

0

1

0

0

0

0

1

1

0

1

1

0

0

0

0

1

0

1

0

1

1

1

0

1

1

1

1

1

1

1

主析取式=m001∨m011∨m101∨m110∨m111=

（¬p∧¬q∧r）∨（¬p∧q∧r）∨（p∧¬q∧r）∨（p∧q∧¬r）∨（p∧q∧r）

主合取式=M000∧M010∧M100=（p∨q∨r）∧（p∨¬q∨r）∧（¬p∨q∨r）

（p∧q）∨r

=（p∧q∧1）∨（1∧1∧r）

=（p∧q∧（¬r∨r））∨（（¬p∨p）∧（¬q∨q）∧r）

=（p∧q∧¬r）∨（p∧q∧r）∨（¬p∧¬q∧r）∨（¬p∧q∧r）∨（p∧¬q∧r）

（p∧q）∨r

=（p∨r）∧（q∨r）

=（p∨0∨r）∧（0∨q∨r）

=（p∨（¬q∧q）∨r）∧（（¬p∧p）∨q∨r）

=（p∨¬q∨r）∧（p∨q∨r）∧（¬p∨q∨r）∧（p∨q∨r）

=（p∨¬q∨r）∧（p∨q∨r）∧（¬p∨q∨r）

（8）（p→q）∧（q→r）

p

q

r

（p→q）

（q→r）

（p→q）∧（q→r）

0

0

0

1

1

1

0

0

1

1

1

1

0

1

0

1

0

0

0

1

1

1

1

1

1

0

0

0

1

0

1

0

1

0

1

0

1

1

0

1

0

0

1

1

1

1

1

1

主析取式=m000∨m001∨m011∨m111

=（¬p∧¬q∧¬r）∨（¬p∧¬q∧r）∨（¬p∧q∧r）∨（p∧q∧r）

主合取式=M010∧M100∧M101∧M110=

=（p∨¬q∨r）∧（¬p∨q∨r）∧（¬p∨q∨¬r）∧（¬p∨¬q∨r）

（p→q）∧（q→r）=（¬p∨q）∧（¬q∨r）

=（¬p∨q∨0）∧（0∨¬q∨r）

=（¬p∨q∨（¬r∧r））∧（（¬p∧p）∨¬q∨r）

=（¬p∨q∨¬r）∧（¬p∨q∨r）∧（¬p∨¬q∨r）∧（p∨¬q∨r）

（p→q）∧（q→r）=（¬p∨q）∧（¬q∨r）

=（¬p∧¬q）∨（¬p∧r）∨（q∧¬q）∨（q∧r）

=（¬p∧¬q∧1）∨（¬p∧1∧r）∨（1∧q∧r）

=（¬p∧¬q∧（¬r∨r））∨（¬p∧（¬q∨q）∧r）∨（（¬p∨p）∧q∧r）

=（¬p∧¬q∧¬r）∨（¬p∧¬q∧r）∨（¬p∧¬q∧r）∨（¬p∧q∧r）∨（¬p∧q∧r）∨（p∧q∧r）

=（¬p∧¬q∧¬r）∨（¬p∧¬q∧r）∨（¬p∧q∧r）∨（p∧q∧r）

（9）（p∧q）→q

p

q

（p∧q）

（p∧q）→q

0

0

0

1

0

1

0

1

1

0

0

1

1

1

1

1

永真式，只有小项的析取构成的主析取式=（¬p∧¬q）∨（¬p∧q）∨（p∧¬q）∨（p∧q）

没有为假的指派，所以没有由大项的合取构成的主合取式

（p∧q）→q

=¬（p∧q）∨q

=（¬p∨¬q）∨q

=¬p∨¬q∨q

=1

（10）¬（r↔p）∧p∧q

p

q

r

r↔p

¬（r↔p）

¬（r↔p）∧p∧q

0

0

0

1

0

0

0

0

1

0

1

0

0

1

0

1

0

0

0

1

1

0

1

0

1

0

0

0

1

0

1

0

1

1

0

0

1

1

0

0

1

1

1

1

1

1

0

0

主析取式=m110=p∧q∧¬r

主合取式=M000∧M001∧M010∧M011∧M100∧M101∧M111

=（p∨q∨r）∧（p∨q∨¬r）∧（p∨¬q∨r）∧（p∨¬q∨¬r）∧（¬p∨q∨r）∧（¬p∨q∨¬r）∧（¬p∨¬q∨¬r）

¬（r↔p）∧p∧q

=¬（（¬p∨r）∧（p∨¬r））∧p∧q

=（（p∧¬r）∨（¬p∧r））∧p∧q

=（p∧¬r∧p∧q）∨（¬p∧r∧p∧q）

=（p∧q∧¬r）

¬（r↔p）∧p∧q

=¬（（p∧r）∨（¬p∧¬r））∧p∧q

=（（¬p∨¬r）∧（p∨r））∧p∧q

=（¬p∨¬r）∧（p∨r）∧p∧q

=（¬p∨¬r）∧（（p∨r）∧p）∧q

=（¬p∨¬r）∧p∧q

=（¬p∨（¬q∧q）∨¬r）∧（p∨（¬q∧q）∨（¬r∧r））∧（（¬p∧p）∨q∨（¬r∧r））

=（¬p∨¬q∨¬r）∧（¬p∨q∨¬r）∧

（p∨¬q∨¬r）∧（p∨¬q∨r）∧（p∨q∨¬r）∧（p∨q∨r）∧

∧（¬p∨q∨¬r）∧（¬p∨q∨r）∧（p∨q∨¬r）∧（p∨q∨r）

=（p∨q∨r）∧（p∨q∨¬r）∧（p∨¬q∨r）∧（p∨¬q∨¬r）∧（¬p∨q∨r）∧（¬p∨q∨¬r）∧（¬p∨¬q∨¬r）

=M000∧M001∧M010∧M011∧M100∧M101∧M111

二、应用题

1、某次课间休息时，1位同学作为主持人与另外3位同学进展猜数游戏，主持人说这个数是30、50、70中的某一个，你们三位同学各猜一次，然后主持人分析每人猜数的结果，从而最终确定是哪个数。

同学1说：

这个数是30，不是50

同学2说：

这个数是50，不是70

同学3说：

这个数既不是30，也不是50

主持人听后说道：

你们3人中，有一人全对，有二人对了一半，请问到底是哪个数。

解：

令S表示“这个数是30〞，W表示“这个数是50〞，Q表示“这个数是70〞

同学1的话：

S∧¬W

同学2的话：

W∧¬Q

同学3的话：

¬S∧¬W

对于每个人来说，只有二个选择：

全对、对一半，对一半又分成：

第一句对第二句错、第一句错第二句对，因此每个同学的对错情况为：

√√、√×、×√，因此3个人共有3*3*3=27种可能的情况，其中有些情况不符合“有一人全对，有二人对了一半〞而剔除。

我们按“√√、√×、×√〞顺序，构造“类真值表〞来分析其组合情况

同学1

同学2

同学3

命题公式

分析

√√

√√

√√

不必写

不可能全对

√√

√√

√×

不必写

不可能有2个对

√√

√√

√×

不必写

不可能有2个对

√√

√×

√√

不必写

不可能有2个对

√√

√×

√×

S∧¬W∧W∧Q∧¬S∧W=0

真值为0不对

√√

√×

√×

S∧¬W∧W∧Q∧S∧¬W=0

真值为0不对

√√

√×

√√

不必写

不可能有2个对

√√

√×

√×

S∧¬W∧¬W∧Q∧¬S∧W=0

真值为0不对

√√

√×

√×

S∧¬W∧¬W∧¬Q∧S∧¬W=S∧¬W∧¬Q

可能对的，是30

不是50，不是70

√×

√√

√×

S∧W∧W∧¬Q∧¬S∧W=0

不可能

√×

√√

√×

S∧W∧W∧¬Q∧S∧¬W=0

不可能

√×

√×

√√

S∧W∧W∧Q∧¬S∧¬W=0

不可能

√×

√×

√√

S∧W∧¬W∧¬Q∧¬S∧¬W=0

不可能

√×

√√

√×

×S,¬W,W,¬Q,S,W=0

不可能

×√

√√

×√

¬S,¬W,W,¬Q,S,¬W=0

不可能

×√

√×

√√

¬S,¬W,W,Q,¬S,¬W=0

不可能

×√

×√

√√

¬S，¬W，¬W，¬Q，¬S，¬W=

3个数都不是，不可能

答案是：

是30，不是50，不是70

同学1说：

这个数是30，不是50全对

同学2说：

这个数是50，不是70第一句错第二句对

同学3说：

这个数既不是30，也不是50第一句错第二句对

2、设计一个如下的电路图：

它有三个输入p1、p2、p3，当其中有2个及以上的值为1时输出的结果为1，其他情况下输出0。

请给出其真值表，同时针对此真值表给出主析取式、主合取式，并给出其最简单的表达式。

答：

与课堂例题一样

在真实的教材将其换成了如下习题

2、设计一个如下的电路图：

它有三个输入p1、p2、p3，当其中任意二个的值为0时输出的结果为1，其他情况下输出0。

请给出其真值表，同时针对此真值表给出主析取式、主合取式，并给出其最简单的表达式。

p1

p2

p3

表达式的值

0

0

0

1

0

0

1

1

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

0

1

1

0

0

1

1

1

0

其主析取式=m000∨m001∨m010∨m100

=（¬p1∧¬p2∧¬p3）∨（¬p1∧¬p2∧p3）∨（¬p1∧p2∧¬p3）∨（p1∧¬p2∧¬p3）

=（（¬p1∧¬p2）∧（¬p3∨∧p3））∨（（（¬p1∧p2）∨（p1∧¬p2））∧¬p3）

=（¬p1∧¬p2）∨（（（¬p1∧p2）∨（p1∧¬p2））∧¬p3）

其主合取式=M011∧M101∧M110∧M111

=（p1∨¬p2∨¬p3）∧（¬p∨p2∨¬p3）∧（¬p1∨¬p2∨p3）∧（¬pq∨¬p2∨¬p3）

=（（（p1∨¬p2）∧（¬p1∨p2））∨¬p3）∧（¬p1∨¬p2）

3、某年级要从1班、2班、3班、4班、5班中选出一名才子主持元旦晚会，每班最多一人，也可能没有，这些人满足如下条件，请确定最终选择哪些班级的学生：

（1）如果1班有人选中，那么2班有人选中。

（2）假设5班有人选上那么1班与2班均有人选上。

（3）5班与4班必有一班有被选中。

（4）3班与4班同时有人选上或同时没人选上。

解：

用One表示1班选了人，Two表示2班选了人，Three表示3班选了人，Four表示4班选了人，Five表示5班选了人。

那么这4个条件依次为

One→Two，Five→（One∧Two），Four∨Five，Three↔Four

满足这4个条件，即这4个条件的值均为真即为1，所以其合取为1

（One→Two）∧（Five→（One∧Two））∧（Four∨Five）∧（Three↔Four）=1，

将以上合取式转换为主析取式，因此双条件应转换为析取式的合取式

原式=

（¬One∨Two）∧（¬Five∨（One∧Two））∧（Four∨Five）∧（（¬Three∨Four）∧（Three∨¬Four））

=[（¬One∨Two）∧（¬Five∨（One∧Two））]∧（Four∨Five）∧（¬Three∨Four）∧（Three∨¬Four）

=[（¬One∧¬Five）∨（¬One∧（One∧Two）∨（Two∧¬Five）∨（Two∧（One∧Two）]∧（Four∨Five）∧（¬Three∨Four）∧（Three∨¬Four）

={[（¬One∧¬Five）∨（Two∧¬Five）∨（Two∧One）]∧（Four∨Five）}

∧（¬Three∨Four）∧（Three∨¬Four）

={[（¬One∧¬Five∧Four）∨（Two∧¬Five∧Four）∨（Two∧One∧Four）∨（Two∧One∧Five）]

∧（¬Three∨Four）}∧（Three∨¬Four）

={（¬One∧¬Five∧Four∧¬Three）∨

（¬One∧¬Five∧Four）∨

（Two∧¬Five∧Four∧¬Three）∨

（Two∧¬Five∧Four）∨

（Two∧One∧Four∧¬Three）∨

（Two∧One∧Four）∨

（Two∧One∧Five∧¬Three）∨

（Two∧One∧Five∧Four）}∧（Three∨¬Four）

=（¬One∧¬Five∧Four∧Three）∨

（Two∧¬Five∧Four∧Three）∨

（Two∧One∧Four∧Three）∨

（Two∧One∧Five∧¬Three∧¬Four）∨

（Two∧One∧Five∧Four∧Three）

=（¬One∧Three∧Four∧¬Five）∨

（Two∧Three∧Four∧¬Five）∨

（One∧Two∧Three∧Four）∨

（One∧Two∧¬Three∧¬Four∧Five）∨

（One∧Two∧Three∧Four∧Five）

一班

二班

三班

四班

五班

条件1

条件2

条件3

条件4

方案一

无

不限

有

有

无

满足

满足

满足

满足

方案二

不限

有

有

有

无

满足

满足

满足

满足

方案三

有

有

有

有

不限

满足

满足

满足

满足

方案四

有

有

无

无

有

满足

满足

满足

满足

方案五

有

有

有

有

有

满足

满足

满足

满足

（1）如果1班有人选中，那么2班有人选中。

（2）假设5班有人选上那么1班与2班均有人选上。

（3）5班与4班必有一班有被选中。

（4）3班与4班同时有人选上或同时没人选上。

按照某位帅哥的质疑，经仔细思考，应该将其转换为主析取式，所以最终结果为：

=（¬One∧1∧Three∧Four∧¬Five）∨

（1∧Two∧Three∧Four∧¬Five）∨

（One∧Two∧Three∧Four∧1）∨

（One∧Two∧¬Three∧¬Four∧Five）∨

（One∧Two∧Three∧Four∧Five）

=（¬One∧¬Two∧Three∧Four∧¬Five）∨（¬One∧Two∧Three∧Four∧¬Five）∨

（¬One∧Two∧Three∧Four∧¬Five）∨（One∧Two∧Three∧Four∧¬Five）∨

（One∧Two∧Three∧Four∧¬Five）∨（One∧Two∧Three∧Four∧Five）∨

（One∧Two∧¬Three∧¬Four∧Five）∨（One∧Two∧Three∧Four∧Five）

=（¬One∧¬Two∧Three∧Four∧¬Five）∨（¬One∧Two∧Three∧Four∧¬Five）∨

（One∧Two∧Three∧Four∧¬Five）∨（One∧Two∧Three∧Four∧Five）∨

（One∧Two∧¬Three∧¬Four∧Five）

一班

二班

三班

四班

五班

条件1

条件2

条件3

条件4

方案一

无

无

有

有

无

满足

满足

满足

满足

方案二

无

有

有

有

无

满足

满足

满足

满足

方案三

有

有

有

有

无

满足

满足

满足

满足

方案四

有

有

有

有

有

满足

满足

满足

满足

方案五

有

有

无

无

有

满足

满足

满足

满足

（1）如果1班有人选中，那么2班有人选中。

（2）假设5班有人选上那么1班与2班