第六章-数理逻辑

1、第六章数理逻辑,数理逻辑：用数学的方法来研究形式逻辑。所谓数学的方法，主要是指引进一套符号体系的方法。故又称为符号逻辑。,1命题演算,1.1命题1.2命题公式1.3重言式1.4命题演算基本公式1.5命题演算的基本蕴含重言式及推理规则1.6范式,1.1命题,一、命题的基本概念,定义1.命题：能分辨其真假的语句。一般用大写字母（P,Q,R,）表示。如1.三角形的内角之和为180O。2.中国在亚洲。,一、命题的基本概念,NOTE:(1)命题分为真命题、假命题。（分别用T、F表示）如：子路是孔子的学生（T）张飞是孔子的学生（F）3是素数（T）3210（F）(2)只有陈述句才能是命题。如：请问到中关村怎

2、么走？请把门关上！均不是命题。,一、命题的基本概念,(3)悖论不是命题。如：我正在撒谎。村里有名理发师，他约定：“每个人只给不给自己刮胡子的人刮胡子。”鸡蛋悖论柏拉图与苏格拉底悖论柏拉图：“苏格拉底老师下面的话是假话。”苏格拉底：“柏拉图上面的话是对的。”,一、命题的基本概念,(4)命题要么是真，要么是假。（具有模棱两可含义的语句不能作为命题）如：100是个很大的数。(5)有些语句目前不能判断其真假，但他是有真假的。这样的语句也是命题。如：木星上有生命。任一足够大偶数都能表示为两素数之和（哥德巴赫猜想）均是命题。,一、命题的基本概念,例1：判断下列语句哪些是命题。(1)红楼梦的作者是曹雪芹。(

3、2)1110（是否正确与“数制”有关）(3)我喜欢听你唱歌。(4)你喜欢“蓝色的多瑙河”吗？(5)x+y=3(x和y是任意数),解：(1)、(2)、(3)是命题。(4)、(5)不是。对于(5)，不能确定真假（x、y代入不同的值，会得不同的真假值，当x、y为复数时，比较关系根本不存在！）,一、命题的基本概念,定义2.一个命题若不能再分成更简单的命题，则称为原子命题；否则称为复合命题。,例：P:李明学习好。Q:李明球踢得好。R：李明学习好，并且球踢得也很好。则R是一个复合命题,二、命题联接词,(1)合取联接词“并且”。P并且Q，记为PQ,称为P与Q的合取式；P、Q称为合取项。,真值表：,例2.P:

4、4是偶数Q:2是奇数PQ：4是偶数且2是奇数。,P或者Q，记为PQ。称为P与Q的析取式；P、Q称为析取项。例3.P:今晚我看电视Q:今晚我看离散数学PQ：今晚我看电视或看离散数学。,(2)析取联接词“或者”,真值表：,P的否定命题，记为P。例4.P:地球是圆的P:地球不是圆的,其真值关系表为：,(3)否定联接词“非”,P蕴含Q，记为PQ。可理解为“如果P，则Q”。其中P称为蕴含前件，Q称为蕴含后件。例5:P:下雨了Q:地湿了PQ：如果下雨了，则地湿了。,其真值关系表为：,(4)蕴含联结词,NOTE:注意理解真值表后两行。注意数理逻辑与日常用语的区别。,(5)等价联接词,例6.P:2-30Q:3

5、-20,P等价Q:,2-3=0,例7.P:爱因斯坦是个伟大的科学家Q:李白是唐代著名的诗人,爱因斯坦是个伟大的科学家当且仅当李白是唐代著名的诗人。,其真值关系为：,等价表达式：充分必要、只有才能,NOTE:命题联接词是命题间的联接词，而不是名词或形容词之间的联接词。如：P:“王兰和王英是姐妹”中的“和”不是命题联接词，故P也不是一个复合语句。,(5)等价联接词,例8.求下列命题的真值。(1)如果123，则雪是黑的(2)如果太阳从西边出来，那么地球自转(3)如果太阳从东边出来，那么地球自转停止。,三、复合命题,运算优先级问题：,优先级：“”“”“”“”“”,复合命题：经过命题连接词连接而成的命题

6、。,三、复合命题,例9.命题P为：“明天下雨”。Q为：“明天下雪”。R为：“我去学校”。则：明天不是雨夹雪，则我去学校。可写成(PQ)R明天不下雨，且不下雪，则我去学校。PQR明天下雨或下雪，我不去学校。PQR只有当明天不下雨且不下雪，我才去学校。,明天我一定去学校，风雨无阻。(PQR)(PQR)(PQR)(PQR),PQR,三、复合命题,例10.除非你陪我或给我叫车，否则我不出去。可理解为:“我出去的充要条件是你陪我或给我叫车”。令P:你陪我Q:给我叫车R:我出去则上述语句可用如下复合命题来表达：,(PQ)R,1命题演算,1.1命题1.2命题公式1.3重言式1.4命题演算基本公式1.5命题演

7、算的基本蕴含重言式及推理规则1.6范式,1.2命题公式,定义3.一个任意的未指定真值的命题，称为命题变元。（一般也简称为命题）定义4.经有限步使用，下面法则所得到的公式称为命题公式。1.命题变元是命题公式,2.若P和Q是命题公式，则P、PQ、PQ、PQ、PQ是命题公式。,1.2命题公式,例11.已知P、Q、R是命题，则,是命题公式,1.2命题公式,例12.PQ不是公式。定义5.命题变元一组确定的值称为公式的一个指派。所有的指派构成的公式的真值组合称为公式真值表。,问题：一个由n个命题变元构成的公式共有种多少指派？,答案：2n,1.2命题公式,例13.构造下列命题的真值表,解：,F,T,F,F,

8、F,T,T,T,T,T,F,F,F,T,F,T,F,F,F,T,T,T,F,F,PQ,(PQ),P,Q,PQ,1命题演算,1.1命题1.2命题公式1.3重言式1.4命题演算基本公式1.5命题演算的基本蕴含重言式及推理规则1.6范式,1.3重言式,考虑,的真值表,定义1.命题公式若对其所有指派的真值均为T，称为永真式或重言式。相反，命题公式若对其所有指派的真值均为F，称为永假式或矛盾。定义2.一个命题公式如果至少存在一个指派，使其取值为F，则称为非永真式。如果至少存在一个指派，使其取值为T，则称为可满足的。,1.3重言式,例1.（1）PP是永真式（2）PP是永假式,1.3重言式,关于重言式和矛盾

9、，有些显而易见的特性：（1）重言式的否定是矛盾，矛盾的否定是重言式。（2）两个重言式的合取、析取、蕴含、等价均为重言式。（3）两个矛盾的合取、析取必为矛盾；两个矛盾的蕴含、等价必为重言式。,（4）两个公式P、Q，若PQ为重言式，则P、Q对任何指派必为同真假。,1.3重言式,定义4.P、Q为两个公式，若PQ为重言式，则称为蕴含重言式，记为。,1命题演算,1.1命题1.2命题公式1.3重言式1.4命题演算基本公式1.5命题演算的基本蕴含重言式及推理规则1.6范式,1.4命题演算基本等式,P178-179,1.4命题演算基本等式,定义5.（对偶公式）设有公式A，若它仅用联接词、，把A种的、T、F分别

10、换成、F、T，得到公式A*，称为A的对偶公式。,又如：吸收律：,如狄摩根定律：,定理1.设有等式A=B,则必有A*=B*。(此处A、B仅有联接词、和),1.4命题演算基本等式,例2.化简下面语句：情况并非如此：如果他不来，那么我也不去。,即：我去了但他没来。,解：P:他来，Q：我去,1.4命题演算基本等式,例3.试证语句“不会休息的人不会工作，没有丰富知识的人也不会工作”,“工作好的人一定,会休息，并且具有丰富的知识”。,解：P:某人会休息Q：某人有丰富的知识R:某人工作的好,则语句为,1.4命题演算基本等式,例4.化简程序：如有下面一段PASCAL程序：IFATHENIFBTHENXELSE

11、YELSEIFBTHENXELSEY;,1.4命题演算基本等式,解：原程序用公式可表示为：,令,则上式可写为：,IFATHENIFBTHENXELSEYELSEIFBTHENXELSEY;,1.4命题演算基本等式,解：原程序用公式可表示为：,令,IFATHENIFBTHENXELSEYELSEIFBTHENXELSEY;,故原程序可化简为：IFBTHENXELSEY.,1命题演算,1.1命题1.2命题公式1.3重言式1.4命题演算基本公式1.5命题演算的基本蕴含重言式及推理规则1.6范式,1.5命题演算的基本蕴含重言式及推理规则,首先，1.4节中的所有基本等式都可以作为两个蕴含重言式,即：P=

12、Q相当于,1.5命题演算的基本蕴含重言式及推理规则,除此之外，还有一些基本蕴含式，其正确性可由真值表给出。,PQ,P,QR,R,1.5命题演算的基本蕴含重言式及推理规则,例.某女子深夜下班在路上被杀害，经初步查证凶手为某甲或某乙，后进一步查实，某乙当晚在厂值夜班未外出，从而最后断定凶手必为甲。,(69),(拒取式),(67),(析取三段论),QR，RQ,Q,PQP,解：P:甲是凶手Q:乙是凶手R:乙当晚外出前提为：PQ，R，隐含前提：凶手必当晚外出。即：QR,1命题演算,1.1命题1.2命题公式1.3重言式1.4命题演算基本公式1.5命题演算的基本蕴含重言式及推理规则1.6范式,1.6.1析取

13、范式,定义1.一个命题公式称为析取范式，当且仅当它具有形式，其中Ai为由若干个命题变元或命题变元的否定组成的合取式。,利用分配律最后化成。,化解步骤：,用(36式)(37式)把公式的“”和“”去掉。,用狄摩根定律将公式的否定符号深入至命题变元，并利用减少否定符号。,1.6.1析取范式,例1.求公式,的析取范式。,析取范式的特性:公式为矛盾析取范式中每个析取项均为矛盾析取项中必同时包含一个命题变元及其否定。如:即为矛盾。,1.6.2特异析取范式,定义2.如果一个析取范式中，每个析取项均包含了所有命题变元，它以命题变元或命题变元之否定形式出现且仅出现一次，这样的析取范式称为特异析取范式。,化解步骤

14、：,化成析取范式；除去永假项（即PP）用PP=P化简,某变元未出现,若某变元Q未出现，则用下式补充：,1.6.2特异析取范式,例2.求命题公式的特异析取范式。,1.6.2特异析取范式,定义3.特异析取范式中的析取项称为最小项。n个命题变元可组成2n个最小项。,使最小项为T的指派,最小项,如3个命题变元P、Q、R：,1.6.2特异析取范式,每个最小项只存在唯一的指派使其为T。（规则：若以P形式出现，则令其为T；若以P形式出现，则其为F），如上表。如此，最小项与指派间建立了一一对应关系。,定理：在公式的真值表中，以使公式真值为T的指派所对应的最小项为析取项所构成的公式为原公式的特异析取范式。,1.

15、6.2特异析取范式,例3.例2中公式的真值表为：,1.6.2特异析取范式,由公式的真值表可知，公式S的特异析取范式为：,（与例2结果相同）,1.6.2特异析取范式,如何理解该定理：设原式为S，按定理规则所构成的公式为S，只须证S与S同真假。为此需考虑公式S的所有指派（分以下2类）（1）对于使S为真的指派，由于它所对应的最小项出现在S中，故该指派也必使S为真。（2）对于使S为假的指派，由于它所对应的最小项不出现在S中，故该指派也必使S的每一项为假，从而使S为假。在不考虑命题变元的次序前提下，一个命题公式的特异析取范式是唯一的。,1.6.2特异析取范式,关于特异析取范式，有以下结论：（1）n个命题

16、变元只能组成22n个不能的公式。,（2）一公式为永真式其特异析取范式包含所有的最小项,（3）一公式为矛盾其特异析取范式不包含任何最小项，即为“空”。,（4）两公式相等两公式的特异析取范式一样。,1.6.3合取范式和特异合取范式,与析取式对应，合取范式有如下形式：,其中P1为由若干个命题变元或其否定形式构成的析取式。合取范式的特性：公式为永真式合取范式中每个合取项均为永真式合取范式中每个合取项同时包含一个命题变元及其否定。可以类似地把一个公式化为合取范式和特异合取范式。特异合取范式中的合取项称为最大项。,1.6.3合取范式和特异合取范式,n个命题变元可组成2n个最大项，每一个最大项只存在一个指派

17、使其为假。特异合取范式的性质：（1）一公式为矛盾其特异合取范式包含所有的最大项。（2）一公式为重言式其特异合取范式为空。（3）两公式相等其特异合取范式一致。,2谓词演算,2.1谓词与个体2.2量词2.3函数2.4谓词演算公式2.5自由变元和约束变元2.6谓词演算的永真公式,2谓词演算,2.1谓词与个体命题演算中，原子命题是一个基本的不可分割的单位。但有些论证只靠命题演算是不够的，如“苏格拉底论题”：凡人必死苏格拉底是人所以，苏格拉底必死,PQR,？,2.1谓词与个体,故应如此符号化：所有A是BC是AC是B从语法上看，每个被视为命题的语句是由主语和谓语两部分组成。例1.（1）苏格拉底是人（2）这

18、本书很有趣,2.1谓词与个体,个体客观存在的人或事物，可具体、抽象，用a，b，c表示。谓词描述个体的性质或几个个体之间的关系，用F，G，H表示。,每个个体有一定的变化范围，称为个体域。不考虑具体的个体而只考虑以个体域为变域的变元称为个体变元。一般用x，y，z表示。,由谓词与与之相关的若干个体构成命题，此命题可写为：,如：陈化和陈华是兄妹。,定义：,例2.令F(x,y)表示x和y是兄妹。a:陈化b：陈华则命题可表示为F(a,b)。例3.苏格拉底是人。解：A(x)表示“x是人”a:苏格拉底则A(a)：苏格拉底是人。,2.1谓词与个体,例4.这栋大楼建成了。解：F(x)：x建成了G(x)：x是楼H(

19、x)：x是大的a：这个则：F(a)G(a)H(a),2.1谓词与个体,2.1谓词与个体,例5.这个人正在看那本红皮书。解：F1(x)：x是人F2(x)：x是书F3(x,y)：x看yF4(x)：x是红皮的a：这个b：那个则：,2.1谓词与个体,例6.我一面讲课，一面注意学生甲、乙的反应。解：F1(x)：x讲课F2(x,y)：x注意y的反应F3(x)：x是学生a：我b：甲c：乙则：,2.1谓词与个体2.2量词2.3函数2.4谓词演算公式2.5自由变元和约束变元2.6谓词演算的永真公式,2.2量词,例1.所有的书都有价值。例2.存在实数x使x+3=2。,例1中，令F(x)：x有价值；,例2中，令G(x)：x+3=2；,x：表示所