离散数学朱保平.doc

1、第一章 命题演算基础1.1 判断下列语句是否为命题，若是请翻译为符号公式；若不是说明由。（1）请给我一支笔！（2）火星上有生物。（3）（4）只有努力工作，方能把事情做好。（5）如果嫦娥是虚构的，而圣诞老人也是虚构的，那么许多孩子受骗了。解（1）不为命题，因为它不是陈述句。（2）是命题，用命题变元表示该命题。（3）不为命题，虽为陈述句，但不能判断其真假性。（4）是命题。设表示努力工作，表示把事情做好，则原句翻译为命题公式。（5）是命题。设表示嫦娥是虚构的，表示圣诞老人也是虚构的，表示许多孩子受骗了，则原句翻译为。1.2 试判定下列公式的永真性和可满足性。（1）解（1）当时，原式= =当=时，上式

2、=；当时，上式=，因此公式存在成真解释，存在成假解释，故公式可满足，但非永真。（2）解当时原式= = =当=时 上式= = =当=时 上式= = = =当时，上式=，因此公式存在成真解释，存在成假解释，故公式可满足，但非永真。（3）解当时原式= = = 当时 上式= = 当时，上式=，当时，上式=，因此，公式存在成真解释，存在成假解释，故公式可满足，但非永真。（4）解当时原式= = = =当时上式= = =当时，上式=，当时，上式=，因此，公式存在成真解释，存在成假解释，故公式可满足，但非永真。1.3 试求下列公式的成真解释和成假解释（1）解（1）当时 原式= = =当时，上式=，当时，上式=

3、。当时 原式= =当时上式= = =当时上式= = =当时，上式=，当时，上式=，因此，公式的成真解释为；成假解释为。（2）解当时 原式= = = = 当时，上式=；当时，上式=。当时 原式= = = =因此，公式的成真解释为；成假解释为。（3）解当时 原式= = = 当时 上式= = = 当时，上式=；当时，上式=。 当时 上式= = 当时 原式= = = =因此，公式的成真解释为；成假解释为。（4）解当时 原式= = = 当时 上式= = = 当时 上式= = = 当时，上式=；当时，上式=。 当时 原式= = = = 当时，上式=；当时，上式=。因此，公式的成真解释为；成假解释为。1.4

4、 试写出下列公式的对偶式和内否式（1）（2）（3）（4）解（1） 内否式为 消去“”得式子 对偶式=（2）内否式为 消去“”得式子 对偶式为（3）内否式为 消去“”得式子 对偶式为（4）内否式为 消去“”得式子 对偶式为1.5 试证明联结词集合是完备的。证明 因为， 所以，联结词集合可以表示集合。又因为，联结词集合是完备的，即可以表示任何一个命题演算公式，所以可以表示任何一个命题演算公式，故联结词集合是完备的。1.6 试证明联结词集合不是完备的。证明 设集合是完备的，则由联结词集合的完备性定义知。当全取为真时，上式左边=，右边=，矛盾。 因此不是完备的。 设集合是完备的，则由联结词集合的完备性

5、定义知，其中表示“”。当全取为真时，上式左边=，右边=，矛盾。 因此不是完备的。1.7 试求下列公式的析取范式和合取范式（1）解原式= = =（析取范式） = = =（合取范式）（2）解原式= = = =（合取范式和析取范式）（3）解原式= =（合取范式） = = =（析取范式）（4）解原式= = =（析取范式） = = = = = = =（合取范式）1.8 试求下列公式的主析取范式和主合取范式（1）解原式= = = = = = = = =（2）解原式= = = = = = = = =（3）解原式= = = = （4）解原式= = = = = = =1.9 用把公式化为主范式的方法判断下列各题

6、中两式是否等价（1）解（1）= = =由此可见两公式的主析取范式不相等，因此，两公式不等价。（2）解= = = = =由此可见两公式的主合取范式相等，因此，两公式等价。47第二章 命题演算的推理理论2.1 用永真公理系统证明下列公式（1）证明（1） 公理1（2） 公理13（3） 用代入（4） 分（3）（1）（5） 分（4）（1）（6） 公理11（7） 用代入（8） 公理7（9） 用代入（10） 分（9）（7）（11） 分（10）（5）（2）证明 （1） 公理14（2） 用代入，用代入（3） 公理15（4） 定理（5）用代入，用代入， 用代入（6） 分（5）（3）（7） 公理3（8） 用代入，用

7、代入，用代入（9） 分（8）（2）（10） 分（9）（6）（11） 定理（12）（4）式中用代入，用代入，用代入（13） 分（12）（11）（14） （7）式中用代入，用代入，用代入（15） 分（14）（13）（16） 分（15）（10）（3）证明（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）（4）证明 （1） 公理1（2） 用代入（3） 定理（4） 用代入，用代入（5） 分（4）（2

8、）（6） 公理3（7）用代入，用，用代入（8） 分（7）（5）2.2 已知公理： 及分离规则和代入规则。试证明（1）为定理 （2）为定理。证明（1） 公理（2） 公理（3） 用代入（4） 公理（5）用代入，用代入（6） 分（5）（1）（7） 分（6）（3）（8）（2）式中用代入，用代入（9） 分（8）（7）（10） 公理（11） 用代入，用代入（12） 分（11）（9）2.3 用假设推理系统证明下列公式（1）证明（1） 假设（2） 假设（3） 后件的否定（4） 公理15（5） 分（4）（3）（6） 分（1）（5）（7） 分（2）（5）（6）（7）矛盾由反证法推理定理知，由推理定理知（2）证明

9、（1） 假设（2） 假设（3） 假设（4） 分（1）（3）（5） 分（2）（3）（6） 分（4）（5）由假设推理过程的定义知，由推理定理知（3）证明 （1） 假设（2） 假设（3） 假设（4） 公理10（5） 分（4）（2）（6） 分（5）（3）（7） 分（1）（6）由假设推理过程的定义知，由推理定理知（4）证明 （1） 假设（2） 公理8（3） 公理9（4）（2）式中用代入，用代入（5）（3）式中用代入，用代入（6） 分（4）（1）（7） 分（5）（1）（8） 分（2）（6）（9） 分（3）（6）（10）（2）式中用，用代入（11）（3）式中用，用代入（12） 分（10）（7）（13） 分（

10、11）（7）（14） 分（12）（8）（15） 分（13）（9）（16） 公理10（17） 用，用代入（18） 分（17）（14）（19） 分（18）（15）由假设推理过程的定义知由推理定理知2.4 用归结原理证明下列公式（1）证明化为合取范式：=建立子句集（1） （2）（3）（4）（5）（6） （1）（3）归结（7） （5）（6）归结（8） （4）（7）归结（9） （2）（8）归结（2）证明 化为合取范式： = = 建立子句集： （1） （2） （3） （4） （1）（3）归结 （5） （2）（3）归结 （6） （4）（5）归结（3）证明 化为合取范式： = 建立子句集： （1） （2）（3

11、）（4）（5） （1）（4）归结（6） （2）（3）归结（7） （5）（6）归结（4）证明 化为合取范式： = 化为子句集： （1） （2）（3） （1）（2）归结第三章 谓词演算基础3.1试把下列语句符号化（1）如果我知道你不在家，我就不去找你了。解设表示知道不在家；表示去找；表示我；表示你；则原句表示为：。（2）他送给我这只大的红气球。解设表示送给；表示为大的；表示为红的；表示为气球；表示他，表示我，表示这只；则原句译为：。（3）苏州位于南京与上海之间。解设表示位于与之间；表示苏州，表示南京，表示上海；则原句表示为：。（4）他既熟悉C+语言，又熟悉PASCAL语言。解设表示熟悉；表示他，表示C+语言，表示PASCAL语言；则原句译为：。3.2 试将下列语句符号化为含有量词的谓词演算公式：（1）没有不犯错误的人。解设表示为人；表示为错误；表示犯。则原句译为：。（2）有不是奇数的质数。解设表示为奇数；表示为质数。则原句译为：。（3）尽管有人能干，但未必一切人能干。解设表示为人；表示能干。则原句译为：。（4）鱼