第1章命题逻辑new

离散数学东北大学信息学院软件所胡明涵一.课程的性质、内容：数学所研究的对象根据它们的取值分为两种：连续的，如长度、温度、面积等。离散的，如商店商品，学生所学课程等。离散数学是研究离散对象的结构以及它们之间相互关系的科学。课程性质：是计算机科学与技术专业的重要的专业基础课，也是该专业的主干课。内容：1.数理逻辑2.集合论3.代数系统4.图论*5.组合数学*6.形式语言与自动机(由于时间的关系，我们只讨论前四部分内容。)二.学习此课的目的：1.计算机的诞生与发展和离散数学密切相关正如马克思所说的：“一门科学，只有当它能够运用数学时，才算真正发展了。”计算机正是在离散数学中的图灵机的理论指导下诞生的(1936提出图灵机---1946诞生计算机)。计算机科学的发展十分迅速，计算机的硬件从第一代起现在发展到第四代(电子管晶体管集成电路大规模集成电路)，第五代即将问世，正在向网络化发展。而且计算机技术发展速度越来越快。计算机科学的发展(硬件、软件的发展)离不开计算机的理论：例如，程序设计语言的发展，从机器语言汇编语言高级面向过程语言面向对象语言智能语言…，系统软件的发展，如操作系统，从单用户多用户网络操作系统，…，即如DOSWindowsWindowsNT...;所有这些发展都依赖于离散数学、数据结构、编译原理、操作系统、数据库原理、软件工程、网络等理论。其中离散数学是基础，其它的理论中都用到了离散数学中的基本概念、基本思想、基本方法。计算机专业的学生学习计算机不同于非计算机专业的学生学习计算机，必须掌握离散数学的理论，才能更好地了解和从事计算机科学的研究。2.此课是主干课，也是后继课的基础课计算机专业的后续课中都大量地应用到离散数学中的基本理论，所以要想学好专业课，必须先学好离散数学。3.培养学生抽象的思维和逻辑推理能力和创新能力在大学学习知识很重要，但是能力的培养更重要。正如著名的物理学家劳厄所说：“重要的不是获得知识，而是发展思维能力。教育无非是一切已学过的东西都遗忘的时候，所剩下来的东西。”剩下的就是思维能力，它可以长期起作用。“数学是学习科学技术的钥匙和先决条件。”数学修养包括：理解、抽象、见识、体验。理解能力：逻辑推理能力、不同语言对应的转换能力、想象能力等。抽象能力：敏锐的洞察力，灵活的联想类比、举一反三能力，特别是把实际问题转化为数学问题的能力。见识：就是让学生见识一些重要的数学思想、数学方法以及用数学解决实际问题的著名事例。有了这样见识才会思路宽，办法多，遇到问题会自觉求助于数学。体验:数学是一种分析问题、解决问题的实践活动。与打猎一样是活本领。像转换观点、选择方法、熟悉软件、检验结果、发现毛病、查找原因多环节只有亲身经历才能学到手。学到这些活本领，就是一些基本素质问题。离散数学可以帮助学生提高数学素质。提高创造力。三.特点及学习方法：特点：内容较杂，概念多，定理多，比较抽象，给学习带来一定难度。学习方法：1.准确掌握每个概念(包括内涵及外延)。2.要有刻苦钻研精神,不断总结经验。3.在理解内容的基础上，要较多地做些习题，从而再进一步加深理解所学内容。4.注意培养分析问题和解决问题的能力第一篇数理逻辑逻辑--是研究人的思维的科学。它包含：1.辩证逻辑：是研究人的思维中的辩证法。例如：用全面的和发展的观点观察事物；具体问题具体分析；实践是检查事物正误的唯一标准；等等。2.形式逻辑：研究人思维的形式结构和一般规律。我们只关心形式逻辑。一形式逻辑人的思维过程：概念判断推理概念和判断人们通过学习(理论学习和从实践中学习)来掌握。人的思维形式主要表现为推理，所以形式逻辑主要研究推理。推理：是由若干个已知的判断(前提)，推出新的判断(结论)的思维过程。正确的思维如何能正确的思维？概念清楚，判断正确，推理合乎逻辑。二推理方法类比推理：由个别事实推出个别结论。如：地球上有空气、水、阳光，地球上有生物。火星上有空气、水、阳光。火星上有生物。归纳推理：由若干个别事实推出一般结论。如：铜能导电。铁能导电。锡能导电。铅能导电。……一切金属都导电。演绎推理：由一般规律推出个别事实。形式逻辑主要研究演绎推理。演绎推理举例如果天下雨，则路上有水。(一般规律)今天下雨了。(个别事实)推出结论：今天路上有水。(个别结论)(大前提)：所有金属都导电。(一般规律)(小前提)：铜是金属。(个别事实)推出结论：铜能导电。(个别结论)三数理逻辑数理逻辑是用数学的方法研究形式逻辑。“数学方法”：建立一套有严格定义的符号，即建立一套形式语言，来研究形式逻辑。所以数理逻辑也称为“符号逻辑”。这里只讨论“命题逻辑”和“谓词逻辑”。第一章命题逻辑命题逻辑以命题为中心1-1命题与命题的真值1.命题的概念命题是表达判断的陈述句。2.命题的真值一个判断只有两种可能：是正确的判断或者是错误的判断,所以命题的真值只有两个：“真”或“假”真值为真:一个命题所表达的判断与客观情况一致,记作T(True)。真值为假:一个命题表达的判断与客观情况不一致,记作F(False)。判断一句话是否是命题有两个关键：（1）是陈述句（2）有且只有一个真值例:判定下面这些句子哪些是命题?⑴2是个素数。⑵雪是黑色的。⑶2020年人类将到达火星。⑷如果ab且bc，则ac。⑸x+y5⑹请打开书！⑺您去吗？⑻我正在撒谎。⑴⑵⑶⑷是命题3.原子命题与复合命题原子命题(简单命题)：不能再分解成更简单的陈述句的命题。复合命题(分子命题)：由若干个连结词，标点符号及原子命题复合构成的命题。4.命题的表示例P:今天下雨。Q1:小王是大学生。作业第8页:(1)(3)(4)(6)1-2联结词复合命题是用“联结词”将原子命题联结起来构成的。归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：(1)否定“”(2)合取“∧”(3)析取“∨”(4)异或“”(5)蕴涵“”(6)等价“”一.否定“”表示：“并非…”，“不…”等。用于对一个命题P的否定，写成P，并读成“非P”。“”为一元运算定义：设P为一命题，P的否定是一个新命题，记作P。P的真值与P的真值相反。例P：2是素数。P：2不是素数。PPTFFT二.合取“∧”表示：“并且”、“不但…而且...”、“既…又...”“尽管…还…”等。例P：小王能唱歌。Q：小王能跳舞。P∧Q：小王能歌善舞。P∧Q读成P合取Q。P∧Q为二元运算。定义：两个命题P和Q的合取是一个复合命题，记作P∧Q。当且仅当P和Q的真值均为T时，P∧Q的真值为T，其他情况下，P∧Q的真值均为F。可看出真值规定符合语言与思维的习惯。PQP∧QTTTTFFFTFFFF三.析取“∨”、异或“”连接词“或者”有两种情况：可兼取的或，即两件事情可以同时发生。用析取“∨”表达。不可兼取的或，即两件事情不能同时发生。用异或（也称排斥或）“”表达。1.析取“∨”例P：小王能唱歌。Q：小王能跳舞。P∨Q：小王能唱歌或者能跳舞。P∨Q，读成P析取Q当且仅当P与Q的真值均为F时,P∨Q的真值为F,其他情况均为T。PQP∨QTTTTFTFTTFFF2.异或“”例P：十二次列车早晨8:30开。Q：十二次列车早晨9:00开。十二次列车早晨8:30或者早晨9:00开表示成PQ，读成P异或Q。当且仅当P与Q的真值相同时，PQ的真值为F。TTFTFTFTTPQPQFFF四.条件“”表示“如果…那么…”，“若…则…”等。例P：土壤缺少水分。Q：这颗植物会死亡。PQ：如果土壤缺少水分，这颗植物就会死亡。PQ读成“如果P则Q”。称P是PQ的前件，Q是PQ的后件。还可以说P是Q的充分条件，Q是P的必要条件。PQ的真值表：P:土壤缺少水分。Q:这颗植物会死亡。PQ:如果土壤缺少水分,这颗植物就会死亡。当且仅当P为T，Q为F时，PQ的真值为F，而其它都为T。注意“善意规定”PQP→QTTTTFFFTTFFT充分条件：就是只要条件成立，结论就成立，则该条件就是充分条件。上例中，“缺少水分”就是“这颗植物会死亡”的充分条件。在自然语言中表示充分条件的词有：如果…则…，只要…就…，若…则…。必要条件：就是如果该条件不成立，那么结论就不成立,则该条件就是必要条件。上例中，“这颗植物死亡”就是“缺少水分”的必要条件(这颗植物未死亡，一定不缺少水分)。在自然语言中表示必要条件的词有：只有…才…；仅当…，…;…,仅当…。关于充分条件和必要条件的说明：举例：令：P：天气好。Q：我去公园。1.如果天气好，我就去公园。2.只要天气好，我就去公园。3.天气好，我就去公园。4.仅当天气好，我才去公园。5.只有天气好，我才去公园。6.我去公园，仅当天气好。命题1、2、3写成：PQ命题4、5、6写成：QP可见“”表达的必须是前件是后件的充分条件；这一点要特别注意!!!它决定了哪个作为前件，哪个作为后件。五.等价(双条件）“↔”表示“当且仅当”、“充分且必要”例：P：⊿ABC是等边三角形。Q：⊿ABC是等角三角形。PQ：⊿ABC是等边三角形当且仅当它是等角三角形。PQPQTTTTFFFTFFFTPQ的真值表：当且仅当P与Q的真值相同，PQ的真值为T，否则为F。比较下面二表：PQPQTTFTFTFTTFFFPQPQTTTTFFFTFFFTPQ⇔(PQ)本节小结：要熟练掌握这五个联结词在自然语言中所表示的含义以及它们的真值表的定义。PQP∧QP∨QPQPQFFFFTTFTFTTFTFFTFFTTTTTT特别要注意“或者”的二义性，即要区分给定的“或”是“可兼取的或”还是“不可兼取的或”。特别要注意“”的用法，要弄清哪个作为前件，哪个作为后件。练习：填空已知P∧Q为T，则P为()，Q为()。已知P∨Q为F，则P为()，Q为()。已知P为F，则P∧Q为()。已知P为T，则P∨Q为()。已知P∨Q为T，且P为F，则Q为()。已知PQ为F，则P为()，Q为()。已知P为F，则PQ为()。已知Q为T，则PQ为()。已知PQ为F，则P为()，Q为()。已知P为T，PQ为T，则Q为()。已知Q为T,PQ为T，则P为()。已知PQ为T，P为T,则Q为().已知PQ为F，P为T,则Q为().PP的真值为().PP的真值为()。1-3命题公式及命题符号化一.常值命题与命题变元常值命题：即是具体的命题，有固定的真值。例如：“3是素数。”就是常值命题。命题变元：任一命题用大写的英字母如P、Q等表示。对命题变元作指派(给命题变元一个解释)：将一个常值命题赋予命题变元的过程，或者是直接赋给命题变元真值“T”或“F”的过程。注意：命题变元本身不是命题，只有给它一个解释，才变成命题。二.合式公式(wff)(wellformedformulas)定义：⑴单个命题变元是个合式公式。⑵若A是合式公式，则A是合式公式。⑶若A和B是合式公式，则(A∧B)，(A∨B)，(AB)和(AB)都是合式公式。⑷当且仅当有限次地应用⑴，⑵，⑶所得到的含有命题变元、联结词和括号的符号串是合式公式。注意这个定义是递归的。(1)是递归的基础，由(1)开始，使用(2)(3)规则进行递归，可以得到任意的合式公式。这里所谓的合式公式可以解释为合法的命题公式之意，也称之为命题公式，有时也简称公式。下面的式子是合式公式：(P∧Q)，(PR)，((P∧Q)∨R)P∧Q，PR，P∧Q∨R上面的式子不是合式公式约定：(1)最外层括号可省，(2)不影响运算次序的括号可省运算次序由高到低为:,∧,∨,,上面的合式公式可以写成：P∧Q，PR，(P∧Q)∨R,P∧Q∨R一个含有命题变元的命题公式不是命题，因它没有固定真值，但是给其中的所有命题变元作指派以后它就有了真值。将所有各种指派情况汇列成表，即为该