应用离散数学（第2版）全套教学课件.pptx

命 题 逻 辑 《应用离散数学（第2版）》 第1章 第1章 命题逻辑 第2章 谓词逻辑 第3章 集合与关系 第4章 代数结构 第5章 图 第6章 有向图 目录 1.1 命题和逻辑连接词 1.2 命题公式及其真值表 1.3 命题公式的等价演算 1.4 命题公式的范式 1.5 命题公式的推理演算 1.6 逻辑门电路 逻辑是探索、阐述和确立有效推理原则的学科，最早由古希腊学者亚里士多德（Aristotle）创建。数理逻辑是用数学的方法来研究逻辑问题。数理逻辑也叫符号逻辑，它已在逻辑电路、自动控制、程序设计、人工智能以及计算机科学的其他领域有着广泛的应用。 利用计算的方法来代替人们思维中的逻辑推理过程，这种想法早在17世纪就有人提出过。 莱布尼茨（G.W.Leibniz）就曾经设想过能不能创造一种“通用的科学语言”，可以把推理过程像数学一样利用公式来进行计算，从而得出正确的结论。限于当时的条件，他的想法并没有实现，但是他的思想却是现代数理逻辑部分内容的萌芽。从这个意义上讲，莱布尼茨可以说是数理逻辑的先驱。 本书介绍数理逻辑的两个最基本，也是最重要的部分：命题逻辑和谓词逻辑。本章首先介绍命题逻辑。 命题逻辑是研究命题如何通过一些逻辑连接词构成更复杂的命题以及逻辑推理的方法。命题是指具有具体意义且又能判断它是真还是假的句子。 本章主要介绍命题、逻辑连接词、命题公式、命题公式的范式、命题公式的等价演算、命题公式的推理演算等命题逻辑中的有关内容。 1.1.1 命题 所谓命题，是指能区分真假的陈述句，这与中学数学中的命题定义是一样的。 命题可分为真命题和假命题。如果命题所表述的内容与客观实际相符，则称该命题是真命题；否则称之为假命题。 命题的这种真假属性称为命题的真值。当一个命题是真命题时，我们称它的真值为“真”，用T表示；当一个命题是假命题时，我们称它的真值为“假”，用F表示。 例1.1 判断下面的语句是否是命题。 （1）6是质数。 （2）5是有理数。 （3）2105年元旦是晴天。 （4）地球外存在智慧生物。 （5）现在是白天。 （6）王平是大学生。 （7） 。 （8） 。 （9）请不要吸烟！ （10）我正在说假话。 解 本例中，语句（1）、（2）、（3）、（4）、（5）、（6）、（7）是命题，语句（8）、（9）、（10）不是命题。 语句（1）是一个假命题，语句（2）是一个真命题。语句（3）和（4）也都是命题，虽然限于现在的认知，我们还不能确定语句（3）和（4）的真值，但它们的真值客观存在而且唯一。 命题的真假可能与该命题的范围、时间和空间有关。例如，语句（5），如果对生活在北京的人来说是真命题，则对居住在纽约的人来说便是假命题了。尽管如此，这里语句（5）的范围、时间、空间应是有所指的，是特定的，所以，它的真值也是客观存在而且唯一的，所以它也是命题。同样，对于语句（6），这里的人“王平”应是特指某个人，所以它们的真值也客观存在而且唯一，所以它们都是命题。 语句（8）不是命题，是因为根据变量x和y的不同取值情况它可真可假，即无唯一的真值，所以不是命题。而语句（9）不是命题，是因为该语句不是陈述句。 对于语句（10），若（10）的真值为“真”，即“我正在说假话”为真，则（10）这句话也应是假话，所以（10）的真值应为假，矛盾。反之，若（10）的真值为“假”，即“我正在说假话”为假，也就是“我正在说真话”，则（10）这句话也应是真话，所以（10）的真值应为“真”，也矛盾。于是（10）的真值无法确定，从而不是命题。 像例1.1中语句（10）这样由真推出假，又由假推出真的陈述句称为悖论。悖论的例子很多，例如“本命题是假的”这句话也是一个悖论，读者不妨试着分析一下。 命题还可以分为简单命题和复合命题。简单命题也称为原子命题，是一个不能再分解为更简单的陈述句的命题，如例1.1的命题（1）、（2）、（3）、（4）、（5）、（6）、（7）。 简单命题可以用小写英文字母p，q，r，…，p1，p2，p3，…等表示，例如，用p表示命题“6是质数”，用q表示命题“5是有理数”等。但是在各种论述和推理中，所出现的命题多数不是简单命题，而是由原子命题和自然语言中的连接词构成的复合命题，如下面的例1.2。 例1.2 将下列复合命题写成原子命题与连接词的复合。 （1）6是偶数是不对的。 （2）6是偶数且是3的倍数。 （3）6是偶数或是3的倍数。 （4）如果6是偶数