逻辑学(北大精品课)02.ppt

《逻辑学(北大精品课)02.ppt》由会员分享，可在线阅读，更多相关《逻辑学(北大精品课)02.ppt（92页珍藏版）》请在三一办公上搜索。

1、A Course in Logic,主讲人：何向东,-进入-,逻辑学教程,第二章 命题逻辑,第一节 命题逻辑概述,2023年5月9日星期二,3,命题,（1）西南大学在重庆。（2）闪光的东西都是金子。（3）如果小王有作案动机，那么他就会作案。符合实际的命题是真命题，不符合实际的命题是假命题。上述（1）是真命题;而（2）、（3）是假命题。,命题是通过语句来反映事物情况的思维形态。例如：,命题的主要特征：命题有真假,2023年5月9日星期二,4,命题和语句,首先，有的语句不能直接表达命题，如：（1）西南大学在重庆吗?（2）请把门关上！一般来讲：陈述句与反诘句可以直接表达命题。其次，同一命题可以用不同

2、的语句来表达，如：“所有的鸟都会飞”与“没有鸟不会飞”表达了相同的命题。此外，同一命题可用不同的民族语言的语句来表达。再次，同一语句，可以表达不同的命题，如：小张将书还给小王，因为他要回家了。,任何命题都是通过语句来表达的，但语句和命题并非一一对应：,语句(陈述句和反诘句)有内涵也有外延:语句的内涵即它表达的命题；语句的外延即真、假这两个真值。采用这种观点的逻辑理论，称为二值外延逻辑或经典逻辑。逻辑学上所说的命题，一般指这种或者为真或者为假的抽象语句。,2023年5月9日星期二,5,命题和判断,一个命题是否能成为判断，与断定者的知识、立场等有关。如：“杜甫是伟大的诗人”能否被断定就与断定者的知

3、识水平有很大关系。充分假言命题被断定是前后件的关系，而不是支命题。如：“如果物体受到摩擦，那么物体发热”这个命题，我们既没有断定“物体受到摩擦”，也没有断定“物体发热”，我们所断定的只是前件是后件的充分条件。,判断：就是被断定者断定了的命题。判断的主要特征：有所断定。,2023年5月9日星期二,6,命题的分类,2023年5月9日星期二,7,命题分析的层次,将联结词所联结的命题作为一个完整的单位来看待研究关于联结词的推理(命题逻辑)深入到命题内部，把命题分析为主项、谓项、量项和联项研究关于量项和联项的推理(传统词项逻辑)深入到命题内部，把命题分析为个体词、谓词、量词及联结词研究关于量词的推理(现

4、代谓词逻辑)把命题中包含的模态词分析出来研究关于模态词的推理(模态逻辑),2023年5月9日星期二,8,逻辑语形学与逻辑语义学,逻辑语形(语法)学:研究符号与符号关系的逻辑理论。逻辑语义学:研究符号及其解释的逻辑理论，如:把p、q、r解释为取真假值的命题变元，把、解释为真值集上的运算，把pq、pq、pq解释为真值函数的表达式。推理是由前提和结论组成的，前提和结论之间的关系称为推出（推论、推理）关系。例如：小王既有缺点，又有优点，所以，小王有优点。在推理中，前提是“小王既有缺点，又有优点”，结论是“小王有优点”，“所以”标志前提和结论之间的推出关系。推理形式：p且q，所以，q。逻辑学是从语形和语

5、义两个方面来研究推理的：(1)从前提和结论的形式方面进行(2)从前提和结论的真假方面进行 语形和语义对推出关系的双重刻画,第二章 命题逻辑,第二节 复合命题及其推理,2023年5月9日星期二,10,负命题,(1)并非选修逻辑的学生都是文科生。(2)这个班的学生不都学英语。(3)如果它是三角形，则内角和等于180，这个观点不对。注：负命题的支命题可以是简单命题，也可以是复合命题。负命题的形式:p。其中p称为的辖域。负命题的逻辑性质：负命题的真假与被否定的命题的真假是相反的。,负命题由否定联结词(如“并非”)联结支命题而形成的复合命题。例如：,2023年5月9日星期二,11,负命题,真值表：真值集

6、合只有两个元素T，F，其中T表示命题为真，而F表示命题为假。因此，可用列表的方式表示真值运算的过程，这种表称为真值表。真值函数：当p在真值集合T，F上取真值后，p 的真值也唯一确定。所以，p是p的函数，表达形式为f(p)=p，这种函数称真值函数。的真值表如下：,根据这个真值表，也可以给f(p)=p这个一元真值函数作如下定义：p为真当且仅当p为假；p为假当且仅当p为真。,T,F,真值表的作用,2023年5月9日星期二,12,负命题,根据负命题的逻辑性质，可对p再否定得到p，其真值与p相同，真值表如下：,由上真值表知，对任意公式A，有等值关系：A A,负命题的推导规则:,2023年5月9日星期二,

7、13,联言命题,（1）小张歌唱得好并且舞跳得好。（2）这样建立的逻辑系统既有可靠性，又有完全性。联言命题的形式：p并且q（pq）。p称为的左辖域，q称为的右辖域。pq是二元真值函数：f(p,q)=pq。是在两个真值变元p和q上进行运算的二元运算。,联言命题是由联言联结词(如“并且”)联结支命题而形成的复合命题，又称合取命题。例如：,2023年5月9日星期二,14,从上表可以得出联言命题的逻辑性质：当p、q同时为真时，pq才为真；只要p、q其中一个为假，则pq为假。,合取词的真值表,T,F,F,F,由的真值表,可得出运算的规律:（1）的交换律：pqqp（2）的结合律：p(qr)(pq)r（3）的

8、重言（幂等）律：ppp,2023年5月9日星期二,15,合取引入规则（+）：从A和B可推出AB。图示如下：AB AB合取消去规则（-）：从AB可推出A，从AB可推出B。图示如下：AB AB A B小张喜爱音乐，小张喜爱体育，所以，小张不但喜爱音乐，也喜爱体育。根据+作出一个形式正确的推理，推理形式为：p,q pq。小张既有优点，也有缺点，所以，小张是有优点的。根据_作出一个形式正确的推理，推理形式为：pq p。,联言命题的推导规则,2023年5月9日星期二,16,选言命题,选言命题分为“相容选言命题”和“不相容选言命题”两种。相容选言命题的选言支可以同时为真，如：(1)小王或者是班干部，或者是

9、学生会干部(二者可以得兼)。(2)这份统计材料，或者是原始材料有错误，或者是计算有错误，或者两种情况都存在。而不相容选言命题的选言支不能同时为真，如：(1)鱼，我所欲也，熊掌，亦我所欲也，二者不可得兼。(2)要么选老王当村长，要么选小李当村长。,选言命题用选言联结词联结支命题而形成的复合命题。,2023年5月9日星期二,17,相容选言命题的形式：p或者q(pq)的真值表：相容选言命题的逻辑特征：相容选言命题为真，则它的选言支至少有一个为真；反过来讲，当选言命题至少有一个选言支为真，选言命题一定为真。,T,F,T,T,相容选言命题及推理,2023年5月9日星期二,18,的运算规律和的混合运算规律

10、,(1)对的分配律:p(qr)(pq)(pr)。(2)对的分配律：p(qr)(pq)(pr)。(3)吸收律：p(pq)p；p(pq)p。(4)德摩根律：(pq)pq；(pq)pq。,(1)的交换律：pq qp，(2)的结合律：p(qr)(pq)r(3)的重言律：pp p。,2023年5月9日星期二,19,用真值表检验德摩根律：从上真值表，可得：(pq)pq应用德摩根律的实例:并非这件衣服物美(而且)价廉这件衣服或者物不美，或者价不廉。并非小李或者喜欢音乐，或者喜欢体育小李既不喜欢音乐，也不喜欢体育。,2023年5月9日星期二,20,析取消去规则()从AB和A可推出B；从AB和B可推出A。AB

11、AB A B B A（只讨论有两个选言支的选言命题，下同）析取消去规则的应用实例：或者李某是嫌疑犯，或者王某是嫌疑犯(或者二者都是)；李某不是嫌疑犯；所以，王某是嫌疑犯。其推理形式为：pq,p q肯定一个选言支，不能否定另一个选言支。下述推理形式均错误：AB,A B；AB，B A,规则：否定一个选言支，就要肯定另一个选言支。,2023年5月9日星期二,21,析取引入规则(记为)：从A可推出AB；从B可推出AB。A B AB AB 析取引入规则的应用实例：小王是医生；所以，小王是医生，或者小王是教师。其推理形式为：p pq,2023年5月9日星期二,22,F,T,T,F,不相容选言命题及推理,逻

12、辑性质：不相容选言命题为真，当且仅当两个选言支有且只有一个为真。,2023年5月9日星期二,23,2023年5月9日星期二,24,假言命题,（1）如果寒潮到来，那么气温就会下降。（2）只有你去，我才放心。（3）人不犯我，我不犯人，人若犯我，我必犯人。在（1）、（2）中由“如果”、“只有”引出的支命题称为前件，由“那么”、“才”引出的支命题称为后件。假言命题的种类一、充分条件假言命题二、必要条件假言命题三、充分必要条件假言命题,假言命题是由假言联结词(如“如果，那么”、“只有，才”、“当且仅当”等)联结支命题而形成的复合命题，例如：,2023年5月9日星期二,25,充分条件假言命题,(1)如果你

13、不断地坚持锻炼，你的身体就会康复。(2)假如语言能创造财富，那么，夸夸其谈的人就会成为世界上最富有的人。充分条件假言命题的形式：如果p，那么q(pq)在蕴涵式pq中，p称为的前件(左辖域)，q称为的后件(右辖域)。,充分条件假言命题亦称条件命题或者实质蕴涵命题,是用“如果，那么”等联结词联结前、后件形成的假言命题，例如：,2023年5月9日星期二,26,的真值表 充分条件假言命题的逻辑性质是：除了前件为真而后件为假时充分条件假言命题是假的以外,在其它三种情况下,充分条件假言命题都是真的。,T,T,T,F,2023年5月9日星期二,27,必要条件假言命题,(1)只有由细菌引起的疾病，才能用抗生素

14、治疗。(2)我不去，除非你去。必要条件假言命题的形式：只有p,才q(pq),用“只有，才”联结前、后件形成的假言命题，例如：,在蕴涵式pq中，p称为的前件(左辖域)，q称为的后件(右辖域)。,2023年5月9日星期二,28,的真值表必要条件假言命题的逻辑性质是：除了前件为假而后件为真时充分条件假言命题是假的之外,其它情况下,充分条件假言命题都是真的。,2023年5月9日星期二,29,充分必要条件假言命题,(1)a和b平行,当且仅当它们的同位角相等。(2)人不犯我，我不犯人；人若犯我，我必犯人。充要条件假言命题的形式：p当且仅当q(pq)在充要条件式pq中，称p为的前件(左辖域)，称q为 的后件

15、(右辖域)。,充分必要条件假言命题又称双条件命题，简称充要条件假言命题，是用“当且仅当”等作为联结词的命题，例如：,2023年5月9日星期二,30,的真值表的逻辑性质：当p和q的真值相同时，pq的真值为真；当p和q的真值不相同时，pq的真值为假。除上述已有规则外，、还有一些运算规律,F,F,T,T,2023年5月9日星期二,31,关于的推理规则,规则：肯定前件就要肯定后件,规则：否定后件就要否定前件,2023年5月9日星期二,32,关于的推理规则的应用,（1）如果甲方付给了定金,乙方就得按时发货。甲方已付给了定金。所以乙方得按时发货。其推理形式为：p q，p q（2）如果这部电影受观众欢迎，那

16、么买票的人就多。买票的人不多。所以这部电影不受观众欢迎。其推理形式为：p q,q p,规则：肯定前件就要肯定后件,规则：否定后件就要否定前件,2023年5月9日星期二,33,关于的推理的错误应用,在日常思维中，关于的推理，容易发生的错误是：从AB和B推出A；从AB和 A推出 B。例如如是小K是持枪杀人凶手，那么他肯定有枪。小K有枪。所以，他是持枪杀人凶手。如是小K是持枪杀人凶手，那么他肯定有枪。小K不是持枪杀人凶手。所以，他肯定没有枪。,为避免错误，制定了这样的规则：肯定后件不能肯定前件；否定前件不能否定后件。,2023年5月9日星期二,34,规则：否定前件就要否定后件,规则：肯定后件就要肯定

17、前件,关于的推理规则,2023年5月9日星期二,35,关于的推理规则应用,(1)只有你学习努力，才能取得好成绩。你学习不努力，所以，你不能取得好成绩。其推理形式为：pq，p q(2)除非发生了意外情况，这趟列车不会停在这个地方。它既然停在这个地方，可见，发生了意外情况。其推理形式为：pq,q p,2023年5月9日星期二,36,关于的推理的错误应用,在日常思维中，关于的推理的错误应用，容易发生的错误是:从AB和A推出B；从AB和 B推出 A。例如:只有小A在作案现场，他才是杀人凶手。有人证明小A在作案现场，所以，小A是杀人凶手。只有小A在作案现场，他才是杀人凶手。小A不是杀人凶手，所以，小A不

18、在作案现场。,为避免错误，制定了这样的规则：肯定前件不能肯定后件；否定后件不能否定前件。,2023年5月9日星期二,37,关于的推理规则,2023年5月9日星期二,38,其他常见的推理,1.假言易位推理：ABBA；ABBA；ABBA2.二难推理：简单构成式：AC,BC,AB C 复杂构成式：AC,BD,AB CD 简单破坏式：AB,AC,BC A 复杂破坏式：AC,BD,CDAB3.假言三段论：AB，BC AC4.反三段论：(AB)C(AC)B(AB)C(BC)A5.反证法：AB，AB A6.归谬法：AB，AB A,第二章 命题逻辑,第三节：命题逻辑的自然演绎系统NP,2023年5月9日星期二

19、,40,自然演绎系统NP,命题逻辑的自然演绎系统NP是由形式语言L 和一组推导（变形）规则构成的。其中形式语言L 包括初始符号、形成规则和定义。一、初始符号(1)甲类符号：p1,p2,p3,；(2)乙类符号：，；(3)丙类符号：(，)。这些符号构成的有穷长的序列叫做符号串，例如:p,pq，pq,pq；(pq)r，p(qr)，其中p、p 都称 p 的子公式。,构建命题逻辑的形式系统，可以采用公理化方法，也可采用自然演绎的方法。为接近人们的日常思维，现采用自然演绎的方法来构建命题逻辑的一个形式系统NP。,2023年5月9日星期二,41,自然演绎系统NP,二、形成规则(1)任何单个的命题变元p是合式

20、公式；(2)如果A是合式公式，则A是合式公式；(3)如果A和B是合式公式，则AB、AB、AB是合式公式；只有（1）-（3）形成的符号串是合式公式。三、定义：用来表示缩写的，定义两边的符号串可以相互代替。如：(AB)=df(AB)(BA)。形式语言L 的全体合式公式记为Form(L)。形式语言L 是我们的研究对象，叫对象语言。讨论对象语言的语言叫元语言或语法语言。,形成规则的作用,2023年5月9日星期二,42,NP系统的推导规则,1.合取引入规则(记为+)：从A和B推出AB；2.合取消去规则(记为_):从AB推出A；从AB推出B；3.析取引入规则(记为+)：从A推出AB；从B推出AB；4.析取

21、消去规则(记为_):从AB和A推出B；从AB和B推出A；5.蕴涵引入规则(记为+)：如果从公式集和A推出B，则从推出AB；6.蕴涵消去规则(记为_)：从AB和A推出B；7.否定消去规则(记为_)：如果从和A推出BB，则从推出A。,又称条件证明规则或演绎定理，是把从推出AB的推理转化为从和临时的假设A推出B的推理。(即移出律),又称间接证明或反证法，是把由推出A的推理转化为由和临时的假设A推出BB的推理。,2023年5月9日星期二,43,NP系统有前提的形式推演,一个有穷的公式序列B1,B2,，Bm是从前提集(不是空集)到结论B的有前提的形式推演，如果每一个公式Bi(1im)满足以下条件之一：(

22、1)Bi(即Bi是前提集中的一个公式)；(2)Bi是一个据+或-临时引入的假设；(3)Bi是该序列中在前的若干公式应用NP系统的推导规则得到的公式；(4)B=Bm。则我们称和B具有语法推出关系，B从中可演绎的，或者说，从可以推出B，记为：NPB。,2023年5月9日星期二,44,NP系统中的语法(语形)推出关系,我们以T1，T2，来给由基本推导规则确立的语法推出关系的编号，用(1)，(2)，(m)给形式推理过程中的公式序列中的每一个公式编号。T1 A A(肯定前提)(1)A 前提A既是该序列的第1个公式，也是第m个公式(m=1)。T2 A，B A(肯定前提)T3 A，B B(1)A A1(2)

23、B A2B是第2个公式，也是第m个公式(m=2)。,2023年5月9日星期二,45,NP系统中的语法(语形)推出关系,T4 A，B ABT5(a)AB AT5(b)AB BT6(a)A ABT6(b)B ABT7(a)AB,A BT7(b)AB,B AT8 AB,A B,2023年5月9日星期二,46,NP系统中的语法(语形)推出关系,T8:AB,A B(1)AB A1(2)A A2(3)B(1)，(2)，_T9(假言三段论，记为H.S.)：AB，BC AC(1)AB A1(2)BC A2(3)A H1(+的假设)(4)B(1)，(3)，_(5)C(2)，(4)，_(6)AC(3)(5)，+(

24、消去H1),2023年5月9日星期二,47,NP系统中的语法(语形)推出关系,T10(双重否定消去规则，记为_)：AA(1)A A(2)A H（_的假设）(3)AA(1)，(2)，+(4)A(2)(3)，_(消去H)T11(双重否定引入规则，记为+):AA(1)A A(2)A H（_的假设）(3)A(2)，_(4)AA(1)，(3)，+(5)A(2)(4)，_（消去H）,2023年5月9日星期二,48,NP系统中的语法(语形)推出关系,T12 A，BT13，A B只证T12：(1)A A1(2)A A2(3)AB(1),+(4)B(3)，(2)，_T14 AB，AB A(归谬法，记为+)(1)

25、AB A1(2)AB A2(3)A H1(_的假设)(4)A(3)，_(5)B(1)，(4)，_(6)B(2)，(4)，_(7)BB(5)，(6)，+(8)A(3)(7)，_（消去H1）,2023年5月9日星期二,49,NP系统中的语法(语形)推出关系,T15(a)AB BA(假言易位)T15(b)BA AB 只证T5(a)：(1)AB A(2)B H1（+的假设）(3)A H2(_的假设)(4)A(3)，_(5)B(1)，(4)，_(6)BB(2)，(5)，+(7)A(3)(6)，_（消去H2）(8)BA(2)(7)，+（消去H1）T15(c)ABBAT15(d)ABBA,2023年5月9日

26、星期二,50,NP系统中的语法(语形)推出关系,可证等价关系也称演绎等值关系,如果A B且BA，A和B就具有可证等价关系，记为AB。据T15(a)和T15(b)，有如下可证等价关系：ABBA。可证等价置换规则(记为RP)：如果AB，则在A出现的公式C中(即A是C的子公式)，可以用B代替A，在B出现的公式C中(即B是C的子公式)，可以用A代替B。,2023年5月9日星期二,51,NP系统中的语法(语形)推出关系,T16 AB，BA(否定后件,记为M.T.)(1)AB A1(2)B A2(3)BA(1)，RP(4)A(2)，(3)，_T17 AB，AC，BC C(二难推理,记为D.C.)(1)AB

27、 A1(2)AC A2(3)BC A3(4)C H1（_的假设）(5)A(2)，(4)，MT(6)B(1)，(5)，_(7)C(3)，(6)，_(8)CC(4)，(7)，+(9)C(4)(8)，_（消去H1）,2023年5月9日星期二,52,NP系统中的语法(语形)推出关系,T18(a)(AB)A B(记为DeM.)T18(b)(AB)A B(记为DeM.)T19(a)(AB)AT19(b)(AB)BT20(a)A(AB)T20(b)B(AB),2023年5月9日星期二,53,NP系统中的语法(语形)推出关系,T18(a)(AB)A B的证明先证(AB)AB:(1)(AB)A(2)(AB)H1

28、(_的假设)(3)A H2(_的假设)(4)AB(3)，+(5)(AB)(AB)(2),(4),+(6)A(3)(5),_(消去H2)(7)B H3(_的假设)(8)AB(7)，+(9)(AB)(AB)(2)，(8)，+(10)B(7)(9)，_(消去H3)(11)AB(6)，(10),+(12)(AB)(AB)(1)，(11),+(13)AB(2)(12)，_(消去H1),2023年5月9日星期二,54,NP系统中的语法(语形)推出关系,T18(a)(AB)A B的证明再证AB(AB)：(1)AB A(2)(AB)H(_的假设)(3)AB(2)，_(4)A(3)，_(5)B(3)，_(6)A

29、(4)，+(7)B(1),(6),_(8)BB(5),(7),+(9)(AB)(2)(8),_(消去H),2023年5月9日星期二,55,NP系统中的语法(语形)推出关系,交换律T21(a)ABBAT21(b)ABBA结合律T22(a)A(BC)(AB)CT22(b)A(BC)(AB)C分配律T23(a)A(BC)(AB)(AC)T23(b)A(BC)(AB)(AC),2023年5月9日星期二,56,NP系统中的语法(语形)推出关系,T21(b)ABBA的证明先证AB BA(1)AB A(2)A H1(+的假设)(3)BA(2)，+(4)ABA(2)(3)，+（消去H1）(5)B H2(+的假

30、设)(6)BA(5)，+(7)BBA(5)(6)，+（消去H2）(8)BA(1)，(4)，(7)，D.C.同理，可证BAAB。,2023年5月9日星期二,57,NP系统中的语法(语形)推出关系,T24(a)AB(AB)T24(b)(B)ABT25(a)ABAB(蕴析律)T25(b)ABAT26(a)(AB)AT26(b)A(A)T27(a)A(A)T27(b)A(A)T28(b)AB,AC,BCA(二难推理)T28(c)AC，BD，ABBDT28(d)AC，BD，CDAB,2023年5月9日星期二,58,NP系统中的语法(语形)推出关系,T29(a)ABCACB(反三段论)T29(b)ABCB

31、CAT30 ABC A(BC)(条件输出)T31 A(BC)ABC(条件输入)T32 A(BC)B(AC)(条件互易)T33 A(BC)(AB)(AC)T34 A(AB)AB(条件融合)T35(a)AB ACBC(前件附加)T35(b)AB ACBCT35(c)AB(CA)(CB)T36（AB）C BC,2023年5月9日星期二,59,NP系统中的语法(语形)推出关系,T37 AB，BA AB(+)T38(a)AB AB(_)T38(b)AB BAT39 AC,BC ABC(前件合取)T40 AB,AC ABC(后件合取)T41 ABC(AC)(BC)T42 ABC(AC)(BC)T43 AB

32、C(AB)(AC)T44 ABC(AB)(AC),2023年5月9日星期二,60,NP系统中的语法(语形)推出关系,应用实例(一)如果不换8号上场（p），或者换12号上场(q)，甲队的形势不会好转(r)。教练没有换8号上场，也没有换12号上场。所以，甲队的形势不会好转。首先，将前提和结论形式化：A1：(pq)r A2：pq B：r(1)(pq)r A1(2)pq A2(3)(pq)(2)，DeM.(4)r(1)，(3)，_,2023年5月9日星期二,61,NP系统中的语法(语形)推出关系,应用实例(二)如果线段L有存在无穷多个点，那么，如果这些点有长度，则线段L将无穷长，而且，如果这些点都没有

33、长度,则线段L也不会有长度。但是，一条线段既不会无穷长,也不会没有长度。所以L上不会有无穷多个点。前题和结论符号化：A1：p(qr)(qs)A2：rsB：p,2023年5月9日星期二,62,(1)p(qr)(qs)A1(2)rs A2(3)p H（_的假设)(4)p(3),_(5)(qr)(qs)(1)，(4)，_(6)qr(5),_(7)qs(5),_(8)r(2),_(9)s(2),_(10)q(6),(8),M.T.(11)q(7),(9),M.T.(12)qq(10),(11),+(13)p(3)(12)，_,(消去H),2023年5月9日星期二,63,NP系统中的语法(语形)推出关系

34、,应用实例(三)如果货币供应量保持现状，而货币需求量增加，则银行利率就会上升。如果货币需求量增加导致银行利率上升，则在银行存款更被看好。主管部门已宣布货币供应总是保持不变。因此，在银行存款更被看好。A1：pqrA2：(qr)sA3：pB：s,2023年5月9日星期二,64,NP系统中的语法(语形)推出关系,应用实例(三)方法一：（1）pqr A1（2）（qr）s A2（3）p A3(4)q H1（+的假设)(5)pq(3)，(4)，+(6)r(1)，(5)，_(7)qr(4)(6)，+(消去H1)(8)s(2)，(7)，_,2023年5月9日星期二,65,NP系统中的语法(语形)推出关系,应用

35、实例(三)方法二：（1）pqr A1（2）（qr）s A2（3）p A3(4)s H（_的假设)(5)（qr）(2),(4)M.T.(6)qr(5),R.P.(7)r(6)，_(8)(pq)(1),(7)M.T.(9)pq(8),R.P.(10)q(6)，_(11)q(10),+(12)p(9),(11),_(13)pp(3),(12),+(14)s(4)(13),_(消去H),2023年5月9日星期二,66,证明公式集不一致,包括逻辑矛盾的公式(命题)集称为不相容(不一致,不协调)的公式集.判定公式集ABC，(AC)D，BD是否为不一致的公式集.(1)ABC A1(2)CD A2(3)AD

36、A3(4)A(3)，_(5)D(3)，_(6)AB(4)，+(7)C(1)，(6)，_(8)D(2)，(7)，_(9)DD(5)，(8)，+故原公式集是不一致的公式集。,第二章命题逻辑,第四节：命题逻辑有效性的判定,2023年5月9日星期二,68,真值指派和真值赋值,真值指派（简称指派）：给每个命题变元指定一个真值的过程，记为。从直观上讲，真值指派实质上可看成是给构成复合命题的支命题（表示为命题变元）指定真值的过程。(p)=T（(p)=F）就是把p解释为一个真（假）命题。真值赋值（简称赋值）:给定一个真值指派以后，给每个公式确定一个唯一的真值的过程。这个过程称为由该真值指派导出的真值赋值，记为

37、。公式A在赋值下的值，记为(A)。真值指派导出真值赋值，实质上可看成由支命题（表示为命题变元）的真值确定复合命题（表示为公式）的真值的过程。,2023年5月9日星期二,69,形式语言L 的基本语义解释,设为任一指派，是由导出的赋值：()对任何命题变元p，(p)=(p)，其中(p)已有定义。()(A)=T当且仅当(A)=F;()(AB)=T当且仅当(A)=T并且(B)=T;()(AB)=T当且仅当(A)=T或者(B)=T;()(AB)=T当且仅当(A)=F或者(B)=T。给定一个真值指派:(p)=T,(q)=F,(r)=T,。根据基本语义解释，可以导出一个真值赋值,以确定由这些命题变元构成的任何

38、公式在下的真值。例如：(p)=F,(pr)=T,(pqr)=T,(prq)=F，。真值条件语义学：上述基本基本语义解释，实质上是以严格的形式陈述了真值表所表示的真值运算或真值函数，陈述了命题变元或子公式与公式的真值对应关系或真值条件联系，因此，我们也把这种对形式语言L 所作的语义解释，称为真值条件语义学。形式语言L 的语义解释，就是根据基本语义解释来确定L 的全体公式的真值。,2023年5月9日星期二,70,重要的语义概念,可满足性：对任何公式A，如果存在赋值,使得(A)=T，则称A是可满足的。如果对任何赋值，都有(A)=F，则称A为不可满足的。协调性：对公式集(=A1,A2,An)中的任一公

39、式Ai(i=1,2,n)，如果存在赋值,使得(Ai)=T，则称公式集是协调的。语义后承：设是一个公式集，B是一个公式，如果对任何赋值都有：如果()=T(即（A1）=T，（A2）=T，（An）=T)，则（B）=T，则称B是的语义后承（或逻辑蕴涵B，能有效地推出B，与B具有语义推出关系），记为：=B。语义等值：如果A=B并且B=A，则称A语义等值于B（或A逻辑等值于B），记为AB。,2023年5月9日星期二,71,基本推导规则的保真性,逻辑的中心任务是从语形方面和语义方面刻画前提和结论之间的推出关系。从语义方面看,任何推导规则的根本作用在于保证从真前提能而且只能得出真结论。+的保真性 1.+:从A

40、，B推出AB(A,BAB)对任何赋值，如果（A）=T,（B）=T，那么，根据基本语义解释()，（AB）=T，因此：A，B=AB。故+能保证从真前提必然得出真结论。类似地，_、_、+、也都具有保真性。,2023年5月9日星期二,72,基本推导规则的保真性,应用举例证明AB，AB(1)假如AB，AB,即存在,使得(AB)=T,(A)=T,但是(B)=F;(2)由(A)=T,得(A)=F，从(B)=F得(B)=T;(3)从(A)=F,(B)=T,得(AB)=T，与假设(AB）=T不矛盾；(4)这就是说，存在：(A)=F，(B)=T，在此赋值下，（AB）=T，（A）=T，但是，（B）=F。所以，AB，

41、AB。,2023年5月9日星期二,73,用真值表检验语义推出关系,例1：判定AB，BA是否有语义推出关系。从真值表可知：(AB)BA是一个永真蕴涵式。这就是说，对任何赋值，都有如果(AB)=T且(B)=T，那么有(A)=T，也就是说有：AB，B=A,判定A1A2AnB是否永真（重言）式，就可以判定A1，A2，An是否逻辑蕴涵B。,2023年5月9日星期二,74,用真值表检验语义推出关系,例2：判定（AB）AB是否有语义推出关系。从真值表可知，（AB）AB不是永真式蕴涵式.存在何赋值：(A)=T，(B)=T使得（AB）=T，(A)=T，但是(B)=F。所以，我们有：（AB）A=B,2023年5月

42、9日星期二,75,可靠性定理,可靠性定理：凡NP系统中的语法推论关系都是语义推论关系。NP系统内的所有语法推论关系原则上都可以由7条基本推导规则生成。根据语义解释的方法，这7条基本推导规则能保证从真前提能而且只能推出真结论。其它语法推出关系原则上都可以由这7条基本推导规则生成，因此，它们也是语义推出关系。可靠性定理的作用：P系统具有可靠性，这意味着当我们把NP系统运用到其它领域的理论研究和日常思维中进行推理或论证时，决不会从真前提推出假结论甚至逻辑矛盾。,2023年5月9日星期二,76,完全性定理,完全性定理：凡NP系统中的语义推出关系都是语法推出关系。NP系统完全性的证明要涉及相容性、可满足

43、性以及极大相容集等概念。证明的主要思路是证明：（1）B当且仅当B不相容；（2）如果=B则B不可满足；因此，只要证明：（3）如果B不可满足，则B不相容，就可以证明：如果=B,则B。完全性定理的作用：凡是关于联结词的从真前提必然得出真结论的推理形式，都包含在NP系统中了，都表现为NP系统的语法推出关系了。,2023年5月9日星期二,77,本章小结,基本内容命题的概念、复合命题的推理规则。自然演绎系统NP,七条基本推导规则。系统NP的语义解释。重难点运用七条基本推导规则进行形式推演。语法推出关系与语义推出关系；可靠性和完全性。,2023年5月9日星期二,78,复合命题,复合命题是由联结词联结若干命题

44、而形成的命题，例如:（1）莱布尼茨既是数学家，又是哲学家。（2）如果明天天气好，我可能去泡北温泉，也可能去登缙云山。构成复合命题的命题，称为复合命题的支命题。支命题可以是简单命题也可以是复合命题。,2023年5月9日星期二,79,简单命题,简单命题是不包含其它命题的命题，例如:（1）所有有教养的人都有礼貌。（2）有的学生通过了这次考试。简单命题的成分：主项、谓项、量项和联项。(从词项逻辑的角度)个体词、谓词、量词和联结词。(从谓词逻辑的角度),2023年5月9日星期二,80,模态命题,模态命题是包含了“必然”、“应当”等模态词的命题，例如:（1）长期不懈的努力必然有收获。（2）任何公民都应当遵

45、纪守法。（3）如果所有人不种田，那么所有人会饿死，这是可能的。,2023年5月9日星期二,81,推出关系的双重刻画,2023年5月9日星期二,82,逻辑系统的可靠性和完全性,如果有A1,A2,An B 当且仅当A1,A2,，An=B(n1)，我们就说这样的形式系统既可靠又完全。这样的逻辑系统能保证从真前提推出真的结论，决不会推出假结论甚至逻辑矛盾。凡是从真前提推出真结论的推出关系都包含在这个逻辑系统中，在系统之外，没有从真前提推出真结论的推出关系。,可靠性：语法推出关系都是语义推出关系。完全性：语义推出关系都是语法推出关系。,2023年5月9日星期二,83,真值表的作用,真值表在命题逻辑中是一

46、种重要的工具，它的作用有：,一、定义作用：(1)定义逻辑联接项的性质，如:、。(2)定义命题的类型，如:重言式（永真式）、矛盾式（永假式）、协调式（有真有假）。,2023年5月9日星期二,84,真值表的作用,二、判定作用：(1)判定命题间的关系，如：pq与(pq)pq与pq pq与pq(2)判定推理是否有效，如：(pq)pq(pq)qp,2023年5月9日星期二,85,真值表的作用,三、总结正确推理形式及其规则：如通过真值表可总结(pq)pq，即 当pq真并且p真时，q必定为真。又如对于(pq)qp，即 当pq真并且q假时，p必假。,2023年5月9日星期二,86,、的运算规律,（）的定义：p

47、q=df(pq)（）的定义：pq=df(pq)（）pq的定义：pqdf(pq)(pq)（）转换为：pqqp pqpq（5）蕴析律：pqpq（6）假言易位律：pqqp pqqp pqqp(7)对的否定：(pq)pq(8)对的否定：(pq)pq(9)对的否定：(pq)(pq)(qp)(pq)pq(pq)pq(pq)pq(pq)(pq)(pq),2023年5月9日星期二,87,形成规则的作用,（1）以递归的方式定义合式公式。（2）提供一种能行、可判定的方法判定任一符号串是不是合式公式。（3）检验合式公式的性质。如:(pq)(p)q)的形成过程是：p，q，(pq)，(p)，(pq)(p)，q，(pq)

48、(p)q)。这个字符串是反复运用形成规则而形成的，因此它是合式公式。,2023年5月9日星期二,88,合式公式的子公式,合式公式的子公式：在生成合式公式的过程中，每一步所生成的公式。A的子公式是A和A；AB 的子公式是A、B和AB；AB 的子公式是A、B和AB；AB 的子公式是A、B和AB。如：p，q，（pq），(p)，(pq)(p)，(pq)(p)q)都是(pq)(p)q)的子公式。主联结词：辖域最大的联结词。(pq)(p)q)的主联结词是。省略括号的约定：(1)公式最外层的括号可以省略。(2)联结词的结合力依下列次序递减：，。如：(pq)(p)q)可简记为(pq)pq。,2023年5月9日

49、星期二,89,基本推导规则的保真性,_的保真性2._：从AB,A推出B；从AB,B推出A（AB,AB；AB,BA）。(1)假设存在赋值，使得(AB)=T，(A)=T,但是(B)=F；(2)根据基本语义解释（），由(A)=T，得(A)=F;(3)由(A)=F和(B)=F,根据基本语义解释（），得(AB)=F；(4)（AB）=F，与假设(AB)=T矛盾；因此，假设不成立，即没有赋值，使得：(AB)=T，(A)=T，但是(B)=F；所以，AB，A=B。同理，AB,B=A。故_能保证从真前提必然得出真结论。,2023年5月9日星期二,90,基本推导规则的保真性,+的保真性3.+：如果，AB,则AB（1

50、）假设，A=B，但是AB，即对任何赋值，只要()=T，(A)=T，那么(B)=T；但是，又存在赋值，使得()=T，并且(AB)=F；（2）由（AB）=F，得（A）=T，并且，(B）=F；（3）这就是说存在赋值,使得()=T，（A）=T，但（B）=F，即，A B，与假设，A=B矛盾；假设不成立，即我们有：如果,A=B，则=AB。故+能保证从真前提必然得出真结论。,2023年5月9日星期二,91,基本推导规则的保真性,_的保真性4._:从AB和A推出B(AB,AB)(1)假设存在赋值，使得(AB)=T，(A)=T,但是(B)=F;(2)根据基本语义解释（），由(A)=T,(B)=F,得(AB)=F