离散数学及其应用第3章-命题演算与推理(上)课件.ppt

1、2022-8-5计算机应用技术研究所计算机应用技术研究所11离散数学离散数学Discrete Mathematics汪荣贵汪荣贵 教授教授合肥工业大学计算机与信息学院合肥工业大学计算机与信息学院2022-8-5计算机应用技术研究所计算机应用技术研究所2第第3 3章章 命题演算与推理命题演算与推理（上）（上）2022-8-52022-8-5 命题公式与等值演算命题公式与等值演算2 23 3 命题的概念与运算命题的概念与运算1 1&命题演算与推理命题演算与推理(上上)3 联结词的完备集2022-8-5计算机应用技术研究所计算机应用技术研究所4命题的概念与运算命题的概念与运算&命题的概念与运算命题的

2、概念与运算J 逻辑与命题逻辑逻辑与命题逻辑4 命题的基本概念命题的基本概念4 命题的常用联结词命题的常用联结词2022-8-5计算机应用技术研究所计算机应用技术研究所6&逻辑学逻辑学辩证逻辑辩证逻辑：研究人的思维中的辩证法。例如：用全：研究人的思维中的辩证法。例如：用全面的和发展的观点观察事物；具体问题具体分析；面的和发展的观点观察事物；具体问题具体分析；实践是检查事物正误的唯一标准；等等。实践是检查事物正误的唯一标准；等等。形式逻辑形式逻辑：研究人的思维的形式和一般规律。本课：研究人的思维的形式和一般规律。本课程只关心形式逻辑。程只关心形式逻辑。2022-8-5计算机应用技术研究所计算机应用

3、技术研究所7&人类的思维规律人类的思维规律人类的思维过程：人类的思维过程：通过学习掌握概念和判断，然通过学习掌握概念和判断，然后进行推理，即：后进行推理，即：概念概念 判断判断 推理推理 推理：推理：由若干个已知的判断由若干个已知的判断(前提前提)，推出新的判，推出新的判断断(结论结论)的思维过程。的思维过程。正确的思维：正确的思维：概念清楚，判断正确，推理合乎逻辑概念清楚，判断正确，推理合乎逻辑2022-8-5计算机应用技术研究所计算机应用技术研究所8&逻辑推理实例逻辑推理实例公安人员审查一件盗窃案，已知的事实如下：公安人员审查一件盗窃案，已知的事实如下：甲或乙盗窃了录音机；甲或乙盗窃了录音

4、机；若甲盗窃者，则作案时间不会发生在午夜前；若甲盗窃者，则作案时间不会发生在午夜前；若乙的证词正确，则午夜时屋里的灯光未灭；若乙的证词正确，则午夜时屋里的灯光未灭；若乙的证词不正确，则作案时间发生在午夜前；若乙的证词不正确，则作案时间发生在午夜前；午夜时屋里的灯光灭了。午夜时屋里的灯光灭了。问：盗窃者是谁？问：盗窃者是谁？2022-8-5计算机应用技术研究所计算机应用技术研究所9&逻辑推理实例逻辑推理实例前提：甲或乙盗窃了录音机；若甲盗窃了录音机，则作案时间不可能发生在午夜前；若乙的证词正确，则午夜时屋里的灯光没有灭；若乙的证词不正确，则作案时间发生在午夜前；午夜时屋里的灯光熄灭了。结论：后承

5、关系，推理后承关系，推理盗窃录音机的是乙2022-8-5计算机应用技术研究所计算机应用技术研究所10&学习逻辑的目的学习逻辑的目的u 各门科学都是在特殊领域的思维推理各门科学都是在特殊领域的思维推理活动活动,故逻辑是一切科学的公共基础故逻辑是一切科学的公共基础.u 逻辑思维能力是学习、工作乃至日常逻辑思维能力是学习、工作乃至日常生活中的重要能力生活中的重要能力.2022-8-5计算机应用技术研究所计算机应用技术研究所11&古典逻辑古典逻辑亚里士多德的亚里士多德的三段论三段论(syllogismsyllogism)从两个前提推出一个结论的逻辑论证形式从两个前提推出一个结论的逻辑论证形式:1.大前

6、提(major premise)人都是两足动物人都是两足动物 2.小前提(minor premise)希腊人都是人希腊人都是人 3.结论(conclusion)希腊人都是两足动物希腊人都是两足动物2022-8-5计算机应用技术研究所计算机应用技术研究所12&数理逻辑数理逻辑数理逻辑的创始人数理逻辑的创始人德国数学家莱布尼茨德国数学家莱布尼茨1646-17161646-1716英国数学家布尔英国数学家布尔1815-18641815-1864德国数学家弗雷格德国数学家弗雷格1848-19251848-19252022-8-5计算机应用技术研究所计算机应用技术研究所13&莱布尼茨莱布尼茨Gottfr

7、ied Wilhelm Leibniz(1646-1716)Gottfried Wilhelm Leibniz(1646-1716)首先使用首先使用“数理逻辑数理逻辑”这个术语这个术语 LeibnizLeibnizs Dream:s Dream:把推理归结为把推理归结为(符号符号)计算计算.提出提出“思维演算思维演算”的思想：的思想：“发生争论时我们可以简单地说发生争论时我们可以简单地说:让我们计让我们计算一下吧算一下吧,看谁正确看谁正确.”2022-8-5计算机应用技术研究所计算机应用技术研究所14&布布 尔尔George Boole(1815-1864)1847 1847年的论文年的论文:

8、逻辑的数学分析逻辑的数学分析:论演绎推理的演算法论演绎推理的演算法.发明了布尔代数发明了布尔代数(逻辑代数逻辑代数,命题代数命题代数,布尔逻辑布尔逻辑)，初步实现了初步实现了LeibnizLeibniz梦想。梦想。布尔代数亦可解释成集合代数布尔代数亦可解释成集合代数,开关代数，是计开关代数，是计算机数字逻辑的基础。算机数字逻辑的基础。附注附注:Augustus de Morgan(1806-1871):Augustus de Morgan(1806-1871)几乎同时独立几乎同时独立地做出重要贡献地做出重要贡献.2022-8-5计算机应用技术研究所计算机应用技术研究所15&弗雷格弗雷格Frie

9、drich Ludwig Gottlob Frege(1848-1925)18791879年的重要著作：年的重要著作：概念文字概念文字:一种模仿算术语言构造的纯思维的形式语言一种模仿算术语言构造的纯思维的形式语言 是第一个公理化谓词逻辑系统是第一个公理化谓词逻辑系统 是自是自AristotleAristotle以来逻辑的最重要进展以来逻辑的最重要进展 基本实现了基本实现了LeibnizLeibniz梦想梦想2022-8-5计算机应用技术研究所计算机应用技术研究所16&数理逻辑的概念数理逻辑的概念u 用数学方法研究用数学方法研究演绎推理演绎推理的一门数学学科的一门数学学科u 数学方法数学方法通过

10、引进一整套形式化符号系统通过引进一整套形式化符号系统的方法。因此，数理逻辑有时候也称为的方法。因此，数理逻辑有时候也称为符号逻辑符号逻辑u 数理逻辑的构成数理逻辑的构成 一套符号体系一套符号体系 +一组运算规则一组运算规则2022-8-5计算机应用技术研究所计算机应用技术研究所17&数理逻辑的内容数理逻辑的内容u 数理逻辑包括：数理逻辑包括：命题逻辑、谓词逻辑、公理化集合论、命题逻辑、谓词逻辑、公理化集合论、递归论、模型论、证明论递归论、模型论、证明论u 本课程只讨论本课程只讨论“命题逻辑命题逻辑”和和“谓词逻谓词逻辑辑”2022-8-5计算机应用技术研究所计算机应用技术研究所18&命题逻辑命

11、题逻辑命题逻辑也称命题演算，或语句逻辑命题逻辑也称命题演算，或语句逻辑。研究内容：研究内容：（1 1）研究以）研究以命题为基本单位命题为基本单位构成的构成的前提和结论之前提和结论之间的可推导关系间的可推导关系 （2 2）研究）研究什么是命题什么是命题？（3 3）研究）研究如何表示命题如何表示命题？（4 4）研究）研究如何由一组前提推导一些结论如何由一组前提推导一些结论？2022-8-5计算机应用技术研究所计算机应用技术研究所19&数理逻辑与软件数理逻辑与软件2022-8-5计算机应用技术研究所计算机应用技术研究所20&数理逻辑与硬件数理逻辑与硬件&命题的概念与运算命题的概念与运算4 逻辑与命题

12、逻辑逻辑与命题逻辑J 命题的基本概念命题的基本概念4 命题的常用联结词命题的常用联结词2022-8-5计算机应用技术研究所计算机应用技术研究所22&命题的概念命题的概念2022-8-5计算机应用技术研究所计算机应用技术研究所23&命题的概念命题的概念 真命题真命题：命题表达的内容为真或者说命题的取值为真；假命题假命题：否则命题表达的内容为假或者说命题的取值为假；真值真值:命题或真或假的取值。2022-8-5计算机应用技术研究所计算机应用技术研究所24&命题举例命题举例（1 1）合肥是安徽的省会。合肥是安徽的省会。（2 2）中国是世界上人口最多的国家。中国是世界上人口最多的国家。（3 3）圆周率

13、圆周率 是一个有理数。是一个有理数。（4 4）整数整数 3 3 能被能被 2 2 整除。整除。（5 5）小张是个大学生。小张是个大学生。（6 6）今天是你的生日。今天是你的生日。（7 7）2100 2100 年元旦是晴天。年元旦是晴天。（8 8）地球外的星球上也有人。地球外的星球上也有人。（9 9）我正在说假话。我正在说假话。（1010）满山的杜鹃花，满山的杜鹃花，真让人心旷神怡！真让人心旷神怡！（1111）请把门关上。请把门关上。（1212）你是饿了吗？你是饿了吗？【分析】语句语句(1)(1)到到(8)(8)都是命题。其中：语句都是命题。其中：语句(1)(1)、(2)(2)的判断都符合实际情

14、况，因而都是真的判断都符合实际情况，因而都是真值为值为的命题，的命题，即为真命题；即为真命题；语句语句(3),(4)(3),(4)的判断都是错误的，因而都是真的判断都是错误的，因而都是真值为值为的命题，即为假命题；的命题，即为假命题；对于语句对于语句(5)(5)、(6)(6)、(7)(7)、(8)(8)，其真值虽然，其真值虽然是唯一确定的，但是确定正确这些命题真值的是唯一确定的，但是确定正确这些命题真值的相关条件均未知，相关条件均未知，故这些命题的真值均为未知故这些命题的真值均为未知。2022-8-5计算机应用技术研究所计算机应用技术研究所25&命题举例命题举例【分析】语句语句（9 9）虽然）

15、虽然是一个陈述句，是一个陈述句，但是但是如将其作为命题，如将其作为命题，则根据该命题所表达的含义则根据该命题所表达的含义可知可知，其，其真值的取值无论为真还是为假，都会产真值的取值无论为真还是为假，都会产生矛盾生矛盾。因此，该。因此，该陈述句是一个悖论，其真值既陈述句是一个悖论，其真值既不能为不能为真，也不能为假真，也不能为假，不能，不能作为命题作为命题。语句语句(1010)、(1111)、(1212)均均不是陈述句不是陈述句，都，都不能不能形成一形成一个逻辑上的是非判断，个逻辑上的是非判断，因而都不能成为因而都不能成为命题。命题。2022-8-5计算机应用技术研究所计算机应用技术研究所26&

16、命题举例命题举例2022-8-5计算机应用技术研究所计算机应用技术研究所27&命题举例命题举例【注意注意】一切没有判断内容的句子都不能作为命题一切没有判断内容的句子都不能作为命题，如命令句、感叹句、疑问句、祈使句、二义性的陈如命令句、感叹句、疑问句、祈使句、二义性的陈述句等。述句等。【解解】语句（1）到（8）都是命题，其中语句（1）、（2）为真命题，命题（3）、（4）是假命题，命题（5）、（6）、（7）、（8）的真值未知。语句（9）到（12）都不是命题。2022-8-5计算机应用技术研究所计算机应用技术研究所28&命题的基本概念命题的基本概念【定义定义】对于任意一个给定的命题，当它不能再分解为

17、更加简单的陈述句时，则称该命题为原原子命题子命题；否则，称之为复合命题复合命题。2022-8-5计算机应用技术研究所计算机应用技术研究所29&命题的基本概念命题的基本概念【例题】父亲让两个孩子（一男一女）在后院玩耍，并嘱咐他们不要把身上搞脏。然而，在玩的过程中，两个孩子都在额头上沾了泥。当孩子们回来后，父亲首先说他们当中至少有一个人额头上有泥，然后问每个孩子能否确定自己额头上是否有泥，两个孩子都说不能；可是当父亲第二次问同样问题时，两个孩子都说可以。假设：（1）每个孩子都可以看到对方的额头上是否有泥，但不能看见自己的额头；（2）两个孩子都很诚实并且都同时回答每一次提问。试分析两孩子能够做出正确

18、判断的原因。2022-8-5计算机应用技术研究所计算机应用技术研究所30&命题的基本概念命题的基本概念2022-8-5计算机应用技术研究所计算机应用技术研究所31&命题的基本概念命题的基本概念2022-8-5计算机应用技术研究所计算机应用技术研究所32&小小 结结J 命题一定是陈述句，但并非一切陈命题一定是陈述句，但并非一切陈述句都是命题。述句都是命题。J 命题的真值有时可明确给出，有时命题的真值有时可明确给出，有时还需要依靠还需要依靠环境、条件、时间、实际环境、条件、时间、实际情况情况才能确定其真值。才能确定其真值。&命题的概念与运算命题的概念与运算4 逻辑与命题逻辑逻辑与命题逻辑4 命题的

19、基本概念命题的基本概念J 命题的常用联结词命题的常用联结词2022-8-5计算机应用技术研究所计算机应用技术研究所34&联结词的概念联结词的概念 命题可以通过逻辑联结词逻辑联结词(逻辑运算逻辑运算)构成新的命题复合命题。复合命题的真值依赖于其中简单命题的真值。2022-8-5计算机应用技术研究所计算机应用技术研究所35&联结词举例联结词举例 【例例】（1 1）期中考试，张三）期中考试，张三没有没有考及格。考及格。（2 2）其中考试，张三和李四）其中考试，张三和李四都都考及格了。考及格了。（3 3）期中考试，张三和李四中）期中考试，张三和李四中有人有人考了考了9090分。分。（4 4）如果如果张

20、三能考张三能考9090分，分，那么那么李四也能考李四也能考9090分。分。（5 5）张三能考）张三能考9090分，分，当且仅当当且仅当李四也能考李四也能考9090分。分。2022-8-5计算机应用技术研究所计算机应用技术研究所36&五个常用联结词五个常用联结词Negation Negation (NOT)(NOT)否定词否定词 ：Conjunction Conjunction (AND)(AND)合取词合取词 ：Disjunction Disjunction (OR)(OR)析取词析取词Implication Implication (if then)(if then)蕴涵词蕴涵词 Bicon

21、ditionalBiconditional (if and only if)(if and only if)等价词等价词2022-8-5计算机应用技术研究所计算机应用技术研究所37372022-8-5&“非非”运算运算2022-8-5计算机应用技术研究所计算机应用技术研究所38382022-8-5&“非非”运算运算2022-8-5计算机应用技术研究所计算机应用技术研究所39&“与与”运算运算2022-8-5计算机应用技术研究所计算机应用技术研究所40402022-8-5&“与与”运算运算2022-8-5计算机应用技术研究所计算机应用技术研究所41412022-8-5&“与与”运算运算2022-

22、8-5计算机应用技术研究所计算机应用技术研究所42422022-8-5&“与与”运算运算【分析】在自然语言中，除了联结词“并且”，其它的一些联结词，例如“不但而且”、“既也”、“虽然但是”、“一方面另一方面”等也表示同时为真的含义，因而也可用合取联结词表示。2022-8-5计算机应用技术研究所计算机应用技术研究所43432022-8-5&“与与”运算运算2022-8-5计算机应用技术研究所计算机应用技术研究所44&“(可兼可兼)或或”运算运算P:李明在教室。李明在教室。Q:米卢是个好教练。米卢是个好教练。PQ:李明在教室或米卢是个好教练。李明在教室或米卢是个好教练。2022-8-5计算机应用技

23、术研究所计算机应用技术研究所45PQ的真值为的真值为F，当且仅当，当且仅当P与与Q均为均为F&“(可兼可兼)或或”运算运算2022-8-5计算机应用技术研究所计算机应用技术研究所46&“(可兼可兼)或或”运算运算【例题】用复合命题表示下图所示的开关电路：2022-8-5计算机应用技术研究所计算机应用技术研究所47&“(可兼可兼)或或”运算运算2022-8-5计算机应用技术研究所计算机应用技术研究所48&“蕴涵蕴涵”运算运算2022-8-5计算机应用技术研究所计算机应用技术研究所49&“蕴涵蕴涵”运算运算P表示：缺少水分。Q表示：植物会死亡。P PQQ：如果：如果缺少水分缺少水分，植物就会死亡植

24、物就会死亡。2022-8-5计算机应用技术研究所计算机应用技术研究所50当且仅当当且仅当P P为真且为真且Q Q为假时，为假时，P PQ Q为假为假&“蕴涵蕴涵”运算运算2022-8-5计算机应用技术研究所计算机应用技术研究所51令：令：P P：天气好。：天气好。QQ：我去公园。：我去公园。1.1.如果天气好，我就去公园。如果天气好，我就去公园。（充分）（充分）2.2.只要天气好，我就去公园。只要天气好，我就去公园。（充分）（充分）3.3.仅当天气好，我才去公园。仅当天气好，我才去公园。（必要）（必要）4.4.只有天气好，我才去公园。只有天气好，我才去公园。（必要）（必要）命题命题1 1、2

25、2 写成：写成：P PQ Q 命题命题3 3、4 4 写成：写成：Q QP P&“蕴涵蕴涵”运算运算2022-8-5计算机应用技术研究所计算机应用技术研究所52&“等价等价”运算运算2022-8-5计算机应用技术研究所计算机应用技术研究所53&“等价等价”运算运算2022-8-5计算机应用技术研究所计算机应用技术研究所54&小小 结结设命题设命题P,Q表示任意两个命题表示任意两个命题,则则最常见的命题联结词有：最常见的命题联结词有：2022-8-5计算机应用技术研究所计算机应用技术研究所55552022-8-5&小小 结结设命题设命题P,Q表示任意两个命题表示任意两个命题,则有则有：2022-

26、8-5计算机应用技术研究所计算机应用技术研究所56&命题符号化命题符号化 1.1.首先要明确给定命题的含义。首先要明确给定命题的含义。2.2.对于复合命题，找联结词，用联结词对于复合命题，找联结词，用联结词断句，分解出各个原子命题。断句，分解出各个原子命题。3.3.设原子命题符号，并用逻辑联结词联设原子命题符号，并用逻辑联结词联结原子命题符号，构成给定命题的符号表结原子命题符号，构成给定命题的符号表达式。达式。2022-8-5计算机应用技术研究所计算机应用技术研究所57&若干要点若干要点联结词与自然语言之间的对应联结词与自然语言之间的对应并非一一对应并非一一对应2022-8-5计算机应用技术研

27、究所计算机应用技术研究所58&例例 题题【例例】符号化下列命题符号化下列命题2022-8-5计算机应用技术研究所计算机应用技术研究所59592022-8-5&例例 题题【例例】符号化下列命题符号化下列命题 （1 1）四川不是人口最多的省份；）四川不是人口最多的省份；（2 2）王超是一个）王超是一个德智体德智体全面发展的好学生；全面发展的好学生；（3 3）教室的灯不亮可能是灯管坏了）教室的灯不亮可能是灯管坏了或者或者是停电了；是停电了；（4 4）如果周末天气晴朗，那么学院将组织我们到石象）如果周末天气晴朗，那么学院将组织我们到石象湖春游；湖春游；（5 5）两个三角形全等）两个三角形全等当且仅当当

28、且仅当三角形三边对应相等。三角形三边对应相等。2022-8-5计算机应用技术研究所计算机应用技术研究所60602022-8-5&例例 题题【例例】符号化下列命题符号化下列命题（1 1）除非）除非明天不下雨且不下雪，否则我将不去学校；明天不下雨且不下雪，否则我将不去学校；（2 2）只要）只要明天明天不不下雨下雨或或不不下雪，下雪，我就去学校；我就去学校；（3 3）只有明天不是雨夹雪）只有明天不是雨夹雪，我，我才才去学校去学校；（4 4）明天上午我将明天上午我将雨雪无阻雨雪无阻一定去学校一定去学校。2022-8-5计算机应用技术研究所计算机应用技术研究所61612022-8-5&例例 题题【例例】

29、符号化下列命题符号化下列命题 除非除非你陪伴我或代我叫车子，你陪伴我或代我叫车子，否则否则我将我将不不出去出去。如果如果你陪伴我你陪伴我并且并且代我叫辆车子，代我叫辆车子，那么那么我将出去我将出去。如果如果你你不不陪伴我陪伴我或或不不代我叫辆车子，代我叫辆车子，那么那么我将我将不不出去出去。2022-8-5计算机应用技术研究所计算机应用技术研究所62622022-8-5&联结词的应用联结词的应用2022-8-5计算机应用技术研究所计算机应用技术研究所63632022-8-5QPP P Q QQP P PQ QPP P设设P P：输入端为高电位，：输入端为高电位，Q Q：输入端为高电位：输入端为

30、高电位,则则 “与门与门”对应于对应于 PQPQ “或门或门”对应于对应于 PQPQ “非门非门”对应于对应于 P P&应用实例应用实例2022-8-5计算机应用技术研究所计算机应用技术研究所64&应用实例应用实例【例题例题】使用命题联结词将下列命题符号化：使用命题联结词将下列命题符号化：（1）说离散数学无用且枯燥无味是不对的。说离散数学无用且枯燥无味是不对的。（2）只有我不复习功课只有我不复习功课,我才去看电影。我才去看电影。（3）除非你陪我或代我叫车，否则我将不出去。除非你陪我或代我叫车，否则我将不出去。（4）若两个圆面积相等，则半径相等，反之亦然。若两个圆面积相等，则半径相等，反之亦然。

31、（5）如果天不下雨且不刮风，我就去书店看书，否则如果天不下雨且不刮风，我就去书店看书，否则我就在家休息。我就在家休息。（6）若不是他生病或出差，老板是不会同意他不参加若不是他生病或出差，老板是不会同意他不参加这个会议的。这个会议的。2022-8-5计算机应用技术研究所计算机应用技术研究所65&应用实例应用实例【分析】命题（命题（1）直接按题意进行符号化；直接按题意进行符号化；命题（命题（2），），“我不复习功课我不复习功课”是是“我去看电影我去看电影”的一的一个必要条件，可用个必要条件，可用“”表示；表示；命题（命题（3）中中“除非除非否则不否则不”表示如果前件不表示如果前件不发生，发生，那我

32、就一定不会做什么，那我就一定不会做什么，或者说若做了什么，或者说若做了什么，则前件一定发生，则前件一定发生，因此，如果我出去的话，你肯定是陪因此，如果我出去的话，你肯定是陪我或者替我叫车，或者说如果你既不陪我，也不替我叫车我或者替我叫车，或者说如果你既不陪我，也不替我叫车，那我肯定不出去；，那我肯定不出去；2022-8-5计算机应用技术研究所计算机应用技术研究所66&应用实例应用实例【分析】命题（命题（4），），由两圆面积相等可推出其半径由两圆面积相等可推出其半径相等，半径相等也可推出两圆面积相等，相等，半径相等也可推出两圆面积相等，故故“圆半径圆半径相等相等”与与“圆面积相等圆面积相等”之间

33、是等价关系，之间是等价关系，可用可用“”表示；表示；命题（命题（5）中用了三个联结词）中用了三个联结词“如果如果就就”、“且且”和和“或或”，其中，其中“或或”联结词是从命题中理解出来的联结词是从命题中理解出来的，没有明确给出。没有明确给出。因为从命题中因为从命题中“否则否则”一词可理解一词可理解为为“否则，否则，如果天下雨或刮风，我就在家休息如果天下雨或刮风，我就在家休息”；命题（命题（6）则可以理解为）则可以理解为“他不生病并且不出差，老他不生病并且不出差，老板就不同意他不参加会议板就不同意他不参加会议”。2022-8-5计算机应用技术研究所计算机应用技术研究所67&应用实例应用实例202

34、2-8-5计算机应用技术研究所计算机应用技术研究所68&应用实例应用实例2022-8-5计算机应用技术研究所计算机应用技术研究所69&应用实例应用实例【解】令P表示“A是骑士”，Q表示“B是骑士”，则P和 Q分别表示“A是流氓”和“B是流氓”。首先假设A是骑士，即P为真。由于A是骑士，那么A说的命题“B是骑士”就为真，即Q为真。此时，A和B就是一类人。但如果B是骑士，那么B的话也应该为真，即(PQ)(PQ)为真，由此得到矛盾，因为A和B都是骑士。故此时不存在A是骑士的情形。2022-8-5计算机应用技术研究所计算机应用技术研究所70&应用实例应用实例如果A是流氓，则由题意知A所说的命题“B是骑

35、士”为假，也就是说Q为假，即B也是流氓。进一步，如果B是流氓，那么B说的命题也为假，这与A和B都是流氓的判断是一致的。因此得出的结论为：A和B都是流氓。2022-8-5计算机应用技术研究所计算机应用技术研究所71本节内容到此结束本节内容到此结束2022-8-52022-8-5命题的概念与运算命题的概念与运算1 1命题公式与等值演算命题公式与等值演算2 2&本章学习内容本章学习内容(上上)3 3 联结词的完备集联结词的完备集2022-8-5计算机应用技术研究所计算机应用技术研究所73命题公式与等值演算命题公式与等值演算&命题公式与等值演算命题公式与等值演算J 命题公式的基本知识命题公式的基本知识

36、4 等值关系与等值演算等值关系与等值演算4 公式的内否与对偶公式的内否与对偶2022-8-5计算机应用技术研究所计算机应用技术研究所75752022-8-5&命题变元命题变元u 如果命题标识符表示一个具体、确定的如果命题标识符表示一个具体、确定的命题，称为命题，称为命题常元命题常元。u 如果命题标识符表示任意一个命题，称如果命题标识符表示任意一个命题，称为为命题变元命题变元。命题命题是能判断真假的陈述句。命题变元命题变元代表任意的命题，其真值是不确代表任意的命题，其真值是不确定的，定的，它的变域是集合它的变域是集合 T T，F F(或或00，11)。2022-8-5计算机应用技术研究所计算机应

37、用技术研究所76762022-8-5&命题公式命题公式 把命题常元，命题变元按照一把命题常元，命题变元按照一定的逻辑顺序和规则，用命题联结定的逻辑顺序和规则，用命题联结词连接起来就构成了命题演算的词连接起来就构成了命题演算的合合式公式式公式，也叫，也叫命题公式命题公式。2022-8-5计算机应用技术研究所计算机应用技术研究所77&命题公式的定义命题公式的定义 按下列规则构成的符号串称为命题演算的按下列规则构成的符号串称为命题演算的合式公合式公式式，也称为，也称为命题公式命题公式，简称，简称公式公式。单个命题变元和常元是合式公式。单个命题变元和常元是合式公式。如果如果A A是合式公式，那么是合式

38、公式，那么A A是合式公式。是合式公式。如果如果A A和和B B是合式公式，那么是合式公式，那么(AB)(AB)、(AB)(AB)、(AB)(AB)和和(A(AB)B)是合式公式。是合式公式。当且仅当有限次地应用了、所得到当且仅当有限次地应用了、所得到的符号串是合式公式。的符号串是合式公式。2022-8-5计算机应用技术研究所计算机应用技术研究所78&命题公式的定义命题公式的定义 上面的定义给出合式公式定义的方法称为归上面的定义给出合式公式定义的方法称为归纳定义，它包括三部分：纳定义，它包括三部分：基础、归纳、界限基础、归纳、界限 其中是基础，和是归纳，是界限。其中是基础，和是归纳，是界限。以

39、后将多次出现这种形式的定义。以后将多次出现这种形式的定义。2022-8-5计算机应用技术研究所计算机应用技术研究所79&命题公式举例命题公式举例【例例】下列符号串是合式公式：下列符号串是合式公式：(pq)，(pq)，(p(pq)，(pq)(qr)(st)【例例】下列符号串不是合式公式：下列符号串不是合式公式：(pq)(q)，(pq，(pq)q)2022-8-5计算机应用技术研究所计算机应用技术研究所80802022-8-5&一些约定一些约定【约定约定】为方便，最外层括号可以不写，为方便，最外层括号可以不写，合式公式可以写成：合式公式可以写成：P PQQ，P PR R，(PQ)R(PQ)R【约定

40、约定】逻辑联接词优先级：逻辑联接词优先级：、此时此时P PQQR R也是合式公式也是合式公式 原子公式原子公式：表示原子命题的命题变量是最简单的命题公式。2022-8-5计算机应用技术研究所计算机应用技术研究所81812022-8-5&例例 题题【例例】试用符号形式写出下列命题：试用符号形式写出下列命题：（1 1）虽然今天天气晴朗，老陈还是不来；）虽然今天天气晴朗，老陈还是不来；【解解】设设 P P：今天天气晴朗：今天天气晴朗,Q,Q：老陈要来：老陈要来,则有：则有：PPQ Q；（2 2）除非你陪伴我或代我叫车子，否则我将不出去；）除非你陪伴我或代我叫车子，否则我将不出去；【解解】设设 P:P

41、:你陪伴我你陪伴我;Q:;Q:你代我叫车子你代我叫车子;R:;R:我出去。我出去。则有：则有：RPQ RPQ 或或 PPQQR R；2022-8-5计算机应用技术研究所计算机应用技术研究所82&例例 题题【例题】对于下列字符串，试判别哪些是命题公式，哪些不是，为什么？（1）(QPS)；（2）(PQ)(QP)；（3）(PQR)；（4）(PP)(QQ)R)；（5）(PQ)(Q)；（6）(PQ)(QR)(ST)；2022-8-5计算机应用技术研究所计算机应用技术研究所83&例例 题题【分析】由命题公式的定义可知：一个命题公式可以是由命题公式的定义可知：一个命题公式可以是一个单个的命题变元，也可以是由

42、多个命题公式通过命一个单个的命题变元，也可以是由多个命题公式通过命题联结词以及括弧联结而成的。因此有：题联结词以及括弧联结而成的。因此有：（1）、（）、（2）、（）、（6）是命题公式，因为它们都满足命）是命题公式，因为它们都满足命题公式的定义。题公式的定义。（3）、（）、（4）、（）、（5）都不是命题公式，（）都不是命题公式，（3）中）中“PQ”之间没有联结词，所表达的含义不明确，（之间没有联结词，所表达的含义不明确，（4）中多了）中多了一个一个“)”，（，（5）是因为）是因为是一个二元联结词，是一个二元联结词，(Q)中中的左边缺少命题变量或者命题公式，因而不是命题公的左边缺少命题变量或者命题

43、公式，因而不是命题公式。式。2022-8-5计算机应用技术研究所计算机应用技术研究所84&例例 题题【解】（1）、（）、（2）、（）、（6）是命题公式，（）是命题公式，（3）、）、（4）、（）、（5）不是命题公式。由命题公式的定义可）不是命题公式。由命题公式的定义可知：知：（1）表示原子命题的命题变量是最简单的命题公式）表示原子命题的命题变量是最简单的命题公式，通常称之为原子公式；，通常称之为原子公式；（2）就像初等代数中的多项式没有具体数值一样，）就像初等代数中的多项式没有具体数值一样，命题公式也没有具体的真值，只有当命题公式中每命题公式也没有具体的真值，只有当命题公式中每个命题变量都进行具

44、体的真值指派以后，才可确定个命题变量都进行具体的真值指派以后，才可确定命题公式的真值；命题公式的真值；2022-8-5计算机应用技术研究所计算机应用技术研究所85&例例 题题（3）命题公式的结构可以很简单，例如原子命题）命题公式的结构可以很简单，例如原子命题公式，也可以很复杂；公式，也可以很复杂；（4）为叙述方面，对于命题变量）为叙述方面，对于命题变量P和和Q，通常也分，通常也分别将别将(P)、(PQ)、(PQ)、(PQ)、(PQ)称为称为否定式、合取式、析取式、蕴涵式和等价式，在合否定式、合取式、析取式、蕴涵式和等价式，在合取式取式(PQ)中，中，P、Q被称为合取项，在析取式被称为合取项，在

45、析取式(PQ)中，中，P、Q被称为析取项。被称为析取项。2022-8-5计算机应用技术研究所计算机应用技术研究所86862022-8-5&公式的解释公式的解释【定义定义】设设P P1 1,P P2 2,P Pn n是出现在公式是出现在公式G G中中的所有命题变元的所有命题变元，指定指定P P1 1,P P2 2,P Pn n一组真一组真值，值，例如例如(0,1,1)(0,1,1)，则称这组真值为，则称这组真值为对公式对公式G G的一个的一个解释解释或或赋值赋值,记为记为2022-8-5计算机应用技术研究所计算机应用技术研究所87872022-8-5&赋值类型赋值类型 若指定的赋值使若指定的赋值

46、使G G的真值为的真值为T T，则称这个赋值为，则称这个赋值为G G的的成真赋值成真赋值，若指定的赋值使若指定的赋值使G G的真值为的真值为F F，则称这个赋值为，则称这个赋值为G G的的成假赋值成假赋值。【例例】给公式给公式(p pq qr r)的赋值的赋值 赋值赋值011011是指是指p p=0=0，q q=1=1，r r=1=1，它是该公式的成真，它是该公式的成真赋值；赋值；赋值赋值110110是指是指p p=1=1，q q=1=1，r r=0=0，它是该公式的成假，它是该公式的成假赋值。赋值。2022-8-5计算机应用技术研究所计算机应用技术研究所88&真值表的概念真值表的概念 若若公

47、式公式G G中有个不同的命题变元中有个不同的命题变元，则该公式应有则该公式应有2 2n n个不同的解释。个不同的解释。将将公式公式G G在其所有可能解释下在其所有可能解释下的的真值真值情况列成的表，称为情况列成的表，称为G G的的真值表真值表。2022-8-5计算机应用技术研究所计算机应用技术研究所89&真值表的概念真值表的概念 在命题公式在命题公式G G中，对中，对G G的每一个赋值，就确定了的每一个赋值，就确定了G G的的一个真值，把这些所有的真值汇列成表，一个真值，把这些所有的真值汇列成表，称该表为命称该表为命题公式题公式G G的真值表。的真值表。PQ P PQ(PQ)QTTFTTTFF

48、TTFTTTTFFTFF2022-8-5计算机应用技术研究所计算机应用技术研究所90902022-8-5&真值表举例真值表举例【例题】构造公式(PQ)R的真值表。【分析】构造真值表的可以分为以下三步：（1）列出公式所有命题变元以及其所有的可能赋值状态；（2）按运算优先级从高到低的顺序写出命题公式各层次运算表达式；（3）针对各个赋值状态计算出各层次的真值，直到最后计算出公式的真值。2022-8-5计算机应用技术研究所计算机应用技术研究所91912022-8-5&真值表举例真值表举例【解】按照如上步骤，构造真值表如下：2022-8-5计算机应用技术研究所计算机应用技术研究所92922022-8-5

49、&真值表举例真值表举例【例题】构造公式(PQ)(QP)的真值表。【解】与上述解法类似，写出公式：P、Q、PQ、QP、(PQ)(QP)的真值表如表所示。2022-8-5计算机应用技术研究所计算机应用技术研究所93932022-8-5&真值表举例真值表举例【例题】有一逻辑学家误入某部落，有一逻辑学家误入某部落，该部落酋该部落酋长对逻辑学家说：长对逻辑学家说：“今有两扇门，一为死亡门今有两扇门，一为死亡门，一为自由门，你可任意开启其中一扇以选择，一为自由门，你可任意开启其中一扇以选择死亡和自由。死亡和自由。现派两人助你选择，这两人负责现派两人助你选择，这两人负责解答你提出的任何问题，但是这两人中一名

50、天解答你提出的任何问题，但是这两人中一名天性诚实、一名说谎成性。性诚实、一名说谎成性。”逻辑学家沉思片刻逻辑学家沉思片刻，即手指一门向一人发问，然后选择一门从容，即手指一门向一人发问，然后选择一门从容离去。离去。试问：试问：该逻辑学家如何发问？该逻辑学家如何发问？2022-8-5计算机应用技术研究所计算机应用技术研究所94&真值表举例真值表举例【分析】逻辑学家问其中一人：逻辑学家问其中一人：“这扇门是这扇门是死亡门，他将回答是，死亡门，他将回答是，对吗？对吗？”如果被问者如果被问者天性诚实，天性诚实，且回答对，那么另外一人则说谎且回答对，那么另外一人则说谎成性，回答是则意味着不是，也就是说，逻