离散数学01-5

《离散数学01-5》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

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

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

6、======由此可见两公式的主析取范式不相等，因此，两公式不等价。（2）解=====47=======由此可见两公式的主合取范式相等，因此，两公式等价。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）定理47（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）分（1547）（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）定理47（4）用代入，用代入（5）分（4）（2）（6）公理3（

8、7）用代入，用，用代入（8）分（7）（5）2.2已知公理：及分离规则和代入规则。试证明（1）为