离散数学朱保平Word文档下载推荐.doc

离散数学朱保平Word文档下载推荐.doc

《离散数学朱保平Word文档下载推荐.doc》由会员分享，可在线阅读，更多相关《离散数学朱保平Word文档下载推荐.doc（47页珍藏版）》请在冰点文库上搜索。

（2）

当时

=

当=时

上式=

当时

当时，上式=，当时，上式=，因此，公式存在成真解释，存在成假解释，故公式可满足，但非永真。

（4）

上式=

当时，上式=，当时，上式=，因此，公式存在成真解释，存在成假解释，故公式可满足，但非永真。

1.3试求下列公式的成真解释和成假解释

（1）当时

原式=

当时，上式=，当时，上式=。

当时，上式=，当时，上式=，

因此，公式的成真解释为；

成假解释为。

当时，上式=；

当时，上式=。

1.4试写出下列公式的对偶式和内否式

（1）内否式为

消去“”得式子

对偶式=

（2）内否式为

消去“”得式子

对偶式为

（3）内否式为

（4）内否式为

1.5试证明联结词集合{}是完备的。

证明

因为，

所以，联结词集合可以表示集合。

又因为，联结词集合是完备的，即可以表示任何一个命题演算公式，所以可以表示任何一个命题演算公式，故联结词集合是完备的。

1.6试证明联结词集合不是完备的。

设集合是完备的，则由联结词集合的完备性定义知。

当全取为真时，上式左边=，右边=，矛盾。

因此不是完备的。

设集合是完备的，则由联结词集合的完备性定义知，其中表示“”。

1.7试求下列公式的析取范式和合取范式

=（析取范式）

=（合取范式）

=（合取范式和析取范式）

1.8试求下列公式的主析取范式和主合取范式

1.9用把公式化为主范式的方法判断下列各题中两式是否等价

=

由此可见两公式的主析取范式不相等，因此，两公式不等价。

由此可见两公式的主合取范式相等，因此，两公式等价。

47

第二章命题演算的推理理论

2.1用永真公理系统证明下列公式

（1）公理1

（2）公理13

（3）用代入

（4）分（3）

（1）

（5）分（4）

（1）

（6）公理11

（7）用代入

（8）公理7

（9）用代入

（10）分（9）（7）

（11）分（10）（5）

证明

（1）公理14

（2）用代入，用代入

（3）公理15

（4）定理

（5）

用代入，用代入，用代入

（6）分（5）（3）

（7）公理3

（8）

用代入，用代入，用代入

（9）分（8）

（2）

（10）分（9）（6）

（11）定理

（12）

（4）式中用代入，用代入，用代入

（13）分（12）（11）

（14）

（7）式中用代入，用代入，用代入

（15）分（14）（13）

（16）分（15）（10）

（1）公理11

（2）用代入

（3）定理

（4）用代入

（5）分（4）（3）

（6）公理12

（7）用代入

（8）公理3

（9）

（10）分（9）（5）

（11）分（10）（7）

（12）定理

（13）用代入

（14）分（13）（11）

（1）公理1

（2）用代入

（3）定理

（4）用代入，用代入

（5）分（4）

（2）

（6）公理3

（7）

用代入，用，用代入

（8）分（7）（5）

2.2已知公理：

及分离规则和代入规则。

试证明

（1）为定理

（2）为定理。

（1）公理

（2）公理

（3）用代入

（4）公理

（5）用代入，用代入

（6）分（5）

（1）

（7）分（6）（3）

（2）式中用代入，用代入

（9）分（8）（7）

（10）公理

（11）

用代入，用代入

（12）分（11）（9）

2.3用假设推理系统证明下列公式

（1）假设

（2）假设

（3）后件的否定

（4）公理15

（5）分（4）（3）

（6）分

（1）（5）

（7）分

（2）（5）

（6）（7）矛盾

由反证法推理定理知

，├

由推理定理知

（1）假设

（2）假设

（3）假设

（4）分

（1）（3）

（5）分

（2）（3）

（6）分（4）（5）

由假设推理过程的定义知

，，├

（1）假设

（2）假设

（4）公理10

（5）分（4）

（2）

（6）分（5）（3）

（7）分

（1）（6）

（1）假设

（2）公理8

（3）公理9

（3）式中用代入，用代入

（6）分（4）

（1）

（7）分（5）

（1）

（8）分

（2）（6）

（9）分（3）（6）

（10）

（2）式中用，用代入

（11）（3）式中用，用代入

（12）分（10）（7）

（13）分（11）（7）

（14）分（12）（8）

（15）分（13）（9）

（16）公理10

（17）用，用代入

（18）分（17）（14）

（19）分（18）（15）

├

2.4用归结原理证明下列公式

化为合取范式：

建立子句集

（2）

（6）

（1）（3）归结

（7）（5）（6）归结

（8）（4）（7）归结

（9）

（2）（8）归结

化为合取范式：

建立子句集：

（1）

（3）

（4）

（1）（3）归结

（5）

（2）（3）归结

（6）（4）（5）归结

（5）

（1）（4）归结

（6）

（2）（3）归结

（7）（5）（6）归结

化为子句集：

（3）

（1）

（2）归结

第三章谓词演算基础

3.1试把下列语句符号化

（1）如果我知道你不在家，我就不去找你了。

设表示知道不在家；

表示去找；

表示我；

表示你；

则原句表示为：

。

（2）他送给我这只大的红气球。

设表示送给；

表示为大的；

表示为红的；

表示为气球；

表示他，表示我，表示这只；

则原句译为：

（3）苏州位于南京与上海之间。

设表示位于与之间；

表示苏州，表示南京，表示上海；

（4）他既熟悉C++语言，又熟悉PASCAL语言。

设表示熟悉；

表示他，表示C++语言，表示PASCAL语言；

3.2试将下列语句符号化为含有量词的谓词演算公式：

（1）没有不犯错误的人。

设表示为人；

表示为错误；

表示犯。

（2）有不是奇数的质数。

设表示为奇数；

表示为质数。

（3）尽管有人能干，但未必一切人能干。

表示能干。

（4）鱼