1-1-命题逻辑-离散数学-教学课件.ppt
x1x2x3y1y2Yy3X离 散 数 学离散数学课程的重要性n现代科学技术的各个领域，都提出了大量离散结构现代科学技术的各个领域，都提出了大量离散结构的科学问题。例如：的科学问题。例如：n计算机科学计算机科学n程序设计程序设计n计算机网络计算机网络n信息论与编码信息论与编码它们都与它们都与离散数学离散数学密切相关。密切相关。n离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。n主要目标研究离散量的结构和相互之间关系研究离散量的结构和相互之间关系n研究对象一般是有限个或可数个元素一般是有限个或可数个元素n通信理论通信理论n现代密码学现代密码学n数字信号处理数字信号处理n形式语言形式语言离散数学课程的重要性n研究内容n数理逻辑数理逻辑n集合论集合论n代数学代数学n组合数学组合数学n与之关系密切的课程n数据结构数据结构n操作系统操作系统n编译原理编译原理n算法分析算法分析n图论图论n计算理论计算理论n复杂网络复杂网络n网格及网络计算网格及网络计算n逻辑设计逻辑设计n系统结构系统结构n容错诊断容错诊断n机器定理证明机器定理证明离散数学课程的主要内容n第一部分第一部分数理逻辑数理逻辑n第第1章章命题逻辑命题逻辑n第第2章章一阶逻辑一阶逻辑n第二部分第二部分集合论集合论n第第3章章集合的基本概念和运算集合的基本概念和运算n第第4章章二元关系和函数二元关系和函数n第三部分第三部分代数结构代数结构n第第5章章代数系统的一般性质代数系统的一般性质n第第6章章几个典型的代数系统几个典型的代数系统n第四部分第四部分图论图论n第第7章章图的基本概念图的基本概念n第第8章章一些特殊的图一些特殊的图n第第9章章树树n第五部分第五部分组合分析初步组合分析初步（第（第10章）章）第一部分数理逻辑n先看著名物理学家爱因斯坦出的一道题先看著名物理学家爱因斯坦出的一道题:n一个商人想招聘一个聪明的助手，有两人前来应聘，一个商人想招聘一个聪明的助手，有两人前来应聘，商人为了试试哪个更聪明些，就把两个人带进一间漆商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，黑的屋子里，n他打开灯后说他打开灯后说：“桌子上有五顶帽子，桌子上有五顶帽子，两顶红色两顶红色，三三顶黑色顶黑色，现在把灯关掉，并把帽子的位置弄乱，然后，现在把灯关掉，并把帽子的位置弄乱，然后我们每人摸一顶帽子戴在自己头上，我再藏起余下的我们每人摸一顶帽子戴在自己头上，我再藏起余下的两顶帽子，开灯后，你们要尽快说出自己头上戴的帽两顶帽子，开灯后，你们要尽快说出自己头上戴的帽子的颜色。子的颜色。”n当开灯后，那两个应试者看到商人头上戴的是一顶当开灯后，那两个应试者看到商人头上戴的是一顶红红帽子帽子，其中一个人便喊道：，其中一个人便喊道：“我戴的是我戴的是黑帽子黑帽子。”n请问这个人说得对吗？他是怎么推导出来的呢？请问这个人说得对吗？他是怎么推导出来的呢？第一部分数理逻辑n这需要经历如下过程：n 什么是前提？有哪些前提？什么是前提？有哪些前提？n 结论是什么？结论是什么？n 根据什么进行推理？根据什么进行推理？n 怎么进行推理？怎么进行推理？n数理逻辑将回答这些问题，它包括数理逻辑将回答这些问题，它包括n命题逻辑命题逻辑n一阶逻辑一阶逻辑n数理逻辑n研究的中心问题是研究的中心问题是推理推理n是用数学方法来研究推理的是用数学方法来研究推理的形式结构形式结构和和推理规律推理规律的数的数学学科学学科吴文俊(1919-)数学机械化n1976年，年，吴文俊教授在教授在中国古代数学中国古代数学机械机械化思想的启发下，创建了化思想的启发下，创建了数学机械化方法数学机械化方法n从从几何公理体系几何公理体系出发，引进坐标，将任意几何问题出发，引进坐标，将任意几何问题代数化代数化，将证明，将证明题的题的假设假设与与结论结论分别表示成分别表示成多元多项式方程多元多项式方程，在计算机上编程运算，在计算机上编程运算，以判断定理是否成立。，以判断定理是否成立。n至至2008年，运用年，运用吴文俊教授的方法，已证明出教授的方法，已证明出600多条定理，许多多条定理，许多定理的证明不超过几秒钟。甚至有一些定理证明相当繁杂，即便交定理的证明不超过几秒钟。甚至有一些定理证明相当繁杂，即便交给杰出的数学家来证也是相当困难的。给杰出的数学家来证也是相当困难的。n“数学机械化数学机械化”是近代数学史上的第一个中国原创的领域，被国是近代数学史上的第一个中国原创的领域，被国际上称为际上称为“吴方法吴方法”。n它它终于实现了千百年来终于实现了千百年来几何定理几何定理机械化证明的梦想。机械化证明的梦想。n它它给给2000多年的公理化演绎体系带来了强烈冲击。多年的公理化演绎体系带来了强烈冲击。n20002000年年吴文俊吴文俊院士获院士获首届首届国家最高科技奖国家最高科技奖。1.1命题符号化及联结词n 命题的概念n引例就是要对引例就是要对“我戴的是黑帽子我戴的是黑帽子”进行判断。进行判断。这样的陈述句称为命题。这样的陈述句称为命题。n命题命题 可可判断真假的陈述句。判断真假的陈述句。n如：如：2 2是素数。是素数。雪是黑色的。雪是黑色的。n命题的真值命题的真值 判断的结果判断的结果n真值的取值真值的取值真（真（1或或T）与假（）与假（0或或F）n真命题真命题:真值为真的命题（真值为真的命题（判断正确）判断正确）n假命题假命题:真值为假的命题（真值为假的命题（判断错误）判断错误）n任何命题的真值都是唯一的。任何命题的真值都是唯一的。1.1命题符号化及联结词n注意:n感叹句、祈使句、疑问句都不是命题感叹句、祈使句、疑问句都不是命题n如：如：你跑得真快！你跑得真快！请不要讲话！请不要讲话！又开学了吗？又开学了吗？n陈述句中的判断结果不惟一确定以及陈述句中的判断结果不惟一确定以及悖论悖论也不是命题也不是命题n如：如：x+5 3 我正在说谎话。我正在说谎话。我正在说谎。我正在说谎。n判断给定句子是否为命题的步骤n首先判定它是否为陈述句，首先判定它是否为陈述句，n其次判断它是否有唯一的真值。其次判断它是否有唯一的真值。除地球外的星球有生物。除地球外的星球有生物。明天是晴天。明天是晴天。简单命题符号化n用小写英文字母用小写英文字母p,q,r,pi,qi,ri(i1）表示）表示简单命题简单命题n用用“1”表示真，用表示真，用“0”表示假表示假例如，令例如，令 p：2是奇数，则是奇数，则p 的真值为的真值为0 q：2+5=7，则则q 的真值为的真值为1联结词2.合取 n定义定义:设命题设命题p和和q是两个命题，构造一个新命是两个命题，构造一个新命题题“p与与q”，称作命题，称作命题p和和q的合取，表示成的合取，表示成“p q”。n规定规定n当且仅当当且仅当p和和 q都为真时都为真时,p q为真为真.n自然语言中用到的联结词自然语言中用到的联结词:n“和和”，“与与”,“,“并且并且”n“既既.又又.”.”“不仅不仅.而且而且.”n“虽然虽然.但是但是.p q p q000110110001 例:将下列命题符号化 p:李平聪明李平聪明.q:李平用功李平用功.(1)李平李平既既聪明聪明又又用功用功.(2)李平李平虽然虽然聪明聪明但但不用功不用功.(3)李平李平不但不但聪明聪明而且而且用功用功.(4)李平李平不是不是不聪明不聪明而是而是不用功不用功.p qp qp q(p)q例例:p:今天下雨今天下雨.q:3+3=6今天下雨与今天下雨与3+3=6.可表示为可表示为:p q“”可以连接两个完全没有联系的命题可以连接两个完全没有联系的命题.联结词n例如：例如：np:灯泡有故障灯泡有故障.q:开关有故障开关有故障.n灯泡有故障或开关有故障灯泡有故障或开关有故障.(可能同时发生可能同时发生)n应表示为应表示为p qn注意注意:析取词析取词 表示的是表示的是“可兼或可兼或”.n例如例如:np:小王正在宿舍小王正在宿舍.q:小王正在图书馆小王正在图书馆.n小王现在在宿舍或在图书馆小王现在在宿舍或在图书馆.（不可能同时发生）（不可能同时发生）n表示为：表示为：(p q)(p q)=p q书P4：例1.6(2):也可表示为p q p q pq000110110110 p q p q0001101101114.蕴涵n定义定义:设设p、q为二命题，复合命题为二命题，复合命题“如果如果p，则，则q”称作称作p与与q的的蕴涵式蕴涵式，记作，记作pq，并称，并称np是蕴涵式的是蕴涵式的前件前件，nq为蕴涵式的为蕴涵式的后件后件.n称作称作蕴涵联结词蕴涵联结词，np是是q的的充分条件充分条件，q是是p的的必要条件必要条件。n常见错误常见错误n不分不分充分与必要条件或充分与必要条件或混淆混淆充分与必要条件充分与必要条件联结词n“如果如果 p，则，则 q”的不同表述法很多的不同表述法很多n若若p，就就qn只要只要p，就就qnp仅当仅当qn只有只有q才才pn除非除非q,才才pn除非除非q,否则非否则非p联结词（1）只要不下雨，我就骑自行车上班。（2）只有不下雨，我才骑自行车上班。设：设：p：天下雨。：天下雨。q：我骑自行车上班。：我骑自行车上班。（1）等价为：除非下雨，否则我就骑自行车上班除非下雨，否则我就骑自行车上班。pq（2）等价为：如果下雨，我就不骑自行车上班如果下雨，我就不骑自行车上班。q p注意：注意：pq中的中的p和和q不一定有内在联系不一定有内在联系。例:将下列命题符号化 联结词n规定规定npq为假当且仅当为假当且仅当p为真为真q为假为假.n当当p为假时，为假时，p q为真为真n说明说明n如：如：p：“天气好天气好”q：“我去接你我去接你”n则则pq：“若天气好，若天气好，则则我去接你我去接你”n当天气好当天气好时时，n我去接了你，此我去接了你，此时时，pq真真n我没去接你，此我没去接你，此时时，pq假假n当天气不好当天气不好时时，n我无我无论论去或不去接你均未食言，此去或不去接你均未食言，此时认时认定定pq为为真真是适当的是适当的 p q pq000110111101pq=p q联结词举例p：两个三角形是全等的。q：两个三角形的三条对应边相等。则等价命题：则等价命题：p q：两个三角形全等，当且仅当它们的三条对应边两个三角形全等，当且仅当它们的三条对应边分别相等。分别相等。下列复合命题的真值为(1)2+2 4 当且仅当当且仅当 3+3 6.(2)2+2 4 当且仅当当且仅当 3 是偶数是偶数.(3)2+2 4 当且仅当当且仅当 太阳从东方升起太阳从东方升起.110联结词的优先顺序为：联结词的优先顺序为：,1.2命题公式及分类n命题常项n真值确定的简单命题。真值确定的简单命题。n如：如：2 2是素数。是素数。n命题常项的真值是确定不变的，取值为命题常项的真值是确定不变的，取值为1或或0。n命题变项n泛指简单的陈述句。符号表示如泛指简单的陈述句。符号表示如p,qn命题变项的真值不确定。命题变项的真值不确定。n命题公式n把把命命题题常常量量、命命题题变变量量按按照照一一定定的的逻逻辑辑顺顺序序用用命命题题联联结词结词连接起来就构成了命题演算的连接起来就构成了命题演算的合式公式。合式公式。命题公式n命题公式（合式公式)的递归定义：(1)单单个个命命题题常常项项或或变变项项p,q,r,pi,qi,ri,0,1是是合合式公式式公式(2)若若A是合式公式，则是合式公式，则(A)也是合式公式也是合式公式(3)若若A,B是是合合式式公公式式，则则(A B),(A B),(AB),(AB)也是合式公式也是合式公式(4)只只有有有有限限次次地地应应用用(1)(3)形形成成的的符符号号串串才才是是合合式式公式公式n说明:元语言与对象语言元语言与对象语言,外层括号可以省去外层括号可以省去n即即(A)、(A B)等等外外括括号号可可省省去去成成 A、A B。n(pq),p(qr),(p q)r是命题公式是命题公式npqr,pq，(pr)(p)不是命题公不是命题公式式公式的赋值n定义定义 n给给公公式式A中中的的命命题题变变项项p1,p2,pn指指定定一一组组真真值值称称为对为对A的一个的一个赋值赋值或或解释。解释。n成真赋值成真赋值:使公式为真的赋值使公式为真的赋值n成假赋值成假赋值:使公式为假的赋值使公式为假的赋值n说明：说明：nA中中仅仅出出现现p1,p2,pn，给给A赋赋值值 1 2 n是是指指p1=1,p2=2,pn=nn赋值赋值=1 2 n之间不加标点符号，之间不加标点符号，i=0或或1.n如：A=（p q）rn111（p=1，q=1，r=1）为成真赋值，n110（p=1，q=1，r=0）为成假赋值n含含n个变项的公式有个变项的公式有2n个赋值个赋值.真值表 真值表公式在所有赋值下的取值情况列成的表五个联结词的含义由真值表唯一确定五个联结词的含义由真值表唯一确定 p q p q p q pq q p000110110111000111011001 p p0110公式公式B=(p q)q的的真值表真值表 p q p p q (p q)(p q)q0 00 11 01 11100110100100000若公式若公式B无无成真赋值成真赋值，则称，则称B为为矛盾式矛盾式(也称也称永假式永假式)公式公式 C=(p q)r的的真值表真值表 p q r p q r (p q)r0 0 00 0 10 1 00 1 11 0 01 0 11 1 0 1 1 10011111 11010101 011101010若公式若公式C不是不是矛盾式矛盾式，则称，则称C为为可满足式可满足式)注意：重言式是可满足式，重言式是可满足式，但反之不真但反之不真.作业1P32:1(2)(4)(6)(8)P33:3(1)(3)(5)P33:5(1)(3)(5)(7)P33:6(1)(2)P33:7(1)(2)
