《离散数学课后习题合集.doc》由会员分享，可在线阅读，更多相关《离散数学课后习题合集.doc（153页珍藏版）》请在金锄头文库上搜索。
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）解= = = = =由此可见两公式的主合取范式相等，因此，两公式等价。36第二章 命题演算的推理理论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） 用代入，用代入，用代入（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）
