离散数学数理逻辑初步.ppt

《离散数学数理逻辑初步.ppt》由会员分享，可在线阅读，更多相关《离散数学数理逻辑初步.ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学数理逻辑初步现在学习的是第1页，共60页前言计算机科学基础理论的核心课程研究离散量的结构和相互之间的关系数学与计算机科学的结合点现在学习的是第2页，共60页主要内容数理逻辑初步集合论代数结构图论上述内容之间有密切联系,但是看起来又是非常离散的!现在学习的是第3页，共60页数理逻辑初步内容提要用数学方法来研究推理的规律引进一套符号体系基本内容：命题逻辑和谓词逻辑现在学习的是第4页，共60页数理逻辑初步命题逻辑什么是命题？具有真假值判断的陈述句 注意感叹句、疑问句、祈使句等都不是命题；悖论也不是命题。真假值的表示 真值=True=T;假值=False=F现在学习的是第5页，共60页数理逻辑

2、初步命题种类与表示1.原子命题不能分解为更为简单的陈述句；通常用大写字母表示，A，B，P，Q2.复合命题有限个原子命题由若干个联结词按一定规则复合构成的;注意:复合命题的真假值将由它所包含的原子命题的真假值和联结词的逻辑意义所决定.现在学习的是第6页，共60页数理逻辑初步联结词(1)否定 P是一命题,P为P的否定;P的逻辑意义为当P为真时P为假；当P为假时，P为真。PPTFFT现在学习的是第7页，共60页数理逻辑初步联结词(2)合取 P、Q是两个命题,PQ是合取复合命题;PQ的逻辑意义为当且仅当P、Q同时为真时，PQ为真。PQPQTTTTFFFTFFFF现在学习的是第8页，共60页数理逻辑初步

3、联结词(3)析取 P、Q是两个命题,P Q是析取复合命题;P Q的逻辑意义为当且仅当P、Q同时为假时，P Q为假。PQP QTTTTFTFTTFFF现在学习的是第9页，共60页数理逻辑初步联结词(4)条件（蕴涵）P、Q是两个命题,P Q是一个条件复合命题;P Q的逻辑意义为当且仅当P为真、Q为假时，P Q为假。PQP QTTTTFFFTTFFT现在学习的是第10页，共60页数理逻辑初步联结词(5)双条件（等价）P、Q是两个命题,P Q是一个等价复合命题;P Q的逻辑意义为当且仅当P和Q的真值相同时，P Q为真。PQP QTTTTFFFTFFFT现在学习的是第11页，共60页数理逻辑初步最小联结

4、词集能够表达其它联结词的逻辑意义，但不能互相表达。可以证明：最小联结词集为，（或，）*因为（涉及下面讲的等值公式）：P Q=（P Q）；P Q=P Q；P Q=（P Q）（Q P）。现在学习的是第12页，共60页数理逻辑初步命题公式（合式公式）回忆：联结词需要有一定规则构成复合命题。递归定义（1）原子命题是一个命题公式；（2）如果A是命题公式，那么A也是命题公式；（3）如果A和B是命题公式，那么AB、A B、A B和 A B都是命题公式；（4）一个命题公式只能有限次地应用（1）、（2）、（3）得到。现在学习的是第13页，共60页数理逻辑初步思考 给定任意一串字符，如何判定它是否为一个命题公式？

5、现在学习的是第14页，共60页数理逻辑初步表达与翻译目标：知识表达（推理的第一步）过程：原子命题+联结词+逻辑意义例子Q：上海到北京的火车是下午五点半或六点开。A：P=上海到北京的火车是下午五点半开；Q=上海到北京的火车是下午六点开。原句为（P Q）（P Q）现在学习的是第15页，共60页数理逻辑初步指派与真值表指派：命题公式中所含的原子命题的真值的一种组合；真值表：所有指派列成的表。请看书中例题现在学习的是第16页，共60页数理逻辑初步命题公式等值（等价公式）两个命题公式在所有不同指派下所对应的真值相同，即它们的真值表相同，那么这两个命题公式等值。回忆：表达的例子（上海到北京的火车）（P Q

6、）=（P Q）（P Q）现在学习的是第17页，共60页数理逻辑初步 命题等值基本定律对合律 P=P1幂等律PP=P,PP=P2结合律(P Q)R=P(Q R)(PQ)R=P(Q R)3交换律P Q=Q P,P Q=Q P4分配律P(Q R)=(P Q)(P R)P(Q R)=(P Q)(P R)5吸收律P (P Q)=P,P(P Q)=P6De Morgan律(P Q)=P Q(P Q)=P Q7同一律PF=P,PT=P8零律PT=T,PF=F9否定律P P=T,P P=F10现在学习的是第18页，共60页数理逻辑初步等值置换与证明等值置换：如果是的子命题公式，那么将中的用来置换所得到的公式与

7、等值，即。等值公式的证明（）真值表相同；（）经过等值置换后得到。现在学习的是第19页，共60页数理逻辑初步重言式（永真式）永真公式：所有指派下都取真值；永假公式：所有指派下都取假值。几个结论：（）任何两个永真式的合取（或析取）都永真；（）永真式经等值置换后仍永真；（）当且仅当永真。现在学习的是第20页，共60页数理逻辑初步对偶注意：传统上，命题公式通常包含，而不是最小联结词集，或，对偶式：在命题公式A中将联结词换成，将换成，T换成F，F换成T，所得公式A*与A互为对偶。现在学习的是第21页，共60页数理逻辑初步关于对偶的几个结论设A和A*是对偶式，P1，P2，Pn是出现在命题公式中的原子命题，

8、则 A(P1，P2，Pn)=A*(P1，P2，Pn)(注：用数学归纳法可证）P1，P2，Pn是出现在命题公式中的原子命题，如果A=B，则A*=B*。现在学习的是第22页，共60页数理逻辑初步范式文字：原子命题与它的非；简单合取式：有限个文字组成的合取式；简单析取式：有限个文字组成的析取式；合取范式：有限个简单析取式的合取；析取范式：有限个简单合取式的析取。现在学习的是第23页，共60页数理逻辑初步思考任何一个命题公式都可以等值转化为合取范式或析取范式吗？如果可以转换，那么合取范式或析取范式是唯一的吗？现在学习的是第24页，共60页数理逻辑初步主范式：范式的唯一性小项：所有原子命题或它的非都在简

9、单合取式中出现，但不同时出现。每一个小项唯一地对应一个简单合取式，任意两个不同小项的合取永假，全体小项的析取永真。大项：所有原子命题或它的非都在简单析取式中出现，但不同时出现。每一个大项唯一地对应一个简单析取式，任意两个不同的大项的析取永真，全体大项的合取永假。现在学习的是第25页，共60页数理逻辑初步主合取范式和主析取范式主合取范式：仅由大项所组成的合取范式；主析取范式：仅由小项所组成的析取范式。从命题公式的真值表中可得到主合取范式和主析取范式：成真指派所对应的小项的析取即为主析取范式；成假指派所对应的大项的合取即为主合取范式。为什么？现在学习的是第26页，共60页数理逻辑初步基本推理 设H

10、1，H2，Hn，C是一组命题公式，C是前提H1，H2，Hn的逻辑结论的充分必要条件是（H1 H2 Hn）C永真。通常记为：（H1 H2 Hn）C（即在使前提为真的所有指派下结论也为真）重要性：在符号世界和现实世界中建立了一条道路！现在学习的是第27页，共60页数理逻辑初步推理方法真值表法直接证明法间接证明法 欲证明（H1 H2 Hn）C永真，即证明 H1 H2 Hn C永假！现在学习的是第28页，共60页数理逻辑初步谓词逻辑知识表达的粒度问题原子命题：命题层次不可分解刻画命题内部的逻辑结构的需要命题逻辑的局限性 例子：三段论 所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。现在学习的是

11、第29页，共60页数理逻辑初步谓词的概念对命题概念的扩充与分解把命题分成两个结构：主语和谓语主语：描述具体或抽象的客体（个体）；谓语：刻划客体的性质或关系。现在学习的是第30页，共60页数理逻辑初步谓词的表示主语：小写字母，a,b,x,y谓语：大写字母，A，B，P，Q谓词：P（a）（注：一元原子谓词）推广到 n 元原子谓词 P（a1,a2,an）具有真假值原子命题即为0元原子谓词现在学习的是第31页，共60页数理逻辑初步常元与变元常元：个体作为常量，表示具体的客体；通常用 a,b,c 表示。变元：个体作为变量，表示抽象的客体；通常用 x,y,z 表示。现在学习的是第32页，共60页数理逻辑初步

12、个体域个体的定义域：客体的论述范围有限或无限全总个体域：所有个体所组成的集合现在学习的是第33页，共60页数理逻辑初步函词个体的函数：值域还是个体域 f(x1,x2,xn)=y,x1,x2,xn为 n 个常元或变元，y是一个常元或变元，f 是 n 元函词。注意：函词与谓词的区别！现在学习的是第34页，共60页数理逻辑初步项递归定义：（1）常元是项；（2）变元是项；（3）如果 f 是 n 元函词，x1,x2,xn为 n 个项，那么f(x1,x2,xn)也是项；（4）项只能有限次应用上述（1）、（2）、（3）得到。现在学习的是第35页，共60页数理逻辑初步自由变元与约束变元自由变元：变元在个体域中

13、自由取值；约束变元：变元在个体域中的取值是受到一定约束的。约束的定性化与定量化：自由变元=量词约束=常元现在学习的是第36页，共60页数理逻辑初步量词表示变元在个体域中的定性约束全称量词：表示个体域中的所有个体；记作存在量词：表示个体域中的某几个个体；记作 现在学习的是第37页，共60页数理逻辑初步量词的作用域对于x P(x)或x P(x)，x 是约束变元，谓词P(x)即为量词的辖域（作用域）。注意：量词的约束只在它的作用域内，也就是说，量词作用域之外的变元是自由变元。现在学习的是第38页，共60页数理逻辑初步谓词公式（合式公式）递归定义（1）原子谓词公式是谓词公式；（2）若A（x1,x2,x

14、n)是 n 元原子谓词公式，t1,t2,tn是项，则A（t1,t2,tn）也是谓词公式；（3）若A是谓词公式，则A也是谓词公式；（4）若A和B都是谓词公式，则AB、A B、A B和 A B也是谓词公式；（5）若A是谓词公式，x是A中出现的任意变元，则Vx A和x A也是谓词公式；（6）一个谓词公式只能有限次地应用上述规则得到。现在学习的是第39页，共60页数理逻辑初步思考给定任意一个字符串，如何判断它是否为一个谓词公式？现在学习的是第40页，共60页数理逻辑初步约束变元的改名避免变元名称的混淆约束变元的逻辑意义与使用名称无关则有Vx A(x)=Vy A(y)x A(x)=y A(y)现在学习的

15、是第41页，共60页数理逻辑初步自由变元的代入自由变元作为参数自由变元的改名需要保持一致代入后不能与约束变元相冲突 改名与代入的意义在于：使得谓词公式中的变元名称各不相同，逻辑意义更加清楚。现在学习的是第42页，共60页数理逻辑初步谓词公式的真值与哪些因素有关？谓词个体域函词量词联结词现在学习的是第43页，共60页数理逻辑初步思考给定一个谓词公式，如何判断它的真假值？*首先，谓词公式的真假值能够判定吗？（注意：个体域的不可确定性）现在学习的是第44页，共60页数理逻辑初步谓词公式的指派谓词（包括命题）、函词、量词和个体域组成指派的成分通常把个体域单独考虑由于个体域有无限多个，通常假定为全总个体

16、域作为缺省个体域注：谓词公式的真值表能列出吗？现在学习的是第45页，共60页数理逻辑初步表达与翻译符号世界与现实世界的转换知识表达的更细粒度过程：原子谓词的表示确定常元与变元存在函词、量词吗？联结词的选择现在学习的是第46页，共60页数理逻辑初步谓词公式表达举例极限的定义P(x,y)：x 大于 y;Q(x,y)：x 小于 y;(V)()(Vx)(P(,0)P(,0)Q(|x-a|,)P(|x-a|,0)Q(|f(x)-b|,)现在学习的是第47页，共60页数理逻辑初步谓词公式的等值回忆：无法判断谓词公式的真假值！但是：在确定的个体域中，可以判断谓词公式的真假值！对于两个谓词公式A和B，在相同的

17、个体域E下，所有的指派都有相同的真值，那么A和B在个体域E下等值。现在学习的是第48页，共60页数理逻辑初步等值谓词公式（举例）命题公式的推广量词与否定的关系 (Vx)P(x)=(x)P(x)(x)P(x)=(Vx)P(x)量词作用域的变化量词与联结词的关系 （请看书中例子）现在学习的是第49页，共60页数理逻辑初步永真的、可满足的和不可满足的永真的：一个谓词公式在一个确定的个体域下的所有指派都为真；可满足的：一个谓词公式在一个确定的个体域下的有某些指派为真；不可满足的：一个谓词公式在一个确定的个体域下的所有指派都为假。现在学习的是第50页，共60页数理逻辑初步思考谓词公式有标准形式吗？现在学

18、习的是第51页，共60页数理逻辑初步前束范式前束范式：所有量词都在公式的前面，即如形式 1x 1 2x 2 mx m P，其中i 取 V 或，P是母式，x 为变元。现在学习的是第52页，共60页数理逻辑初步结论：谓词公式可以转化成前束范式关键：？如何转化？注意：为了变元清晰，需要使用改名！现在学习的是第53页，共60页数理逻辑初步进一步：前束合取范式前束合取范式：母式为合取范式的前束范式结论：任意一个谓词公式都可以等值转化为一个前束合取范式。为什么？现在学习的是第54页，共60页数理逻辑初步进一步：前束析取范式前束析取范式：母式为析取范式的前束范式与前束合取范式类似的结论。现在学习的是第55页

19、，共60页数理逻辑初步更进一步：全称前束合取范式全称前束合取范式：前束合取范式中的开头量词都是全称量词结论：任意一个谓词公式都可以转化为全称前束合取范式。Q：怎么转化？A：引入一个特殊函词=现在学习的是第56页，共60页数理逻辑初步Skolem函词对于前束合取范式 1x 1 2x 2 mx m P，假定k是第一个出现的存在量词，用一个函词f(x1,x2,xk-1)来代替在P中出现的xk,其真假值不变！（其它的存在量词依此类推）为什么？现在学习的是第57页，共60页数理逻辑初步谓词公式的推理与命题逻辑方法相类似设H1，H2，Hn，C是一组命题公式，（H1 H2 Hn）C的充分必要条件是（H1 H2 Hn）C永真，即 H1 H2 Hn C永假。现在学习的是第58页，共60页数理逻辑初步应用简单规则的推理方法（1）全称指定规则(Vx)P(x)P(a),a是常元。（2）全称推广规则P(x)(Vy)P(y)，x是自由变元。（3）存在指定规则(x)P(x)P(a)。（4）存在推广规则P(a)(x)P(x)。现在学习的是第59页，共60页数理逻辑初步基本推理举例三段论（苏格拉底）注：复杂的推理方法请看数理逻辑方面的专著。现在学习的是第60页，共60页