编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、.ppt

离散数学是计算机科学离散数学是计算机科学(编译原理、数据结构、操编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、计算作系统、数据库系统、算法的分析与设计、计算机网络等机网络等)、数学、数字电路、人工智能等多学、数学、数字电路、人工智能等多学科的共同语言和基础。科的共同语言和基础。本学期将讲授数理逻辑与图论个部分本学期将讲授数理逻辑与图论个部分。其中数理逻辑讲授命题逻辑、谓词逻辑两部分，其中数理逻辑讲授命题逻辑、谓词逻辑两部分，分别由分别由Boole于于1847年和年和Frege于于1879年建立。命年建立。命题逻辑把简单命题作为基本单元进行推理演算；题逻辑把简单命题作为基本单元进行推理演算；而谓词逻辑对简单命题进一步剖析，并考虑到变而谓词逻辑对简单命题进一步剖析，并考虑到变量数量的一般与个别。量数量的一般与个别。前言前言1例例1 1：在举重比赛中，有两名副裁判，一名：在举重比赛中，有两名副裁判，一名主裁判。当两名以上裁判（必须包括主裁判主裁判。当两名以上裁判（必须包括主裁判在内）认为运动员举杠铃合格，按电钮，才在内）认为运动员举杠铃合格，按电钮，才裁决合格。试用与非门设计该电路。裁决合格。试用与非门设计该电路。解解：设主裁判为变元：设主裁判为变元A A，副裁判分别为变元副裁判分别为变元B B和变元和变元C C；按电钮为按电钮为1 1，不按为，不按为0 0。表示合格。表示合格与否的灯为与否的灯为Y Y，合格为合格为1 1，否则为，否则为0 0。（1 1）根据逻辑要求列出真值表。）根据逻辑要求列出真值表。关于命题逻辑的两个有趣例子关于命题逻辑的两个有趣例子2真 值 表3（2）由真值表写出表达式：（3）化简：这个小例子涉及到简单命题、复合命题、逻辑联结词的定义、运算优先权、联结词的完备集(例如“与非联结词”构成一个完备集)等等。我们都将介绍到。4（4）画出逻辑电路图：5例例2 2：设计一个楼上、楼下开关的控制逻辑电：设计一个楼上、楼下开关的控制逻辑电路来控制楼梯上的路灯。使之在上楼前，用楼路来控制楼梯上的路灯。使之在上楼前，用楼下开关打开电灯，上楼后，用楼上开关关灭电下开关打开电灯，上楼后，用楼上开关关灭电灯；或者在下楼前，用楼上开关打开电灯，下灯；或者在下楼前，用楼上开关打开电灯，下楼后，用楼下开关关灭电灯。楼后，用楼下开关关灭电灯。解：解：设楼上开关为变元设楼上开关为变元A A，楼下开关为变元楼下开关为变元B B，灯灯泡为变元泡为变元Y Y。并设并设A A、B B向上时为向上时为1 1，向下时为，向下时为0 0；灯亮时；灯亮时Y Y为为1 1，灯灭时，灯灭时Y Y为为0 0。6本题的解题关键在于：不管开关和灯处于什么状态，灯的状态改变当且仅当只有一个开关的状态发生改变。因此，本题有多解。（1）若A=0,B=0时Y=0，则相应真值表设计如下7相应逻辑表达式为用异或门实现8（2）若A=0,B=0时Y=1，则相应真值表设计如下相应逻辑表达式为9用同或门实现10第1章命题逻辑的基本概念l内容：内容：命题逻辑研究的是命题的推理演算这一章介绍命题逻辑的基本概念，包括引入命题联结词，讨论合式公式、重言式以及自命题联结词，讨论合式公式、重言式以及自然语句的形式化等内容然语句的形式化等内容11命题逻辑的基本概念l命题定义：命题是一个非真即假命题定义：命题是一个非真即假(不可兼不可兼)的陈的陈述句述句有两层意思，首先首先命题是一个陈述句，其次其次真假不可兼l命题的取值称为真值命题的取值称为真值 l通常用T表示真值为真，用F表示真值为假因为只有两种取值，所以这样的命题逻辑称为二二值逻辑值逻辑12举例说明l(1)“雪是白的”是命题是命题，真值为真真值为真l(2)“雪是黑的”是命题是命题真值为假真值为假l(3)“好大的雪啊”不是陈述句，不是命题不是陈述句，不是命题l(4)“一个偶数可表示成两个素数之和”是命是命题题，不知真值不知真值l(5)“1+101110”是命题是命题，这个句子所表达的内容在十进制范围中真值为假十进制范围中真值为假，而在二进制范围二进制范围中真值为真中真值为真可见，这个命题的真值与所讨论问题的范围(论域论域)有关13命题变项l命题变项定义：命题变项定义：约定用大写字母表示命题用大写字母表示命题，如以P表示“雪是白的”，Q表示“北京是中国的首都”等当当P P表示任一命题时，表示任一命题时，P P就称为命题就称为命题变项变项(变元变元)l命题与命题变项区别：命题与命题变项区别：命题与命题变项含义是不同的，命题指具体的陈述句，是有确定的真值，而命题变项的真值不定，只当将某个具体命只当将某个具体命题代入命题变项时题代入命题变项时，命题变项化为命题，方可确方可确定其真值定其真值，命题与命题变项像数学中常量与变量常量与变量的关系一样在不混淆的情况下，逻辑演算中不在不混淆的情况下，逻辑演算中不再区分它们了。再区分它们了。14简单命题和复合命题l简单命题定义：简单命题又称原子命题，它是不简单命题定义：简单命题又称原子命题，它是不包含任何的与、或、非一类联结词的命题包含任何的与、或、非一类联结词的命题如111中例子这样的命题不可再分割不可再分割，如再分割就不是命题了而像命题“雪是白的而且l+l2”，就不是简单命题，它可以分割为“雪是白的”以及“1十12”两个简单命题，联结词是“而且”l命题逻辑与谓词逻辑区别：命题逻辑与谓词逻辑区别：命题逻辑中将简单命题作为一个不可分的整体来看待在谓词逻辑里，才对命题中的主谓结构进行深入分析15l复合命题定义：复合命题定义：把一个或几个简单命题用联结词(如与、或、非)联结所构成的新的命题称为复合命题l复合命题真值判断：复合命题真值判断：复合命题自然也是陈述句，其真值依赖于构成该复合命题的各各简单命题简单命题的真值以及联结词联结词，如“张三学英语和李四学日语”就是一个复合命题，由简单命题“张三学英语”“李四学日语”经联结词“和”联结而成，这两个简单命题真值均为真时，该复合命题方为真16l数理逻辑关心什么？不关心内容：数理逻辑关心什么？不关心内容：这些具体的陈述句的真值究竟为什么是真还是假。关心形式：关心形式：关心的仅是命题可以被赋予真或假这样的可能性，以及规定了真值后怎样与其他命题发生联系17命题联结词及真值表l联结词可将命题联结起来构成复杂的命题，从而使命题逻辑的内容变得丰富起来。l值得注意的是逻辑联结词与日常自然用语中的有关联结词的共同点和不同点18常用的逻辑联结词l称谓、读法、记号称谓、读法、记号：否定词“”是个一元联结词，亦称否定符号，读作非。一个命题P加上否定词就形成了一个新的命题，记作P。l否定词的运算规则真值表否定词的运算规则真值表：1.否定词否定词19PPTFFT20例1l“昨天张三去看球赛了”该命题以P表示，于是l“昨天张三没有去看球赛”，该新命题便可用P表示l若昨天张三去看球赛了，命题P是真的，那么新命题P必然是假的反之，若命题P是假的，那么P就是真的21例2lQ：今天是星期三lQ：今天不是星期三l然而Q不能理解为“今天是星期四”，因为“今天是星期三”的否定，并不一定必是星期四，还可能是星期五、星期六222.2.合取词合取词l称谓、读法、记号称谓、读法、记号：合取词是个二元命题联结词，亦称合取符号将两个命题P，Q联结起来，构成一个新的命题PQ，读作P,Q的合取，也可读作P与Ql合取词的运算规则真值表：合取词的运算规则真值表：23PQPQFFFFTFTFFTTT24例3lP：教室里有10名女同学lQ：教室里有15名男同学l不难看出，命题PQ:“教室里有10名女同学与15名男同学”25例4lA：今天下雨了lB：教室里有100张桌子。l可知AB就是命题“今天下雨了并且教室里有100张桌子”26同日常自然用语关系同日常自然用语关系l日常自然用语里的联结词“和”、“与”、“并且”，一般是表示两种同类有关事物的并列关系而在逻辑语言中仅考虑命题与命题之间的形式关系并不顾及日常自然用语中是否有此并不顾及日常自然用语中是否有此说法说法这样，“”同“与”、“并且”又不能等同视之l逻辑联结词是自然用语中联结词的抽象，两者两者并不等同并不等同。合取词有“与”、“并且”的含义，有时也有“但是”的含义。273析取词l称谓、读法、记号称谓、读法、记号：析取词“”是个二元命题联结词。将两个命题P、Q联结起来,构成一个新的命题PQ,读作P、Q的析取,也读作P或Q。l运算规则真值表：运算规则真值表：28PQPQFFFFTTTFTTTT当P、Q有一取值为T时,PQ便为T。仅当P、Q均取F值时,PQ方为F。这就是析取词的定义,PQ可用来表示自然用语P或Q。29l例5:P:今天刮风。Q:今天下雨。命题“今天刮风或者下雨”便可由PQ来描述了。l例6:A:2小于3。B:雪是黑的。AB就是命题“2小于3或者雪是黑的”。由于2小于3是真的,所以AB必取值为真,尽管“雪是黑的”这命题取假。304 4 蕴涵词蕴涵词l称谓、读法、记号称谓、读法、记号：蕴涵词“”也是个二元命题联结词。将两个命题P、Q联结起来,构成一个新的命题PQ,读作如果P则Q,或读作P蕴涵Q,如果P那么Q,其中P称前件(前项、条件),Q称后件(后项、结论)。l运算规则：运算规则：规定只有当P为T而Q为F时,PQ=F。而P=F、Q任意,或P=T、Q=T时PQ均取值为T。运算规则真值表运算规则真值表：31PQPQFFTFTTTFFTTTPQ体现了P是Q成立的充分条件。PQ体现了P不必是Q成立的必要条件。32l引入引入的目的：的目的：希望用来描述命题间的推理,表示因果关系。即PQ为真时,只要P为真必有Q真,。l其它定义：其它定义：当P=F时对PQ真值的不同定义方式将给推理的讨论带来不同的表示形式,也是允许的。33 性质性质：可由可由、来表示：来表示：PQ=PQPQPQFFTFTTTFFTTT注意1：真值相同的等值命题以等号联结2：从逻辑上看“如果P则Q”同“非P或Q”是等同的两个命题3：实际上，,构成一个联结词的完备集，可表达任何联结词。34l同自然用语关系：同自然用语关系：蕴涵词与自然用语“如果那么”有一致的一面，可表示因果关系。然而P、Q是无关的命题时,逻辑上允许讨论PQ。并且P=F则PQ=T,这在自然用语中是不大使用的。35例7:P:n3(n为整数)Q:n29命题PQ表示“如果n3那么n29”,分析PQ的真值。1.P=Q=T。这时如n=43,有n2=169,这符合事实PQ=T,正是我们所期望的可以PQ表示P、Q间的因果关系,这时规定PQ=T是自然的自然的。2.P=T,Q=F。如n3而n29这是不会成立的,也可用PQ表示P、Q间的因果关系是不成立的,自然规定自然规定PQ=F。3.P=F而Q=F或T。如n=23有n2=49n=-49由于前提条件n3不成立，而n29成立与否并不重要，都不违反不违反对自然用语“如果n3那么n29”成立的肯定。于是P=F时可规定PQ=T。36例8：P:2+2=5Q:雪是黑的PQ就是命题“如果2+2=5,那么雪是黑的”。从蕴涵词的定义看，由2+2=5是不成立的或说P取F值,不管Q取真取假都有PQ=T。375双条件词PQPQFFTFTFTFFTTT 称谓、读法称谓、读法称谓、读法称谓、读法(等价于、当且仅当等价于、当且仅当)、记号、记号、记号、记号：运算规则真值表：运算规则真值表：运算规则真值表：运算规则真值表：38l真值表解释真值表解释：只有当两个命题P、Q的真值相同或说P=Q时,PQ的真值方为T。而当P、Q的真值不同时,PQ=F。l性质性质：若建立(PQ)(QP)的真值表,就可发现(PQ)(QP)和PQ有相同的真值,于是(PQ)(QP)=PQ39例9P:ABC是等腰三角形Q:ABC中有两个角相等命题PQ就是“ABC是等腰三角形当且仅当ABC中有两个角相等”。显然就这个例子而言PQ=T。40总结l完备集初探：完备集初探：定义的五个联结词是数理逻辑中最基本最常用的逻辑运算。一元二元多元联结词还有很多，这个个数是算得出的。l联结词使命：联结词使命：联结词是由命题定义新命题的基本方法。l真值表方法是极为有力的工具真值表方法是极为有力的工具(如：书写逻辑表达式、建立新型联结词)。41l取值、真值、真值指派、真值组合、解释取值、真值、真值指派、真值组合、解释：由联结词构成新命题的真值表中，对仅由两个变元P、Q构成的新命题A而言,每个变元有T、F两种取值取值,从而P、Q共有四种可能的取值,对应于真值表中的四行,每一行中命题A都有确定的真值真值。对P、Q的每组真值组合真值组合(如P=T,Q=F)或说真值指派真值指派,都称作命题A的一个解释解释。l上述概念的推广：上述概念的推广：一般地说,当命题A依赖于命题P1,Pn时，由P1,Pn到A的真值表就有2n行,每一行对应着P1,Pn的一组真值称作命题A的一个解释解释。A有2n个解释,命题的命题的解释用符号解释用符号I表示表示。42l与自然用语的差异与自然用语的差异l与硬件电路关系：与硬件电路关系：联结词、同构成计算机的与门、或门和非门电路是相对应的。从而命题逻辑是计算机硬件电路的表示、分析和设计的重要工具。l不同的符号表达方法：不同的符号表达方法：五个联结词在不同的书中会采用不同的符号。如P可以以P表示,PQ以PQ表示,PQ以P+Q表示等等。阅读时应注意不同的表示方式。431.3 1.3 合式公式合式公式l命命题题逻逻辑辑的的全全部部符符号号由由命命题题变变项项、命命题题联联结结词词和圆括号组成。和圆括号组成。怎样组合，才能使生成的命题公式有意义呢？怎样组合，才能使生成的命题公式有意义呢？44 合式公式(简记为wff)的定义：1.(1.(初始初始)简单命题是合式公式。简单命题是合式公式。2.(2.(递归递归)如果如果A A是合式公式是合式公式,那么那么 A A也是合式也是合式公式。公式。3.(3.(递归递归)如果如果A A、B B是合式公式是合式公式,那么那么(AB),(AB),(AB),(A(AB),(AB)B)和和(A(AB)B)是合式公式。是合式公式。4.4.当且仅当经过当且仅当经过有限次有限次地使用地使用1.2.31.2.3所组成的所组成的符号串才是合式公式。符号串才是合式公式。(Well Formed Formula)45合式公式的判断：层层解脱回归到简单命题例：例：(P(PQ)(QQ)(QR)R)(P(PR)R)是合式公式。是合式公式。(P(PQ)Q)(Q)(Q)不是合式公式。不是合式公式。46l通过定义优先级进行简写(省去部分圆括号)1.规定联结词运算优先级：按(),，的排列次序。2.多个同一联结词按从左到右的优先次序。(P(QR)可写成P(QR)或PQR。(P(PR)可写成P(PR)。l命题演算中只讨论合式公式,将合式公式就称作公式。471.4 1.4 重言式重言式 /可满足式可满足式/矛盾式矛盾式l重言式：重言式：如果一个公式，对于任一解释I，其真值都为真，就称为重言式（永真式）。如PP是一个重言式。由由、和和联结的重言式仍是重言式。联结的重言式仍是重言式。l矛盾式（永假式或不可满足式）矛盾式（永假式或不可满足式）：如果一个公式，对于任一解释I值都是假的，便称是矛盾式。如PP就是矛盾式。由什么联结的矛盾式仍是矛盾式？由什么联结的矛盾式仍是矛盾式？l可满足式可满足式：一个公式，如在某个解释I0下值为真,则称它是可满足的。重言式当然是可满足的。48 三类公式间关系三类公式间关系三类公式间关系三类公式间关系1.公式A永真，当且仅当永假。2.公式A可满足,当且仅当A非永真。3.不是可满足的公式必永假。4.不是永假的公式必可满足。49 代入规则代入规则定义：一个重言式，对其中所有相同的定义：一个重言式，对其中所有相同的*命题命题变项变项*都用一个合式公式代换，其结果都用一个合式公式代换，其结果也是重言式。也是重言式。例例*：可用：可用(RS)来代换某公式中的来代换某公式中的P,记为记为而不能反过来用而不能反过来用P代换某公式中的代换某公式中的(RS)。50例例*A=P P,使用使用 得得 B=QQ 仍是重言式。仍是重言式。若将若将 P以以Q代替得代替得B=PQ不是重言式了不是重言式了n n例例1:1:判断判断(R(RS)S)(R(RS)S)为重言式。为重言式。因因P P P P为重言式为重言式,P,P以以(R(RS)S)代入代入得得(R(RS)S)(R(RS)S)。依据代入规则依据代入规则,这公式必是重言式。这公式必是重言式。n n例例2 2：判断判断(R(RS)S)(R(RS)S)(P(PQ)Q)(P(PQ)Q)为重为重言式言式.不难验证不难验证(A(A(A(AB)B)B B是重言式是重言式,A A 以以R RS S代入，代入，B B 以以P PQ Q代入代入得得(R(RS)S)(R(RS)S)(P(PQ)Q)(P(PQ)Q)是重言式。是重言式。511.5 1.5 命题形式化命题形式化l本节讨论如何把自然语句形式化成逻辑公本节讨论如何把自然语句形式化成逻辑公式。步骤：式。步骤：1.1.字母表示自然语句中的简单命题字母表示自然语句中的简单命题(非变元非变元)2.2.通过联结词形成表示自然语句的合式公通过联结词形成表示自然语句的合式公 式式521.5.1简单自然语句的形式化(1)1)北京不是村庄。北京不是村庄。令令P P表示表示“北京是村庄北京是村庄”，于是，于是(1)(1)表示为表示为 P P。(2)(2)李明既聪明又用功李明既聪明又用功。令令P P表示表示“李明聪明李明聪明”，Q Q表示表示“李明用功李明用功”，于是于是(2)(2)可表示为可表示为PQPQ。531.5.2较复杂自然语句的形式化命题逻辑与自然语句区别：1.命题联结词只表达了自然语句的一种客观性质，忽视了主观性。例：2.又由于自然语句本身常有二义性，自然会出现同一自然语句的不等价的逻辑描述。例如：爱因斯坦是我的崇拜者爱因斯坦是我的崇拜者。3.自然语句联结词与逻辑联结词无固定关系。54例1:张三与李四是表兄弟。(“与与”未必为合取未必为合取词词)这是普通的自然用语，它是一个命题，令以R表示,若形式地规定:P:张三是表兄弟。Q:李四是表兄弟。那么 R=PQ。显然，这样的形式化是错误的。原因很简单。“张三是表兄弟”，“李四是表兄弟”都不是命题。实际上“张三与李四是表兄弟”才是一个命题，而且是一个简单命题。这例子说明自然语句中的“与”不一定都能用合取词来表达。55例2：张三或李四都能做这件事。(“或或”未必为析取词未必为析取词)这句话中的“或”不一定就用析取词来表示，应允许有的人把这命题的内容理解为：张三能做这件事而且李四也能做这件事，这样，这句话便可以PQ的形式表示了。56例3:给了三个命题(“或或”未必为析取词未必为析取词)lA:今晚我在家里看电视。lB:今晚我去体育场看球赛。lC:今晚我在家里看电视或去体育场看球赛。问题是C与AB是否表达的是同一命题呢?57l否。因为C同A、B的真值关系为ABCABFFFFFTTTTFTTTTFT58花絮：花絮：第六个联结词：异或第六个联结词：异或(不可兼或不可兼或)l上例中，C同A,B的逻辑关系,常称为异或(不可兼或),以表示,有C=AB不难验证C=(AB)(AB)59例4:今天我上班,除非今天我病了l以P表示今天我病了,Q表示今天我上班,l例4是个因果关系,意思是如果今天我不病,那么我上班,所以可描述成PQ。601.6 1.6 波兰表达式波兰表达式运算优先权利弊运算优先权利弊1.1.命题联结词的中缀、前缀、后缀命题联结词的中缀、前缀、后缀2.2.中缀式如中缀式如P PQ Q，前缀式如前缀式如PQPQ，后缀式如后缀式如PQPQ。一般用一般用一般用一般用中缀式。什么联结词没有中缀？中缀式。什么联结词没有中缀？3.3.2.2.中缀式有运算优先权，因而造成计算机识别的中缀式有运算优先权，因而造成计算机识别的高复杂度高复杂度4.4.3.3.波兰式的前缀表达，和逆波兰式的后缀表达，波兰式的前缀表达，和逆波兰式的后缀表达，均减弱了运算优先权，因而减小了计算机识别的均减弱了运算优先权，因而减小了计算机识别的高复杂度高复杂度61