离散数学 贾振华 第一章

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

1、21世纪高等院校规划教材离散数学中国水利水电出版社1第1章命题逻辑1.1命题命题联结词1.2命题公式与解释1.3真值表与等价公式1.4对偶定理1.5范式1.6公式的蕴涵1.7其它联结词与最小联结词组1.8命题逻辑推理理论21.1命题及其表示法1.1.1命题把具有确定真假意义的陈述句，称为命题。如果一个句子是命题，必需满足以下条件：（1）该句子是具有判断性的陈述语句；（2）它有确定的真值，非真即假。31.1命题及其表示法例1.1.1判断下列语句是否为命题，若是命题，判断其真值。（1）10是素数。（2）f（x）=x2在[a，b]上连续。（3）北京是中国的首都。（4）1001+11=110

2、0（5）请勿喧哗！（6）你记住了吗？（7）这个风景真美呀！（8）x+y=741.1命题及其表示法由于命题只有真、假二个真值情况，所以命题逻辑也称为二值逻辑。例1.1.2判断下面语句是否为命题。（1）其它星球上有生命存在。（2）我正在说谎。51.1命题及其表示法命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如Ai，[10]，R等，例如A1：我是一名大学生。A1:我是一名大学生.[10]：我是一名大学生。R：我是一名大学生。表示命题的符号称为命题标识符，A1、[10]和R都是标识符。61.1命题及其表示法命题常量命题变元原子变元71.1.2命题联结词1否定联结词2合取联

3、结词3析取联结词4条件联结词5双条件联结词81.1.2命题联结词1否定联结词﹁PP﹁P0110PQP∧Q0000101001113析取联结词∨PQP∨Q0000111011112合取联结词∧9PQP→Q0010111001114条件联结词→5双条件联结词PQPQ0010101001111.1.2命题联结词101.2命题公式与解释1.2.1命题公式1.2.2命题公式的解释111.2.1命题公式1.定义命题公式，简称公式，定义为：（1）命题变元是公式；（2）如果P是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、PQ、PQ都是公式；（4）当且仅当能够有限次的应用(1

4、)、(2)、(3)所得到的包括命题变元、联结词和括号的符号串是才是公式。12命题公式是由命题变元、联结词和括号组成的，但并非由命题变元、联结词和括号组成的符号串都能成为命题公式。例如，下面的符号串都是公式：（（（（﹁P）∧Q）R）∨S）（（P﹁Q）（﹁R∧S））（﹁P∨Q）∧R以下符号串都不是公式：（（P∨Q）（∧Q））（∧Q）1.2.1命题公式132.命题的符号化可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译,也称为符号化。命题翻译时应注意下列事项：（1）确定所给句子是否为命题。（2）句子中联结词是否为命题联结词。（3）要正确的选择原子命题和合适的命

5、题联结词。（4）用正确的语法将原命题表示由原子命题、联结词和圆括号组成的合式公式。1.2.1命题公式14例1.2.1将下列命题符号化。（1）张莉既聪明又好学。（2）张莉虽然聪明但不好学。（3）仅当你走，我将留下。（4）上海到北京的14次列车是下午五点半或六点开。1.2.1命题公式15解：设P：张莉聪明；Q：张莉好学，则（1）张莉既聪明又好学，可符号化为P∧Q；（2）张莉虽聪明但不好学，可符号化为P∧（﹁Q）。（3）设P：你走；Q：我留下；这句话中“你走”是“我留下”的必要条件。因此命题可表示为QP。（4）设P：上海到北京的14次列车是五点半开；Q：上海到北京的14次列车是六点开；1

6、.2.1命题公式16汉语的意思是不可兼或，而逻辑联结词∨是“可兼或”，因此不能直接对两个命题析取。构造表如表1.2-1所示。PQ（4）命题PQ（PQ）0001001101101011101017例1.2.2将下列命题符号化。（1）假如上午不下雨，我去看电影，否则就在家里读书或看报。（2）我今天进城，除非下雨。（3）张三或李四都可以做这件事。（4）除非你努力，否则你将失败。（5）如果你和她都不固执己见的话，那么不愉快的事也不会发生了。（6）如果你和她不都是固执己见的话，那么不愉快的事也不会发生了。1.2.1命题公式18解：（1）设P：上午下雨；Q：我去看电影；R：我在家里读书；S

7、：我在家里看报。本命题可表示为：（PQ）∧（P（RS））。（2）设P：我今天进城；Q：今天下雨；这句话的意思是“如果今天不下雨，那么我就进城”，本可表示为QP。（3）设P：张三可以做这件事；Q：李四可以做这件事。这个命题可以理解为：张三可以做这件事，并且李四也可以做这件事。因此原命题可符号化为：P∧Q。19（4）设P：你努力；Q：你将失败。原命题可符号化为：PQ。（5）设P：你固执己见；Q：她固执己见；R：不愉快的事也不会发生。原命题可符