命题演算(1-4节).ppt

数理逻辑MathematicalLogic,2,绪论,“逻辑”一词来源于希腊字oyez(罗各斯，英语logic)音译。原意指思维。逻辑是以思维作为研究对象的，是研究人类思维及其规律的一门科学。,逻辑的发源地、代表人物、代表作古希腊亚里士多德（逻辑之父）其代表著作工具论(十篇)中提出了(形式)逻辑的雏形,形成了逻辑这门古老的科学。古代中国墨子墨经古印度“因明学”正理经,注.亚里士多德(Aristoteles，公元前384-322年):古希腊哲学家.西方三圣之一.另两位是苏格拉底(Socrates，公元前469-399年)和柏拉图(Platon，公元前427-347年).墨子(公元前468-376年,一说公元前476-390年,又一说公元前480-400年;鲁国人，有的说是宋国人):春秋末战国初时期的思想家、学者，墨家学派的创始人.,3,逻辑：,形式逻辑：(formallogic)形式逻辑也称为初等逻辑。它研究思维的(逻辑)形式结构和(逻辑)规律，而不管思维的的具体内容。,形式逻辑只管形式，从错误的前提推出错误的结论，在形式上也可以是正确的。毛泽东在延安文艺座谈会上的讲话,绪论,4,绪论,形式逻辑：,演绎逻辑：(deductivelogic)演绎逻辑的任务在于研究如何检验演绎的正确性(即决定一个推理是否是正确地演绎出一个已知规则)以及如何构造出正确的未知(演绎推理)规则。归纳逻辑：(inductivelogic)归纳逻辑的任务在于研究如何測定不充分置信的推理的归纳概率的大小，从而决定该不充分置信推理的归纳强度规则，并且研究如何构造出归纳强度高的推理规则。,5,绪论,辩证逻辑：(dialecticallogic)也称为高等逻辑。它是研究人类的辩证思维及其规律的科学。辩证逻辑结合思维的具体内容来研究思维形式的辩证规律。,形式逻辑和辩证逻辑都是从定性的角度来研究思维规律的。,西方哲学指导思想：西方哲学指导思想形式逻辑一切通过实验找因果关系爱因斯坦在1935给加里福尼亚的朋友舒卫特的信中说：欧洲现代科学技术是伟大的，它之所以伟大，是因为当时它们是在一种指导思想下产生的。这个指导思想是什么呢？是古希腊的哲学，即形式逻辑体系和文艺复兴时代的一切通过实验找它的因果关系的思想。因为有这样的哲学指导思想，所以才产生了近代的科学体系。,6,绪论,数学方法：引进一套符号体系，用以建立一类数学符号语言(形式语言)，以其作为思维的载体，进而建立起逻辑的各种形式系统，从而来研究思维及其规律的方法。数理逻辑是从定量的角度来研究思维规律的。西方公认的数理逻辑创始人是十七世纪德国的莱布尼茨(Leibniz，公元1646-1716年)，他力图建立一种精确的普遍语言，并寻求一种推理演算，以便用来解决论辩的争论问题。数理逻辑在十九世纪兴起，二十世纪得到飞跃式的发展。,数理逻辑：(mathematicallogic)数理逻辑也称为符号逻辑。它是用数学的方法来研究形式逻辑(主要是演绎逻辑)，即研究演绎推理的规律的科学。数理逻辑是现代的形式逻辑。,7,绪论,数理逻辑：,经典逻辑：,现代逻辑：,8,第一章命题演算1.命题联结词命题函数2.命题的形式化真值联结词真值函项3.初始符号形成规则合式公式指派真值表4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理5.联结词归约范式(NF)6.命题演算的形式推理,9,1.命题联结词命题函数,每给出一个命题,就要求你作出一次判断。所以,在形式逻辑中,命题有时也称为判断。命题的真假取决于它是否如实地反映事物的真实情况,是否与事物的真实情况相符。如实反映事物的真实情况,与事物的真实情况相符,就是真命题;否则,就是假命题。真命题用t(true)来表示;假命题用f(false)来表示;t和f共称为命题的真值(truth)。,命题是命题逻辑推理的基本要素！,1.命题(proposition)：命题是可辨真假的陈述语句。,10,2.简单命题(simpleproposition)：简单命题是不包含其它命题作为组成部分的命题。,1.命题联结词命题函数,3.复合命题(compoundproposition)：复合命题是包含其它命题作为组成部分，由其它命题组成的命题。4.支命题(branchproposition)：支命题是组成复合命题的各个命题。支命题可以是简单命题，也可以是复合命题。,简单命题是命题逻辑推理的最小单位！,11,5.联结词(connective)：将支命题联结起来构成复合命题的词项称为联结词。一个复合命题由支命题以及联结它们的联结词构成。复合命题的真假依赖于构成它的各支命题的真假、以及所用的联结词的种类。,1.命题联结词命题函数,6.命题函数(propositionalfunction)：含有未知因素的具有命题形式的陈述语句。命题函数不是命题，不能确定真假。,12,例1.(1)中国人民是伟大的。(2)雪是蓝的。(3)1+101=110。(4)全体立正!(5)明天是否开大会?(6)天气多好啊!(7)我正在说谎。(8)我学英语,或者我学日语。(9)如果天气好,那么我去散步。,1.命题联结词命题函数,例2.(1)别的星球上有类人的高级生命。(2)在的小数展式中，数串12345将出现偶数次。,13,例5.(1)a能被2整除。(2)a2能被2整除。(3)a是完全平方数。(4)a的素数分解式中各指数均是偶数。(5)x大于3。,1.命题联结词命题函数,例4.(1)并非所有的人都是好人。(2)2是偶数并且是最小的素数。(3)未来战争是常规战争，或者是核战争。(4)如果a2能被2整除，则a能被2整除。(5)a是完全平方数当且仅当它的素数分解式中各指数均是偶数。,例3.(1)北京是中华人民共和国的首都。(2)3是素数。(3)大于3。,14,7.命题函数转化为命题的方法：,1.命题联结词命题函数,例6.(1)大于3。(2)如果a2能被2整除，则a能被2整除。(3)a是完全平方数当且仅当它的素数分解式中各指数均是偶数。(4)对于所有实数x，x大于3。(5)存在着实数x，x大于3。,15,2.命题的形式化真值联结词真值函项,1.真值联结词(truthconnective)：在命题逻辑中所使用的、意义比较严格的联结词称为真值联结词或命题联结词。,2.命题的形式化：使用数学符号来表示一个命题中的简单命题和真值联结词，从而将命题表示成一个公式(符号串)的过程，称作命题的形式化(或命题的符号化)。一般的，用小写的英文字母p,q,r,等表示简单命题。,16,(1)“否定(negation)”(负判断)表示“否定”的符号是:(读作:非、并非,not)(或,N)符号称为否定联结词,简称否定词。对于一个命题p,p的否定命题“非p”表示为:p。p称为p的否定式。p为真当且仅当p为假。“否定”的真值表见表1:常见的否定词还有:不;不是;没;没有;。,2.命题的形式化真值联结词真值函项,表1,例1.并非所有的人都是好人。解.令:p所有的人都是好人形式化:p。,17,2.命题的形式化真值联结词真值函项,(2)“合取(conjunct)”(联言判断)表示“合取”的符号是:(读作:且、并且,and)(或却；。,表2,18,(3)“析取(disjunct)”(选言判断)表示“析取”的符号是:(读作:或、或者,or)(或+,D)符号称为析取联结词,简称析取词。对于两个命题p和q,p和q的析取命题“p或q”表示为:pq。pq称为p和q的析取式。p、q称为该析取式的析取项。pq为真当且仅当p、q至少之一为真。“析取”的真值表见表3:常见的析取词还有:是,还是;也许,也许;可能,可能;。,2.命题的形式化真值联结词真值函项,表3,19,例2.2是偶数并且是最小的素数。解.令:p2是偶数q2是最小的素数形式化:pq。,例3.未来战争是常规战争，或者是核战争。解.令:p未来战争是常规战争q未来战争是核战争形式化:pq。,2.命题的形式化真值联结词真值函项,20,(4)“蕴涵(material)implication)”(假言判断)（又称为“蕴含”）表示“蕴涵”的符号是:(读作:如果,则,if-then)(或,I)符号称为蕴涵联结词,简称蕴涵词。对于两个命题p和q,p和q的蕴涵命题“如果p,则q”表示为:pq。pq称为p和q的蕴涵式。p称为该蕴涵式的前件(antecedent);q称为该蕴涵式的后件(consequent)。pq为真当且仅当q真或p假。“蕴涵”的真值表见表4:常见的蕴涵词还有:a.充分条件:如果,那么(那末);若,则;倘若,则;假使,就;只要,就;当,便;推出;由于,从推演出;推得;因为,所以;。b.必要条件:只有,才;必须,不;必须,才;没有,就没有;不,就不;除非,不;除非,才;才;。,2.命题的形式化真值联结词真值函项,表4,21,2.命题的形式化真值联结词真值函项,例4.如果a2能被2整除，则a能被2整除。解.令:pa2能被2整除qa能被2整除形式化:pq。,注.“只有,才”。例如.人民,只有人民,才是创造世界历史的动力。日常语言与数理逻辑在蕴涵词上的区别之一:日常语言只注重条件(蕴涵前件)成立(为真)时,蕴涵命题的真假;而不关心条件不成立(为假)时,蕴涵命题的真假。例如:如果我去图书馆,我就帮你还了这本书。,例5.只有充分发扬民主，才能充分调动人民群众的积极性。解.令:p我们充分发扬民主q我们充分调动人民群众的积极性形式化:qp。,22,2.命题的形式化真值联结词真值函项,例如.对称性:xRyyRx;反对称性:xRyyRxx=y;传递性:xRyyRzxRz日常语言与数理逻辑在蕴涵词上的区别之二:日常语言只关心条件(蕴涵前件)与结论(蕴涵后件)间有某种内在联系(遗传性(entailment或genetic)的蕴涵命题的真假;而不讨论条件与结论间没有任何内在联系(无遗传性)的蕴涵命题的真假。例如.如果雪是黑的,则牛有三条腿。如果1+1=3,则太阳从西边升起。如果细胞能进行分裂,则飞机能飞。这正是将此种真值联结词称为“形式蕴涵”或“实质蕴涵”的原因。即只与形式有关,而与内容无关。西方人认为内容是表象,形式(结构)是本质(实质)。,蕴涵怪论,23,2.命题的形式化真值联结词真值函项,(5)“等价(material)equivalence)”(充要条件假言判断)（又称为“等值”。）表示“等价”的符号是:(读作:当且仅当,iffifandonlyif)(或,E)符号称为等价联结词,简称等价词。对于两个命题p和q,p和q的等价命题“p当且仅当q”表示为:pq。pq称为p和q的等价式。p称为该等价式的左端；q称为该等价式的右端。pq为真当且仅当p与q真值相同。“等价”的真值表见表5:常见的等价词还有:充分必要;除非不,否则;等价于；与等价；。,表5,24,2.命题的形式化真值联结词真值函项,例6.a是完全平方数当且仅当它的素数分解式中各指数均是偶数。解.令:pa是完全平方数qa的素数分解式中各指数均是偶数形式化:pq。,注.日常语言与数理逻辑在等价词上的区别之一:日常语言只注重条件和结论(左右端)至少有一方成立(为真)时的等价命题;而不关心条件和结论都不成立(为假)时的等价命题的真假。例如.地球人能到河外星系当且仅当宇宙飞船能突破光束。,日常语言与数理逻辑在等价词上的区别之二:日常语言只关心条件与结论(左右端)间有某种内在联系(遗传性)的等价命题的真假;而不讨论条件与结论间没有任何内在联系(无遗传性)的等价命题的真假。例如.牛有三条腿当且仅当雪是黑的。太阳从西边升起当且仅当1+1=3。飞机能飞当且仅当细胞能进行分裂。这正是将此种真值联结词称为“形式等价”或“实质等价”的原因。即只与形式有关,而与内容无关。,等价怪论,25,2.命题的形式化真值联结词真值函项,3.形式化举例：例7.(1)如果小张做完了作业并且没有其他事情,他就去踢球或去看电视。(2)小王总是在办公室忙碌，除非他病了或办公室停电。(3)小李没在图书馆看书,他要么找老师答疑去了,要么因身体不舒服先回宿舍去了。解.(1)令:p小张做完了作业q小张有其他事情r小张踢球s小张看电视形式化:(pq)(rs)。,26,2.命题的形式化真值联结词真值函项,(2)令:p小王病了q办公室停电r小王在办公室忙碌形式化:(pq)r。,(3)令:p小李在图书馆看书q小李找老师答疑r小李身体舒服s小李回宿舍形式化:p(q(r)s)。,27,2.命题的形式化真值联结词真值函项,例8.(1)拿破仑(Napoleon)相信“巴拓(Brutus)杀了凯撒(Caesar)”。(2)第一个命题是逻辑上根据第二个命题得出的。,4.真值函项(truth-function)：一个联结词,只要给出自变项们的真值,就能够推断出由此联结词构成的整个复合命题的真值,具有这种特性的联结词称为真值函项算子(truth-functionaloperator)。由真值函项算子构成的复合命题称为真值函项。五大真值联结词:,均是真值函项算子;由它们构成的复合命题都是真值函项。,28,3.初始符号形成规则合式公式指派真值表,1.初始符号(initialsymbol)：命题变项(propositionalvariables)：p,q,r,(不够加下标);真值联结词(truth-connectives)：，(not,and,or,if-then,iff);,2.形成规则(formationrules)：FR1.单独一个命题变项是公式(原子);FR2.如果是公式，则也是公式;FR3.如果,都是公式，则()也是公式;注：这里:=,;原子原子公式。,3.合式公式(Wff-wellformedformula)：有限次应用上述FR1FR3规则所构成的有限符号串称为合式公式(简称公式)。,29,3.初始符号形成规则合式公式指派真值表,注：由于有限符号串称为字(word),故合式公式就是合法的(legal)字;形成规则的三种表示法:a.归纳定义(见2的定义)；b.巴科斯范式(BNF-backusnormalform):Wff:=propositionalvariables|Wff|(WffWff)这里:=,；c.条件-结论式(condition-conclusion):p，这里:=,；课本引入命题常项(propositionalconstants)：T,F(两个特殊的命题)我们的演算系统不引入；空箱理论:形式逻辑数理逻辑(符号化,形式化,结构化,抽象)命题公式(符号化,形式化,结构化,抽象)。,30,3.初始符号形成规则合式公式指派真值表,4.括号省略的原则：(1)最外层括号省略；(2)使用优先级：(高);，(中);，(低)。,5.指派（指派value-assignment)：给公式所涉及到的所有命题变项(原子公式)的每一个指派一个真值的过程称为一个指派。设公式所含的全部命题变项为:p1,p2,pn，则公式称为一个n元命题公式，并记为(p1,p2,pn)。,例1.公式(pq)(r)(pr)。,31,3.初始符号形成规则合式公式指派真值表,由于公式是真值函项,故只要命题变项p1,p2,pn的真值确定,则公式的相应真值也就确定了。给公式的命题变项p1,p2,pn一组确定的真值p1,p2,pn后所得到的序列v=(p1,p2,pn)称为公式关于命题变项组(p1,p2,pn)的一个指派。公式在该指派v下的真值记为(v)或v或更明确的(p1,p2,pn)。,成真指派（成真指派verifyingvalue-assignment):使(v)=t的指派v称为公式的一个成真指派。成假指派（成假指派falsifyingvalue-assignment):使(v)=f的指派v称为公式的一个成假指派。一个公式=(p1,p2,pn)的指派有2n个。,32,3.初始符号形成规则合式公式指派真值表,6.真值表(truth-table)：将一公式在所有指派下形成真值的过程排列起来形成一张表,这张表就称为真值表。,例2.3元命题公式=(pqr)q的真值表。,33,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,1.可满足性(satisfiability)：公式是可满足的当且仅当至少存在着的一个成真指派v。可满足的公式记为Sat。,例1.公式=(pqr)q是可满足的。,2.永假公式不可满足性(unsatisfiability)：公式是不可满足的当且仅当的每一个指派v都是它的成假指派。不可满足的公式记为Unsat或Insat。,例2.公式=pp是永假公式。注.不可满足的公式又称为逻辑谬误(logicalmistake)、矛盾式(contradiction)。,34,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,3.永真公式永真性(validity)：公式是永真公式当且仅当的每一个指派v都是它的成真指派。永真公式记为。,例3.公式=pp是永真公式。注.永真公式又称为逻辑真理(logicaltruth)、重言式(tauology)。,永真公式的证明方法：真值表法:看之列是否全为t，若是则有效；否则不有效。反证法:假设有一成假指派v,则得到矛盾。,35,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,例4.判断并证明公式=(pq)(pr)(qr)r是永真公式。解.真值表法:,=(pq)(pr)(qr)r之列全是t,故有效,即(pq)(pr)(qr)r。,反证法:假设有一指派v=(p,q,r),是公式=(pq)(pr)(qr)r的成假指派,则(v)=f。,注.永假公式的证明方法：真值表法:看之列是否全为f，全为f,不可满足;否则,可满足。反证法:假设有一成真指派v,则得到矛盾。可能性偶然性(contingency)：公式是可能的(或偶然的)当且仅当既不是重言的又不是矛盾的。,36,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,二个简单的结论:(1)公式是永真公式当且仅当公式是永假公式;(2)公式是可能的(偶然的)当且仅当公式和都是可满足的。注.永真公式(重言式)、偶然性、永假公式(矛盾式)三概念将全部命题公式的集合划分为三部分；可满足性=偶然性+永真公式(重言式)；根椐上述简单结论(1)可知，重言式与矛盾式一一对应；也即逻辑真理与逻辑谬误是结伴而生的；有一个逻辑真理，就有一个逻辑谬误；反之亦然。,37,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,4.逻辑蕴涵关系(logicalimplicationrelation)：称公式与公式1,2,n有逻辑蕴涵关系（公式1,2,n逻辑蕴涵公式），记为1,2,n当且仅当对于公式1,2,n和公式的合成变项组的任一指派v,均有：如果v同时是公式1,2,n的成真指派，则v也是公式的成真指派。即如果1(v)=t,2(v)=t,n(v)=t，则(v)=t。其中：公式1,2,n称为前提(premise)，公式称为结论(conclusion)。,注.逻辑蕴涵关系又称为逻辑推论关系,简称逻辑推论(logicalinference)，也称为逻辑推理关系,简称逻辑推理(logicalreasoning)。逻辑蕴涵关系1,2,n按关系的记法应是(1,2,n,)；这说明逻辑蕴涵关系是一n+1元关系。,38,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,特殊情况，前提公式只有一个(n=1),即当且仅当对于公式和公式的合成变项组的任一指派v，均有：如果v是公式的成真指派，则v也是公式的成真指派。即如果(v)=t，则(v)=t。逻辑蕴涵可看作是有条件(即(v)=t)的永真性。在表达逻辑蕴涵时，连接的左右两边都是公式。符号表示逻辑蕴涵关系，符号表示逻辑等价关系。,使(v)=t的指派的集合,全部指派的集合,在此集合上公式永真,定理1.以下三条等价(1)(逻辑蕴涵)(2)(是永真公式)(3)Insat()(是永假公式、是不可满足的),39,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,证.(1)(2):对(,的合成变项组的)任一指派v,若(v)=t,则根据,由逻辑蕴涵的定义,有(v)=t，从而按的真值表，可知()(v)=t。若(v)=f,则无论(v)=t还是f，按的真值表，均有()(v)=t。综合这两种情况，总有()(v)=t，按永真公式的定义，有。,(2)(3):对任一指派v,若(v)=t,则根据,由永真性的定义,有()(v)=t，从而按的真值表，可知(v)=t,于是按的真值表，可知()(v)=f,最后按的真值表，可知()(v)=f。若(v)=f,则无论()(v)=t还是f，按的真值表，均有()(v)=f。综合这两种情况，总有()(v)=f，按永假公式的定义，有Insat()。,40,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,注.定理1中(1)(2)（当且仅当）表明了永真性与逻辑蕴涵间的转换关系。也表明了逻辑蕴涵与形式蕴涵间的转换关系，即逻辑蕴涵是永真的形式蕴涵。定理1中(1)(3)表明了逻辑蕴涵的结论的反面与其前提是不可能相容的。而这点正是人工智能中证明逻辑蕴涵的理论根据。其思想是:为了证明逻辑蕴涵,转而去证是永假公式。而证是永假公式,人工智能有强有力的工具鲁滨逊(Robbins)1965年提出的消解原理(也称归结法)。,(3)(1):对任一指派v,若(v)=t,则根据Insat(),由永假公式的定义,有()(v)=f，从而按的真值表，可知必有()(v)=f,于是按的真值表，可知(v)=t,所以按逻辑蕴涵的定义，有。,41,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,逻辑蕴涵的证明方法：真值表法:看之列是否之列?若,逻辑蕴涵;否则,不逻辑蕴涵。(列是对应元素的;并且ff,ft,tt。)分析指派法:(a)构造法：对任一指派v,证明如果(v)=t，则(v)=t;(b)逆否证法：对任一指派v,证明如果(v)=f，则(v)=f;(c)无义证法：对任一指派v,证明(v)=f;(d)平凡证法：对任一指派v,证明(v)=t。,42,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,例5.判断并证明逻辑蕴涵(pq)(qr)pr。解.令=(pq)(qr)，=pr。逻辑蕴涵的真值表如下表2所示:,表2,观察可知之列之列，故逻辑蕴涵，即(pq)(qr)pr。,43,例6.证明逻辑蕴涵q(pq)p。证.(a)令=q(pq)，=p。对任一指派v=(p,q)，若(v)=t，则q(pq)=t。于是按的真值表，必有q=t，且pq=t，又按的真值表，可得q=f，从而按的真值表，必有p=f，再按的真值表，可得p=t，即(v)=t。故根椐构造法，可知逻辑蕴涵，即q(pq)p。,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,44,(b)令=q(pq)，=p。对任一指派v=(p，q)，若(v)=f，则p=f，按的真值表，可得p=t。于是(1)若q=t，则按的真值表，有q=f，无论pq=t还是f,按的真值表,都有q(pq)=f；(2)若q=f，则由已证得的p=t，按的真值表，可得pq=f，无论q=t还是f，按的真值表,都有q(pq)=f。综合(1)，(2)，总有q(pq)=f，即(v)=f。故根椐逆否证法，可知逻辑蕴涵，即q(pq)p。,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,45,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,例7.证明逻辑蕴涵ppq。证.采用无义证法:令=pp，=q。显然，是永假公式。故按永假公式的定义，对任一赋值v，总有(v)=f;根椐无义证法，可知逻辑蕴涵，即ppq。,例8.证明逻辑蕴涵p(qq)q。证.采用平凡证法:令=p，=(qq)q。易证是永真公式。故按永真公式的定义，对任一指派v，总有(v)=t;根椐无义证法，可知逻辑蕴涵，即p(qq)q。,46,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,定理2.以下五条等价(1)1,2,n-1,n;(2)1(2(n-1(n);(3)12n-1n;(4)12n-1n;(5)Insat(12n-1n)。证.(3)(4)(5):令:=12n-1n，则根据定理1,可知(3)(4)(5)。,47,(1)(2):对任一指派v,若1(v)=t,2(v)=t,n-1(v)=t,n(v)=t,根据1,2,n-1,n，由逻辑蕴涵的定义,有(v)=t,于是由n(v)=t,按的真值表,可知(n)(v)=t，再由n-1(v)=t,按的真值表,可知(n-1(n)(v)=t,，再由2(v)=t,按的真值表，可知(2(n-1(n)(v)=t，最后再1(v)=t,按的真值表，可知(1(2(n-1(n)(v)=t。,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,48,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,否则，必存在着k(1kn)，使1(v)=t,2(v)=t,k-1(v)=t,k(v)=f，则无论(k+1(n-1(n)(v)=t还是f，由k(v)=f,按的真值表，都有(k(k+1(n-1(n)(v)=t,从而再由k-1(v)=t,按的真值表，可知(k-1(k(k+1(n-1(n)(v)=t,再由2(v)=t,按的真值表，可知(2(n-1(n)(v)=t,最后再由1(v)=t,按的真值表，可知(1(2(n-1(n)(v)=t。综合,这两种情况，总有(1(2(n-1(n)(v)=t，,49,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,按永真公式的定义，有1(2(n-1(n)。(2)(3):对任一指派v,若(12n-1n)(v)=t，则按的真值表，可知1(v)=t，2(v)=t，n-1(v)=t，n(v)=t，则根据1(2(n-1(n)，由永真公式的定义，可知(1(2(n-1(n)(v)=t,于是由1(v)=t,按的真值表,可知(2(n-1(n)(v)=t,再由2(v)=t,按的真值表,可知(3(n-1(n)(v)=t，,50,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,再由n-2(v)=t,按的真值表，可知(n-1(n)(v)=t,再由n-1(v)=t,按的真值表，可知(n)(v)=t,最后再由n(v)=t,按的真值表，可知(v)=t。于是由的真值表,可知(12n-1n)(v)=t。否则,(12n-1n)(v)=f,则无论(v)=t还是f,按的真值表，都有(12n-1n)(v)=t。综合,这两种情况，总有(12n-1n)(v)=t，所以按永真公式的定义，有12n-1n。,51,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,(3)(1):对任一指派v,若1(v)=t,2(v)=t,n-1(v)=t,n(v)=t,则按的真值表,可知(12n-1n)(v)=t,于是根据12n-1n,由永真公式的定义,可知(12n-1n)(v)=t,从而按的真值表,可知(v)=t。所以,由逻辑蕴涵的定义,可得1,2,n-1,n。,52,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,定理3.(基本逻辑蕴涵式)(1)pqp,pqq(合取分析式)(2)ppq,qpq(析取构成式)(3)p,pqq(充足理由律，假言推理、肯定(分离)前件式)(4)q,pqp(假言推理、否定(拒绝)后件式)(5)q,pqp(换质位律、否定(拒绝)后件式)(6)p,pqq(相容选言推理、否定肯定式)(7)pq,qrpr(假言)三段论原则)(8)pq,pr,qrr(二难推理、简单构成式)(9)pp(排中律)(10)(pp)(无矛盾律)(11)pp(或pp)(同一律),53,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,注.定理3的(11)(10)(9)(3)反映的是形式逻辑的命题逻辑中著名的四大推理规律:同一律,无矛盾律,排中律,充足理由律。同一律:在同一思维的过程中,每一思想的自身都具有同一性。其形式表示为:pp。无矛盾律:在同一思维的过程中,反映对象的同一方面的两个互相矛盾、互相反对的思想不能都是真的，必有一个是假的。其形式表示为:(pp)。排中律:在同一思维的过程中,两个互相矛盾的思想不能都是假的，必有一个是真的。其形式表示为:pp。充足理由律:在思维过程中,任何一个正确的真实的思想总有它的充足理由。其形式表示为:p(pq)q。（p,pqq）,54,注.逻辑等价关系按关系的记法应是(,)；这说明逻辑等价关系是一二元关系。如果，则且,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,5.逻辑等价关系(logicalequivalencerelation)：称公式与公式有逻辑等价关系(公式逻辑等价公式)，记为当且仅当对于公式和公式的合成变项组的任一指派v，均有：(v)=(v)。其中：公式称为左边，公式称为右边。,逻辑等价的证明方法：真值表法:看之列是否=之列，若=,逻辑等价;否则不逻辑等价。,55,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,例9.判断并证明逻辑等价(pq)rp(qr)。解.采用真值表法。令=(pq)r，=p(qr)。逻辑等价的真值表如下表3所示:观察可知之列=之列，故逻辑等价，即(pq)rp(qr)。,表3,56,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,例10.判断并证明逻辑等价p(qr)(pq)(pr)。解.采用真值表法。令=p(qr)，=(pq)(pr)。逻辑等价的真值表如下表4所示:观察可知之列=之列，故逻辑等价，即(pq)r(pq)(pr)。,表4,57,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,例11.判断并证明逻辑等价pqqp。解.采用真值表法。令=pq，=qp。逻辑等价的真值表如表5所示:观察可知之列=之列，故逻辑等价，即pqqp。,表5,58,定理4.当且仅当(逻辑等价与形式等价间的转换关系)证.先证:对公式、的合成变项组的任一指派v,若(v)=t,则根据,由逻辑等价的定义,有(v)=(v),于是(v)=t,从而按的真值表,可知()(v)=t。若(v)=f,则根据,由逻辑等价的定义,有(v)=(v),于是(v)=f,从而按的真值表,可知()(v)=t。综合,这两种情况，总有()(v)=t，按永真公式的定义，有。,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,59,次证:对任一指派v,若(v)=t,根据,由永真公式的定义,有()(v)=t,从而按的真值表,可知(v)=t,于是(v)=(v)=t。若(v)=f,根据,由永真公式的定义,有()(v)=t,从而按的真值表,可知(v)=f,于是(v)=(v)=f。综合,这两种情况，总有(v)=(v)，按逻辑等价的定义，有。,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,60,定理5.逻辑等价关系是(全体命题公式集上的)一种等价关系。(1)自反性:;(2)对称性:如果，则;(3)传递性:如果且，则,证.(1)自反性:对任一命题公式，对任一指派v，(v)=(v)(相等=的自反性)推出(逻辑等价的定义)(2)对称性:推出对于公式、的合成变项组的任一指派v，(v)=(v)(逻辑等价定义)推出对任一指派v,(v)=(v)(相等=的对称性)推出(逻辑等价的定义),4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,61,(3)传递性:且推出对于公式、的合成变项组的任一指派v,(v)=(v)且(v)=(v)(逻辑等价的定义)推出对任一指派v,(v)=(v)(相等=的传递性)推出(逻辑等价的定义),4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,定理6.(基本逻辑等价式)(1)双重否定律：pp;(2)幂等律：ppp,ppp;(3)结合律：(pq)rp(qr),(pq)rp(qr);,62,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,定理6.(基本逻辑等价式)(4)吸收律：p(pq)p,p(pq)p;(5)交换律：pqqp,pqqp;(6)分配律：p(qr)(pq)(pr),p(qr)(pq)(pr);(7)逆否律：pqqp;(换质位律)(8)deMorgan律：(pq)pq,(pq)pq;(9)归约律：pqpq,pq(pq)(qp);(10)化简律：p(qqr)p,p(qqr)p。,(真值联结词),63,注.定理6中(3)结合律，(5)交换律，(2)幂等律，(4)吸收律说明命题逻辑(,)构成(代数)格。定理6中(3)结合律，(5)交换律，(2)幂等律，(4)吸收律，(6)分配律说明命题逻辑(,)构成分配格。如果引入两个命题常项(propositionalconstant)T(真值恒为t)和F(真值恒为f),以及序(当且仅当),则有FpT及ppT,ppF。于是命题逻辑(,F,T)是有界格，进而有补的分配格,即，布尔代数。定理6中(1)双重否定律是形式逻辑与辩证逻辑的主要区别之一：辩证逻辑三大规律之一否定之否定规律说：事物否定之否定的发展过程，不是(象命题逻辑那样)简单的回到原位，而是呈现螺旋式(似有周期性)上升和波浪式前进运动的特点。,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,64,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,定理6中(1)双重否定律以及定理3中(9)排中律也是经典逻辑与现代直觉主义逻辑的主要区别之一：现代直觉主义逻辑不仅不承认排中律，而且也不承认双重否定律的一半：pp，只承认另一半：pp。利用双重否定律可检查一些命题(判断)语句的失误。例如科学发展到今天，谁也不会否认地球不是围绕着太阳运行的。任何人在工作中难免不犯错误。我并非反对在写战争的影片里不该有某些爱情描写。难道能够否认这部小说没有不足之处吗？能否坚持实践第一的观点是贯彻实事求是路线的思想前提。,65,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,定理7.逻辑蕴涵关系是(全体命题公式集上的)一种“半序关系”。(1)自反性:;(2)反对称性:如果且，则;(3)传递性:如果且，则。,证.(1)自反性:对任一命题公式，对任一指派v,若(v)=t，则(v)=t(同一性)推出(逻辑蕴涵的定义)(2)反对称性:且推出对公式、的合成变项组的任一指派v,(如果(v)=t，则(v)=t)且(如果(v)=t，则(v)=t)(逻辑蕴涵)推出对任一指派v,(v)=t当且仅当(v)=t推出对任一指派v,(v)=(v)推出(逻辑等价的定义),66,注.逻辑蕴涵关系不是(全体命题公式集上的)一种真正的半序关系，而是(全体命题公式集上的)一种(类似的)“半序关系”。因为在反对称性里，用逻辑等价代替了相等。结合逻辑等价定义的注二及定理7的(2)反对称性，得到下面的结论：当且仅当且,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,(3)传递性:且推出对公式、的合成变项组的任一指派v,(如果(v)=t，则(v)=t)且(如果(v)=t)，则(v)=t)(逻辑蕴涵)推出对任一指派v,如果(v)=t，则(v)=t推出(逻辑蕴涵的定义),67,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,引理1.逻辑运算是保持逻辑等价的。即如果11且22,则(1)11;(2)1212;(3)1212;(4)1212;(5)1212。,证.(2)对任一指派v,根据条件11且22,由逻辑等价的定义可知,1(v)=1(v)且2(v)=2(v),从而按的真值表:若1(v)=1(v)=t且2(v)=2(v)=t,则(12)(v)=t=(12)(v);,68,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,若1(v)=1(v)=t且2(v)=2(v)=f,则(12)(v)=t=(12)(v);若1(v)=1(v)=f且2(v)=2(v)=t,则(12)(v)=t=(12)(v);若1(v)=1(v)=f且2(v)=2(v)=f,则(12)(v)=f=(12)(v);综合,总有(12)(v)=(12)(v),按逻辑等价的定义可知1212。,69,定理8.替换定理(replacementtheorem)等价替换是保持逻辑等价的。即设是含有子公式的公式,将其中的出现一处或多处用子公式替换,从而得到,即,=(/),则如果，则。注.替换定理也称为或置换定理(permutationtheorem)。,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,例12.令:=pq,=pq,于是(联结词归约律)。令:=(pq)p(pq)q)(pq)r,从而1=(pq)p(pq)q)(pq)r,2=(pq)p(pq)q)(pq)r,3=(pq)p(pq)q)(pq)r,由替换定理可知:1,2,3。,70,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,证.平凡情况:(1)若中不含,则=。于是由自反性有,也就是;(2)若=，则=。由条件，就是;以下除原子公式的情况外，不考虑平凡情况。非平凡情况：(采用结构归纳法)施归纳于合式公式的结构(1)若=(为一原子公式,即命题变项,比如p)，则(i)若,则=,归结为平凡情况(1);(ii)若=,则=,归结为平凡情况(2);(2)若=1,则=(/)=(1)(/)=(1(/)=1。这里:1=1(/)。归纳假设为:11,根据引理1的(1)可知:11，也就是;,71,注.结构归纳法是符号串集(公式集)上的(串值)数学归纳法。结构归纳法是数理逻辑中一种很重要的证明方法。,4.可满足性永真性逻辑推论逻辑等价替换定理代入定理对偶定理,(3)若=12，则=(/)=(12)(/)=1(/)2(/)=12这里:1=1(/),2=2(/)。归纳假设为：11,22。根据引理1的(2)可知:1212,即。(4)(5)(6)仿证。归纳