命题逻辑 .ppt

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

1、命题逻辑命题逻辑现在学习的是第1页，共123页第一章第一章 命题逻辑命题逻辑命命题题逻逻辑辑,也也称称命命题题演演算算,它它它它与与与与谓谓词词逻逻辑辑构构构构成成成成数数理理逻逻辑辑的基础的基础,而而而而命题逻辑命题逻辑又是又是谓词逻辑谓词逻辑的基础的基础的基础的基础数数理理逻逻辑辑是是是是用用用用数数学学方方方方法法法法(通过引入表意符号)研研研研究究究究推推推推理理理理的学科。的学科。的学科。的学科。因此因此,数理逻辑又名为数理逻辑又名为数理逻辑又名为数理逻辑又名为符号逻辑符号逻辑。(一套符号体系一套符号体系 +一组推理规则一组推理规则 )命命题题逻逻辑辑是是研研究究由由命命题题为为基基

2、本本单单位位构构成成的的前前提提和和结结论论之间的可推导关系。之间的可推导关系。之间的可推导关系。之间的可推导关系。现在学习的是第2页，共123页第一章第一章 命题逻辑命题逻辑1.1命题符号化及联结词命题符号化及联结词1.2命题公式及分类命题公式及分类1.3等值演算等值演算1.4联结词全功能集联结词全功能集*1.5对偶与范式对偶与范式1.6推理理论推理理论1.7例题分析例题分析现在学习的是第3页，共123页1.1命题符号化及联结词命题符号化及联结词一、什么是命题一、什么是命题定义：定义：命题命题是能判断真假的是能判断真假的陈述句陈述句。该定义有该定义有2层含义层含义:(1)命题是一个陈述句命题

3、是一个陈述句;(2)命题具有真假值。命题具有真假值。命题命题仅有两种可能的仅有两种可能的真值真值:真真、假假,且二者只居其一。且二者只居其一。真真用用 1 或或 T 表示表示,假假用用 0 或或 F 表示。表示。二值逻辑二值逻辑命题是具有唯一真命题是具有唯一真值的陈述句值的陈述句现在学习的是第4页，共123页判断判断给定句子是否为命题给定句子是否为命题,应该分两步应该分两步应该分两步应该分两步：首先判定它是否为首先判定它是否为陈述句陈述句,其次判断它的其次判断它的真值是否唯真值是否唯一一。例例1.1判断下例句子是否为命题。判断下例句子是否为命题。(1)2是素数。是素数。(2)雪是黑色的。雪是黑

4、色的。(3)1+101=110(4)十是整数。十是整数。(5)向右看齐！向右看齐！(6)今天是十五号。今天是十五号。(7)这朵花多美啊！这朵花多美啊！(8)我们这里四季如春。我们这里四季如春。(9)x+y5(10)你是谁？你是谁？(11)明年十月一日是晴天。明年十月一日是晴天。(12)地球外的星球上也有人。地球外的星球上也有人。现在学习的是第5页，共123页定义：定义：由简单陈述句由简单陈述句(一套主谓结构一套主谓结构)构成的命题称构成的命题称为为简单命题简单命题或或原子命题原子命题。由若干个由若干个简单命题简单命题用用联结词联结词联结而成的命题是联结而成的命题是复合复合命题命题。如果一陈述句

5、再也不能分解成更为简单的陈述句如果一陈述句再也不能分解成更为简单的陈述句如果一陈述句再也不能分解成更为简单的陈述句如果一陈述句再也不能分解成更为简单的陈述句,由它由它由它由它构成的命题称为构成的命题称为构成的命题称为构成的命题称为简单命题简单命题。简单命题简单命题是命题逻辑的基本是命题逻辑的基本单位单位。二、简单命题与复合命题二、简单命题与复合命题现在学习的是第6页，共123页三、命题符号化三、命题符号化(1)简单命题简单命题用英文字母用英文字母P,Q,R或带下标的或带下标的Pi,Qi,Ri,表示。表示。P:2是素数。是素数。Q:雪是黑的。雪是黑的。将表示命题的符号将表示命题的符号命题标识符命

6、题标识符放在该命题放在该命题前面前面,称为称为命题符号化命题符号化。(2)命题的命题的真值真值也也符号化符号化:用用T或或1表示表示“真真”;用用F或或0表示表示“假假”。(3)命题中的命题中的联结词联结词也也符号化符号化:、。现在学习的是第7页，共123页四、命题常量与命题变元四、命题常量与命题变元简单命题可用简单命题可用命题标识符命题标识符表示。表示。表示命题的符号有双表示命题的符号有双重作用重作用:(1)如果如果命题标识符命题标识符表示确定的命题表示确定的命题(真值确定真值确定)命题命题常元常元;(2)如果如果命题标识符命题标识符只表示任意命题的位置标志只表示任意命题的位置标志,即可表即

7、可表示任意命题示任意命题(真值不确定真值不确定)命题变元命题变元。注注:命题变元不是命题命题变元不是命题,只有用一个特定命题取代时只有用一个特定命题取代时,才才能确定其真值能确定其真值,才变为命题才变为命题即对命题变元进行即对命题变元进行真值真值指派指派后变为命题。后变为命题。现在学习的是第8页，共123页五、联结词五、联结词例例1.2 复合命题示例复合命题示例1.上海不是小城镇。上海不是小城镇。2.他既在学习又在工作。他既在学习又在工作。3.林芳学过英语或日语。林芳学过英语或日语。4.如果他病了如果他病了,那么他就需要休息。那么他就需要休息。5.三角形是等腰三角形三角形是等腰三角形,当且仅当

8、三角形的两个底角当且仅当三角形的两个底角相等。相等。现在学习的是第9页，共123页(一一)否定否定()定义定义1.1设设P为为任任一一命命题题,复复合合命命题题“非非P”(或或P的的否否定定)称为称为P 否定式否定式。记作记作P。为为否定联结词否定联结词。P为真为真,当且仅当当且仅当P为假为假;P是假是假,当且仅当当且仅当P为真。为真。否定联结词否定联结词的定义可由表的定义可由表1-1表示之。表示之。由由由由于于于于“否否否否定定定定”修修修修改改改改了了了了命命命命题题题题,它它它它是是是是对对对对单单单单个个个个命命命命题题题题进进进进行行行行操操操操作作作作,称称称称它它它它为为为为一元

9、一元一元一元联结词。联结词。联结词。联结词。表表表表1-1 的定义的定义的定义的定义P P PP0 0111 100现在学习的是第10页，共123页(二二)合取合取()定义定义1.2设设P、Q为为两两个个命命题题,复复合合命命题题“P并并且且Q”(或或P与与Q)称称作作P与与Q的的合合取取式式,记记作作:PQ。称称为为合合取取联联结词结词。PQ为真当且仅当为真当且仅当P和和Q同为真同为真,否则否则PQ为假。为假。合取联结词合取联结词的定义由表的定义由表1-2表示之。表示之。“合合合合取取取取”是是是是一一一一个个个个二二二二元元元元运算。运算。运算。运算。表表表表1-21-2的定义的定义PQ

10、P Q 11 1 0001100 0 0 现在学习的是第11页，共123页例例1.3：将下列命题符号化。将下列命题符号化。(1)李平既聪明又用功。李平既聪明又用功。(2)李平虽然聪明李平虽然聪明,但不用功。但不用功。(3)李平不但聪明李平不但聪明,而且用功。而且用功。(4)李平不是不聪明李平不是不聪明,而是不用功。而是不用功。(5)张辉和王丽都是三好学生。张辉和王丽都是三好学生。(6)张辉和王丽是同学。张辉和王丽是同学。解：解：命题符号化命题符号化:P:李平聪明。李平聪明。Q:李平用功。李平用功。R:张辉是三好学生。张辉是三好学生。S:王丽是三好学生。王丽是三好学生。T:张辉和王丽是同学。张辉

11、和王丽是同学。选用合适的联结词将命题符号化：选用合适的联结词将命题符号化：(1)PQ(2)PQ(3)PQ(4)(P)Q(5)RS(6)T现在学习的是第12页，共123页(三三)析取析取()定定义义1.3设设P和和Q为为两两个个命命题题,复复合合命命题题“P或或Q”称称作作P与与Q的的析取式析取式,记作记作:PQ,为为析取联结词析取联结词。PQ的为假当且仅当的为假当且仅当P与与Q同为假同为假,否则否则PQ为真。为真。析取联结词析取联结词的定义由表的定义由表1-3表示之。表示之。“析析析析取取取取”是是是是一一一一个个个个二二二二元元元元运算。运算。运算。运算。表表表表 1-31-3的定义的定义P

12、 QP Q000110110111现在学习的是第13页，共123页例：例：将下列命题符号化。将下列命题符号化。1.王燕学过英语或日语。王燕学过英语或日语。(可兼或可兼或)P:王燕学过英语。王燕学过英语。Q:王燕学过日语。王燕学过日语。则则:PQ2.他昨天做了他昨天做了20题或题或30题。题。“或或”只表示了习题的近似数目只表示了习题的近似数目,是是原子命题原子命题。不能。不能用用“”表示。表示。P:他昨天做了他昨天做了20题或题或30题。题。3.我在教室看书或在图书馆看书。我在教室看书或在图书馆看书。排斥或排斥或/异或异或“”表示。表示。P:我在教室看书。我在教室看书。Q:我在图书馆看书。我在

13、图书馆看书。则则:P QP Q=(PQ)(PQ)=(PQ)(PQ)现在学习的是第14页，共123页(四四)蕴涵蕴涵()定义定义1.4设设P和和Q为为两两个个命命题题,复复合合命命题题“如如果果P,则则Q”称称作作P和和Q的的蕴涵式蕴涵式,记作记作:PQ,称称为为蕴涵联结词蕴涵联结词。当当P的的真真值值为为真真,而而Q的的真真值值为为假假时时,命命题题PQ的的真真值为假值为假;否则否则,PQ的真值为真。的真值为真。蕴涵联结词蕴涵联结词的定义由表的定义由表1-4表示之。表示之。表表1-4的定义的定义P QP Q000110111101现在学习的是第15页，共123页注注:在在条条件件命命题题PQ

14、中中,命命题题P 称称为为PQ 的的前前件件或或前提前提,命题命题Q 称为称为PQ 的的后件后件或或结论结论。条件命题条件命题PQ 有有多种方式陈述多种方式陈述：(1)“如果如果P,则则Q”;(2)“P 是是Q 的的充分条件充分条件”;(3)“Q 是是P 的的必要条件必要条件”;(4)“P 仅当仅当Q”;(5)“只有只有Q 才才P”;。现在学习的是第16页，共123页例：例：将下列将下列命题符号化命题符号化。1.如果我拿到奖学金如果我拿到奖学金,我就请客。我就请客。P:我拿到奖学金。我拿到奖学金。Q:我请客。我请客。PQ2.如果他努力学习如果他努力学习,就会门门功课优秀。就会门门功课优秀。P:

15、他努力学习。他努力学习。Q:他门门功课优秀。他门门功课优秀。PQ3.只要不下雨只要不下雨,我就骑自行车上班。我就骑自行车上班。P:天下雨。天下雨。Q:我骑自行车上班。我骑自行车上班。PQ4.只有不下雨只有不下雨,我才骑自行车上班。我才骑自行车上班。P:天下雨。天下雨。Q:我骑自行车上班。我骑自行车上班。QP现在学习的是第17页，共123页注意：注意：在使用在使用在使用在使用联结词联结词联结词联结词时时时时,要特别注意以下几点要特别注意以下几点要特别注意以下几点要特别注意以下几点:1.1.在自然语言里在自然语言里在自然语言里在自然语言里,特别在数学中特别在数学中特别在数学中特别在数学中,QQ是是

16、是是P P的必要条件的必要条件的必要条件的必要条件有多种不同的叙述有多种不同的叙述有多种不同的叙述有多种不同的叙述方式。方式。方式。方式。如如如如:“只要只要只要只要P,P,就就就就QQ”,“”,“因为因为因为因为P,P,所以所以所以所以QQ”,“”,“P P仅当仅当仅当仅当QQ”,“”,“只有只有只有只有QQ才才才才P P”,“”,“除非除非除非除非QQ才才才才P P”,“”,“除非除非除非除非Q,Q,否则非否则非否则非否则非P P”。各种叙述方式表面看来。各种叙述方式表面看来。各种叙述方式表面看来。各种叙述方式表面看来有所不同有所不同有所不同有所不同,但都表达的是但都表达的是但都表达的是但

17、都表达的是QQ是是是是P P的必要条件的必要条件的必要条件的必要条件,故联结词均符号化为故联结词均符号化为故联结词均符号化为故联结词均符号化为,均符号化为均符号化为均符号化为均符号化为 P PQQ。2.2.在自然语言中在自然语言中在自然语言中在自然语言中,“,“如果如果如果如果P,P,则则则则Q”Q”中的中的中的中的前件前件前件前件P P与与与与后件后件后件后件QQ往往具有某种内在往往具有某种内在往往具有某种内在往往具有某种内在联系。而联系。而联系。而联系。而在数理逻辑中在数理逻辑中在数理逻辑中在数理逻辑中,P,P与与与与QQ可以可以可以可以无无无无任何内在联系任何内在联系任何内在联系任何内在

18、联系。3.3.在数学或其它自然科学中在数学或其它自然科学中在数学或其它自然科学中在数学或其它自然科学中,“,“如果如果如果如果P,P,则则则则Q”Q”往往表达的是往往表达的是往往表达的是往往表达的是前件前件前件前件P P为真为真为真为真,后件后件后件后件QQ也为真的也为真的也为真的也为真的推理关系。但在数理逻辑中推理关系。但在数理逻辑中推理关系。但在数理逻辑中推理关系。但在数理逻辑中,作为一种规定作为一种规定作为一种规定作为一种规定,当当当当P P为假时为假时为假时为假时,无论无论无论无论QQ是真是假是真是假是真是假是真是假,P,PQQ均为真。即均为真。即均为真。即均为真。即:“:“只有只有只

19、有只有P P为真为真为真为真QQ为假为假为假为假”使得复合命题使得复合命题使得复合命题使得复合命题P PQQ为假为假为假为假。现在学习的是第18页，共123页(五五)双条件双条件()定义定义1.5令令P、Q是是两两个个命命题题,复复合合命命题题“P当当且且仅仅当当Q”称称作作P与与Q的的等价式等价式,记作记作PQ。称称为为等价联结词等价联结词。当当P和和Q的的真真值值相相同同时时,PQ的的真真值值为为真真;否否则则PQ的真值为假。的真值为假。等价联结词等价联结词的定义由表的定义由表1-5表示之。表示之。表表1-5的定义的定义P Q PQ00 01 10 11 1001现在学习的是第19页，共1

20、23页以上定义了以上定义了以上定义了以上定义了五种五种最基本、最常用、也是最重要的最基本、最常用、也是最重要的最基本、最常用、也是最重要的最基本、最常用、也是最重要的联结词联结词联结词联结词:、,将它们组成一个集合将它们组成一个集合将它们组成一个集合将它们组成一个集合,称为一个称为一个称为一个称为一个联结词集联结词集联结词集联结词集。其中。其中。其中。其中 为一元联结词为一元联结词为一元联结词为一元联结词,其余其余其余其余的都是二元联结词。的都是二元联结词。的都是二元联结词。的都是二元联结词。使用这些联结词有什么好处呢使用这些联结词有什么好处呢使用这些联结词有什么好处呢使用这些联结词有什么好处

21、呢？可以将复杂命题表示成简单的符号公式可以将复杂命题表示成简单的符号公式。PQ PP QP QP QPQPQ00100011011011101000110011011011现在学习的是第20页，共123页把一个用文字叙述的命题相应地写成由命题标识符、把一个用文字叙述的命题相应地写成由命题标识符、联结词和圆括号表示的联结词和圆括号表示的合式公式合式公式,称为称为命题的符号化命题的符号化。符号化应该符号化应该注意注意下列事项下列事项:确定给定句子是否为命题。确定给定句子是否为命题。句子中连词是否为命题联结词。句子中连词是否为命题联结词。要正确地表示原子命题和选择适当命题联结词。要正确地表示原子命题

22、和选择适当命题联结词。命题的符号化命题的符号化现在学习的是第21页，共123页命题符号化是很重要的命题符号化是很重要的,一定要掌握好。一定要掌握好。在在命命题题推推理理中中常常常常最最先先遇遇到到的的就就是是符符号号化化这这个个问问题题,解解决决不不好好,等等于于说说推推理理的的首首要要前前提提没没有有了。了。现在学习的是第22页，共123页在在本本节节结结束束时时,应应强强调调指指出出的的是是:复复合合命命题题的的真真值值只只取取决决于于各各原原子子命命题题的的真真值值,而而与与它它们们的的内内容容、含含义义无无关关,与原子命题之间是否有关系无关与原子命题之间是否有关系无关。理解和掌握这一点

23、是至关重要的理解和掌握这一点是至关重要的,请认真领会。请认真领会。现在学习的是第23页，共123页1.2命题公式及分类命题公式及分类一、命题公式一、命题公式(合式公式合式公式)通通常常把把含含有有命命题题变变元元的的断断言言称称为为命命题题公公式式。但但这这没没能能指指出出命命题题公公式式的的结结构构,因因为为不不是是所所有有由由命命题题变变元元、联联结结词词和和括括号号所所组组成成的的字字符符串串都都能能成成为为命命题题公公式式。为为此此常常使使用用归归纳纳定定义义命命题题公公式式,以以便便构构成成的的公公式式有有规规则则可可循循。由由这这种种定定义义产产生生的的公公式式称称为为合合式式公式

24、公式。现在学习的是第24页，共123页定定义义1.6命命题题演演算算的的合合式式公公式式(Well-formed formula_WFF)是由下列规则所产生的符号串是由下列规则所产生的符号串:(1)单个命题常量、变元是一个单个命题常量、变元是一个WFF;(2)如果如果A是是WFF,则则(A)是是WFF;(3)如果如果A、B是是WFF,则则(AB)、(AB)、(AB)和和(AB)都是都是WFF;(4)只有有限次地使用规则只有有限次地使用规则(1)(3)得到的符号串才是得到的符号串才是合合式公式式公式WFF。一、命题公式一、命题公式(合式公式合式公式)现在学习的是第25页，共123页当当合合式式公

25、公式式比比较较复复杂杂时时,常常常常使使用用很很多多圆圆括括号号。为为了了减少减少圆括号的使用量圆括号的使用量,可作以下可作以下约定约定:规定联结词的优先级规定联结词的优先级由高到低由高到低由高到低由高到低的次序为的次序为:、相相同同的的联联结结词词按按从从左左至至右右次次序序计计算算时时,圆圆括括号号可可省省略。略。最外层的圆括号可以省略。最外层的圆括号可以省略。合式公式合式公式也简称也简称公式公式。现在学习的是第26页，共123页二、命题公式的层次二、命题公式的层次定义定义1.7(1)若若A是单个命题是单个命题(常项或变项常项或变项),则称则称A是是0层公式层公式;(2)称称A是是n+1(

26、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,其中其中B、C的层次同的层次同。现在学习的是第27页，共123页三、命题公式的解释三、命题公式的解释(赋值赋值)定定义义1.8设设A为为命命题题公公式式,P1,P2,Pn 为为出出现现在在A 中中的的所所有有命命题题变变元元。给给Pi(i=1,2,n)指指定定一一组组真真值值,称称为为对对公公式式A的的一一个个真真值值指指派

27、派(也也称称解解释释或或赋赋值值),记作记作I。(1)若指定的一组真值使公式若指定的一组真值使公式A为为真真,则称这组真值为则称这组真值为A的的成真赋值成真赋值；(2)若指定的一组真值使公式若指定的一组真值使公式A为为假假,则称这组真值为则称这组真值为A的的成假赋值成假赋值。现在学习的是第28页，共123页例例：设命题公式：设命题公式：设命题公式：设命题公式 A=PQR：在解释在解释I I1 1=(0,0,0)下下下下,A,A为真为真为真为真,则则I1 1为为为为A的成真赋值的成真赋值的成真赋值的成真赋值;在解释在解释在解释在解释 I2 2=(1,1,0)=(1,1,0)下下下下,A,A为假为

28、假为假为假,则则则则 I2为为为为A的成假赋值。的成假赋值。的成假赋值。的成假赋值。一个命题公式中含有一个命题公式中含有n 个命题变元个命题变元,则共有则共有2n 组组不同的赋值不同的赋值。现在学习的是第29页，共123页四、真值表四、真值表定义定义:在命题公式中在命题公式中,把所有命题变元在所有可能的解把所有命题变元在所有可能的解释释(赋值赋值)下取得的真值汇列成的表格称为下取得的真值汇列成的表格称为真值表真值表。构造构造真值表真值表的的步骤步骤如下如下:(1)找出公式中所含的找出公式中所含的全部命题变元全部命题变元(如有如有n个个),列出列出2n个个赋值赋值;(2)按按从低到高从低到高的顺

29、序写出各层次的子公式的顺序写出各层次的子公式;(3)对应各个赋值对应各个赋值,计算出各层次的真值计算出各层次的真值,直到直到最后计算出最后计算出命题公式的真值命题公式的真值。现在学习的是第30页，共123页例例:下列公式的真值表下列公式的真值表,并求并求成真赋值成真赋值和和成假赋值成假赋值。(1)(PQ)R(2)(PP)(QQ)(3)(PQ)QR现在学习的是第31页，共123页定义定义1.9设设A 为命题公式为命题公式,则则若若A在它的各种赋值下取值均为在它的各种赋值下取值均为真真,则称则称A为为永永真式真式或或重言式重言式。若若A在它的各种赋值下取值均为在它的各种赋值下取值均为假假,则称则称

30、A为为永永假式假式或或矛盾式矛盾式。若若A至少存在一组赋值至少存在一组赋值是是成真赋值成真赋值,则称则称A为为可可满足式满足式。五、命题公式的分类五、命题公式的分类现在学习的是第32页，共123页判定判定给定公式是否为给定公式是否为永真式永真式、永假式永假式或或可满足式可满足式的问题的问题,称为命题公式的称为命题公式的判定问题判定问题。真值表真值表可用来可用来判断判断公式的类型公式的类型：1.若真值表最后一列若真值表最后一列全为全为1,则公式为则公式为永真式永真式。2.若真值表最后一列若真值表最后一列全为全为0,则公式为则公式为永假式永假式。3.若真值表最后一列中若真值表最后一列中至少有一个至

31、少有一个1,则公式为则公式为可满可满足式足式。现在学习的是第33页，共123页注注:由定义可知由定义可知,永真式永真式一定是一定是可满足式可满足式,但反之不真。但反之不真。重点重点将研究将研究重言式重言式,它最有用它最有用,因为它有以下因为它有以下特点特点:重言式重言式的的否定否定是是矛盾式矛盾式,矛盾式矛盾式的的否定否定是是重言式重言式,这样这样只研究其一就可以了。只研究其一就可以了。两两重言式重言式的的合取式合取式、析取式析取式、条件式条件式和和双条件式双条件式等都等都仍是仍是重言式重言式。于是。于是,由简单的由简单的重言式重言式可构造出复杂的可构造出复杂的重重言式言式。由由重言式重言式使

32、用使用公认的规则公认的规则公认的规则公认的规则可以产生许多有用可以产生许多有用等价式等价式和和蕴涵式蕴涵式。现在学习的是第34页，共123页一、等价公式一、等价公式定定义义1.10设设设设 A A、B B 是是是是两两两两个个个个命命命命题题题题公公公公式式式式,若若若若 A A B B 是是是是永永永永真真真真式式式式(即即即即 A A、B B 在在在在任任任任意意意意指指指指派派派派下下下下,真真真真值值值值均均均均相相相相同同同同),),则则则则称称称称 A A 和和和和 B B 是是是是等等价价的的的的,记记记记作作作作 A AB B。显显然然,若若公公式式A和和B的的真真值值表表是是

33、相相同同的的,则则A和和B等等价。价。因因此此,验验证证两两公公式式是是否否等等价价,只只需需做做出出它它们们的的真真值值表表即即可。可。1.3等值演算等值演算现在学习的是第35页，共123页注意注意：和和的区别与联系。的区别与联系。区区别别：是是逻逻辑辑联联结结词词,属属于于目目标标语语言言中中的的符符号号,它它出现在命题公式中出现在命题公式中;不不是是逻逻辑辑联联结结词词,用用于于表表示示两两个个命命题题公公式式的的一一种种关关系系,不不属属于于这这两两个个公公式式的的任任何何一一个个公公式式中中的符号。的符号。联系联系：可用下面定理表明之。：可用下面定理表明之。现在学习的是第36页，共1

34、23页定理：定理：设设A和和B是两个命题公式是两个命题公式,AB当且仅当当且仅当AB是永真式是永真式。证明：证明：(充分性充分性)若若AB是永真式是永真式,则其原子命题不论则其原子命题不论在何种解释下在何种解释下,AB均为真均为真;按照按照AB的真值表的真值表,只有当只有当A、B具有相同的真值时具有相同的真值时,才有才有ABT于是于是,无论什么情况都有无论什么情况都有AB。(必要性必要性)如果如果AB,即即A、B在任意解释下都具有相同在任意解释下都具有相同的真值的真值,故必有故必有AB恒为恒为T,即即AB是永真式。是永真式。#现在学习的是第37页，共123页等价式具有下列性质：等价式具有下列性

35、质：自反性自反性:即对任意公式即对任意公式A,有有AA。对称性对称性:即对任意公式即对任意公式A和和B,若若AB,则则BA。传递性传递性:即对任意公式即对任意公式A、B和和C,若若AB、BC,则则AC。现在学习的是第38页，共123页在在判判定定公公式式之之间间是是否否等等价价,有有一一些些简简单单而而又又经经常常使使用用的的等等价价式式,称称为为基基本本等等价价式式或或称称命命题题定定律律。牢牢固固记记住住并能熟练运用并能熟练运用,是学好数理逻辑的是学好数理逻辑的关键关键关键关键之一之一。24个重要的等值式：个重要的等值式：(1)(1)双重否定律：双重否定律：A A A(2)等幂律：等幂律：

36、A AA A,A AA A A A(3)结合律：结合律：结合律：结合律：(AB)C C A(BC),),(AB B)C A(B BC C)二、基本等价式二、基本等价式命题定律命题定律现在学习的是第39页，共123页(4)(4)交换律：交换律：交换律：交换律：AB B BA A,A AB B BAAB BA(5)(5)分配律：分配律：分配律：分配律：A A(B BC C)(A AB)(AC C)A(BC)(A AB B)(AC)(6)吸收律：吸收律：A(A AB B)A A,A A(A AB B)A(7)(7)德德 摩根律：摩根律：(A AB B)A B (A AB)A A B B(8)(8)同

37、一律：同一律：同一律：同一律：A1 1 A A,A A0 A。(9)零零零零 律：律：律：律：A A0 0 0,A A1 1 1 1。现在学习的是第40页，共123页(10)补余律：补余律：补余律：补余律：A AA 0 0 (矛盾律矛盾律矛盾律矛盾律)A A A 1 1(排中律排中律排中律排中律)(11)蕴含等值式：蕴含等值式：AB A AB B,(12)假言易位：假言易位：假言易位：假言易位：A AB B B A A。(13)等价等值式：等价等值式：A AB (A AB)(B BA A)(AB B)(A A B)(14)等价否定律：等价否定律：等价否定律：等价否定律：AB B AB(15)归

38、谬论：归谬论：归谬论：归谬论：(AB)(AB B)A A。现在学习的是第41页，共123页以上以上15组等值式包含了组等值式包含了24个重要等值式。个重要等值式。由于由于A、B、C可代表任意的公式可代表任意的公式,因而每个公因而每个公式都是一个模式式都是一个模式(称之为称之为等值式模式等值式模式)。每个每个等值式模式等值式模式都给出了无穷多个同类型的具都给出了无穷多个同类型的具体的等值式。体的等值式。现在学习的是第42页，共123页三、代入规则和置换规则三、代入规则和置换规则例如例如,在蕴含等值式在蕴含等值式(AB AB)中中,当取当取A=PQR,B=PQ时时,得等值式为：得等值式为：(PQR

39、)(PQ)(PQR)(PQ)所得的等值式称为原来的所得的等值式称为原来的等值式模式等值式模式的的代换实例代换实例。每个具体的代换实例的正确性都可用真值表证明之每个具体的代换实例的正确性都可用真值表证明之。定定理理:在在一一个个永永真真式式A 中中,任任何何一一个个原原子子命命题题变变元元R 出出现现的的每每一一处处,用用另另一一个个公公式式代代入入,所所得得公公式式B 仍仍是是永永真真式式。(代入规则代入规则)现在学习的是第43页，共123页定定义义如如果果X是是合合式式公公式式A的的一一部部分分,且且X本本身身也也是是一一个合式公式个合式公式,则称则称X为公式为公式A的的子公式子公式。定定理

40、理1.1设设A1是是合合式式公公式式A的的子子公公式式,若若A1B1,并并且且将将A中中的的A1用用B1替替换换得得到到公公式式B,则则AB。称称该该定定理理为为置换规则置换规则。例例:在公式在公式(PQ)R中中,可用蕴含等值式依次置换可用蕴含等值式依次置换,得得:(PQ)R(PQ)R(PQ)R(PQ)R(PR)(QR)现在学习的是第44页，共123页注：注：代入代入和和置换置换有两点区别有两点区别：代代入入是是对对原原子子命命题题变变元元而而而而言言言言的的的的,而而而而置置置置换换换换可可可可对对对对命命命命题题题题公公公公式式式式实行。实行。实行。实行。代代入入必必须须是是处处处处代代入

41、入,置置换换则则可可部部部部分分分分替替替替换换换换,亦亦亦亦可可可可全全全全部替换。部替换。部替换。部替换。现在学习的是第45页，共123页我们已经给出了我们已经给出了:1.重言式重言式(永真式永真式)的的代换实例代换实例为为重言式重言式(永真式永真式)。2.重言式重言式(永真式永真式)的的否定否定为为矛盾式矛盾式(永假式永假式)。3.两两重言式重言式(永真式永真式)的的合取式合取式、析取式析取式、条件式条件式和和双双条件式条件式等都仍是等都仍是重言式重言式(永真式永真式)。于是。于是,由简单的由简单的重言式重言式可构造出复杂的可构造出复杂的重言式重言式。现在学习的是第46页，共123页虽然

42、用真值表法可以判断任何两个命题公式是否等虽然用真值表法可以判断任何两个命题公式是否等值值,但当命题变元较多时但当命题变元较多时,工作量是很大的。工作量是很大的。前面我们已经介绍了前面我们已经介绍了15组组24个重要的个重要的等值式等值式和和代入代入规则规则、置换规则置换规则,利用它们就可以通过利用它们就可以通过等值演算等值演算来判来判断两个命题公式是否等价。断两个命题公式是否等价。四、等值演算四、等值演算现在学习的是第47页，共123页例例:用等值演算判断下列公式的类型：用等值演算判断下列公式的类型：(1)(PQ)PQ(2)(P(PQ)R(3)P(PQ)P)Q)现在学习的是第48页，共123页

43、(1)(PQ)PQ(PQ)PQ(蕴含等值式蕴含等值式蕴含等值式蕴含等值式)(PQ)P)Q(蕴含等值式蕴含等值式蕴含等值式蕴含等值式)(PQ)P)Q(德德德德 摩根律摩根律摩根律摩根律)(PQ)P)Q(德德德德 摩根律、双重否定律摩根律、双重否定律摩根律、双重否定律摩根律、双重否定律)(PP)(QP)Q(分配律分配律分配律分配律)(1(QP)Q(排中律排中律排中律排中律)(QQ)P(交换律、结合律交换律、结合律交换律、结合律交换律、结合律)1P(零律零律零律零律)1最后结果说明最后结果说明(1)中公式是中公式是重言式重言式现在学习的是第49页，共123页(2)(P(PQ)R(PPQ)R(蕴含等值

44、式蕴含等值式蕴含等值式蕴含等值式)(PPQ)R(德德德德 摩根律摩根律摩根律摩根律)0R(矛盾律、零律矛盾律、零律矛盾律、零律矛盾律、零律)0(零律零律零律零律)最后结果说明最后结果说明(2)中公式是中公式是矛盾式矛盾式。现在学习的是第50页，共123页(3)P(PQ)P)Q)P(PQ)P)Q)(蕴含等值式蕴含等值式蕴含等值式蕴含等值式)P(PP)(QP)Q)(分配律分配律分配律分配律)P(0(QP)Q)(矛盾律、零律矛盾律、零律矛盾律、零律矛盾律、零律)P(QPQ)(德德德德 摩根律摩根律摩根律摩根律)P1(排中律排中律排中律排中律)P(同一律同一律同一律同一律)最后结果说明最后结果说明(3

45、)中公式是中公式是可满足式可满足式。现在学习的是第51页，共123页例例:验证下列等值式：验证下列等值式：(1)P(QR)(PQ)R(2)P(PQ)(P Q)现在学习的是第52页，共123页等值演算还能帮助人们解决工作和生活中的判断等值演算还能帮助人们解决工作和生活中的判断问题。问题。例例:在某次研讨会的中间休息时间在某次研讨会的中间休息时间,3名与会者根据王教名与会者根据王教授的口音对他是哪个省市的人进行了判断：授的口音对他是哪个省市的人进行了判断：甲说甲说:王教授不是苏州人王教授不是苏州人,是上海人。是上海人。乙说乙说:王教授不是上海人王教授不是上海人,是苏州人。是苏州人。丙说丙说:王教授

46、既不是上海人王教授既不是上海人,也不是杭州人。也不是杭州人。听完以上听完以上3人的判断后人的判断后,王教授笑着说王教授笑着说,他们他们3人中有人中有一人说的全对一人说的全对,有一人说对了一半有一人说对了一半,另一人说的全不对。另一人说的全不对。试用命题演算法分析王教授到底是哪里人？试用命题演算法分析王教授到底是哪里人？现在学习的是第53页，共123页解解:设命题：设命题：P:王教授是苏州人。王教授是苏州人。Q:王教授是上海人。王教授是上海人。R:王教授是杭州人。王教授是杭州人。P,Q,R中必有一个真命题中必有一个真命题,两个假命题两个假命题,要通要通过命题演算将真命题找出来。过命题演算将真命题

47、找出来。现在学习的是第54页，共123页设：设：甲甲的判断为的判断为:A1=PQ乙乙的判断为的判断为:A2=PQ丙丙的判断为的判断为:A3=QR则有：则有：甲甲的判断的判断全对全对为为:B1=A1=PQ甲甲的判断的判断对一半对一半为为:B2=(PQ)(PQ)甲甲的判断的判断全错全错为为:B3=PQ乙乙的判断的判断全对全对为为:C1=A2=PQ乙乙的判断的判断对一半对一半为为:C2=(PQ)(PQ)乙乙的判断的判断全错全错为为:C3=PQ丙丙的判断的判断全对全对为为:D1=A3=QR丙丙的判断的判断对一半对一半为为:D2=(QR)(QR)丙丙甲的判断甲的判断全错全错为为:D3=QR现在学习的是第

48、55页，共123页由王教授所说由王教授所说“甲、乙、丙甲、乙、丙3人中有一人说的全对人中有一人说的全对,有有一人说对了一半一人说对了一半,另一人说的全不对另一人说的全不对”,得出公式得出公式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)

49、R)(P(PQQ QQR)R)0 0现在学习的是第56页，共123页类似地可得：类似地可得：B2C3D10B3C1D2PQRB3C2D10于是于是,由由同一律同一律可知可知E(PQR)(PQR)但因为王教授不能既是上海人但因为王教授不能既是上海人,又是杭州人又是杭州人,因而因而P,R必有一个假命题必有一个假命题,即即PQR0,于是于是EPQR为真命题为真命题,因而必有因而必有P,R为假命题为假命题,Q为真命题为真命题,即即王教王教授是上海人授是上海人。甲说的全对甲说的全对,丙说对了一半丙说对了一半,而乙全说错了而乙全说错了。现在学习的是第57页，共123页1.5对偶与范式对偶与范式要求：要求：

50、掌掌握握对对偶偶与与范范式式,会会求求命命题题公公式式的的主主析析取取范范式式、主合取范式。主合取范式。重点与难点：重点与难点：求命题公式的主析求命题公式的主析(合合)取范式。取范式。现在学习的是第58页，共123页1.5对偶与范式对偶与范式一、对偶一、对偶在在前前面面介介绍绍的的命命题题定定律律中中,多多数数公公式式是是成成对对出出现现的的,这些成对出现的定律就是这些成对出现的定律就是对偶性质对偶性质的反映的反映,即即对偶式对偶式。利利用用对对偶偶式式的的命命题题定定律律,可可以以扩扩大大等等价价式式的的个个数数,也也可可减少减少证明的次数。证明的次数。现在学习的是第59页，共123页定义定