01 绪论-命题逻辑.ppt

1、1.教材离散数学，左晓玲、李伟健、刘永才主编，上海科技文献出版社。离散数学结构参考书离散数学耿素云，瞿万玲主编，高等教育出版社，教材和参考书，2。什么是离散数学、连续数学与连续数学的比较：以连续函数为研究对象，如微积分、实函数和复函数、几何和拓扑学。研究离散量的结构及其相互关系的学科离散量：逻辑变量、集合和关系、代数结构如群和环、图等。离散数学是随着计算机科学的出现、发展和应用而逐渐形成的一门新的工具学科。作为一门课程，那是在20世纪70年代中期。离散数学的地位和作用是计算机专业的一门核心基础课。根据课程设置，离散数学为计算机专业的后续课程提供了必要的数学基础，如数据结构、操作系统、数据库、编

2、译原理、网络和算法设计等。它为学生将来从事计算机科学和技术提供了强有力的工具。离散数学是现代数学的一个重要分支。学习这门课程可以提高学生的抽象思维能力、严格推理能力和综合归纳分析能力，培养高素质人才。离散数学课程的特点，是高等数学的许多分支为响应计算机科学和技术的发展而整合而形成的。其特点是以离散量为研究对象，内容丰富，覆盖面广。因此，有许多概念、定理、推论和抽象的内容。然而，由于它是学生后续专业知识学习所必需的数学准备，所以它的研究内容相对基础而言并不困难。5.如何学好离散数学？要学好这门课程，首先我们必须充分认识到这门课程的上述特点，需要做好以下几个方面的工作：讲解清楚这门课程，阅读好教材

3、。准确理解各种概念和定理的含义(结合几个例子)，并理解必要的推理过程(它可以帮助你熟悉和深刻理解定理的含义)。独立思考，多多练习。你不能仅仅通过熟悉教材就把书本上的知识变成你自己的知识。在熟悉教材的基础上，你必须通过大量的实践和独立思考来真正获得知识。注重抽象思维能力的培养。与其他学科相比，数学是高度抽象的，而离散数学更抽象。它包含了许多抽象的概念和抽象的推理。要学好这门课程，我们必须具备良好的抽象思维能力，才能深刻掌握课程内容。7，4，离散数学课程的主要内容，课程描述，数学逻辑的第一部分。包括命题逻辑和谓词逻辑(教科书的第一章和第二章)。包括集合、关系和函数。(教科书的第3章和第4章)第3部

4、分代数系统。包括代数系统的一般概念，几个典型的代数系统，如群、群、环、域、格和布尔代数。第四部分是图论。包括图、有向图和无向图的基本概念。(教科书第7章)，第8节。用数学方法研究推理规律被称为数理逻辑。这里所指的数学方法是引入一套符号系统的方法，所以数理逻辑也叫符号逻辑，是从量的角度研究思维规律的一门学科。命题逻辑谓词逻辑，数学逻辑的第一章，9，命题逻辑的第一章，命题及其表示连词，命题公式和翻译真值表和等价重言式和蕴涵对偶及范式推理理论，10，1-1命题及其表示，通过概念判断事物是否具有某些属性。命题：可以表达判断的陈述句。一个命题总是有一个“价值”，这就是所谓的真正价值。只有两种真值，“真”

5、和“假”，记录为真和假，分别用符号t和f表示。注：只有具有确定真值的陈述句才是命题，所有没有判断内容的句子，如感叹句、疑问句和祈使句，都不能视为命题。有两种类型的命题：原子命题：不能分解成更简单的陈述的命题。复合命题：由连词、标点符号和原子命题组成的命题。所有这些命题都应该有明确的真值。连词的例子，如“and”、“or”、“if then”等。判断下列句子是否是命题。中国人民是伟大的。(是的)(2)雪是黑色的。(是)(3)1 101=110(否)二进制方程成立，但十进制方程不成立。这里没有指出上下文，真正的价值是不确定的。(4)其他星球上也有生物。(是的)真正的价值是存在的，但是现在还不知道，

6、还需要确定。(5)全体立正。No是祈使句。13.明天有会议吗？(不)是个问题。多美的一天啊！No是感叹句。我在撒谎。(不)悖论。我学习英语，或者我学习日语(是的)。如果天气好，那么我将去散步。(是)、示例14，您可以使用大写字母A、B、P、Q或带以下标记的大写字母，或括在方括号中的数字来表示命题。今天下雨了。12:今天下雨了。也就是说，命题既可以用字母表示，也可以用数字表示，1-1.2是命题的符号表示，而15，命题常数是一个确定的命题。命题论据经常使用大写字母(或下标)如P，Q，R Q和R来表示一个命题，这被称为命题论据。赋值当命题变量P被一个特定的命题所代替时，P可以决定真值，这意味着赋值命

7、题变量P1-1.3关于命题16，1-1.4的一些概念命题和命题论证的区别在于命题论证和命题是不同的。命题是具体的，是具有真值和确定真值的陈述句；命题的论证是抽象的，只有当一个特定的命题被替代时，才有确定的真值。17，命题常数。命题自变量变量。给变量赋值。1-1.5命题逻辑与程序设计语言之间的对应关系，18，1-2连词，在自然语言中，经常使用一些连词，如“或”、“和”、“不”，但对这些连词的使用一般没有严格的定义。在数理逻辑中，复合命题由原子命题和连词组成，它不仅是复合命题的重要组成部分，而且还起着算符的作用。为了便于写作和推理，连词必须明确定义和符号化。定义：设P是一个命题，P的否定是一个新命

8、题，称为P。如果P是t，P是f；如果p是f，p是t，是否定命题的意思。否定连词有时可以写成，这被称为非运算运算符。1-2.1否定，注：否定的概念与自然语言中的“非”、“否定”和“不”具有相同的含义。20，反面例子，例子：让p:成都是一个大城市；问：每个自然数都是偶数。还有一个问题：成都不是一个大城市；问：不是每个自然数都是偶数。21，定义：两个命题P和Q的合取是一个复合命题，它被记录为PQ，发音为“P和Q”、“P和Q”和“P和Q的合取”。当p和q同时为t时，PQ为t，在其他情况下，PQ的真值为f。1-2.2连词，注：连词的概念以及自然语言中“和”、“和”、“不仅而且”的抽象。我们去电影院吧。问

9、：房间里有十张桌子。然后PQ:“我们去看电影，房间里有十张桌子。”，连词示例，23，定义：两个命题p和q的析取是一个复合命题，它被记录为PQ，发音为“p或q”和“p和q的析取”。当且仅当p和q同时为f时，PQ的真值为f，否则PQ的真值为t，1-2.3析取。注：从析取的定义中，我们可以看出连词的意思与汉语中的“或”相似，但有区别。错位相当于“既可以是也可以是”。举个例子，让我们说p:小王在唱歌。小王正在跳舞。PQ:“小王在唱歌或跳舞。”小王在教室里。小王在宿舍里。小王在教室里还是在宿舍里.如何表达，25，1-2.4异或，定义：两个命题P和Q之间的区别或一个复合命题，记录为PQ，读作“P异或Q”，

10、“P和Q不是析取的”。当且仅当p和q的真值不同时，PQ的真值为t，否则PQ的真值为F.例如，假设小王在教室里。小王在宿舍里。然后说：“小王在教室里，或者在宿舍里。”给定两个命题P和Q，条件命题是一个复合命题，它被记录为PQ，读作“如果P，那么Q”或“如果P，那么Q”。当且仅当P的真值为t，Q的真值为f时，PQ的真值为f，否则PQ的真值为t。我们称P为前部，Q为后部。1-2.5条件，注：在数学和一些逻辑问题中，“如果p是q”也可以称为“p隐含q”，但本书将避免在条件命题中使用“蕴涵”一词，因为“蕴涵”的概念将在将来单独定义。28，连词的真值表:1-2.5条件，29，1-2.5条件。以下几点值得注

11、意：从条件的定义中，我们可以看出连词对应的是汉语中的“如果，那么”，但也有区别。PQ的逻辑意义：P是Q的一个充分条件，Q是P的一个必要条件，“如果P，那么Q”，“只要P是Q”，“只有Q是P”，“只有Q是P”，这些都符合PQ的形式。在自然语言中，“如果，只是”当前提为假时，整个句子的意义就无法判断结论是真是假；在条件命题中，当前提为假时，结论为真，命题为真，称为“善意推定”。在自然语言中，“如果，公正”的前提(前一部分)和结论(后一部分)之间往往有因果关系；和 不涉及具体内容。让p: 225。问：太阳从东方升起。如果225，太阳从东方升起。象征下列命题(让P:下雨，Q:我骑自行车去上班)只要不下

12、雨，我就骑自行车去上班。只有不下雨，我才会骑自行车去上班。除非下雨，否则我骑自行车去上班。如果下雨，我就不骑车去上班了。定义：给定两个命题P和Q，复合命题PQ被称为双条件命题，其读作“P如果且仅Q”。当p和q的真值相同时，p q的真值为t，否则p q的真值为f。注：一个两条件命题也可以只根据连词的定义来确定真值，而不考虑其因果关系。它也可以写成“”或“iff”。1-2.6双条件，33，连词真值表 :1-2.6双条件，34，例1:非仓库人员不允许进入。让p:有人是仓库工人；问：有人可以进入仓库。上述命题可以表示为PQ。对于上述连词，应该注意的是，复合命题的真值仅取决于构成它的每个原子命题的真值，

13、而与这些原子命题的内容和意义无关。命题公式和翻译，命题公式：如果P和Q是命题论点，那么P，PQ，(PQ) (PQ)和P (QP)都被称为命题公式。注：一个命题公式没有真值或假值，只有当公式中的命题变元被一个确定的命题所取代时，才能得到一个命题。这个命题的真值取决于那些替代论点的命题的真值。36，定义1-3.1命题演算公式(wff)，它被指定为： (1)单个命题论证本身就是公式的公式。(2)如果A是一个公式，那么A就是一个公式。(3)如果甲和乙是复合式，那么乙、丙、丙和丙都是复合式。(4)当且仅当在(1)、(2)和(3)中获得的包含命题自变量、连接词和括号的符号串可以在有限时间内应用时，它是一个

14、复合公式。1-3.1复合公式，用复合公式的定义，自然语言中的一些句子可以翻译成数理逻辑中的符号形式。37，1-3.2连词的操作优先级如下：高，低，括号优先，38。我们应该搞好健康、学习和工作，为祖国的四个现代化而奋斗。试着用符号形式写命题：解决方法：找出每个原子命题，用命题符号来表示：我们应该身体健康。人们应该好好学习。列车员：人们应该做好自己的工作。人民应该为祖国的四个现代化而奋斗。因此，这个命题可以形式化为：(基础知识)第39页。解决方案：让乘客：从上海到北京的第14趟列车在下午5: 30发车。问：从上海开往北京的14次列车下午6点发车。因此，这个命题可以表述为：PQ，解：让P:他聪明。问

15、：他学习很努力。因此，这个命题可以表示为：PQ，例2从上海到北京的第14列火车将在5: 30或6: 00离开。他既聪明又勤奋。这个命题的意思可以理解为：如果你不努力，你就会失败。你工作很努力。问：你失败了。因此，这个命题可以表述为：PQ。解决办法：这里的“虽然但是”这个词不能用上面提到的连词来表达，但是它的实际意义是他很聪明，不努力学习。他很聪明。问：他学习很努力。因此，这个命题可以表示为：PQ，例4。虽然他很聪明，但他不努力学习。除非你努力工作，否则你会失败。张三或李四都能做这件事。这个命题的意义在于张三能做到，李四能做到。假设张三能做这件事。问：李四能做到。因此，命题可以表示为：PQ，42

16、，定义1-4.1。在命题公式中，对于给分量赋值的所有可能的组合，命题公式的所有种类的真值都被确定，并且它们被列在一个表中，该表是命题公式的真值表。示例1构建了PQ的真值表。1-4真值表和等效公式，43，例2给出了(pq) p的真值表，44，例3给出了(PQ)(PQ)的真值表。45，示例4给出了(PQ)(PQ)的真值表。46，表明有一种公式，它的真值总是真(假)，而不管命题自变量的赋值，这种公式可以被记录为T(F)。命题公式真值的个数取决于命题论据的个数。一般来说，由n个命题参数组成的命题公式有2n个真值情况。一些命题公式在不同命题参数赋值下具有与另一个命题公式相同的真值。47，定义1-4.2给定两个命题公式A和B，让P1，P2和Pn都是出现在A和B中的原子变量。如果P1，P2和Pn的任何一组真值被赋值，那么A和B是等价的或逻辑上相等的。写为AB。48，例5证明PQ(PQ)(QP)，49，下表所列命题定律可用真值表来验证。50，(1)pQPq(2)P Q(P Q)(Q P)P Q(P Q)(3)(P Q)(P Q)P(可约性理论)(4)关于称为q p的异或P f P P P P P P P pt(5)P Q P(逆形式)的性质定理1-4.1设X是公式A的一个子公式，如果XY