命题逻辑 讲稿.ppt

《命题逻辑 讲稿.ppt》由会员分享，可在线阅读，更多相关《命题逻辑 讲稿.ppt（123页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、命题逻辑命题逻辑第一页，讲稿共一百二十三页哦第一章第一章 命题逻辑命题逻辑命命题题逻逻辑辑,也也称称命命题题演演算算,它它它它与与与与谓谓词词逻逻辑辑构构成成数数理理逻辑逻辑的基础的基础,而而命题逻辑命题逻辑又是又是又是又是谓词逻辑谓词逻辑的基础的基础数数理理逻逻辑辑是是是是用用用用数数学学方方法法(通过引入表意符号)研研究究推推理的学科。理的学科。因此因此因此因此,数理逻辑又名为数理逻辑又名为符号逻辑符号逻辑。(一套符号体系一套符号体系 +一组推理规则一组推理规则 )命命题题逻逻辑辑是是是是研研研研究究究究由由由由命命题题为为基基本本单单位位构构成成的的前前提提和和和和结结论论之间的可推导关

2、系。之间的可推导关系。第二页，讲稿共一百二十三页哦第一章第一章 命题逻辑命题逻辑1.1命题符号化及联结词命题符号化及联结词1.2命题公式及分类命题公式及分类1.3等值演算等值演算1.4联结词全功能集联结词全功能集*1.5对偶与范式对偶与范式1.6推理理论推理理论1.7例题分析例题分析第三页，讲稿共一百二十三页哦1.1命题符号化及联结词命题符号化及联结词一、什么是命题一、什么是命题定义：定义：命题命题是能判断真假的是能判断真假的陈述句陈述句。该定义有该定义有2层含义层含义:(1)命题是一个陈述句命题是一个陈述句;(2)命题具有真假值。命题具有真假值。命题命题命题命题仅有两种可能的仅有两种可能的真

3、值真值:真真、假假,且二者只居其一。且二者只居其一。真真用用 1 或或 T 表示表示,假假用用 0 或或 F 表示。表示。二值逻辑二值逻辑命题是具有唯一真命题是具有唯一真值的陈述句值的陈述句第四页，讲稿共一百二十三页哦判断判断给定句子是否为命题给定句子是否为命题,应该分两步应该分两步应该分两步应该分两步：首先判定它是否为首先判定它是否为陈述句陈述句,其次判断它的其次判断它的真值是否唯真值是否唯一一。例例1.1判断下例句子是否为命题。判断下例句子是否为命题。(1)2是素数。是素数。(2)雪是黑色的。雪是黑色的。(3)1+101=110(4)十是整数。十是整数。(5)向右看齐！向右看齐！(6)今天

4、是十五号。今天是十五号。(7)这朵花多美啊！这朵花多美啊！(8)我们这里四季如春。我们这里四季如春。(9)x+y5(10)你是谁？你是谁？(11)明年十月一日是晴天。明年十月一日是晴天。(12)地球外的星球上也有人。地球外的星球上也有人。第五页，讲稿共一百二十三页哦定义：定义：由简单陈述句由简单陈述句(一套主谓结构一套主谓结构)构成的命题称为构成的命题称为简单命题简单命题或或原子命题原子命题。由若干个由若干个简单命题简单命题用用联结词联结词联结而成的命题是联结而成的命题是复合复合命题命题。如果一陈述句再也不能分解成更为简单的陈述句如果一陈述句再也不能分解成更为简单的陈述句,由由它构成的命题称为

5、它构成的命题称为简单命题简单命题。简单命题简单命题是命题逻辑的是命题逻辑的基本单位基本单位。二、简单命题与复合命题二、简单命题与复合命题第六页，讲稿共一百二十三页哦三、命题符号化三、命题符号化(1)简单命题简单命题用英文字母用英文字母P,Q,R或带下标的或带下标的Pi,Qi,Ri,表示。表示。P:2是素数。是素数。Q:雪是黑的。雪是黑的。将表示命题的符号将表示命题的符号命题标识符命题标识符放在该命题放在该命题前面前面,称为称为命题符号化命题符号化。(2)命题的命题的真值真值也也符号化符号化:用用T或或1表示表示“真真”;用用F或或0表示表示“假假”。(3)命题中的命题中的联结词联结词也也符号化

6、符号化:、。第七页，讲稿共一百二十三页哦四、命题常量与命题变元四、命题常量与命题变元简单命题可用简单命题可用命题标识符命题标识符表示。表示。表示命题的符号有双表示命题的符号有双重作用重作用:(1)如果如果命题标识符命题标识符表示确定的命题表示确定的命题(真值确定真值确定)命题命题常元常元;(2)如果如果命题标识符命题标识符只表示任意命题的位置标志只表示任意命题的位置标志,即可表即可表示任意命题示任意命题(真值不确定真值不确定)命题变元命题变元。注注:命题变元不是命题命题变元不是命题,只有用一个特定命题取代时只有用一个特定命题取代时,才才能确定其真值能确定其真值,才变为命题才变为命题即对命题变元

7、进行即对命题变元进行真值指真值指真值指真值指派派派派后变为命题。后变为命题。第八页，讲稿共一百二十三页哦五、联结词五、联结词例例1.2 复合命题示例复合命题示例1.上海不是小城镇。上海不是小城镇。2.他既在学习又在工作。他既在学习又在工作。3.林芳学过英语或日语。林芳学过英语或日语。4.如果他病了如果他病了,那么他就需要休息。那么他就需要休息。5.三角形是等腰三角形三角形是等腰三角形,当且仅当三角形的两个底角当且仅当三角形的两个底角相等。相等。第九页，讲稿共一百二十三页哦(一一)否定否定()定义定义1.1设设P为为任任一一命命题题,复复合合命命题题“非非P”(或或P的的否否定定)称为称为P 否

8、定式否定式。记作记作P。为为否定联结词否定联结词。P为真为真,当且仅当当且仅当P为假为假;P是假是假,当且仅当当且仅当P为真。为真。否定联结词否定联结词的定义可由表的定义可由表1-1表示之。表示之。由由由由于于于于“否否否否定定定定”修修修修改改改改了了了了命命命命题题题题,它它它它是是是是对对对对单单单单个个个个命命命命题题题题进进进进行行行行操操操操作作作作,称称称称它它它它为为为为一元一元一元一元联结词。联结词。联结词。联结词。表表表表1-1 的定义的定义的定义的定义P P PP0 0111 100第十页，讲稿共一百二十三页哦(二二)合取合取()定义定义1.2设设P、Q为为两两个个命命题

9、题,复复合合命命题题“P并并且且Q”(或或P与与Q)称称作作P与与Q的的合合取取式式,记记作作:PQ。称称为为合合取取联结词联结词。PQ为真当且仅当为真当且仅当P和和Q同为真同为真,否则否则PQ为假。为假。合取联结词合取联结词的定义由表的定义由表1-2表示之。表示之。“合合合合取取取取”是是是是一一一一个个个个二元二元运算。运算。运算。运算。表表表表1-21-2的定义的定义PQ P Q 11 1 0001100 0 0 第十一页，讲稿共一百二十三页哦例例1.3：将下列命题符号化。将下列命题符号化。(1)李平既聪明又用功。李平既聪明又用功。(2)李平虽然聪明李平虽然聪明,但不用功。但不用功。(3

10、)李平不但聪明李平不但聪明,而且用功。而且用功。(4)李平不是不聪明李平不是不聪明,而是不用功。而是不用功。(5)张辉和王丽都是三好学生。张辉和王丽都是三好学生。(6)张辉和王丽是同学。张辉和王丽是同学。解：解：命题符号化命题符号化:P:李平聪明。李平聪明。Q:李平用功。李平用功。R:张辉是三好学生。张辉是三好学生。S:王丽是三好学生。王丽是三好学生。T:张辉和王丽是同学。张辉和王丽是同学。选用合适的联结词将命题符号化：选用合适的联结词将命题符号化：(1)PQ(2)PQ(3)PQ(4)(P)Q(5)RS(6)T第十二页，讲稿共一百二十三页哦(三三)析取析取()定定义义1.3设设P和和Q为为两两

11、个个命命题题,复复合合命命题题“P或或Q”称称作作P与与Q的的析取式析取式,记作记作:PQ,为为析取联结词析取联结词。PQ的为假当且仅当的为假当且仅当P与与Q同为假同为假,否则否则PQ为真。为真。析取联结词析取联结词的定义由表的定义由表1-3表示之。表示之。“析析析析取取取取”是是是是一一一一个个个个二二元元运算。运算。表表表表 1-31-3的定义的定义P QP Q000110110111第十三页，讲稿共一百二十三页哦例：例：将下列命题符号化。将下列命题符号化。1.王燕学过英语或日语。王燕学过英语或日语。(可兼或可兼或)P:王燕学过英语。王燕学过英语。Q:王燕学过日语。王燕学过日语。则则:PQ

12、2.他昨天做了他昨天做了20题或题或30题。题。“或或”只表示了习题的近似数目只表示了习题的近似数目,是是原子命题原子命题。不能。不能用用“”表示。表示。P:他昨天做了他昨天做了20题或题或30题。题。3.我在教室看书或在图书馆看书。我在教室看书或在图书馆看书。排斥或排斥或/异或异或“”表示。表示。P:我在教室看书。我在教室看书。Q:我在图书馆看书。我在图书馆看书。则则:P QP Q=(PQ)(PQ)=(PQ)(PQ)第十四页，讲稿共一百二十三页哦(四四)蕴涵蕴涵()定义定义1.4设设P和和Q为为两两个个命命题题,复复合合命命题题“如如果果P,则则Q”称称作作P和和Q的的蕴涵式蕴涵式,记作记作

13、:PQ,称称为为蕴涵联结词蕴涵联结词。当当P的的真真值值为为真真,而而Q的的真真值值为为假假时时,命命题题PQ的的真真值为假值为假;否则否则,PQ的真值为真。的真值为真。蕴涵联结词蕴涵联结词的定义由表的定义由表1-4表示之。表示之。表表1-4的定义的定义P QP Q000110111101第十五页，讲稿共一百二十三页哦注注:在在条条件件命命题题PQ 中中,命命题题P 称称为为PQ 的的前前件件或或前提前提,命题命题Q 称为称为PQ 的的后件后件或或结论结论。条件命题条件命题PQ 有有多种方式陈述多种方式陈述：(1)“如果如果P,则则Q”;(2)“P 是是Q 的的充分条件充分条件”;(3)“Q

14、是是P 的的必要条件必要条件”;(4)“P 仅当仅当Q”;(5)“只有只有Q 才才P”;。第十六页，讲稿共一百二十三页哦例：例：将下列将下列命题符号化命题符号化。1.如果我拿到奖学金如果我拿到奖学金,我就请客。我就请客。P:我拿到奖学金。我拿到奖学金。Q:我请客。我请客。PQ2.如果他努力学习如果他努力学习,就会门门功课优秀。就会门门功课优秀。P:他努力学习。他努力学习。Q:他门门功课优秀。他门门功课优秀。PQ3.只要不下雨只要不下雨,我就骑自行车上班。我就骑自行车上班。P:天下雨。天下雨。Q:我骑自行车上班。我骑自行车上班。PQ4.只有不下雨只有不下雨,我才骑自行车上班。我才骑自行车上班。P

15、:天下雨。天下雨。Q:我骑自行车上班。我骑自行车上班。QP第十七页，讲稿共一百二十三页哦注意：注意：在使用在使用在使用在使用联结词联结词联结词联结词时时时时,要特别注意以下几点要特别注意以下几点要特别注意以下几点要特别注意以下几点:1.1.在自然语言里在自然语言里在自然语言里在自然语言里,特别在数学中特别在数学中特别在数学中特别在数学中,QQ是是是是P P的必要条件的必要条件的必要条件的必要条件有多种不同的叙有多种不同的叙有多种不同的叙有多种不同的叙述方式。述方式。述方式。述方式。如如如如:“只要只要只要只要P,P,就就就就QQ”,“”,“因为因为因为因为P,P,所以所以所以所以QQ”,“”,

16、“P P仅当仅当仅当仅当QQ”,“”,“只有只有只有只有QQ才才才才P P”,“”,“除非除非除非除非QQ才才才才P P”,“”,“除非除非除非除非Q,Q,否则非否则非否则非否则非P P”。各种叙述方式表。各种叙述方式表。各种叙述方式表。各种叙述方式表面看来有所不同面看来有所不同面看来有所不同面看来有所不同,但都表达的是但都表达的是但都表达的是但都表达的是QQ是是是是P P的必要条件的必要条件的必要条件的必要条件,故联结词均故联结词均故联结词均故联结词均符号化为符号化为符号化为符号化为,均符号化为均符号化为均符号化为均符号化为 P PQQ。2.2.在自然语言中在自然语言中在自然语言中在自然语言

17、中,“,“如果如果如果如果P,P,则则则则Q”Q”中的中的中的中的前件前件前件前件P P与与与与后件后件后件后件QQ往往具有某种内在往往具有某种内在往往具有某种内在往往具有某种内在联系。而联系。而联系。而联系。而在数理逻辑中在数理逻辑中在数理逻辑中在数理逻辑中,P,P与与与与QQ可以可以可以可以无无无无任何内在联系任何内在联系任何内在联系任何内在联系。3.3.在数学或其它自然科学中在数学或其它自然科学中在数学或其它自然科学中在数学或其它自然科学中,“,“如果如果如果如果P,P,则则则则Q”Q”往往表达的是往往表达的是往往表达的是往往表达的是前件前件前件前件P P为为为为真真真真,后件后件后件后

18、件QQ也为真的也为真的也为真的也为真的推理关系。但在数理逻辑中推理关系。但在数理逻辑中推理关系。但在数理逻辑中推理关系。但在数理逻辑中,作为一种规定作为一种规定作为一种规定作为一种规定,当当当当P P为假时为假时为假时为假时,无论无论无论无论QQ是真是假是真是假是真是假是真是假,P,PQQ均为真。即均为真。即均为真。即均为真。即:“:“只有只有只有只有P P为真为真为真为真QQ为为为为假假假假”使得复合命题使得复合命题使得复合命题使得复合命题P PQQ为假为假为假为假。第十八页，讲稿共一百二十三页哦(五五)双条件双条件()定义定义1.5令令P、Q是是两两个个命命题题,复复合合命命题题“P当当且

19、且仅仅当当Q”称称作作P与与Q的的等价式等价式,记作记作PQ。称称为为等价联结词等价联结词。当当P和和Q的的真真值值相相同同时时,PQ的的真真值值为为真真;否否则则PQ的真值为假。的真值为假。等价联结词等价联结词的定义由表的定义由表1-5表示之。表示之。表表1-5的定义的定义P Q P Q00 01 10 11 1001第十九页，讲稿共一百二十三页哦以上定义了以上定义了以上定义了以上定义了五种五种最基本、最常用、也是最重要的最基本、最常用、也是最重要的最基本、最常用、也是最重要的最基本、最常用、也是最重要的联结词联结词联结词联结词:、,将它们组成一个集合将它们组成一个集合将它们组成一个集合将它

20、们组成一个集合,称为称为称为称为一个一个一个一个联结词集联结词集联结词集联结词集。其中。其中。其中。其中 为一元联结词为一元联结词为一元联结词为一元联结词,其余其余其余其余的都是二元联结词。的都是二元联结词。的都是二元联结词。的都是二元联结词。使用这些联结词有什么好处呢使用这些联结词有什么好处呢使用这些联结词有什么好处呢使用这些联结词有什么好处呢？可以将复杂命题表示成简单的符号公式可以将复杂命题表示成简单的符号公式。PQ PP QP QP QPQPQ00100011011011101000110011011011第二十页，讲稿共一百二十三页哦把一个用文字叙述的命题相应地写成由命题标识符、把一个

21、用文字叙述的命题相应地写成由命题标识符、联结词和圆括号表示的联结词和圆括号表示的合式公式合式公式,称为称为命题的符号化命题的符号化。符号化应该符号化应该注意注意下列事项下列事项:确定给定句子是否为命题。确定给定句子是否为命题。句子中连词是否为命题联结词。句子中连词是否为命题联结词。要正确地表示原子命题和选择适当命题联结词。要正确地表示原子命题和选择适当命题联结词。命题的符号化命题的符号化第二十一页，讲稿共一百二十三页哦命题符号化是很重要的命题符号化是很重要的,一定要掌握好。一定要掌握好。在在命命题题推推理理中中常常常常最最先先遇遇到到的的就就是是符符号号化化这这个问题个问题,解决不好解决不好,

22、等于说推理的首要前提没有了。等于说推理的首要前提没有了。第二十二页，讲稿共一百二十三页哦在在本本节节结结束束时时,应应强强调调指指出出的的是是:复复合合命命题题的的真真值值只只取取决决于于各各原原子子命命题题的的真真值值,而而与与它它们们的的内内容容、含含义义无无关关,与原子命题之间是否有关系无关与原子命题之间是否有关系无关。理解和掌握这一点是至关重要的理解和掌握这一点是至关重要的,请认真领会。请认真领会。第二十三页，讲稿共一百二十三页哦1.2命题公式及分类命题公式及分类一、命题公式一、命题公式(合式公式合式公式)通通常常把把含含有有命命题题变变元元的的断断言言称称为为命命题题公公式式。但但这

23、这没没能能指指出出命命题题公公式式的的结结构构,因因为为不不是是所所有有由由命命题题变变元元、联联结结词词和和括括号号所所组组成成的的字字符符串串都都能能成成为为命命题题公公式式。为为此此常常使使用用归归纳纳定定义义命命题题公公式式,以以便便构构成成的的公公式式有有规规则则可可循循。由由这这种种定定义义产产生生的的公公式式称称为为合合式式公式公式。第二十四页，讲稿共一百二十三页哦定定义义1.6命命题题演演算算的的合合式式公公式式(Well-formedformula_WFF)是由下列规则所产生的符号串是由下列规则所产生的符号串:(1)单个命题常量、变元是一个单个命题常量、变元是一个WFF;(2

24、)如果如果A是是WFF,则则(A)是是WFF;(3)如果如果A、B是是WFF,则则(AB)、(AB)、(AB)和和(AB)都是都是WFF;(4)只有有限次地使用规则只有有限次地使用规则(1)(3)得到的符号串才是得到的符号串才是合合式公式式公式WFF。一、命题公式一、命题公式(合式公式合式公式)第二十五页，讲稿共一百二十三页哦当当合合式式公公式式比比较较复复杂杂时时,常常常常使使用用很很多多圆圆括括号号。为为了了减少减少圆括号的使用量圆括号的使用量,可作以下可作以下约定约定:规定联结词的优先级规定联结词的优先级由高到低由高到低的次序为的次序为:、相相同同的的联联结结词词按按从从左左至至右右次次

25、序序计计算算时时,圆圆括括号号可可省省略。略。最外层的圆括号可以省略。最外层的圆括号可以省略。合式公式合式公式也简称也简称公式公式。第二十六页，讲稿共一百二十三页哦二、命题公式的层次二、命题公式的层次定义定义1.7(1)若若A是单个命题是单个命题(常项或变项常项或变项),则称则称A是是0层公式层公式;(2)称称A是是n+1(n0)层公式是指层公式是指A符合下列情况之一符合下列情况之一:A=B,B是是n 层公式层公式;A=BC,其中其中B、C分别为分别为i 层和层和j 层公式层公式,n=max(i,j)A=BC,其中其中B、C的层次同的层次同;A=BC,其中其中B、C的层次同的层次同;A=BC,

26、其中其中B、C的层次同的层次同。第二十七页，讲稿共一百二十三页哦三、命题公式的解释三、命题公式的解释(赋值赋值)定定义义1.8设设A为为命命题题公公式式,P1,P2,Pn 为为出出现现在在A 中中的的所所有有命命题题变变元元。给给Pi(i=1,2,n)指指定定一一组组真真值值,称称为为对对公公式式A的的一一个个真真值值指指派派(也也称称解解释释或或赋赋值值),记记作作I。(1)若指定的一组真值使公式若指定的一组真值使公式A为为真真,则称这组真值为则称这组真值为A的的成真赋值成真赋值；(2)若指定的一组真值使公式若指定的一组真值使公式A为为假假,则称这组真值为则称这组真值为A的的成假赋值成假赋值

27、。第二十八页，讲稿共一百二十三页哦例例：设命题公式：设命题公式：设命题公式：设命题公式 A=PQR：在解释在解释I I1=(0,0,0)=(0,0,0)下下下下,A为真为真,则则I1为为为为A的成真赋值的成真赋值;在解释在解释在解释在解释 I2 2=(1,1,0)下下,A为假为假,则则I2为为为为A的成假赋值。的成假赋值。一个命题公式中含有一个命题公式中含有n 个命题变元个命题变元,则共有则共有2n 组组不同的赋值不同的赋值。第二十九页，讲稿共一百二十三页哦四、真值表四、真值表定义定义:在命题公式中在命题公式中,把所有命题变元在所有可能的解释把所有命题变元在所有可能的解释(赋值赋值)下取得的真

28、值汇列成的表格称为下取得的真值汇列成的表格称为真值表真值表。构造构造真值表真值表的的步骤步骤如下如下:(1)找出公式中所含的找出公式中所含的全部命题变元全部命题变元(如有如有n个个),列出列出2n个个赋值赋值;(2)按按从低到高从低到高的顺序写出各层次的子公式的顺序写出各层次的子公式;(3)对应各个赋值对应各个赋值,计算出各层次的真值计算出各层次的真值,直到直到最后计算最后计算出命题公式的真值出命题公式的真值。第三十页，讲稿共一百二十三页哦例例:下列公式的真值表下列公式的真值表,并求并求成真赋值成真赋值和和成假赋值成假赋值。(1)(PQ)R(2)(PP)(QQ)(3)(PQ)QR第三十一页，讲

29、稿共一百二十三页哦定义定义1.9设设A 为命题公式为命题公式,则则若若A在它的各种赋值下取值均为在它的各种赋值下取值均为真真,则称则称A为为永真式永真式或或重言式重言式。若若A在它的各种赋值下取值均为在它的各种赋值下取值均为假假,则称则称A为为永假式永假式或或矛盾式矛盾式。若若A至少存在一组赋值至少存在一组赋值是是成真赋值成真赋值,则称则称A为为可可满足式满足式。五、命题公式的分类五、命题公式的分类第三十二页，讲稿共一百二十三页哦判定判定给定公式是否为给定公式是否为永真式永真式、永假式永假式或或可满足式可满足式的问题的问题,称为命题公式的称为命题公式的判定问题判定问题。真值表真值表可用来可用来

30、判断判断公式的类型公式的类型：1.若真值表最后一列若真值表最后一列全为全为1,则公式为则公式为永真式永真式。2.若真值表最后一列若真值表最后一列全为全为0,则公式为则公式为永假式永假式。3.若真值表最后一列中若真值表最后一列中至少有一个至少有一个1,则公式为则公式为可满可满足式足式。第三十三页，讲稿共一百二十三页哦注注:由定义可知由定义可知,永真式永真式一定是一定是可满足式可满足式,但反之不真。但反之不真。重点重点将研究将研究重言式重言式,它最有用它最有用,因为它有以下因为它有以下特点特点:重言式重言式的的否定否定是是矛盾式矛盾式,矛盾式矛盾式的的否定否定是是重言式重言式,这样这样只研究其一就

31、可以了。只研究其一就可以了。两两重言式重言式的的合取式合取式、析取式析取式、条件式条件式和和双条件式双条件式等等都仍是都仍是重言式重言式。于是。于是,由简单的由简单的重言式重言式可构造出复杂的可构造出复杂的重言式重言式。由由重言式重言式使用使用公认的规则公认的规则可以产生许多有用可以产生许多有用等价式等价式和和蕴涵式蕴涵式。第三十四页，讲稿共一百二十三页哦一、等价公式一、等价公式定定义义1.10设设设设 A A、B B 是是是是两两两两个个个个命命命命题题题题公公公公式式式式,若若A B B 是是永永真真式式(即即即即 A A、B B 在在在在任任任任意意意意指指指指派派派派下下下下,真真真真

32、值值值值均均均均相相相相同同同同),则则则则称称称称 A A 和和B B 是是等等价价的的,记作记作记作记作 A AB。显显然然,若若公公式式A和和B的的真真值值表表是是相相同同的的,则则A和和B等等价。价。因因此此,验验证证两两公公式式是是否否等等价价,只只需需做做出出它它们们的的真真值值表表即可。即可。1.3等值演算等值演算第三十五页，讲稿共一百二十三页哦注意注意：和和的区别与联系。的区别与联系。区区别别：是是逻逻辑辑联联结结词词,属属于于目目标标语语言言中中的的符符号号,它出现在命题公式中它出现在命题公式中;不不是是逻逻辑辑联联结结词词,用用于于表表示示两两个个命命题题公公式式的的一一种

33、种关关系系,不不属属于于这这两两个个公公式式的的任任何何一一个个公公式式中中的的符号。符号。联系联系：可用下面定理表明之。：可用下面定理表明之。第三十六页，讲稿共一百二十三页哦定理：定理：设设A和和B是两个命题公式是两个命题公式,AB当且仅当当且仅当AB是永真式是永真式。证明：证明：(充分性充分性)若若AB是永真式是永真式,则其原子命题不论则其原子命题不论在何种解释下在何种解释下,AB均为真均为真;按照按照AB的真值表的真值表,只有当只有当A、B具有相同的真值时具有相同的真值时,才有才有ABT于是于是,无论什么情况都有无论什么情况都有AB。(必要性必要性)如果如果AB,即即A、B在任意解释下都

34、具有相同在任意解释下都具有相同的真值的真值,故必有故必有AB恒为恒为T,即即AB是永真式。是永真式。#第三十七页，讲稿共一百二十三页哦等价式具有下列性质：等价式具有下列性质：自反性自反性:即对任意公式即对任意公式A,有有AA。对称性对称性:即对任意公式即对任意公式A和和B,若若AB,则则BA。传递性传递性:即对任意公式即对任意公式A、B和和C,若若AB、BC,则则AC。第三十八页，讲稿共一百二十三页哦在在判判定定公公式式之之间间是是否否等等价价,有有一一些些简简单单而而又又经经常常使使用用的的等等价价式式,称称为为基基本本等等价价式式或或称称命命题题定定律律。牢牢固固记记住住并并能熟练运用能熟

35、练运用,是学好数理逻辑的是学好数理逻辑的关键关键之一之一。24个重要的等值式：个重要的等值式：(1)双重否定律：双重否定律：双重否定律：双重否定律：A A A(2)等幂律：等幂律：AA A A,AA A(3)结合律：结合律：结合律：结合律：(AB)C A(B BC),(AB)C A(B BC)二、基本等价式二、基本等价式命题定律命题定律第三十九页，讲稿共一百二十三页哦(4)(4)交换律：交换律：AB B BA,AB B BAA AB B BA(5)分配律：分配律：A(BC C)(AB)(AC)A A(B BC C)(AB B)(AC C)(6)吸收律：吸收律：吸收律：吸收律：A(AB)A,A(

36、A AB)A(7)德德 摩根律：摩根律：(A AB B)AB B(AB)AB(8)同一律：同一律：A1 A A,A0 A。(9)(9)零零律：律：A A0 0 0,A1 1 1。第四十页，讲稿共一百二十三页哦(10)补余律：补余律：AA 0 (矛盾律矛盾律矛盾律矛盾律)AA 1 1(排中律排中律)(11)蕴含等值式：蕴含等值式：AB AB,(12)假言易位：假言易位：AB B BA。(13)等价等值式：等价等值式：AB (AB B)(BA)(AB)(A AB B)(14)等价否定律：等价否定律：等价否定律：等价否定律：AB AB(15)归谬论：归谬论：(A AB)(AB B)A A。第四十一页

37、，讲稿共一百二十三页哦以上以上15组等值式包含了组等值式包含了24个重要等值式。个重要等值式。由于由于A、B、C可代表任意的公式可代表任意的公式,因而每个公因而每个公式都是一个模式式都是一个模式(称之为称之为等值式模式等值式模式)。每个每个等值式模式等值式模式都给出了无穷多个同类型的具都给出了无穷多个同类型的具体的等值式。体的等值式。第四十二页，讲稿共一百二十三页哦三、代入规则和置换规则三、代入规则和置换规则例如例如,在蕴含等值式在蕴含等值式(AB AB)中中,当取当取A=PQR,B=PQ时时,得等值式为：得等值式为：(PQR)(PQ)(PQR)(PQ)所得的等值式称为原来的所得的等值式称为原

38、来的等值式模式等值式模式的的代换实例代换实例。每个具体的代换实例的正确性都可用真值表证明之每个具体的代换实例的正确性都可用真值表证明之。定定理理:在在一一个个永永真真式式A 中中,任任何何一一个个原原子子命命题题变变元元R 出出现现的的每每一一处处,用用另另一一个个公公式式代代入入,所所得得公公式式B 仍仍是是永永真真式式。(代入规则代入规则)第四十三页，讲稿共一百二十三页哦定定义义如如果果X是是合合式式公公式式A的的一一部部分分,且且X本本身身也也是是一一个合式公式个合式公式,则称则称X为公式为公式A的的子公式子公式。定定理理1.1设设A1是是合合式式公公式式A的的子子公公式式,若若A1B1

39、,并并且且将将A中中的的A1用用B1替替换换得得到到公公式式B,则则AB。称称该该定定理理为为置换规则置换规则。例例:在在公公式式(PQ)R中中,可可用用蕴蕴含含等等值值式式依依次次置置换换,得得:(PQ)R(PQ)R(PQ)R(PQ)R(PR)(QR)第四十四页，讲稿共一百二十三页哦注：注：代入代入和和置换置换有两点区别有两点区别：代代代代入入入入是是是是对对对对原原子子命命题题变变元元而而言言的的,而而置置换换可可对对命命题题公公式式实行。实行。代代入入必必须须是是处处处处代代入入,置置换换则则可可部部分分替替换换,亦亦可可全全部替换。部替换。第四十五页，讲稿共一百二十三页哦我们已经给出了

40、我们已经给出了:1.重言式重言式(永真式永真式)的的代换实例代换实例为为重言式重言式(永真式永真式)。2.重言式重言式(永真式永真式)的的否定否定为为矛盾式矛盾式(永假式永假式)。3.两两重言式重言式(永真式永真式)的的合取式合取式、析取式析取式、条件式条件式和和双双条件式条件式等都仍是等都仍是重言式重言式(永真式永真式)。于是。于是,由简单的由简单的重言式重言式可构造出复杂的可构造出复杂的重言式重言式。第四十六页，讲稿共一百二十三页哦虽然用真值表法可以判断任何两个命题公式是否等虽然用真值表法可以判断任何两个命题公式是否等值值,但当命题变元较多时但当命题变元较多时,工作量是很大的。工作量是很大

41、的。前面我们已经介绍了前面我们已经介绍了15组组24个重要的个重要的等值式等值式和和代入代入规则规则、置换规则置换规则,利用它们就可以通过利用它们就可以通过等值演算等值演算来判断来判断两个命题公式是否等价。两个命题公式是否等价。四、等值演算四、等值演算第四十七页，讲稿共一百二十三页哦例例:用等值演算判断下列公式的类型：用等值演算判断下列公式的类型：(1)(PQ)PQ(2)(P(PQ)R(3)P(PQ)P)Q)第四十八页，讲稿共一百二十三页哦(1)(PQ)PQ(PQ)PQ(蕴含等值式蕴含等值式蕴含等值式蕴含等值式)(PQ)P)Q(蕴含等值式蕴含等值式蕴含等值式蕴含等值式)(PQ)P)Q(德德德德

42、 摩根律摩根律摩根律摩根律)(PQ)P)Q(德德德德 摩根律、双重否定律摩根律、双重否定律摩根律、双重否定律摩根律、双重否定律)(PP)(QP)Q(分配律分配律分配律分配律)(1(QP)Q(排中律排中律排中律排中律)(QQ)P(交换律、结合律交换律、结合律交换律、结合律交换律、结合律)1P(零律零律零律零律)1最后结果说明最后结果说明(1)中公式是中公式是重言式重言式第四十九页，讲稿共一百二十三页哦(2)(P(PQ)R(PPQ)R(蕴含等值式蕴含等值式蕴含等值式蕴含等值式)(PPQ)R(德德德德 摩根律摩根律摩根律摩根律)0R(矛盾律、零律矛盾律、零律矛盾律、零律矛盾律、零律)0(零律零律零律

43、零律)最后结果说明最后结果说明(2)中公式是中公式是矛盾式矛盾式。第五十页，讲稿共一百二十三页哦(3)P(PQ)P)Q)P(PQ)P)Q)(蕴含等值式蕴含等值式蕴含等值式蕴含等值式)P(PP)(QP)Q)(分配律分配律分配律分配律)P(0(QP)Q)(矛盾律、零律矛盾律、零律矛盾律、零律矛盾律、零律)P(QPQ)(德德德德 摩根律摩根律摩根律摩根律)P1(排中律排中律排中律排中律)P(同一律同一律同一律同一律)最后结果说明最后结果说明(3)中公式是中公式是可满足式可满足式。第五十一页，讲稿共一百二十三页哦例例:验证下列等值式：验证下列等值式：(1)P(QR)(PQ)R(2)P(PQ)(P Q)

44、第五十二页，讲稿共一百二十三页哦等值演算还能帮助人们解决工作和生活中的判等值演算还能帮助人们解决工作和生活中的判断问题。断问题。例例:在某次研讨会的中间休息时间在某次研讨会的中间休息时间,3名与会者根据王教名与会者根据王教授的口音对他是哪个省市的人进行了判断：授的口音对他是哪个省市的人进行了判断：甲说甲说:王教授不是苏州人王教授不是苏州人,是上海人。是上海人。乙说乙说:王教授不是上海人王教授不是上海人,是苏州人。是苏州人。丙说丙说:王教授既不是上海人王教授既不是上海人,也不是杭州人。也不是杭州人。听完以上听完以上3人的判断后人的判断后,王教授笑着说王教授笑着说,他们他们3人中有人中有一人说的全

45、对一人说的全对,有一人说对了一半有一人说对了一半,另一人说的全不对。另一人说的全不对。试用命题演算法分析王教授到底是哪里人？试用命题演算法分析王教授到底是哪里人？第五十三页，讲稿共一百二十三页哦解解:设命题：设命题：P:王教授是苏州人。王教授是苏州人。Q:王教授是上海人。王教授是上海人。R:王教授是杭州人。王教授是杭州人。P,Q,R中必有一个真命题中必有一个真命题,两个假命题两个假命题,要通过命要通过命题演算将真命题找出来。题演算将真命题找出来。第五十四页，讲稿共一百二十三页哦设：设：甲甲的判断为的判断为:A1=PQ乙乙的判断为的判断为:A2=PQ丙丙的判断为的判断为:A3=QR则有：则有：甲

46、甲的判断的判断全对全对为为:B1=A1=PQ甲甲的判断的判断对一半对一半为为:B2=(PQ)(PQ)甲甲的判断的判断全错全错为为:B3=PQ乙乙的判断的判断全对全对为为:C1=A2=PQ乙乙的判断的判断对一半对一半为为:C2=(PQ)(PQ)乙乙的判断的判断全错全错为为:C3=PQ丙丙的判断的判断全对全对为为:D1=A3=QR丙丙的判断的判断对一半对一半为为:D2=(QR)(QR)丙丙甲的判断甲的判断全错全错为为:D3=QR第五十五页，讲稿共一百二十三页哦由王教授所说由王教授所说“甲、乙、丙甲、乙、丙3人中有一人说的全对人中有一人说的全对,有有一人说对了一半一人说对了一半,另一人说的全不对另一

47、人说的全不对”,得出公式得出公式E：E=(B1C2D3)(B1C3D2)(B2C1D3)(B2C3D1)(B2C1D2)(B3C2D1)为真命题。为真命题。其中：其中：B1C2D3=(PQ)(PQ)(PQ)(QR)(PQQR)(PQPR)0B1C3D2=(PQ)(PQ)(QR)(QR)(PQR)(PQQR)PQRB2B2C1C1D3D3=(=(P PQ)Q)(P(PQ)Q)(P(P Q)Q)(Q(QR)R)(P PQQP P QQQQR)R)(P(PQQ QQR)R)0 0第五十六页，讲稿共一百二十三页哦类似地可得：类似地可得：B2C3D10B3C1D2PQRB3C2D10于是于是,由由同一律

48、同一律可知可知E(PQR)(PQR)但因为王教授不能既是上海人但因为王教授不能既是上海人,又是杭州人又是杭州人,因而因而P,R必有一个假命题必有一个假命题,即即PQR0,于是于是EPQR为真命题为真命题,因而必有因而必有P,R为假命题为假命题,Q为真命题为真命题,即即王教王教授是上海人授是上海人。甲说的全对甲说的全对,丙说对了一半丙说对了一半,而乙全说错了而乙全说错了。第五十七页，讲稿共一百二十三页哦1.5对偶与范式对偶与范式要求：要求：掌掌握握对对偶偶与与范范式式,会会求求命命题题公公式式的的主主析析取取范范式式、主合取范式。主合取范式。重点与难点：重点与难点：求命题公式的主析求命题公式的主

49、析(合合)取范式。取范式。第五十八页，讲稿共一百二十三页哦1.5对偶与范式对偶与范式一、对偶一、对偶在在前前面面介介绍绍的的命命题题定定律律中中,多多数数公公式式是是成成对对出出现现的的,这些成对出现的定律就是这些成对出现的定律就是对偶性质对偶性质的反映的反映,即即对偶式对偶式。利利用用对对偶偶式式的的命命题题定定律律,可可以以扩扩大大等等价价式式的的个个数数,也也可可减少减少证明的次数。证明的次数。第五十九页，讲稿共一百二十三页哦定义定义1.17在仅含联结词在仅含联结词、和和的命题公式的命题公式A中中,若若把把和和互换互换,0 和和1 互换而得到一个命题公式互换而得到一个命题公式A*,则则称

50、称A*为为A的的对偶式对偶式。显然显然,A也是也是A*的对偶式。即的对偶式。即A与与A*互为互为对偶式对偶式。且有且有:(A*)*=A一、对偶一、对偶第六十页，讲稿共一百二十三页哦定定理理1.2(对对偶偶定定理理)设设A和和A*互互为为对对偶偶式式,P1,P2,Pn是是出现出现A 和和A*中的中的原子命题变元原子命题变元,则则A(P1,P2,Pn)A*(P1,P2,Pn)A(P1,P2,Pn)A*(P1,P2,Pn)表表明明,公公式式A的的否否定定等等价价于于其其命命题题变变元元否否定定的的对对偶偶式式A A*;表明表明,公式公式A的命题变元否定的命题变元否定等价于等价于对偶式对偶式A A*之