离散数学命题逻辑

1、2021-10-281第九章第九章命题逻辑命题逻辑 数理逻辑是用数学方法研究思维规律的一门学科。所谓数学数理逻辑是用数学方法研究思维规律的一门学科。所谓数学方法是指方法是指:用一套数学的符号系统来描述和处理思维的形式与规律。用一套数学的符号系统来描述和处理思维的形式与规律。因此因此,数理逻辑又称为符号逻辑。本章介绍数理逻辑中最基本的内数理逻辑又称为符号逻辑。本章介绍数理逻辑中最基本的内容命题逻辑。首先引入命题、命题公式等概念。然后容命题逻辑。首先引入命题、命题公式等概念。然后,在此基础上在此基础上研究命题公式间的等值关系和蕴含关系研究命题公式间的等值关系和蕴含关系,并给出推理规则并给出推理规则

2、,进行命题进行命题演绎。演绎。主要内容如下：主要内容如下：9.1命题和命题联结词命题和命题联结词9.2命题公式命题公式9.3命题公式的等值关系和蕴含关系命题公式的等值关系和蕴含关系9.5命题演算的推理理论命题演算的推理理论2021-10-282 逻辑是探索、阐述和确立有效推理原则的学科，最早由逻辑是探索、阐述和确立有效推理原则的学科，最早由古希腊学者古希腊学者亚里士多德亚里士多德创建的。用数学的方法研究关于推理创建的。用数学的方法研究关于推理、证明等问题的学科就叫做数理逻辑，也叫做符号逻辑。、证明等问题的学科就叫做数理逻辑，也叫做符号逻辑。 利用计算的方法来代替人们思维中的逻辑推理过程，这利用

3、计算的方法来代替人们思维中的逻辑推理过程，这种想法早在十七世纪就有人提出过。种想法早在十七世纪就有人提出过。莱布尼茨莱布尼茨就曾经设想过就曾经设想过能不能创造一种能不能创造一种“通用的科学语言通用的科学语言”，可以把推理过程象数，可以把推理过程象数学一样利用公式来进行计算，从而得出正确的结论。由于当学一样利用公式来进行计算，从而得出正确的结论。由于当时的社会条件，他的想法并没有实现。但是它的思想却是现时的社会条件，他的想法并没有实现。但是它的思想却是现代数理逻辑部分内容的萌芽，从这个意义上讲，莱布尼茨的代数理逻辑部分内容的萌芽，从这个意义上讲，莱布尼茨的思想可以说是数理逻辑的先驱。思想可以说是

4、数理逻辑的先驱。2021-10-2831847年，英国数学家年，英国数学家布尔布尔发表了发表了逻辑的数学分析逻辑的数学分析，建立了建立了“布尔代数布尔代数”，并创造一套符号系统，利用符号来表，并创造一套符号系统，利用符号来表示逻辑中的各种概念。布尔建立了一系列的运算法则，利用示逻辑中的各种概念。布尔建立了一系列的运算法则，利用代数的方法研究逻辑问题，初步奠定了数理逻辑的基础。代数的方法研究逻辑问题，初步奠定了数理逻辑的基础。十九世纪末二十世纪初，数理逻辑有了比较大的发展，十九世纪末二十世纪初，数理逻辑有了比较大的发展，1884年，德国数学家弗雷格出版了年，德国数学家弗雷格出版了数论的基础数论的

5、基础一书，在一书，在书中引入量词的符号，使得数理逻辑的符号系统更加完备。书中引入量词的符号，使得数理逻辑的符号系统更加完备。对建立这门学科做出贡献的，还有美国人皮尔斯，他也在著对建立这门学科做出贡献的，还有美国人皮尔斯，他也在著作中引入了逻辑符号。从而使现代数理逻辑最基本的理论基作中引入了逻辑符号。从而使现代数理逻辑最基本的理论基础逐步形成，成为一门独立的学科。础逐步形成，成为一门独立的学科。2021-10-284 非欧几何的产生和集合论的悖论的发现非欧几何的产生和集合论的悖论的发现,说明数学本身还存说明数学本身还存在许多问题，为了研究数学系统的无矛盾性问题，需要以数学在许多问题，为了研究数学

6、系统的无矛盾性问题，需要以数学理论体系的概念、命题、证明等作为研究对象，研究数学系统理论体系的概念、命题、证明等作为研究对象，研究数学系统的逻辑结构和证明的规律，这样又产生了数理逻辑的另一个分的逻辑结构和证明的规律，这样又产生了数理逻辑的另一个分支支证明论。证明论。数理逻辑还发展了许多新的分支数理逻辑还发展了许多新的分支,如递归论、模型论等。递归如递归论、模型论等。递归论主要研究可计算性的理论，它和计算机的发展和应用有密切论主要研究可计算性的理论，它和计算机的发展和应用有密切的关系。模型论主要是研究形式系统和数学模型之间的关系。的关系。模型论主要是研究形式系统和数学模型之间的关系。数理逻辑近年

7、来发展特别迅速，主要原因是这门学科对于数数理逻辑近年来发展特别迅速，主要原因是这门学科对于数学其它分支如集合论、数论、代数、拓扑学等的发展有重大的学其它分支如集合论、数论、代数、拓扑学等的发展有重大的影响，特别是对计算机科学的发展起了推动作用。反过来，其影响，特别是对计算机科学的发展起了推动作用。反过来，其他学科的发展也推动了数理逻辑的发展。他学科的发展也推动了数理逻辑的发展。2021-10-285问题o 1.如何用符号有效地表示实际应用中的逻辑问题?o 2.如何用符号进行逻辑演算、推理和论证？o 3.如何将逻辑问题计算机化、自动化？2021-10-2869.1命题和命题联结词命题和命题联结词

8、9.1.1命题的概念命题的概念命题命题：是能分辨真假的陈述句。：是能分辨真假的陈述句。例例1判断下列语句是否是命题。判断下列语句是否是命题。（1）空气是人生存所必需的）空气是人生存所必需的（2）请把门关上。）请把门关上。（3）南京是中国的首都。）南京是中国的首都。（4）你吃饭了吗？）你吃饭了吗？（5）x=3。（6）明年春节是个大晴天。）明年春节是个大晴天。（7）我正在说谎。）我正在说谎。解解 语句（语句（1）,（3）,（5），），(6)是陈述句是陈述句（1），（），（3），），(6)是命题是命题.（7）是悖论）是悖论2021-10-287 用真值来描述命题是用真值来描述命题是“真真”还是还是“

9、假假”。分别用。分别用“1”和和“0”表示表示命题用大写的拉丁字母命题用大写的拉丁字母A、B、C、P、Q、或者带下标的大写的字母来表示。或者带下标的大写的字母来表示。例例2 判断下列陈述句是否是命题。判断下列陈述句是否是命题。P：地球外的星球上也有人；：地球外的星球上也有人；Q：小王是我的好朋友；：小王是我的好朋友；解解P、Q是命题是命题2021-10-2889.1.2命题联结词命题联结词 原子命题原子命题：由简单句形成的命题。：由简单句形成的命题。 复合命题复合命题：由一个或几个原子命题通过联结词的联接：由一个或几个原子命题通过联结词的联接而构成的命题。而构成的命题。例例3A：李明既是三好学

10、生又是足球队员。：李明既是三好学生又是足球队员。B：张平或者正在钓鱼或者正在睡觉。：张平或者正在钓鱼或者正在睡觉。C：如果明天天气晴朗，那么我们举行运动会。：如果明天天气晴朗，那么我们举行运动会。2021-10-289定义五种联结词（或称命题的五种运算）。定义五种联结词（或称命题的五种运算）。1.否定否定“”定义定义9-1设设P是一个命题，利用是一个命题，利用“”和和P组成的复合命题称组成的复合命题称为为P的的否命题否命题，记作，记作“P”(读作读作“非非P”)。命题命题P取值为真时，命题取值为真时，命题P取值为假；命题取值为假；命题P取值为假时，命题取值为假时，命题P取值为真。取值为真。例例

11、4设设P：上海是一个城市；：上海是一个城市；Q：每个自然数都是偶数。：每个自然数都是偶数。 P P 1001则有则有P：上海不是一个城市：上海不是一个城市;Q：并非每个自然数都是偶数。：并非每个自然数都是偶数。2021-10-28102合取合取“”定义定义9-2设设P和和Q是两个命题，由是两个命题，由P、Q利用利用“”组成的复合命题，称为组成的复合命题，称为合取式复合命题合取式复合命题，记作，记作“PQ”（读作（读作“P且且Q”）。）。当且仅当命题当且仅当命题P和和Q均取值为真时，均取值为真时，PQ才取值为真。才取值为真。 例例5设设P：我们去看电影。：我们去看电影。Q：房间里有十张桌子。则：

12、房间里有十张桌子。则PQ表示表示“我们去看电影并且房间里有十张桌子。我们去看电影并且房间里有十张桌子。”PQPQ0000101001112021-10-28113.析取析取“”定义定义9-3由命题由命题P和和Q利用利用“”组成的复合命题，称为组成的复合命题，称为析析取式复合命题取式复合命题，记作，记作“PQ”（读作（读作“P或或Q”）。）。当且仅当当且仅当P和和Q至少有一个取值至少有一个取值为真时，为真时，PQ取值为真。取值为真。 PQPQ000011101111例例6将命题将命题“他可能是他可能是100米或米或400米赛跑的冠军。米赛跑的冠军。”符号化。符号化。解令解令P：他可能是：他可能是

13、100米赛跑冠军；米赛跑冠军；Q：他可能是：他可能是400米赛跑冠军。米赛跑冠军。则命题可表示为则命题可表示为PQ。2021-10-2812设设P、Q是两个命题，是两个命题，P异或异或Q是是一个复合命题，记作一个复合命题，记作PQ。 PQPQ000011101110例例7今天晚上我在家看电视或去剧场看戏。今天晚上我在家看电视或去剧场看戏。令令P：今天晚上我在家看电视。：今天晚上我在家看电视。Q：今天晚上我去剧场看戏：今天晚上我去剧场看戏例例7中的命题可表示为中的命题可表示为PQ，或者表示为，或者表示为（PQ)(PQ)。由于由于“”可用可用“”，“”和和“”表示，故我表示，故我们不把它当作们不把

14、它当作基本基本联结词。联结词。2021-10-28134.蕴含蕴含“”定义定义9-4由命题由命题P和和Q利用利用“”组成的复合命题，称为组成的复合命题，称为蕴含式复合命题蕴含式复合命题，记作，记作“PQ”（读作（读作“如果如果P，则，则Q”）。）。当当P为真，为真，Q为假时，为假时，PQ为为假，否则假，否则PQ为真。为真。PQPQ001011100111例例8将命题将命题“如果我得到这本小说，那么我今夜就读完它。如果我得到这本小说，那么我今夜就读完它。”符号符号化。化。解解令令P：我得到这本小说；：我得到这本小说；Q：我今夜就读完它。：我今夜就读完它。于是上述命题可表示为于是上述命题可表示为P

15、Q。例例9若若P：雪是黑色的；：雪是黑色的；Q：太阳从西边升起；：太阳从西边升起；R：太阳从东边升起。则：太阳从东边升起。则PQ和和PR所表示的命题都是真的所表示的命题都是真的.2021-10-28145等值等值“”定义定义9-5由命题由命题P和和Q，利用，利用“”组成的复合命题组成的复合命题,称为称为等值式复合命题等值式复合命题，记作，记作“PQ”（读作（读作“P当且仅当当且仅当Q”）。）。当当P和和Q的真值相同时的真值相同时,PQ取真取真,否则取假。否则取假。 PQPQ001010100111例例10非本仓库工作人员，一律不得入内。非本仓库工作人员，一律不得入内。解解令令P：某人是仓库工作

16、人员；：某人是仓库工作人员；Q：某人可以进入仓库。：某人可以进入仓库。则上述命题可表示为则上述命题可表示为PQ。2021-10-2815 例例11黄山比喜马拉雅山高，当且仅当黄山比喜马拉雅山高，当且仅当3是素数是素数令令P：黄山比喜马拉雅山高；：黄山比喜马拉雅山高；Q：3是素数是素数本例可符号化为本例可符号化为PQ 从汉语的语义看，从汉语的语义看，P与与Q之间并无联系，但就联结之间并无联系，但就联结词词的定义来看，因为的定义来看，因为P的真值为假，的真值为假，Q的真值为真，的真值为真，所以所以PQ的真值为假。的真值为假。 对于上述五种联结词，应注意到：对于上述五种联结词，应注意到：复合命题的真

17、值只取决于构成它的各原子命题的真复合命题的真值只取决于构成它的各原子命题的真值，而与这些原子命题的内容含义无关。值，而与这些原子命题的内容含义无关。2021-10-28169.1.3命题符号化命题符号化利用联结词可以把许多日常语句符号化。基本步骤如下：利用联结词可以把许多日常语句符号化。基本步骤如下：（1）从语句中分析出各原子命题，将它们符号化；）从语句中分析出各原子命题，将它们符号化；（2）使用合适的命题联结词，把原子命题逐个联结起来，）使用合适的命题联结词，把原子命题逐个联结起来，组成复合命题的符号化表示。组成复合命题的符号化表示。2021-10-2817例例12用符号形式表示下列命题。用

18、符号形式表示下列命题。（1）如果明天早上下雨或下雪，那么我不去学校）如果明天早上下雨或下雪，那么我不去学校（2）如果明天早上不下雨且不下雪，那么我去学校。）如果明天早上不下雨且不下雪，那么我去学校。（3）如果明天早上不是雨夹雪，那么我去学校。）如果明天早上不是雨夹雪，那么我去学校。（4）只有当明天早上不下雨且不下雪时，我才去学校。）只有当明天早上不下雨且不下雪时，我才去学校。解解令令P：明天早上下雨；：明天早上下雨；Q：明天早上下雪；：明天早上下雪；R：我去学校。：我去学校。（2）（）（PQ）R； （1）（）（PQ）R；（4）R（PQ） （3）(PQ）R；2021-10-2818例例13将下列

19、命题符号化将下列命题符号化（1）派小王或小李出差；派小王或小李出差；（2）我们不能既划船又跑步；我们不能既划船又跑步；（3）如果你来了，那么他唱不唱歌将看你是否伴奏而定；如果你来了，那么他唱不唱歌将看你是否伴奏而定；解解（1）令令P：派小王出差；：派小王出差；Q：派小李出差。：派小李出差。命题符号化为命题符号化为PQ。 （2）令令P：我们划船；：我们划船；Q：我们跑步。则命题可：我们跑步。则命题可表示为表示为(PQ）。）。 （3）令）令P：你来了；：你来了；Q：他唱歌；：他唱歌；R：你伴奏。：你伴奏。则命题可表示为则命题可表示为P（QR）2021-10-2819（4）如果李明是体育爱好者，但不

20、是文艺爱好者，那么如果李明是体育爱好者，但不是文艺爱好者，那么李明不是文体爱好者李明不是文体爱好者（5）假如上午不下雨，我去看电影，否则就在家里看书。假如上午不下雨，我去看电影，否则就在家里看书。（4）令）令P：李明是体育爱好者；：李明是体育爱好者；Q：李明是文艺爱好者。：李明是文艺爱好者。则命题可表示为（则命题可表示为（PQ）（PQ）（5）令）令P：上午下雨；：上午下雨；Q：我去看电影；：我去看电影；R：我在家读书。：我在家读书。则命题可表示为（则命题可表示为（PQ）（PR）。）。解：解：2021-10-28201.判断下列语句哪些是命题，若是命题，则指出其真值。判断下列语句哪些是命题，若是

21、命题，则指出其真值。（1）只有小孩才爱哭。只有小孩才爱哭。（2）X+6=Y（3）银是白的。银是白的。（4）起来吧，我的朋友。起来吧，我的朋友。(是是假假) (不是不是)(是是真真) (不是不是)练练 习习2021-10-2821 2将下列命题符号化将下列命题符号化（1）我看见的既不是小张也不是老李。）我看见的既不是小张也不是老李。 解解令令P：我看见的是小张；：我看见的是小张；Q：我看见的是老李。：我看见的是老李。则该命题可表示为则该命题可表示为PQ （2）如果晚上做完了作业并且没有其它的事，如果晚上做完了作业并且没有其它的事，他就会看电视或听音乐。他就会看电视或听音乐。解解令令P：他晚上做完

22、了作业；：他晚上做完了作业；Q：他晚上有其它的事；：他晚上有其它的事；R：他看电视；：他看电视；S：他听音乐。：他听音乐。则该命题可表示为则该命题可表示为（PQ）（RS）2021-10-28229.2命题公式命题公式9.2.1命题公式的概念命题公式的概念1.命题常元命题常元:一个表示确定命题的大写字母。一个表示确定命题的大写字母。2命题变元命题变元:一个没有指定具体内容的命题符号。一个没有指定具体内容的命题符号。 一个命题变元当没有对其赋予内容时，它的真值一个命题变元当没有对其赋予内容时，它的真值不能确定，一旦用一个具体的命题代入，它的真值就确不能确定，一旦用一个具体的命题代入，它的真值就确定

23、了。定了。3.命题公式命题公式 命题公式（或简称公式）是由命题公式（或简称公式）是由0、1和命题变元以和命题变元以及命题联结词按一定的规则产生的符号串（或者说一及命题联结词按一定的规则产生的符号串（或者说一个表达式）。个表达式）。2021-10-2823定义定义9-6（命题公式的递归定义）（命题公式的递归定义）(1)0，1是命题公式；是命题公式；(2)命题变元是命题公式；命题变元是命题公式；(3)如果如果A是命题公式，则是命题公式，则A是命题公式；是命题公式；(4)如果如果A和和B是命题公式，则（是命题公式，则（AB），），(AB),(AB),(AB)也是命题公式；也是命题公式；有限次地利用上

24、述有限次地利用上述(1)-(4)而产生的符号串是命题公式。而产生的符号串是命题公式。例例1下列符号串是否为命题公式。下列符号串是否为命题公式。(1)P(QPR)；(2)(PQ)(QR)解解(1)不是命题公式。不是命题公式。(2)是命题公式。是命题公式。2021-10-2824注：从图论的观点看，每一命题公式都注：从图论的观点看，每一命题公式都可以用一棵二元树来表示，其中树的结可以用一棵二元树来表示，其中树的结点与联结词对应，而树叶则对应于命题点与联结词对应，而树叶则对应于命题变元。变元。2021-10-28259.2.2真值指派真值指派 命题公式代表一个命题，但只有当公式中的每一命题公式代表一

25、个命题，但只有当公式中的每一个命题变元都用一个确定的命题代入时，命题公式才个命题变元都用一个确定的命题代入时，命题公式才成为命题，有确定的真值。成为命题，有确定的真值。如果张老师来了，那么这个问题可以得到解决。如果张老师来了，那么这个问题可以得到解决。如果学校放假，那么我就不去学校。如果学校放假，那么我就不去学校。例如：例如：PR2021-10-2826 公式与其命题变元之间的真值关系，可以用真值公式与其命题变元之间的真值关系，可以用真值表的方法表示出来。表的方法表示出来。如果我们不关心命题变元和命题公式代表什么命题，如果我们不关心命题变元和命题公式代表什么命题，只关心命题变元的真值对命题公式

26、的真值的影响，那么只关心命题变元的真值对命题公式的真值的影响，那么我们就可以对命题变元用真值去代入。我们就可以对命题变元用真值去代入。定义定义9-7设设F为含有命题变元为含有命题变元P1，P2，,Pn的命题公的命题公式，对式，对P1，P2，,Pn分别指定一个真值分别指定一个真值,称为对公式称为对公式F的的一组一组真值指派真值指派。F(P1,P2,P3)=(P1P2)P32021-10-2827例例2给出公式给出公式F=(PQ)(QR)(PR）的真值表）的真值表。 解解公式公式F的真值表如下：的真值表如下：PQRPQQR(PQ)(QR)PRF0 0 00 0 00 0 10 0 10 1 00

27、1 00 1 10 1 11 0 01 0 01 0 11 0 11 1 01 1 01 1 11 1 10 00 01 11 11 11 11 11 10 00 00 01 10 00 00 01 11 11 10 01 10 00 00 01 10 00 00 00 01 10 01 10 00 00 01 10 01 11 11 10 02021-10-28289.2.3公式类型公式类型定义定义9-8如果对于命题公式如果对于命题公式F所包含的命题变元的任何一所包含的命题变元的任何一组真值指派，组真值指派，F的真值恒为真，则称公式的真值恒为真，则称公式F为为重言式重言式（或（或永真公永真公

28、式式），常用），常用“1”表示表示。相反地，若对于。相反地，若对于F所包含的命题变元的所包含的命题变元的任何一组真值指派，任何一组真值指派，F的真值恒为假，则称公式的真值恒为假，则称公式F为为矛盾式矛盾式（或（或永假公式永假公式），常用），常用“0”表示表示。如果至少有一组真值指派使公式。如果至少有一组真值指派使公式F的真值为真，则称的真值为真，则称F为为可满足公式可满足公式。例例3构造下列命题公式的真值表，并判断它们是何种类型的公式构造下列命题公式的真值表，并判断它们是何种类型的公式（1）（）（PQ）（PQ）；）；（2）（）（QP）（PQ）；）；（3）（）（PQ）（QR）（PR）。）。202

29、1-10-2829 解解令令F1=(PQ)(PQ)，F2=(QP)(PQ)F1和和F2的真值表如下：的真值表如下：PQPPQPQ(PQ)F1QPPQF20010101100011101101010010111001100101100由上可知：由上可知：F1是重言式是重言式,F2是矛盾式是矛盾式。 (3)的真值表没有画出，它是可满足公式。的真值表没有画出，它是可满足公式。2021-10-28309.3命题公式的等值关系和蕴含关系命题公式的等值关系和蕴含关系9.3.1命题公式的等值关系命题公式的等值关系定义定义9-9设设A和和B是两个命题公式是两个命题公式,P1,P2,Pn是所有出现是所有出现于于

30、A和和B中的命题变元中的命题变元,如果对于如果对于P1,P2,Pn的任的任一组真值指派一组真值指派,A和和B的真值都相同的真值都相同,则称公式则称公式A和和B等值等值,记为记为AB,称称AB为等值式为等值式。例如例如代数中令代数中令F1(x,y)=(x+y)2,F2(x,y)=x2+2xy+y2则则(x+y)2=x2+2xy+y2即即F1(x,y)=F2(x,y)类似地，在命题逻辑中类似地，在命题逻辑中例如例如令令F1(P1,P2)=P1P2F2(P1,P2)=P2P1则则P1P2P2P1即即F1(P1,P2)F2(P1,P2)2021-10-2831注注 意意：（1）符号）符号“”与与“”的

31、区别与联系。的区别与联系。“”不是联结词，不是联结词，AB不表示一个公式，它表示不表示一个公式，它表示两个公式间的一种关系，即等值关系。两个公式间的一种关系，即等值关系。“”是联结词，是联结词，AB是一个公式。是一个公式。 AB当且仅当当且仅当AB是永真公式。是永真公式。例如例如(PQ)(PQ)(PQ)(PQ)2021-10-2832（2）可以验证，可以验证，等值关系是等价关系等值关系是等价关系。即即自反性自反性：对任意公式：对任意公式A，有，有AA。对称性对称性：对任意公式：对任意公式A，B，若，若AB，则，则BA。可传递性可传递性：对任意公式：对任意公式A、B、C，若，若AB，BC，则，则

32、AC。（3）当）当A是重言式时，是重言式时，A1；当；当A是矛盾式时，是矛盾式时，则则A0。2021-10-28339.3.2基本的等值式基本的等值式设设P、Q、R是命题变元，下表中列出了是命题变元，下表中列出了24个最基本的等值式个最基本的等值式:编号编号 公公式式E1E1 E2E2 E3E3 E4E4 E5E5 E6E6 E7E7 PQQP交换律交换律PQQP交换律交换律(PQ)RP(QR)结合律结合律(PQ)RP(QR)结合律结合律P(QR)(PQ)(PR)分配律分配律P(QR)(PQ)(PR)分配律分配律P0P同一律同一律P1P同一律同一律P P1互否律互否律P P0互否律互否律 （

33、P）P双重否定律双重否定律PPP等幂律等幂律PPP等幂律等幂律2021-10-2834编编号号 公公式式E8E8 E9E9 E10E10 E11E12E13E14E15P11零一律零一律P00零一律零一律P（PQ）P吸收律吸收律P（PQ）P吸收律吸收律 （PQ） P Q德德.摩根定律摩根定律 （PQ） P Q德德.摩根定律摩根定律PQ PQPQ(PQ)( P Q)P(QR)(PQ)RPQ(PQ)(QP)PQ Q P2021-10-28359.3.3等值式的判别等值式的判别有两种方法：真值表方法，命题演算方法有两种方法：真值表方法，命题演算方法1、真值表方法、真值表方法例例1用真值表方法证明用真

34、值表方法证明E10： (P Q)PQ 解解令：令：A= (P Q)，B= PQ，构造，构造A，B以及以及AB的真值表如下：的真值表如下：由于公式由于公式AB所标记的列全为所标记的列全为1，因此，因此AB。 0PQP Q (P Q) P Q PQAB00111110110100111100101101000012021-10-2836例例2用真值表方法证明用真值表方法证明E11：PQP Q解解令令A=PQ，B= P Q构造构造A，B以及以及AB的真值表如下：的真值表如下：由于公式由于公式AB所标记的列全为所标记的列全为1，因此，因此AB.1PQ P P QPQAB0011110111111000

35、01101112021-10-2837例例3用真值表方法判断用真值表方法判断PQPQ是否成立是否成立. 解解令令A=PQ，B= PQ构造构造A，B以及以及AB的真值表的真值表 由于公式由于公式AB所标记的列不全为所标记的列不全为1，AB不是不是永真公式，因此永真公式，因此AB不成立。不成立。P P Q P QPQAB011111010010011001100111Q01012021-10-2838PQ P Q QPPQAB0011111011011101001101100111所以所以PQ QP例例4用真值表方法判断用真值表方法判断PQ QP是否成立是否成立. 解解令令A=PQ，B= Q P构

36、造构造A，B以及以及AB的真值表的真值表2021-10-2839代换实例o 定义: 设A是一个命题公式,P1,P2,Pn是其中出现的所有命题变元.n(1)用某些公式代换A中的某些命题变元n(2)若用命题公式Qi代换Pi,则必须同时用Qi代替公式A中的所有Pi. 这样代换后得到的新公式B称为公式A的一个代换实例2021-10-28402等值演算方法等值演算方法(1)代入规则代入规则代入规则代入规则对于重言式中的任一命题变元出现的每一对于重言式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是重言式。处均用同一命题公式代入，得到的仍是重言式。例如例如F=（PQ）（ QP）是重言式，若是重

37、言式，若用公式用公式AB代换命题变元代换命题变元P得公式得公式F1=（AB）Q）（ Q（AB），），F1仍是重言式。仍是重言式。2021-10-2841注意：因为注意：因为AB当且仅当当且仅当AB是重言式。是重言式。所以，若对所以，若对于等值式中的任一命题变元出现的每一处均用同一命题于等值式中的任一命题变元出现的每一处均用同一命题公式代入，则得到的仍是等值式公式代入，则得到的仍是等值式。例如例如 (PQ) P Q，即即 (PQ) P Q是永真公式是永真公式于是，用于是，用PS对对P进行代入进行代入得得 (PS)Q) (PS) Q结论：结论：基本等值式中基本等值式中P,Q,R可以是任意的命题公式

38、。可以是任意的命题公式。2021-10-2842(2)置换规则置换规则定义定义9-10设设C是命题公式是命题公式A的一部分（即的一部分（即C是公式是公式A中中连续的几个符号），且连续的几个符号），且C本身也是一个命题公式，则称本身也是一个命题公式，则称C为公式为公式A的的子公式子公式。 例如例如设公式设公式A=（ PQ）（PQ）（R S）。）。 则则 PQ，PQ，（，（PQ）（R S）等均是等均是A的子公式，的子公式，但但 P，P和和Q等均不是等均不是A的子公式。的子公式。2021-10-2843置换规则置换规则设设C是公式是公式A的子公式，的子公式，CD。如果将。如果将公式公式A中的子公式中

39、的子公式C置换成公式置换成公式D之后，之后，得到的公式是得到的公式是B，则，则AB。 若若A=( PQ)(PQ)(R S)B=( PQ)( PQ)(R S)则则AB 例如例如2021-10-2844(3)等值演算等值演算等值演算是指利用已知的一些等值式，根据置换等值演算是指利用已知的一些等值式，根据置换规则、代入规则以及等值关系的可传递性推导出另外规则、代入规则以及等值关系的可传递性推导出另外一些等值式的过程。一些等值式的过程。 由代入规则知前述的基本等值式，不仅对任意的命由代入规则知前述的基本等值式，不仅对任意的命题变元题变元P，Q，R是成立的，而且当是成立的，而且当P，Q，R分别为命分别为

40、命题公式时，这些等值式也成立题公式时，这些等值式也成立2021-10-2845例例2证明命题公式的等值关系：证明命题公式的等值关系：（PQ）（RQ）（PR）Q；证明证明（PQ）（RQ）（ PQ）( RQ)E11（ P R）QE3 (分配律分配律) (PR)QE10(德德.摩根定律摩根定律)(PR)QE11所以（所以（PQ）（RQ）（PR）Q2021-10-2846例例3证明下列命题公式的等值关系证明下列命题公式的等值关系(P Q) ( P ( P Q) P Q证明证明(P Q) ( P ( P Q)(P Q) ( P P) Q)E2(结合律结合律)(P Q) ( P Q)E7(等幂律等幂律)(

41、 P Q) (P Q)E1(交换律交换律) P (Q (P Q)E2(结合律结合律) P QE 1，E9(交换律，吸收律交换律，吸收律)2021-10-2847例例4判别下列公式的类型。判别下列公式的类型。（1）Q ( P( PQ)（2）(PQ) P解解(1)Q ( P( PQ)Q (P( PQ)E11,E6Q (P P)(PQ)E3 Q (1(PQ)E5Q (PQ)E4 Q P QE10(Q Q) PE1 ,E20E5 ,E8 所以所以Q ( P( PQ)是矛盾式。是矛盾式。2021-10-2848（2）(PQ) P( PQ) PE11 PE9 于是该公式是可满足式。于是该公式是可满足式。2

42、021-10-2849例例3证明下列命题公式的等值关系证明下列命题公式的等值关系PQ(PQ)(QP)E14PQPQQPPQ001111011000010010111111(PQ)(QP)根据代入规则，对任意命题公式根据代入规则，对任意命题公式A,BAB(AB)(BA)2021-10-2850 有了等值式，再由代入和替换定律可以得到许许多多的等值式。这些等值式还表明，同一个公式G可以有各种各样的表达方式。 经验表明，自觉地使用逻辑规律与不自觉地使用逻辑规律是完全不一样的。2021-10-2851例例试用较少的开关设计一个与如图有相同功能的电路。试用较少的开关设计一个与如图有相同功能的电路。 PQ

43、RSPS 解：将所示之开关电路用下述命令表示：解：将所示之开关电路用下述命令表示：（P Q S） （P S R）=（P S） （Q R） QRPS2021-10-2852例例将下面一段程序语言进行化简将下面一段程序语言进行化简:IfAthenifBthenXelseYelseifBthenXelseY解解将程序用流程图表示：将程序用流程图表示：TSTARTABBTFXYTFF从框图可知：执行从框图可知：执行X的条件为：的条件为：(AB) ( A B)=B (AA)=B执行执行Y的条件为：的条件为：( A B) (AB)= B因此这段程序可以简化为：因此这段程序可以简化为：IfBthenXels

44、eY2021-10-28539.3.4命题公式的蕴含关系命题公式的蕴含关系定义定义9-11设设A，B是两个公式，若公式是两个公式，若公式AB是重言式，即是重言式，即AB1，则称，则称公式公式A蕴含公式蕴含公式B，记作，记作AB。称称“AB”为为蕴含式蕴含式。注意：符号注意：符号“”和和“”的区别和联系与符号的区别和联系与符号“”与与“”的区别和联系类似。的区别和联系类似。 “”不是联结词，不是联结词，“AB”不是公式，它表示公式不是公式，它表示公式A与与B之间存在蕴含关系。之间存在蕴含关系。 “”是联系词，是联系词，AB是一个公式。是一个公式。AB当且仅当当且仅当AB是永真公式是永真公式。20

45、21-10-2854ABAB001011100111AB意味着意味着AB是永真公式，是永真公式，意味着对于命题变元意味着对于命题变元P1,P1,Pn的任意一组真值指派，的任意一组真值指派，A为真而为真而B为假的情形不可能发生，为假的情形不可能发生，即意味着当即意味着当A为真时，为真时，B也一定为真。也一定为真。2021-10-2855AB是偏序关系是偏序关系即即自反性自反性：AA。反对称反对称：若：若AB，BA，则，则AB。传递性传递性：若：若AB，BC，则，则AC。 反对称性的证明：反对称性的证明：设设AB且且BA，由定义由定义9-11AB1且且BA1于是于是AB(AB) (BA)E141

46、11因此因此AB2021-10-2856传递性的证明：传递性的证明：设设AB，BC，则则AB1，BC1( A B C) ( AB C)(AB) C) ( A (BC)(1 C) ( A 1)1 11 因此因此AC.于是于是ACA C ( A C) (BB)2021-10-28579.3.5基本的蕴含式基本的蕴含式编号编号蕴蕴含含式式I1P QPI2P QQI3PP QI4QP QI5 PPQI6QPQI7 (PQ)PI8 (PQ) Q设设P、Q、R是命题变元，下表中列出了是命题变元，下表中列出了16个最基本的蕴含式。个最基本的蕴含式。2021-10-2858编号编号蕴蕴含含式式I9P QP Q

47、或表示为：或表示为：P、QP QI10 P (P Q)Q P、(P Q)QI11P (PQ)QP、PQQI12 Q (PQ)P Q、PQPI13(PQ) (QR)PRPQ、QRPRI14(P Q) (PR) (QR)RP Q、PR、QRRI15PQ(P R)(Q R)I16PQ(P R)(Q R)2021-10-28599.3.6蕴含式的判别蕴含式的判别判定判定“AB”是否成立的问题可转化为判定是否成立的问题可转化为判定AB是否为重言式是否为重言式，有下述判定方法：，有下述判定方法：（1）真值表；）真值表；（2）等值演算；）等值演算；（3）假定前件）假定前件A为真，判断后件为真，判断后件B是否

48、为真；是否为真；（4）假定后件）假定后件B为假，判断前件为假，判断前件A是否为假。是否为假。2021-10-28601.真值表方法真值表方法例例4证明证明I14：(PQ)(PR)(QR) R证明证明令公式令公式F=(PQ)(PR)(QR)R，其真值表如下：其真值表如下：2021-10-2861PQRPQPRQR(PQ)(PR)(QR)F0000010100111001011101110011111111110101110111010001010111111111 公式公式F对任意的一组真值指派取值均为对任意的一组真值指派取值均为1，故，故F是重言式。是重言式。(PQ)(PR）（QR）R2021

49、-10-28622.等值演算方法等值演算方法例例5证明证明I11：P（PQ） Q证明证明（P（PQ）Q(变成证明它为永真变成证明它为永真) （P（ PQ）QE11 （ P （ PQ）QE10 （ PQ） （ PQ）E2 1代入规则代入规则,E5因此因此P（PQ） Q2021-10-28633.假定前件假定前件A真真假定前件假定前件A为真，检查在此情况下，其后件为真，检查在此情况下，其后件B是否也为真。是否也为真。ABAB001011100111证明令前件证明令前件 Q（PQ）为真，）为真，则则 Q为真为真,且且PQ为真。为真。于是于是Q为假，因而为假，因而P也为假。由此也为假。由此 P为真。为

50、真。故蕴含式故蕴含式I12成立。成立。例例6证明证明I12: Q（PQ） P即要证明即要证明 Q（PQ） P为永真为永真2021-10-28644、假定后件假定后件B假假假定后件假定后件B为假，检查在此情况下，其前件为假，检查在此情况下，其前件A是否也为假。是否也为假。例例7证明蕴含式证明蕴含式(PQ) (RS)(P R)(Q S)证明证明令后件令后件(P R)(Q S)为假，则为假，则P R为真，为真，Q S为假为假,于是于是P、R均为真，而均为真，而Q和和S至少一个为假。至少一个为假。由此可知由此可知PQ与与RS中至少一个为假中至少一个为假,因此因此(PQ) (RS)为假为假.故上述蕴含式

51、成立。故上述蕴含式成立。2021-10-28651判断下列等值式是否成立判断下列等值式是否成立（1）（）（PQ）（RQ）（PR）Q解（解（1）（）（PQ）（RQ）（ PQ）（ RQ）E11（ P R）QE3 （PR）QE10（PR）QE11练练 习习2021-10-2866（2）（）（P Q）（ PQ） （ PQ）（ QP）E6，E10 （PQ）（QP）E11 （PQ）E14 （ （P Q） （ PQ）（2） （PQ）（P Q）（ PQ）2021-10-28672判定蕴含式判定蕴含式是否成立是否成立解假定后件（解假定后件（PQ）（PR）为假，）为假，则则PQ为真，为真，PR为假。为假。由由PR

52、为假为假,得得P为真，为真，R为假。为假。又又PQ为真，故得为真，故得Q为真。为真。于是于是P为真，为真，QR为假。为假。从而从而P（QR）为假。）为假。因此蕴含式成立。因此蕴含式成立。)()()(RPQPRQP2021-10-28682判定判定是否成立是否成立)()()(RPQPRQP解法二解法二右式右式（ PQ）（ PR） （ PQ）（ PR）（P Q）（ PR）（P PR）（ Q PR）1（ P QR） P（ QR） P（QR）P（QR）所以所以成立成立)()()(RPQPRQP2021-10-28699.5命题演算的推理理论命题演算的推理理论9.5.1推理推理推理是由已知的命题得到新命

53、题的思维过程。推理是由已知的命题得到新命题的思维过程。 定义定义9-19设设A和和B是两个命题公式，如果是两个命题公式，如果AB，即如，即如果命题公式果命题公式AB为重言式，则称为重言式，则称B是前提是前提A的结论的结论或或从从A推出推出结论结论B。 一般地设一般地设H1，H2，,Hn和和C是一些命题公式是一些命题公式,若蕴含若蕴含式式H1H2HnC (*)成立，则称成立，则称C是前提集合是前提集合H1，H2，,Hn的结论的结论，或称从前提，或称从前提H1，H2，,Hn能推出结能推出结论论C。有时也记作。有时也记作H1，H2，,HnC2021-10-28709.5.2如何判断由一个前提集合能否

54、推出如何判断由一个前提集合能否推出某个结论某个结论 1、真值表法、真值表法对于命题公式对于命题公式中所有命题中所有命题变元的每一组真值指派作出该公式的真值表，看是否为变元的每一组真值指派作出该公式的真值表，看是否为永真永真。CHHHn)(212021-10-2871例例1考察结论考察结论C是否是下列前提是否是下列前提H1，H2的结论。的结论。（1）H1：PQ，H2：P，C：QPQ00011011解解 构造其真值表如下：构造其真值表如下：PQPQ（PQ）P(PQ)P)Q111011010101001001112021-10-2872（2）H1：PQ，H2：P，C：Q解解 构造其真值表如下：构造其

55、真值表如下：PQPQ(PQ)P1111101101000010(PQ)P)Q1011PQ00011011 在这里，我们不关心结论是真还是假，而主要关心由给定在这里，我们不关心结论是真还是假，而主要关心由给定的前提是否能推出这个结论来。的前提是否能推出这个结论来。2021-10-28732、等值演算方法、等值演算方法例例证明证明PRRQQP、分析：根据题意，需证明分析：根据题意，需证明PRRQQP)()(.)()(是永真公式是永真公式即需证明即需证明PRRQQPPRRRQQP)()( ()( ( PRQQP) )()( ( PRQQRQP) )()( ( PRQP)( PRQP)(1PRQP)(

56、)(PRRQQP证明证明PRRQQP) )( ()( (2021-10-28743、“形式证明形式证明”方法方法（1）基本述语）基本述语形式证明形式证明：一个描述推理过程的命题序列，其中每个：一个描述推理过程的命题序列，其中每个命题或者是已知的命题，或者是由某些前提所推得的结论，命题或者是已知的命题，或者是由某些前提所推得的结论，序列中最后一个命题就是所要求的结论，这样的命题序列称序列中最后一个命题就是所要求的结论，这样的命题序列称为形式证明。为形式证明。有效的证明有效的证明：如果证明过程中的每一步所得到的结论：如果证明过程中的每一步所得到的结论都是根据推理规则得到的，则这样的证明称作是有效的

57、。都是根据推理规则得到的，则这样的证明称作是有效的。有效的结论有效的结论：通过有效的证明而得到结论，称作是有：通过有效的证明而得到结论，称作是有效的结论。效的结论。2021-10-2875为了证明为了证明C是前提是前提H1，H2，,Hn的结论的结论,即需证明即需证明:当前提当前提H1，H2，,Hn均为真时，均为真时，C必为真。必为真。H1，Q1，H2，Q2，Hi，Q3，C例如例如通过构造一个命题序列，来描述这一推理过程。通过构造一个命题序列，来描述这一推理过程。2021-10-2876(2)推理规则推理规则前提引用规则前提引用规则：在证明的任何步骤上都可以引用前提。在证明的任何步骤上都可以引用

58、前提。结论引用规则结论引用规则：在证明的任何步骤上所得到的结论都可在证明的任何步骤上所得到的结论都可以在其后的证明中引用。以在其后的证明中引用。置换规则置换规则：在证明的任何步骤上，命题公式的子公式都在证明的任何步骤上，命题公式的子公式都可以用与它等值的其它命题公式置换。可以用与它等值的其它命题公式置换。代入规则代入规则：在证明的任何步骤上，重言式中的任一命题在证明的任何步骤上，重言式中的任一命题变元都可以用一命题公式代入，得到的仍是重言式。变元都可以用一命题公式代入，得到的仍是重言式。2021-10-2877常用的一些蕴涵关系常用的一些蕴涵关系I9P、QP QI10 P、P QQI11P、P

59、QQI12 Q、PQ PE2E2 (PQ)RP(QR),(PQ)RP(QR)I13PQ、QRPRE1E1 PQQP,PQQPE6E6 （ P）PPQ Q PE152021-10-2878例例2证明证明R(PQ)是前提是前提PQ,QR,PS,S的结论。的结论。 所以所以PQ，QR，PS，SR（PQ)编号编号公公式式依依据据（1）（2）（3）（4）（5）（6）（7）（8）PSSPPQQQRRR（PQ）前提（前提引入规则）前提（前提引入规则）前提（前提引入规则）前提（前提引入规则）（1），（），（2）；）；I12前提前提（3），（），（4）；）；I10前提前提（5），（），（6）；）；I11（4），

60、（），（7）；）；I92021-10-2879例例3证明证明RS是前提是前提P（QS），），RP和和Q的有效结论。的有效结论。证明证明 编号编号公公式式依依据据(1)(2)(3)(4)(5)(6)(7)(8)(9)RPRPP（QS）R（QS）R（QS）Q（RS）QRSRS前提前提（1）；）；E11前提前提（2），（），（3）；）；I13（4）；）；E11（5）；）；E1，E2前提前提（6），（），（7）；）；I10（8）；）；E112021-10-2880蕴含证明规则：蕴含证明规则：证明证明P（QR） P（ QR） （PQ）R（PQ）R（ P Q）R,)()(RQPRQPE132021-10-