第1章-命题逻辑

1、1,第1篇数理逻辑MathematicalLogic,2,引言,逻辑是不可战胜的,因为要反对逻辑还得使用逻辑.P.Boutroux数学在过去几乎完全与科学相联结,而逻辑则与希腊哲学连结.但二者在现代都发展了.逻辑变得更数学了而数学变得更逻辑了.无法在二者之间划分界限.D.Vira现代数学和数理逻辑已经使下述事情成为可能,即不但在物理和工程中应用数学,而且在工业规划、医学、生物化学、生物物理,以至于在哲学和语言学问题中应用数学.H.F.Fehr,3,赫拉克利特,赫拉克利特(Heraclitus,约公元前540年-前480年)古希腊哲学家赫拉克利特认为神是涵盖整个世界的事物.但他常常用逻各斯(lo

2、gos,即理性)一词来代替神.他相信世界上有“普遍的理性”来指导大自然发生的每一件事.,什么是逻辑?,4,logic最早被清末的严复翻译成汉语逻辑,属音义意义相结合的公认比较完美的翻译,当然主要是音译.后由中国传入日本,但在日语中则注明只是对logic的注音,logic在日语中的正式汉语翻译词为“论理”.logic另外有个很好的意译译名“理则”,称为理则学,这是由牟宗三先生翻译所作,比早期的逻辑翻译更符合logic的英文定义与拉丁词源.1.思维的规律;2.客观的规律;3.指处理事情的方式,规矩的意思.逻辑是人的一种抽象思维,是人通过概念,判断,推理,论证来理解和区分客观世界的思维过程.,什么是

3、逻辑?(续),5,逻辑学是研究人的思维的科学.它包含:辩证逻辑:是研究人的思维中的辩证法.例如:用全面的和发展的观点观察事物;具体问题具体分析;实践是检查事物正误的唯一标准;等等.形式逻辑:是研究人的思维的形式和一般规律.这里我们只关心形式逻辑.,什么是逻辑?(续),6,人的思维过程:概念判断推理正确的思维:概念清楚,判断正确,推理合乎逻辑.人们是通过各种各样的学习(理论学习和从实践中学习)来掌握许多概念和判断.而形式逻辑主要是研究推理的.推理:是由若干个已知的判断(前提),推出新的判断(结论)的思维过程.,什么是逻辑?(续),7,推理方法类比推理:由个别事实推出个别结论.如:地球上有空气和水

4、,地球上有生物.火星上有空气和水.火星上有生物.归纳推理:由若干个别事实推出一般结论.如:铜能导电.铁能导电.锡能导电.铅能导电.一切金属都导电.演绎推理:由一般规律推出个别事实.形式逻辑主要是研究演绎推理的.,什么是逻辑?(续),8,演绎推理举例例1:如果天下雨,则路上有水.(一般规律)天下雨了.(个别事实)推出结论:路上有水.(个别结论)例2:(大前提):所有金属都导电.(一般规律)(小前提):铜是金属.(个别事实)推出结论:铜能导电.(个别结论),什么是逻辑?(续),9,数理逻辑(MathematicalLogic)是用数学的方法研究形式逻辑.所谓“数学方法”:是建立一套有严格定义的符号

5、,即建立一套形式语言,来研究形式逻辑.所以数理逻辑也称为“符号逻辑”.数理逻辑的主要内容:逻辑演算,证明论,递归论,模型论,公理集合论我们这里只涉及逻辑演算中“命题逻辑”和“谓词逻辑”.数理逻辑与数学的其它分支,计算机科学,人工智能,语言学等学科均有密切联系.下面就前面两个例子,说明如何将推理符号化的.,什么是数理逻辑?,10,数理逻辑把推理符号化之一:例1:如果天下雨,则路上有水.天下雨了.所以路上有水.设P表示:天下雨.设Q表示:路上有水.设表示:如果则例1的推理过程表示为:前提1:PQ(如果天下雨,则路上有水.)前提2:P(天下雨了.)结论:Q(路上有水.)(这就是第一章命题逻辑中要讨论

6、的问题.),什么是数理逻辑?(续),11,数理逻辑把推理符号化之二:例2:所有金属都导电.铜是金属.所以铜能导电.设M(x):x是金属.C(x):x能导电.设x表示:所有的x.设a表示铜.例2的推理过程表示为:前提:x(M(x)C(x)(所有金属都导电.)M(a)C(a)前提:M(a)(铜是金属.)结论:C(a)(铜能导电.)(其中符号M(x),C(x)是谓词,所以这就是第二章“谓词逻辑”中所讨论的内容.),什么是数理逻辑?(续),12,Dijkstra谈数理逻辑,“假如我早年在数理逻辑上下点功夫,就不会出那么多错误,不少东西在数理逻辑上早就讲过了。如果我年轻20岁,一定会去学数理逻辑。”Di

7、jkstra,EdsgerWybeDijkstra(1930-2002),13,钱学森谈“计算机与数理逻辑”,电子计算机与数理逻辑具有非常密切的关系。正是在数理逻辑中，把人类的推理过程分解成一些非常简单原始的、非常机械的动作，才使得用机器代替人类的推理的设想有了实现的可能。有了电子计算机，使用它时，必须先进行程序设计，把整个推理、计算过程丝毫不漏地考虑到，统统编入程序，而机器则依次而运行；如稍有错误，将立即得到毫无意义的结果。可见必须有足够的数理逻辑的训练，熟悉推理过程的全部细节,才能从事程序设计。此外，程序设计是一个很细致又很麻烦的工作，如何从事程序设计，如何防止在计算过程中出错，如何很快地

8、发现这种错误而及时加以改正，都是程序设计理论(软件理论)中非常根本又非常重要的内容，大家都认为，这些内容都与数理逻辑息息相关。,14,第1章命题逻辑,15,第1章命题逻辑,1.1命题逻辑基本概念1.2命题逻辑等值演算1.3范式1.4命题逻辑推理理论,16,1.1命题逻辑基本概念,1.1.1命题与联结词命题与真值(简单命题,复合命题)联结词(,)1.1.2命题公式与分类命题公式及其赋值真值表命题公式的分类,17,命题及其真值,命题:判断结果惟一的陈述句命题的真值:判断的结果,真或假例(1)北京是中华人民共和国的首都.(2)南京是中华人民共和国的首都.真命题:真值为真的命题假命题:真值为假的命题注

9、意:感叹句,祈使句,疑问句都不是命题陈述句中的悖论以及判断结果不惟一确定的也不是命题,18,例下列句子中那些是命题？(1)北京是中华人民共和国的首都.(2)2+510.(3)x+64.(4)你会开车吗？(5)2050年元旦南京是晴天.(6)这只兔子跑得真快呀！(7)请关上窗户！(8)我正在说谎话.,真命题,假命题,真值不确定,疑问句,感叹句,祈使句,悖论,(1),(2),(5)是命题,(3),(4),(6)(8)都不是命题,真值确定,但未知,实例,19,我正在,谎话!,说,悖论:一种导致矛盾的陈述.悖论(paradox)一词来自希腊语“para+dokein”,意思是“多想一想”.,20,简单

10、命题与复合命题,简单命题(原子命题):简单陈述句构成的命题简单命题的符号化:用p,q,r,pi,qi,ri(i1)表示用“1”表示真,用“0”表示假复合命题:由简单命题通过联结词联结而成的陈述句例(1)如果明天天气好,我们就出去郊游.设p:明天天气好,q:我们出去郊游,如果p,则q(2)张三一面喝茶一面看报.设p:张三喝茶,q:张三看报,p并且q,21,联结词,定义1.1设p为命题,复合命题“非p”(或“p的否定”)称为p的否定式,记作p,符号称作否定联结词,并规定p为真当且仅当p为假.例(1)p:北京是中华人民共和国的首都.p:北京不是中华人民共和国的首都.p为真,p为假(2)p:2是合数,

11、p:2不是合数,p为假,p为真,“否定”真值表,22,联结词(续),定义1.2设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式,记作pq,称作合取联结词,并规定pq为真当且仅当p与q同时为真.例(1)p:2是偶数,q:2是素数,pq:2是偶素数,p为真,q为真,pq为真(2)p:2是偶数,q:4是奇数,pq:2是偶数且4是奇数,p为真,q为假,pq为假,“并且”真值表,23,实例,例将下列命题符号化.(1)王晓既用功又聪明.(2)王晓不仅聪明,而且用功.(3)王晓虽然聪明,但不用功.,解:记p:王晓用功,q:王晓聪明,(1)pq,(2)pq,(3)pq,24,实例(续)

12、,例将下列命题符号化.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.(6)王晓很聪明并且3是素数.,解:(4)记r:张辉是三好生,s:王丽是三好生.rs,(5)简单命题,记t:张辉与王丽是同学,(6)记u:王晓很聪明,v:3是素数.uv,注意:只考虑命题与命题之间的形式关系,而不顾及语句的含义.,25,联结词(续),定义1.3设p,q为命题,复合命题“p或q”称作p与q的析取式,记作pq,称作析取联结词,并规定pq为假当且仅当p与q同时为假.,“或者”真值表,例张三和李四至少有一人会英语.(即,张三或李四会英语)设p:张三会英语,q:李四会英语,符号化为pq,26,相容或与排斥或,例张三

13、和李四至少有一人会英语.(即,张三或李四会英语)设p:张三会英语,q:李四会英语,符号化为pq,例今晚我看电视或者我读书.不能同时看电视和读书.设p:今晚我看电视,q:今晚我读书,符号化为(pq)(pq),27,例将下列命题符号化(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.,解记p:2是素数,q:3是素数,r:4是素数,s:6是素数,(1)pr,真值:1(2)pq,真值:1(3)rs,真值:0,实例,28,例将下列命题符号化(4)元元只能拿一个苹果或一个梨.(5)王晓红生于1975年或1976年.(6)今天是晴天或3是素数.,解,(4)记t:元元拿一个苹果,u:元元拿一个梨.(

14、tu)(tu)(5)记v:王晓红生于1975年,w:王晓红生于1976年.(vw)(vw)又可形式化为vw(6)记v:今天是晴天,w:3是素数.vw,实例(续),29,联结词(续),定义1.4设p,q为二命题,复合命题“如果p,则q”称作p与q的蕴涵式,记作pq,并称p是蕴涵式的前件,q为蕴涵式的后件.称作蕴涵联结词,并规定,pq为假当且仅当p为真且q为假.例如果明天天气好,我们就出去郊游.设p:明天天气好,q:我们出去郊游,形式化为pq,“蕴含”真值表,30,联结词(续),说明:(1)pq的逻辑关系:p是q的充分条件,q为p的必要条件(2)当p为假时,pq为真(不管q为真,还是为假)例如果你

15、挣的钱超过25000,那你必须备案交税.(3)“如果p,则q”的多种表述方式:若p,就q只要p,就qp仅当q只有q才p除非q,才p除非q,否则非p,31,实例,例设p:天冷,q:小王穿羽绒服.将下列命题符号化(1)只要天冷,小王就穿羽绒服.(2)因为天冷,所以小王穿羽绒服.(3)若小王不穿羽绒服,则天不冷.(4)只有天冷,小王才穿羽绒服.(5)除非天冷,小王才穿羽绒服.(6)除非小王穿羽绒服,否则天不冷.(7)如果天不冷,则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候.,注意:pq与qp等值(真值相同),pq,pq,pq,pq,qp,qp,qp,qp,32,联结词(续),定义1.5设p,q

16、为命题,复合命题“p当且仅当q”称作p与q的等价式,记作pq,称作等价联结词.并规定pq为真当且仅当p与q同时为真或同时为假.pq的逻辑关系:p与q互为充分必要条件例这件事张三能做好,且只有张三能做好.设p:张三做这件事,q:这件事做好了形式化为:pq,“等价”真值表,33,实例,例求下列命题的真值(1)2+24当且仅当3+36.(2)2+24当且仅当3是偶数.(3)2+24当且仅当太阳从东方升起.(4)2+25当且仅当美国位于非洲.(5)f(x)在x0处可导的充要条件是它在x0处连续.,1,0,1,1,0,34,联结词(续),35,复合命题的符号化,例将下列命题符号化(1)只有你主修计算机科

17、学或不是新生,才可以从校园网访问因特网.(2)除非你已满16周岁,否则只要你身高不足4英尺就不能乘公园滑行铁道.,解:(1)设p:你主修计算机科学,q:你是新生,r:你可以从校园网访问因特网.符号化为r(pq)(2)设p:你已满16周岁,q:你身高不足4英尺,r:你能乘公园滑行铁道.符号化为(pq)r,36,命题常项:简单命题2+2=4.北京是一个大城市.0,1命题变项:不确指的简单命题用p,q,r,表示p,q,r,称为取值0或1的变项p,q,r,既以可表示命题常项,又可以表示命题变项,需要由上下文确定它们表示的是常项还是变项.,命题公式,37,命题公式,定义1.6合式公式(命题公式,公式)递

18、归定义如下:(1)单个命题常项或变项是合式公式,并称作原子合式公式(2)若A是合式公式,则(A)也是合式公式(3)若A,B是合式公式,则(AB),(AB),(AB),(AB)也是合式公式(4)只有有限次地应用(1)(3)形成的符号串才是合式公式,说明:(1)联结词优先级:(),;(2)同级按从左到右的顺序进行;(3)在不影响运算顺序时,括号可以省去.,例0,p,pq,(pq)(pr),pqr,(pq)r,38,公式的赋值,定义1.7设p1,p2,pn是出现在公式A中全部的命题变项,给p1,p2,pn指定一组真值,称为对A的一个赋值或解释.使公式为真的赋值称作成真赋值,使公式为假的赋值称作成假赋

19、值说明:(1)赋值记作=12n,i=0或1,诸i之间不加标点符号(2)通常赋值与命题变项之间按下标或字母顺序对应,即当A的全部命题变项为p1,p2,pn时,给A赋值12n是指p1=1,p2=2,pn=n;当A的全部命题变项为p,q,r,时,给A赋值123是指p=1,q=2,r=3,39,实例,例公式A=(p1p2p3)(p1p2)000是成真赋值,001是成假赋值公式B=(pq)r000是成假赋值,001是成真赋值,40,真值表,例给出公式的真值表(1)(qp)qp,真值表:命题公式在所有可能的赋值下的取值的列表含n个变项的公式有2n个赋值.,41,实例(续),(2)(pq)q,42,实例(续

20、),(3)(pq)r,43,命题公式的分类,重言式(永真式):无成假赋值的命题公式矛盾式(永假式):无成真赋值的命题公式可满足式:非矛盾式的命题公式注意:重言式是可满足式,但反之不真.例上例中(1)(qp)qp重言式,可满足式(2)(pq)q矛盾式(3)(pq)r非重言式的可满足式,44,1.2命题逻辑等值演算,1.2.1等值式与基本等值式1.2.2等值演算,45,若A与B在所有可能赋值下的真值都相同,即A与B有相同的真值表,称A与B等值.,例判断(pq)与pq是否等值解,结论:(pq)与pq等值,等值式,(pq)(pq),1111,46,等值式,定义1.8若等价式AB是重言式,则称A与B等值

21、,记作AB,并称AB是等值式.说明:(1)是元语言符号,不要混同于和=(2)A与B等值当且仅当A与B在所有可能赋值下的真值都相同,即A与B有相同的真值表(3)n个命题变项的真值表共有个,故每个命题公式都有无穷多个等值的命题公式(4)可能有哑元出现.在B中出现,但不在A中出现的命题变项称作A的哑元.同样,在A中出现,但不在B中出现的命题变项称作B的哑元.哑元的值不影响命题公式的真值.,47,实例,例判断下述3个公式之间的等值关系:p(qr),(pq)r,(pq)r解,p(qr)(pq)r,但与(pq)r不等值,48,基本等值式,双重否定律AA幂等律AAA,AAA交换律ABBA,ABBA结合律(A

22、B)CA(BC)(AB)CA(BC)分配律A(BC)(AB)(AC)A(BC)(AB)(AC)德摩根律(AB)AB(AB)AB吸收律A(AB)A,A(AB)A,49,基本等值式(续),零律A11,A00同一律A0A,A1A排中律AA1矛盾律AA0蕴涵等值式ABAB等价等值式AB(AB)(BA)假言易位ABBA等价否定等值式ABAB归谬论(AB)(AB)A,50,等值演算,等值演算:由已知的等值式推演出新的等值式的过程置换规则:若AB,则(A)(B)例证明p(qr)(pq)r证p(qr)p(qr)(蕴涵等值式)(pq)r(结合律)(pq)r(德摩根律)(pq)r(蕴涵等值式),51,实例,等值演

23、算不能直接证明两个公式不等值.证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.,例证明:p(qr)(pq)r方法一真值表法(见前例)方法二观察法.容易看出000使左边成真,使右边成假.方法三先用等值演算化简公式,再观察.A=p(qr)p(qr)pqrB=(pq)r(pq)r(pq)r(pq)r容易看出000,010是A的成真赋值,是B的成假赋值.,52,实例,例用等值演算法判断下列公式的类型(1)q(pq)解q(pq)q(pq)(蕴涵等值式)q(pq)(德摩根律)p(qq)(交换律,结合律)p0(矛盾律)0(零律)该式为矛盾式.,53,实例(续),(2)(pq)(qp)解(p

24、q)(qp)(pq)(qp)(蕴涵等值式)(pq)(pq)(交换律)1该式为重言式.,54,实例(续),(3)(pq)(pq)r解(pq)(pq)r(p(qq)r(分配律)p1r(排中律)pr(同一律)非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.,总结:A为矛盾式当且仅当A0;A为重言式当且仅当A1说明:演算步骤不惟一,应尽量使演算短些.,55,1.3范式,1.3.1析取范式与合取范式简单析取式与简单合取式析取范式与合取范式1.3.2主析取范式与主合取范式极小项与极大项主析取范式与主合取范式,56,简单析取式与简单合取式,文字:命题变项及其否定的统称简单析取式:有限个文字

25、构成的析取式例p,q,pq,pqr,简单合取式:有限个文字构成的合取式例p,q,pq,pqr,定理1.1(1)一个简单析取式是重言式当且仅当它同时含某个命题变项和它的否定(2)一个简单合取式是矛盾式当且仅当它同时含某个命题变项和它的否定,57,析取范式与合取范式,析取范式:由有限个简单合取式组成的析取式A1A2Ar,其中A1,A2,Ar是简单合取式合取范式:由有限个简单析取式组成的合取式A1A2Ar,其中A1,A2,Ar是简单析取式范式:析取范式与合取范式的统称定理1.2(1)一个析取范式是矛盾式当且仅当它的每一个简单合取式都是矛盾式.(2)一个合取范式是重言式当且仅当它的每一个简单析取式都是

26、重言式.,58,范式存在定理,定理1.3任何命题公式都存在着与之等值的析取范式与合取范式.证求公式F的范式的步骤:(1)消去F中的,ABABAB(AB)(AB)(2)否定联结词的内移或消去AA(AB)AB(AB)AB,59,范式存在定理(续),(3)使用分配律A(BC)(AB)(AC)求合取范式A(BC)(AB)(AC)求析取范式例求(pq)r的析取范式与合取范式解(pq)r(pq)r(pq)r析取范式(pr)(qr)合取范式注意:公式的析取范式与合取范式不惟一.,60,极小项与极大项,定义1.17在含有n个命题变项的简单合取式(简单析取式)中,若每个命题变项均以文字的形式出现且仅出现一次,而

27、且第i(1in)个文字(按下标或字母顺序排列)出现在左起第i位上,称这样的简单合取式(简单析取式)为极小项(极大项).,例(1)有3个命题变项p1,p2,p3,p1p2p3,p1p2p3,p1p2p3都是极小项p1p2p3,p1p2p3,p1p2p3都是极大项(2)有3个命题变项p,q,r,pqr,pqr,pqr都是极小项pqr,pqr,pqr都是极大项,61,极小项与极大项(续),定理1.4设mi与Mi是由同一组命题变项形成的极小项和极大项,则miMi,Mimi,62,极小项与极大项(续),极小项极大项公式成真赋值名称公式成假赋值名称pqr000m0pqr000M0pqr001m1pqr00

28、1M1pqr010m2pq10M2pqr011m3pqr11M3pqr100m4pqr101m5pqr110m6pqr111m7,p,q,r形成的极小项与极大项,63,主析取范式与主合取范式,主析取范式:由极小项构成的析取范式主合取范式:由极大项构成的合取范式例n=3,命题变项为p,q,r时,(pqr)(pqr)m1m3是主析取范式(pqr)(pqr)M1M5是主合取范式定理1.5任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是惟一的.,64,求主析取范式的步骤,设公式A含命题变项p1,p2,pn(1)求A的析取范式A=B1B2Bs,其中Bj是简单合取式j=1,2,s(2)若某个B

29、j既不含pi,又不含pi,则将Bj展开成BjBj(pipi)(Bjpi)(Bjpi)重复这个过程,直到所有简单合取式都是长度为n的极小项为止(3)消去重复出现的极小项,即用mi代替mimi(4)将极小项按下标从小到大排列,65,实例,例求(pq)r的主析取范式解(pq)r(pq)rpq(pq)1(同一律)(pq)(rr)(排中律)(pqr)(pqr)(分配律)m4m5r(pp)(qq)r(同一律,排中律)(pqr)(pqr)(pqr)(pqr)m0m2m4m6(分配律)得(pq)rm0m2m4m5m6可记作(0,2,4,5,6),66,主析取范式快速求法,设公式含有n个命题变项,则长度为k的简

30、单合取式可展开成2nk个极小项的析取,例求A(pq)(pqr)r的主析取范式解用快速求法pq(pqr)(pqr)m2m3pqrm1r(pqr)(pqr)(pqr)(pqr)m1m3m5m7得Am1m2m3m5m7(1,2,3,5,7),67,求主合取范式的步骤,设公式A含命题变项p1,p2,pn(1)求A的合取范式A=B1B2Bs,其中Bj是简单析取式j=1,2,s(2)若某个Bj既不含pi,又不含pi,则将Bj展开成BjBj(pipi)(Bjpi)(Bjpi)重复这个过程,直到所有简单析取式都是长度为n的极大项为止(3)消去重复出现的极大项,即用Mi代替MiMi(4)将极大项按下标从小到大排

31、列,68,实例,例求(pq)r的主合取范式解(pq)r(pr)(qr)prp0r(同一律)p(qq)r(矛盾律)(pqr)(pqr)(分配律)M1M3qr(pp)qr(同一律,矛盾律)(pqr)(pqr)(分配律)M3M7得(pq)rM1M3M7可记作(1,3,7),69,主合取范式快速求法,设公式含有n个命题变项,则长度为k的简单析取式可展开成2nk个极大项的合取,例求Bp(pqr)的主合取范式解p(pqr)(pqr)(pqr)(pqr)M4M5M6M7pqrM1得BM1M4M5M6M7(1,4,5,6,7),70,由主析取范式求主合取范式,设,没有出现的极小项是,其中t=2ns,于是,例求

32、A=(pqr)(pqr)(pqr)的主合取范式解Am1m3m7M0M2M4M5M6,71,例求(pq)r的主析取范式和主合取范式解令A=(pq)r,pqr(pq)rAA00001100010001010011001100011001110101101011001101110001,真值表法,72,求主析取范式:1.选出表中A的成真赋值所在行对应的变项之值如下:000,010,100,101,1102.将所寻出的各行变项之值还原成相应的原子命题符号,值为1者还原为原变量,值为0者还原为原变量的否定,得到:pqr,pqr,pqr,pqr,pqr3.将上述各行分别构成合取式:pqr,pqr,pqr,

33、pqr,pqr4.将上述各合取式用析取词”联结,所得的析取式即为所求的主析取范式:(pqr)(pqr)(pqr)(pqr)(pqr),真值表法(续),73,求主合取范式:,真值表法(续),2.再由A的主析取范式得到A的主合取范式:AA(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr),1.求A的主合取范式,先求A的主析取范式:A(pqr)(pqr)(pqr),74,主析取范式的用途,(1)求公式的成真赋值和成假赋值设公式A含n个命题变项,A的主析取范式有s个极小项,则A有s个成真赋值,它们是极小项下标的二进制表示,其余2ns个赋值都是成假赋值例(pq)r

34、m0m2m4m5m6成真赋值:000,010,100,101,110;成假赋值:001,011,111,75,主析取范式的用途(续),(2)判断公式的类型设A含n个命题变项,则A为重言式当且仅当A的主析取范式含2n个极小项A为矛盾式当且仅当A的主析取范式不含任何极小项,记作0A为可满足式当且仅当A的主析取范式中至少含一个极小项,76,实例,例用主析取范式判断公式的类型:(1)A(pq)q(2)Bp(pq)(3)C(pq)r解(1)A(pq)q(pq)q0矛盾式(2)Bp(pq)1m0m1m2m3重言式(3)C(pq)r(pq)r(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m0m

35、1m3m5m7非重言式的可满足式,77,主析取范式的用途(续),(3)判断两个公式是否等值例用主析取范式判断下面2组公式是否等值:(1)p与(pq)(pq)解pp(qq)(pq)(pq)m2m3(pq)(pq)(pq)(pq)(pq)(pq)m2m3故p(pq)(pq),78,实例(续),(2)(pq)r与p(qr)解(pq)r(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m1m3m5m6m7p(qr)(pq)(pr)(pqr)(pqr)(pqr)(pqr)m5m6m7故(pq)rp(qr),79,实例,例某单位要从A,B,C三人选派若干人出国考察,需满足下述条件:(1)若A去,

36、则C必须去;(2)若B去,则C不能去;(3)A和B必须去一人且只能去一人.问有几种可能的选派方案?解记p:派A去,q:派B去,r:派C去(1)pr,(2)qr,(3)(pq)(pq)求下式的成真赋值A=(pr)(qr)(pq)(pq),80,实例(续),求A的主析取范式A=(pr)(qr)(pq)(pq)(pr)(qr)(pq)(pq)(pq)(pr)(rq)(rr)(pq)(pq)(pq)(pq)(pr)(pq)(rq)(pq)(pq)(pq)(pr)(pq)(rq)(pq)(pqr)(pqr)成真赋值:101,010结论:方案1派A与C去,方案2派B去,81,主合取范式的用途,(1)求公式

37、的成真赋值和成假赋值设公式A含n个命题变项,A的主合取范式有s个极大项,则A有s个成假赋值,它们是极大项下标的二进制表示,其余2ns个赋值都是成假赋值.例(pq)rM1M3M7成假赋值:001,011,111成真赋值:000,010,100,101,110,82,主合取范式的用途(续),(2)判断公式的类型设A含n个命题变项，则A为矛盾式当且仅当A的主合取范式含2n个极大项A为重言式当且仅当A的主合取范式不含任何极大项,记作1A为可满足式当且仅当A的主合取范式中不含全部极大项(3)判断两个公式是否等值,83,1.4命题逻辑推理理论,1.4.1推理的形式结构有效推理和推理的形式结构推理定律1.4

38、.2自然推理系统P推理规则直接证明法,附加前提证明法,归谬法(反证法),84,有效推理,定义1.20若对于每组赋值,A1A2Ak为假,或者当A1A2Ak为真时,B也为真,则称由前提A1,A2,Ak推B的推理有效或推理正确,并称B是有效的结论.定理1.6由前提A1,A2,Ak推出B的推理正确当且仅当A1A2AkB为重言式.,85,推理的形式结构,形式(1)A1A2AkB形式(2)前提:A1,A2,Ak结论:B推理正确记作A1A2AkB判断推理是否正确的方法:真值表法等值演算法主析/合取范式法构造证明法,86,实例,例判断下面推理是否正确(1)若今天是1号,则明天是5号.今天是1号.所以明天是5号

39、.解设p:今天是1号,q:明天是5号推理的形式结构为(pq)pq证明用等值演算法(pq)pq(pq)p)q(pq)p)qpqq1得证推理正确.,所以明天是5号:有效结论,但并非一定是真命题.若认定前提是真的,且推理正确,则该结论是合法的,称此结论为有效结论.,87,实例(续),(2)若今天是1号,则明天是5号.明天是5号.所以今天是1号.解设p:今天是1号,q:明天是5号.推理的形式结构为(pq)qp证明用主析取范式法(pq)qp(pq)qp(pq)q)pqp(pq)(pq)(pq)(pq)m0m2m301是成假赋值,所以推理不正确.,88,推理定律重言蕴涵式,A(AB)附加律(AB)A化简律

40、(AB)AB假言推理(AB)BA拒取式(AB)BA析取三段论(AB)(BC)(AC)假言三段论(AB)(BC)(AC)等价三段论(AB)(CD)(AC)(BD)构造性二难(AB)(AB)(AA)B构造性二难(特殊形式)(AB)(CD)(BD)(AC)破坏性二难,89,证(分情况讨论)a是非0实数,故a是正数或a是负数.若a是正数,则a20;若a是负数,则a20.,例证明:非0实数的平方为正数.,a20,设p:a是正数,q:a是负数,r:a20,(pq)(pr)(qr)rr,(AB)(CD)(AC)(BD)构造性二难,在一个形式证明中,所使用的推理规则都是公认的,而且要明确的列出.但在传统的数学

41、中,这种证明一般都是非形式化的,对于推理规则的引用,常常不是被省略就是被认为是显然的,有时根本不加说明.,推理定律与数学证明,90,有理数和无理数(RationalvsIrrational),问题:若a和b是无理数,ab可能是有理数么?,我们知道2是无理数,那么22呢?,Case1:22是有理数,那么我们就找到了满足题目要求的a和b:a=2,b=2.,Case2:22是无理数,那么(22)2=22=2,是有理数,因此a=22,b=2满足题意.,无论哪一种情况,都存在无理数a和b,使得ab是有理数.,我们不需要知道那种情况为真!,91,证证明若m是奇数,则m2是奇数.因为m是奇数,则m=2l+1

42、,其中l是整数.,例证明:若m2是偶数,则m是偶数.,设p:m是奇数,q:m2是奇数.有p:m是偶数,q:m2是偶数.(pq)qp,(AB)BA拒取式,所以m2是奇数.,有m2=(2l+1)2,=(2l)2+2(2l)+1,推理定律与数学证明(续),92,自然推理系统P,自然推理系统P由下述3部分组成:1.字母表(1)命题变项符号:p,q,r,pi,qi,ri,(2)联结词:,(3)括号与逗号:(),2.合式公式3.推理规则(1)前提引入规则(2)结论引入规则(3)置换规则,93,自然推理系统P(续),94,自然推理系统P(续),说明:推理规则就是指确定论证的有效的判据,常是用命题形式表示这些

43、规则,而不涉及实际命题和它的真值.,95,直接证明法,例在自然推理系统P中构造下面推理的证明:前提:pq,qr,ps,s结论:r(pq)证明ps前提引入s前提引入p拒取式pq前提引入q析取三段论qr前提引入r假言推理r(pq)合取推理正确,r(pq)是有效结论,96,例构造推理的证明:若今天是1号,则明天是5号.今天是1号.所以明天是5号.解:设p:今天是1号,q:明天是5号.前提:pq,p结论:q证明pq前提引入p前提引入q假言推理推理正确,q是有效结论.,若认定前提是真的,且从前提集合推导出结论的论证是遵守了推理规则的,则称此结论是合法的,结论为有效结论.按公认的推理规则,从前提集合中推导

44、出一个结论来,这样的推导过程称为演绎,或者叫形式证明.,97,实例日常生活中的推理,例构造推理的证明:若明天是星期一或星期三,我就有课.若有课,今天必须备课.我今天下午没备课.所以,明天不是星期一和星期三.解设p:明天是星期一,q:明天是星期三,r:我有课,s:我备课前提:(pq)r,rs,s结论:pq,98,实例日常生活中的推理(续),前提:(pq)r,rs,s结论:pq证明rs前提引入s前提引入r拒取式(pq)r前提引入(pq)拒取式pq置换结论有效,即明天不是星期一和星期三.,99,实例数学中的推理,例若数a是实数,则它不是有理数就是无理数.若a不能表示成分数,则它不是有理数.a是实数且它不能表示成分数.所以,a是无理数.解首先将简单命题符号化.设p:a是实数,q:a是有理数,r:a