离散数学第一章 3.ppt

21世纪高等院校规划教材离散数学 中国水利水电出版社 第1章 命题逻辑 1.1 命题命题联结词 1.2 命题公式与解释 1.3 真值表与等价公式 1.4 对偶定理 1.5 范式 1.6 公式的蕴涵 1.7 其它联结词与最小联结词组 1.8 命题逻辑推理理论 1.1 命题及其表示法 1.1.1 命题 把具有确定真假意义的陈述句，称为命题。 如果一个句子是命题，必需满足以下条件： （1）该句子是具有判断性的陈述语句； （2）它有确定的真值，非真即假。 1.1 命题及其表示法 例1.1.1 判断下列语句是否为命题，若是命题，判断其真值。 （1）10是素数。 （2）f（x）= x2在[a，b]上连续。 （3）北京是中国的首都。 （4）1001+11=1100 （5）请勿喧哗！ （6）你记住了吗？ （7）这个风景真美呀！ （8）x+y=7 1.1 命题及其表示法 由于命题只有真、假二个真值情况，所以命题逻辑也称为二值逻辑。 例1.1.2 判断下面语句是否为命题。 （1）其它星球上有生命存在。 （2）我正在说谎。 1.1 命题及其表示法 命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如Ai，[10]，R等，例如 A1：我是一名大学生。 A1:我是一名大学生. [10]：我是一名大学生。 R：我是一名大学生。 表示命题的符号称为命题标识符，A1、[10]和R都是标识符。 1.1 命题及其表示法 命题常量 命题变元 原子变元 1.1.2 命题联结词 1 否定联结词 2 合取联结词 3 析取联结词 4 条件联结词 5 双条件联结词 1.1.2 命题联结词 1 否定联结词﹁P 1.1.2 命题联结词 5 双条件联结词? 1.2 命题公式与解释 1.2.1 命题公式 1.2.2 命题公式的解释 1.2.1 命题公式 1.定义 命题公式，简称公式，定义为： （1）命题变元是公式； （2）如果P是公式，则﹁P是公式； （3）如果P、Q是公式，则P∧Q、P∨Q、P?Q、 P?Q都是公式； （4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号 串是才是公式。 1.2.1 命题公式 命题公式是由命题变元、联结词和括号组成的，但并非由命题变元、联结词和括号组成的符号串都能成为命题公式。 例如，下面的符号串都是公式： （（（（﹁P）∧Q）?R）∨S） （（P?﹁Q）?（﹁R∧S）） （﹁P∨Q）∧R 以下符号串都不是公式： （（P∨Q）?（∧Q）） （∧Q） 1.2.1 命题公式 2. 命题的符号化 可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译,也称为符号化。 命题翻译时应注意下列事项： （1）确定所给句子是否为命题。 （2）句子中联结词是否为命题联结词。 （3）要正确的选择原子命题和合适的命题联结词。 （4）用正确的语法将原命题表示由原子命题、联结词和圆括号组成的合式公式。 1.2.1 命题公式 1.2.1 命题公式 解：设P：张莉聪明；Q：张莉好学，则 （1）张莉既聪明又好学，可符号化为P∧Q； （2）张莉虽聪明但不好学，可符号化为P∧（﹁Q）。 （3）设P：你走；Q：我留下；这句话中“你走”是“我留下”的必要条件。因此命题可表示为Q?P。 （4）设P：上海到北京的14次列车是五点半开；Q：上海到北京的14次列车是六点开； 1.2.1 命题公式 例1.2.2 将下列命题符号化。 （1）假如上午不下雨，我去看电影，否则就在家里读书或看报。 （2）我今天进城，除非下雨。 （3）张三或李四都可以做这件事。 （4）除非你努力，否则你将失败。 （5）如果你和她都不固执己见的话，那么不愉快的事也不会发生了。 （6）如果你和她不都是固执己见的话，那么不愉快的事也不会发生了。 解：（1）设P：上午下雨；Q：我去看电影；R：我在家里读书；S：我在家里看报。本命题可表示为：（?P?Q）∧（P??（R?S））。 （2）设P：我今天进城；Q：今天下雨； 这句话的意思是“如果今天不下雨，那么我就进城”，本可表示为?Q?P。 （3）设P：张三可以做这件事；Q：李四可以做这件事。这个命题可以理解为：张三可以做这件事，并且李四也可以做这件事。因此原命题可符号化为：P∧Q。 （4）设P：你努力；Q：你将失败。原命题可符号化为：?P?Q。 （5）设P：你固执己见；Q：她固执己见；R：不愉快的事也不会发生。