第二章 命题逻辑.ppt

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

2、的鸟都会飞”与“没有鸟不会飞”表达了相同的命题。 此外，同一命题可用不同的民族语言的语句来表达。 再次，同一语句，可以表达不同的命题，如： 小张将书还给小王，因为他要回家了。,任何命题都是通过语句来表达的，但语句和命题并非一一对应：,2020年8月21日星期五,5,命题和判断,一个命题是否能成为判断，与断定者的知识、立场等有关。如：“杜甫是伟大的诗人”能否被断定就与断定者的知识水平有很大关系。 充分假言命题被断定是前后件的关系，而不是支命题。如：“如果物体受到摩擦，那么物体发热”这个命题，我们既没有断定“物体受到摩擦”，也没有断定“物体发热”，我们所断定的只是前件是后件的充分条件。,判断：就是

3、被断定者断定了的命题。 判断的主要特征：有所断定。,2020年8月21日星期五,6,语句(直陈句和反诘句)有内涵也有外延。 语句的内涵即它表达的命题。 语句的外延即真、假这两个真值。 采用这种观点的逻辑理论，称为二值外延逻辑或经典逻辑。 我们所说的命题，一般指这种或者为真，或者为假的抽象的语句。,语句的内涵和外延,语句(直陈句和反诘句)有内涵也有外延。 语句的内涵即它表达的命题。 语句的外延即真、假这两个真值。 采用这种观点的逻辑理论，称为二值外延逻辑或经典逻辑。 逻辑学上所说的命题，一般指这种或者为真或者为假的抽象语句。,2020年8月21日星期五,7,命题的分类,2020年8月21日星期五

4、,8,命题分析的层次,将联结词所联结的命题作为一个完整的单位来看待 研究关于联结词的推理(命题逻辑) 深入到命题内部，把命题分析为主项、谓项、量项和联项 研究关于量项和联项的推理(传统词项逻辑) 深入到命题内部，把命题分析为个体词、谓词、量词及联结词 研究关于量词的推理(现代谓词逻辑) 把命题中包含的模态词分析出来 研究关于模态词的推理(模态逻辑),2020年8月21日星期五,9,推理的种类,2020年8月21日星期五,10,推理是由前提和结论组成的，前提和结论之间的关系称为推出（推论、推理）关系。例如： 小王既有缺点，又有优点，所以，小王有优点。 在推理中，前提是“小王既有缺点，又有优点”，

5、结论是“小王有优点”， “所以”标志前提和结论之间的推出关系。 推理形式：p且q，所以，q。,逻辑学是从两个方面来研究推理的： (1)从前提和结论的真假方面进行 (2)从前提和结论的形式方面进行,推出关系,2020年8月21日星期五,11,自然演绎系统L,自然演绎系统L:由形式语言L 的初始符号、公式的形成规则、定义以及一组变形(推导)规则所组成的。 逻辑语形(语法)学:研究符号与符号关系的逻辑理论。 逻辑语义学:研究符号及其解释的逻辑理论，如:把p、q、r解释为取真假值的命题变元，把、 、解释为真值集上的运算，把pq、pq、pq解释为真值函数的表达式。,2020年8月21日星期五,12,推出

6、关系的双重刻画,小王既有缺点，又有优点，所以，小王有优点。,2020年8月21日星期五,13,逻辑系统的可靠性和完全性,如果有A1,A2,An B 当且仅当A1 ,A2,，An = B(n1) ，我们就说这样的形式系统既可靠又完全。 这样的逻辑系统能保证从真前提推出真的结论，决不会推出假结论甚至逻辑矛盾。 凡是从真前提推出真结论的推出关系都包含在这个逻辑系统中，在系统之外，没有从真前提推出真结论的推出关系。,可靠性：语法推出关系都是语义推出关系。 完全性：语义推出关系都是语法推出关系。,第二章 命题逻辑,第二节 复合命题及其推理,2020年8月21日星期五,15,负命题,(1)并非选修逻辑的学

7、生都是文科生。 (2)这个班的学生不都学英语。 (3)如果它是三角形，则内角和等于180，这个观点不对。 注：负命题的支命题可以是简单命题，也可以是复合命题。 负命题的形式: 并非p（p） 负命题的逻辑性质：负命题的真假与被否定的命题的真假是相反的。,负命题是否定一个命题而形成的复合命题。例如：,2020年8月21日星期五,16,负命题,由于真值集合只有两个元素T,F ，因此，用列表的方式表示真值运算最为方便、直观。这种表称为真值表。 当p在真值集合T，F上取真值后， p 的真值也唯一确定。所以， p是p的函数，表达形式为f(p)= p，这种函数称真值函数。 的真值表如下：,根据这个真值表，也

8、可以给f(p)=p这个一元真值函数下如下定义： p为真当且仅当p为假； p为假当且仅当p为真。,T,F,真值表的作用,2020年8月21日星期五,17,负命题,根据负命题的逻辑性质，可对p再否定得到p，其真值与p相同，真值表如下：,由上真值表知，对任意公式A，有等值关系：A A,负命题的推导规则:,2020年8月21日星期五,18,联言命题,（1）小张歌唱得好并且舞跳得好。 （2）这样建立的逻辑系统既有可靠性，又有完全性。 联言命题的形式：p并且q（pq）。 p称为的左辖域， q称为的右辖域。 pq是二元真值函数： f(p,q)=pq。是在两个真值变元p和q上进行运算的二元运算。,联言命题是由

9、命题联结词“并且”联结支命题而形 成的复合命题，又称合取命题。例如：,2020年8月21日星期五,19,从上表可以得出联言命题的逻辑性质：当p、q同时为真，pq为真；只要p、q其中一个为假，则pq为假。,合取词的真值表,T,F,F,F,由的真值表,可得出运算的规律: （1）的交换律：pqqp （2）的结合律：p(qr)(pq)r （3）的重言（幂等）律：ppp,2020年8月21日星期五,20,合取引入规则（+）：从A和B可推出AB。图示如下： A B AB 合取消去规则（-）：从AB可推出A，从AB可推出B。图示如下： AB AB B A 小张喜爱音乐，小张喜爱体育，所以，小张不但喜爱音乐，

10、也喜爱体育。 根据+作出一个形式正确的推理，推理形式为：p,q pq 小张既有优点，也有缺点，所以，小张是有优点的。 根据_作出一个形式正确的推理，推理形式为：pq p。,联言命题的推导规则,2020年8月21日星期五,21,选言命题,(1)李明或者是诗人，或者是小说家。 (2)要么武松打死老虎，要么老虎吃掉武松。 选言命题的种类： 一、相容的选言命题 二、不相容的选言命题,选言命题用“或者”、“要么”等命题联结词 联结支命题而形成的复合命题，例如：,2020年8月21日星期五,22,一、相容选言命题及其推理,(1)小王或者是班干部，或者是学生会干部(二者可以得兼)。 (2)这份统计材料，或者

11、是原始材料有错误，或者是计算有错误，或者两种情况都存在。 相容选言命题的形式：p或者q(pq) 相容选言命题逻辑特征： 相容选言命题为真，它的选言支至少有一个为真，反过来讲，选言命题至少有一个选言支为真，则选言命题为真。,相容选言命题又称弱析取命题，是用“或者”联结支命题而形成的选言命题，例如：,2020年8月21日星期五,23,一、相容选言命题及其推理,的真值表 的运算规律,(1)的交换律：pq qp， (2)的结合律：p(qr) (pq)r, (3)的重言律：pp p。,T,F,T,T,2020年8月21日星期五,24,一、相容选言命题及其推理,和的混合运算规律,(1) 对的分配律: p(

12、qr) (pq)(pr)。 (2) 对的分配律： p(qr) (pq)(pr)。 (3)吸收律： p(pq) p； p(pq) p。 (4)德摩根律： (pq) pq； (pq) pq。,2020年8月21日星期五,25,一、相容选言命题及其推理,用真值表检验德摩根律： 从上真值表，可得：(pq) pq 应用德摩根律的实例: 并非这件衣服物美(而且)价廉这件衣服或者物不美，或者价不廉。 并非小李或者喜欢音乐，或者喜欢体育小李既不喜欢音乐，也不喜欢体育。,2020年8月21日星期五,26,一、相容选言命题及其推理,析取消去规则( ) 从AB和A可推出B；从AB和B可推出A。 AB AB B A

13、A B 析取消去规则应用实例： 或者李某是嫌疑犯，或者王某是嫌疑犯(或者二者都是)；李某不是嫌疑犯；所以，王某是嫌疑犯。 其推理形式为： pq, p q 肯定一部分选言支，不能否定另一部分选言支。下述推理形式均错误： AB ,A B； AB ，B A,规则：否定一部分选言支，就要肯定其余的选言支。,2020年8月21日星期五,27,一、相容选言命题及其推理,析取引入规则(记为 )： 析取引入规则(记为 )：从A可推出AB；从B可推出AB。 A B AB AB,2020年8月21日星期五,28,二、不相容选言命题及其推理,(1)鱼，我所欲也，熊掌，亦我所欲也，二者不可得兼。 (2)要么选老王当村

14、长，要么选小李当村长。,不相容选言命题是用“要么”联结两个支命题构成的选言命题，例如：,2020年8月21日星期五,29,二、不相容选言命题及其推理,F,T,T,F,2020年8月21日星期五,30,二、不相容选言命题及其推理,2020年8月21日星期五,31,假言命题,（1）如果寒潮到来，那么气温就会下降。 （2）只有你去，我才放心。 （3）人不犯我，我不犯人，人若犯我，我必犯人。 由“如果”、“只有”引出的支命题称为前件 ，由“那么”、“才”引出的支命题称为后件。 假言命题的种类 一、充分条件假言命题 二、必要条件假言命题 三、充分必要条件假言命题,假言命题是由“如果，那么”、“只有，才”

15、、“当且仅当”等联结词联结两个支命题而形成的复合命题，例如：,2020年8月21日星期五,32,假言命题的种类,一、充分条件假言命题 (1)只要你不断地坚持锻炼，你的身体就会康复。 (2)假如语言能创造财富，那么，夸夸其谈的人就会成为世界上最富有的人。 充分条件假言命题的形式：如果p，那么q (pq) 在蕴涵式pq中，p称为的前件(左辖域)，q称为的后件(右辖域)。,充分条件假言命题亦称条件命题或者实质蕴涵命题,是用“如果，那么”等联结词联结前、后件形成的假言命题，例如：,2020年8月21日星期五,33,假言命题的种类,的真值表 充分条件假言命题的逻辑性质是：除了前件为真而后件为假时充分条件

16、假言命题是假的之外,其它情况下, 充分条件假言命题都是真的。,T,T,T,F,2020年8月21日星期五,34,假言命题的种类,二、必要条件假言命题 (1)只有由细菌引起的疾病，才能用抗生素治疗。 (2)我不去，除非你去。 必要条件假言命题的形式：只有p,才q(pq),用“只有，才”联结前、后件形成的假言命题，例如：,在蕴涵式pq中，p称为的前件(左辖域)，q称为的后件(右辖域)。,2020年8月21日星期五,35,假言命题的种类,的真值表 必要条件假言命题的逻辑性质是：除了前件为假而后件为真时充分条件假言命题是假的之外,其它情况下, 充分条件假言命题都是真的。,2020年8月21日星期五,3

17、6,假言命题的种类,三、充分必要条件假言命题 (1)a和b平行,当且仅当它们的同位角相等。 (2)人不犯我，我不犯人；人若犯我，我必犯人。 充要条件假言命题的形式：p当且仅当q(pq) 在充要条件式pq中 ，称p为的前件(左辖域)，称q为 的后件(右辖域)。,充分必要条件假言命题又称双条件命题，简称充要条件假言命题，是用“当且仅当”作为联结词的命题，例如：,2020年8月21日星期五,37,假言命题的种类,的真值表 的逻辑性质： 当p和q的真值相同时，pq的真值为真； 当p和q的真值不相同时，pq的真值为假。,F,F,T,T,2020年8月21日星期五,38,、的运算规律,（）的定义： pq=

18、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),2020年8月21日星期五,39,关于的推理规则,规则：肯定前件就要肯定后件,规则：否定后件就要否定前件,2020年8月21日星期五,40,关于的推理规则的应用,（1）如果甲方付给了定金,乙方就得按时发货

19、。甲方已付给了定金。所以乙方得按时发货。 其推理形式为：p q，p q （2）如果这部电影受观众欢迎，那么买票的人就多。买票的人不多。所以这部电影不受观众欢迎。 其推理形式为：p q, q p,2020年8月21日星期五,41,关于的推理的错误应用,在日常思维中，关于的推理，容易发生的错误是：从AB和B推出A；从AB和 A推出 B。例如 如是小K是持枪杀人凶手，那么他肯定有枪。小K有枪。所以，他是持枪杀人凶手。 如是小K是持枪杀人凶手，那么他肯定有枪。小K不是持枪杀人凶手。所以，他肯定没有枪。,为避免错误，制定了这样的规则： 肯定后件不能肯定前件；否定前件不能否定后件。,2020年8月21日星

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

21、小A是杀人凶手。 只有小A在作案现场，他才是杀人凶手。小A不是杀人凶手，所以，小A不在作案现场。,为避免错误，制定了这样的规则： 肯定前件不能肯定后件；否定后件不能否定前件。,2020年8月21日星期五,45,关于的推理规则,2020年8月21日星期五,46,其他常见的推理,1.假言易位推理： ABBA； ABBA； ABBA 2.二难推理： 简单构成式：AC,BC,AB C 复杂构成式：AC,BD,AB CD 简单破坏式：AB,AC,BC A 复杂破坏式：AC,BD,CDAB 3.假言三段论：AB，BC AC 4.反三段论：(AB)C(AC)B (AB)C(BC)A 5.反证法：AB，AB

22、A 6.归谬法：AB，AB A,第二章 命题逻辑,第三节： 命题逻辑的自然演绎系统NP,2020年8月21日星期五,48,自然演绎系统NP,命题逻辑的自然演绎系统NP是由形式语言L 和一组推导（变形）规则构成的。其中形式语言L 包括初始符号、形成规则和定义。 一、初始符号 (1)甲类符号：p1, p2, p3, ； (2)乙类符号：，； (3)丙类符号：(，)。 这些符号构成的有穷长的序列叫做符号串，例如: p, pq，pq, pq；(pq)r，p(qr)，,构建命题逻辑的形式系统，可以采用公理化方法，也可采用自然演绎的方法。为接近人们日常思维的实践，x现采用自然演绎的方法来构建命题逻辑的一个

23、形式系统NP。,2020年8月21日星期五,49,自然演绎系统NP,二、形成规则 (1)任何单个的命题变元p是合式公式； (2)如果A是合式公式，则A是合式公式； (3)如果A和B是合式公式，则AB、AB、AB是合式公式； 只有（1）-（3）形成的符号串是合式公式。 三、定义：用来表示缩写的，定义两边的符号串可以相互代替。 如：(AB)=df(AB)(BA)。 形式语言L 的全体合式公式记为Form(L )。 形式语言L 是我们的研究对象，叫对象语言。 讨论对象语言的语言叫元语言或语法语言。,2020年8月21日星期五,50,形成规则的作用,（1）以递归的方式定义合式公式。 （2）提供一种能行

24、、可判定的方法判定任一符号串是不是合式公式。 （3）检验合式公式的性质。 如:(pq)(p)q)的形成过程是：p，q，(pq)，(p)，(pq)(p)，q ，(pq)(p)q)。这个字符串是反复运用形成规则而形成的，因此它是合式公式。,2020年8月21日星期五,51,合式公式的子公式,合式公式的子公式：在生成合式公式的过程中，每一步所生成的公式。 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)的子公式。 主联结词：辖域最大的联结词。 (

25、pq)(p)q)的主联结词是。 省略括号的约定： (1)公式最外层的括号可以省略。 (2)联结词的结合力依下列次序递减：，。 如：(pq)(p)q)可简记为(pq)pq。,2020年8月21日星期五,52,NP系统的推导规则,1.合取引入规则(记为+)： 从A和B推出AB； 2.合取消去规则(记为_): 从AB推出A；从AB推出B； 3.析取引入规则(记为+)： 从A推出AB；从B推出AB； 4.析取消去规则(记为_): 从AB和A推出B；从AB和B推出A； 5.蕴涵引入规则(记为+)： 如果从公式集和A推出B，则从推出AB； 6.蕴涵消去规则(记为_)： 从AB和A推出B； 7.否定消去规则

26、(记为_)： 如果从和A推出BB，则从推出A。,又称条件证明规则或演绎定理，是把从推出AB的推理转化为从和临时的假设A推出B的推理。(即移出律),又称间接证明或反证法，是把由推出A的推理转化为由和临时的假设A推出BB的推理。,2020年8月21日星期五,53,有前提的形式推演,一个有穷的公式序列B1,B2,，Bm是从前提集(不是空集)到结论B的有前提的形式推演，如果每一个公式Bi(1im)满足以下条件之一： (1)Bi(即Bi是前提集中的一个公式)； (2)Bi是一个据+或-临时引入的假设； (3)Bi是该序列中在前的若干公式应用NP系统的推导规则得到的公式； (4)B=Bm。 则我们称和B具

27、有语法推出关系，B从中可演绎的，或者说，从可以推出B，记为：NPB。,2020年8月21日星期五,54,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) B A2 B是第2个公式，也是第m个公式(m=2)。,2020年8月21日星期五,55,NP系统中的语法(语形)推出关系,T4 A，B AB T5

28、(a)AB A T5(b)AB B T6(a)A AB T6(b)B AB T7(a)AB, A B T7(b)AB, B A T8 AB, A B,2020年8月21日星期五,56,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)，+ (消去H1),2020年8月21日星期五,57,NP系统中的语法(语形

29、)推出关系,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）,2020年8月21日星期五,58,NP系统中的语法(语形)推出关系,T12 A， BT13，A B 只证T12： (1)A A1 (2) A A2 (3) AB (1),+ (4) B (3)，(2)，_ T14 AB，AB A(归谬法，记为

30、+) (1) 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）,2020年8月21日星期五,59,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）

31、(8) BA (2)(7)，+（消去H1） T15(c) ABBA T15(d) ABBA,2020年8月21日星期五,60,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。,2020年8月21日星期五,61,NP系统中的语法(语形)推出关系,T16 AB，BA (否定后件,记为M.T.) (1) AB

32、A1 (2) B A2 (3) BA (1)，RP (4) A (2)，(3)，_ T17 AB，AC，BC C(二难推理,记为D.C.) (1) AB 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）,2020年8月21日星期五,62,NP系统中的语法(语形)推出关系,T18(a) (AB)A B(记为DeM.) T18(b) (AB)A B(记为DeM.) T19(a) (AB) A T19(

33、b) (AB) B T20(a) A (AB) T20(b) B (AB),2020年8月21日星期五,63,NP系统中的语法(语形)推出关系,T18(a) (AB) A B的证明 先证(AB) AB: (1) (AB) A (2) (AB) H1(_的假设) (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)

34、(AB) (1)，(11), + (13) AB (2)(12)，_(消去H1),2020年8月21日星期五,64,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 (4)，+ (7) B (1),(6),_ (8)BB (5),(7),+ (9)(AB) (2)(8),_(消去H),2020年8月21日星期五,65,NP系统中的语法(语形)推出关系,交换律 T21(a) ABBA T21(b) ABBA 结合律

35、T22(a) A(BC)(AB)C T22(b) A(BC)(AB)C 分配律 T23(a) A(BC)(AB)(AC) T23(b) A(BC)(AB)(AC),2020年8月21日星期五,66,NP系统中的语法(语形)推出关系,T21(b) ABBA的证明 先证AB BA (1) AB A (2) A H1(+的假设) (3) BA (2)，+ (4) ABA (2)(3)，+（消去H1） (5) B H2(+的假设) (6) BA (5)，+ (7) BBA (5)(6)，+（消去H2） (8) BA (1)，(4)，(7)，D.C. 同理，可证BAAB。,2020年8月21日星期五,6

36、7,NP系统中的语法(语形)推出关系,T24(a) AB(AB) T24(b) (B)AB T25(a) ABAB (蕴析律) T25(b) ABA T26(a) (AB)A T26(b) A(A) T27(a) A(A) T27(b) A(A) T28(b) AB,AC,BCA(二难推理) T28(c) AC，BD，ABBD T28(d) AC，BD，CDAB,2020年8月21日星期五,68,NP系统中的语法(语形)推出关系,T29(a) ABCACB(反三段论) T29(b) ABCBCA T30 ABC A(BC)(条件输出) T31 A(BC) ABC(条件输入) T32 A(BC)

37、B(AC)(条件互易) T33 A(BC)(AB)(AC) T34 A(AB)AB (条件融合) T35(a) AB ACBC (前件附加) T35(b) AB ACBC T35(c) AB (CA)(CB) T36 （AB）C BC,2020年8月21日星期五,69,NP系统中的语法(语形)推出关系,T37 AB，BA AB (+) T38(a) AB AB (_) T38(b) AB BA T39 AC,BC ABC (前件合取) T40 AB,AC ABC (后件合取) T41 ABC(AC)(BC) T42 ABC(AC)(BC) T43 ABC(AB)(AC) T44 ABC(AB)

38、(AC) ,2020年8月21日星期五,70,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)，_,2020年8月21日星期五,71,NP系统中的语法(语形)推出关系,应用实例(二) 如果线段L有存在无穷多个点，那么，如果这些点有长度，则线段L将无穷长，而且，如果这些点都没有长度,

39、则线段L也不会有长度。但是，一条线段既不会无穷长,也不会没有长度。所以L上不会有无穷多个点。 前题和结论符号化： A1：p(qr)(qs) A2：rs B：p,2020年8月21日星期五,72,(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)

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

41、qr (4)(6)，+(消去H1) (8)s (2)，(7)，_,2020年8月21日星期五,75,NP系统中的语法(语形)推出关系,应用实例(三) 方法二： （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),2020年8月21日星期

42、五,76,证明公式集不一致,包括逻辑矛盾的公式(命题)集称为不相容(不一致,不协调)的公式集. 判定公式集ABC，(AC)D，BD是否为不一致的公式集. (1)ABC A1 (2)CD A2 (3)AD A3 (4)A (3)，_ (5)D (3)，_ (6)AB (4)，+ (7)C (1)，(6)，_ (8)D (2)，(7)，_ (9)DD (5)，(8)，+ 故原公式集是不一致的公式集。,第二章命题逻辑,第四节： 命题逻辑有效性的判定,2020年8月21日星期五,78,真值指派和真值赋值,真值指派（简称指派）：给每个命题变元指定一个真值的过程，记为。 从直观上讲，真值指派实质上可看成是

43、给构成复合命题的支命题（表示为命题变元）指定真值的过程。 (p)=T（(p)=F）就是把p解释为一个真（假）命题。 真值赋值（简称赋值）:给定一个真值指派以后，给每个公式确定一个唯一的真值的过程。这个过程称为由该真值指派导出的真值赋值，记为。公式A在赋值下的值，记为(A)。 真值指派导出真值赋值，实质上可看成由支命题（表示为命题变元）的真值确定复合命题（表示为公式）的真值的过程。,2020年8月21日星期五,79,形式语言L 的基本语义解释,设为任一指派，是由导出的赋值： ()对任何命题变元p，(p)=(p)，其中(p)已有定义。 ()(A)=T当且仅当(A)=F; ()(AB)=T当且仅当(

44、A)=T并且(B)=T; ()(AB)=T当且仅当(A)=T或者(B)=T; ()(AB)=T当且仅当(A)=F或者(B)=T。 给定一个真值指派:(p)=T,(q)=F,(r)=T,。 根据基本语义解释，可以导出一个真值赋值,以确定由这些命题变元构成的任何公式在下的真值。 例如： (p)=F,(pr)=T,(pqr)=T,(prq)=F，。 真值条件语义学： 上述基本基本语义解释，实质上是以严格的形式陈述了真值表所表示的真值运算或真值函数，陈述了命题变元或子公式与公式的真值对应关系或真值条件联系，因此，我们也把这种对形式语言L 所作的语义解释，称为真值条件语义学。 形式语言L 的语义解释，就

45、是根据基本语义解释来确定L 的全体公式的真值。,2020年8月21日星期五,80,重要的语义概念,可满足性：对任何公式A，如果存在赋值,使得(A)=T，则称A是可满足的。 如果对任何赋值，都有(A)=F，则称A为不可满足的。 协调性：对公式集(=A1,A2,An)中的任一公式Ai(i=1,2,n)，如果存在赋值,使得(Ai)=T，则称公式集是协调的。 语义后承：设是一个公式集，B是一个公式，如果对任何赋值都有：如果()=T(即（A1）=T，（A2）=T，（An）=T)，则（B）=T，则称B是的语义后承 （或逻辑蕴涵B，能有效地推出B，与B具有语义推出关系），记为： =B 。 语义等值：如果A=

46、B并且B=A，则称A语义等值于B（或A逻辑等值于B），记为AB。,2020年8月21日星期五,81,基本推导规则的保真性,逻辑的中心任务是从语形方面和语义方面刻画前提和结论之间的推出关系。从语义方面看,任何推导规则的根本作用在于保证从真前提能而且只能得出真结论。 +的保真性 1.+:从A，B推出AB(A,BAB) 对任何赋值，如果（A）=T, （B）=T， 那么，根据基本语义解释()，（AB）=T， 因此： A，B=AB。 故+能保证从真前提必然得出真结论。,2020年8月21日星期五,82,基本推导规则的保真性,_的保真性 2._：从AB,A推出B；从AB,B推出A（AB,AB； AB,BA

47、）。 (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。 故_能保证从真前提必然得出真结论。,2020年8月21日星期五,83,基本推导规则的保真性,_的保真性 3._:从AB和A推出B(AB,AB) (1)假设存在赋值，使得(AB)=T，(A)=T,但是(B)=F; (2)根据基本语

48、义解释（），由(A)=T,(B)=F,得(AB)=F; (3)(AB)=T而且(AB)=F，矛盾。 (4) 因此，假设不成立，即对任何赋值，如果(AB)=T,并且(A)=T，那么(B)=T，即AB,A=B 故_能保证从真前提必然得出真结论。,2020年8月21日星期五,84,基本推导规则的保真性,+的保真性 4.+：如果，AB,则AB （1）假设，A=B，但是AB，即对任何赋值，只要()=T，(A)=T，那么(B)=T；但是，又存在赋值，使得()=T，并且(AB)=F； （2）由（AB）=F，得（A）=T，并且，(B）=F； （3）这就是说存在赋值,使得()=T，（A）=T，但（B）=F，即，

49、A B，与假设，A=B矛盾；假设不成立，即我们有： 如果,A=B，则=AB。 故+能保证从真前提必然得出真结论。,2020年8月21日星期五,85,基本推导规则的保真性,的保真性 5._：如果，A BB,那么 A. (1)假设，A=BB,即对任何赋值，如果()=T并且(A)=T,那么(BB)=T; (2)但是，(BB)T,因此，或者()T,或者(A)T; (3)由（2）可得：如果()=T,则(A)T，如果(A)T,那么(A)=T； (4)因此，如果()=T,那么(A)=T,即=A。 故_能保证从真前提必然得出真结论。,2020年8月21日星期五,86,基本推导规则的保真性,应用举例 证明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) 这就是