离散数学 1_命题逻辑.ppt

1,离散数学,高等教育出版社,2,逻辑学是推理的基础，在社会学、自然科学，特别是在计算机学科中得到普遍应用。数理逻辑是逻辑学的一个分支，也是数学的分支，它用数学方法研究推理规律，它采用符号的方法来描述和处理思维形式、思维过程和思维规律，它在程序设计、数字电路设计、计算机原理、人工智能等计算机课程得到了广泛应用。命题逻辑是数理逻辑的基础部分。,第一章数理逻辑,3,（一）命题逻辑的基本概念第一节命题与联结词一、命题及其分类1.命题与真值(1)命题判断结果惟一的陈述句(必须作出判断)(2)命题的真值判断的结果(真或假)(3)成立的命题称为真命题，不成立的命题称为假命题判定一陈述句是否为命题的两要素：有判断+能定真伪因此：感叹句、祈使句、疑问句都不是命题陈述句中的悖论，判断结果不惟一确定的不是命题,4,例请判断下列句子中那些是命题：(1)是有理数.(2)2+57.(3)x+53.(4)你去教室吗？(5)这个苹果真大呀！(6)请不要讲话！(7)2019年元旦下大雪.(8)我正在说假话。不难看出：(1)是假命题，(2)是真命题.(7)是真命题(它的真值现在不知道，到2009年元旦就知道了.可见命题的真值是客观存在的，不以我们是否知道而改变).(3)(4)(5)(6)(8)不是命题，其中(8)是一悖论.,5,2.命题的分类（1）简单命题:不能分解成更简单的陈述句命题.（2）复合命题：将若干简单命题组合（用联结词联结）起来得到的命题.3.简单命题符号化本书约定：（1）用小写英文字母p,q,r,pi,qi,ri(i1)表示简单命题;（2）用“1”表示真，用“0”表示假.例如，令p：是有理数；q：2+5=7。则p的真值为0，则q的真值为1.在本小节要弄清命题、命题的真值、真命题、假命题、简单命题、复合命题等概念.,6,二、联结词与复合命题简单命题组合成复杂命题时所使用的辅助词称为“联结词”。命题逻辑中的联结词归纳为以下5种。合取：且（and），pq析取：或（or），pq否定：非（not），p条件式：pq（若p则q）双条件式：当且仅当，pq,7,1.否定“”(非)的定义：命题p的真值与命题p恰好相反.,例p:我是法学院的学生。p:我不是法学院的学生。例q:他戴了一顶红色的帽子。q:(1)他戴的帽子不是红色的；(2)他没戴红色的帽子。哪种表述正确？,8,2.合取“”(且)的定义：当命题p、q均取值为真时，“pq”的值才为真，其他情况（p,q中至少一个为假时）pq的值为假.,9,例将下列命题符号化.(1)吴颖既用功又聪明.(2)吴颖不仅用功而且聪明.(3)吴颖虽然聪明,但不用功.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.先将原子命题符号化:p:吴颖用功；q:吴颖聪明；r:张辉是三好生；s:王丽是三好生；t:张辉与王丽是同学则上述命题符号化后为(1)pq;(2)pq;(3)pq;(4)rs;(5)t,10,3.析取“”(或)的定义：命题p,q中至少一个为真时，pq的值为真；pq为假当且仅当p与q同时为假.,11,例将下列命题符号化（1）2或4是素数；（2）2或3是素数；（3）4或6是素数；（4）小元元只能拿一个苹果或一个梨；（5）王小红生于1975年或1976年.解：先将原子命题符号化：p:2是素数；q:3是素数；r:4是素数；s:6是素数；t:小元元拿一个苹果；u:小元元拿一个梨；v:王小红生于1975年;w:王小红生于1976年则命题符号化后为：(1)pr;(2)pq;(3)rs;(4)(tu)(tu);(5)(vw)(vw)或vw（1）（3）为“可兼或”（可同时为真的或）,（4）（5）为“不可兼或”（或“排斥或”）（不可同时为真的或）.,12,4.条件式“”定义设p,q为二命题，复合命题“如果p,则q”记作pq，称作p与q的条件式。p称为前件，q称为后件。规定：仅当p真q假时pq的值为假，p,q取其他值时pq的值为真.说明：（1）pq的逻辑关系：q为p的必要条件（2）当p为假时，pq为真，可称为空证明.即:当p为假时，无论q为真或为假,均规定pq为真;当p为真、q为真时,规定pq为真;当p为真、q为假时,规定pq为假。,13,例设p：我期终考了年级前10，q：我老妈奖励1000元pq：（1）我期终果真考了年级前10，老妈奖励了我1000元，此时pq为真；（2）我期终果真考了年级前10，但老妈食言未奖励我1000元，此时pq为假；（3）我期终没有考进年级前10，此时不管老妈是否奖励我1000元，都应当认为老妈的诺言是真的，即pq为真。,14,5.等价式“”（当且仅当）的定义：设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq.规定pq为真当且仅当p与q同时为真或同时为假.pq的逻辑关系：p与q互为充分必要条件.pq为真当且仅当p与q同真或同假.,15,例求下列复合命题的真值:(1)2+24当且仅当3+36.(2)2+24当且仅当3是偶数.(3)2+24当且仅当太阳从东方升起.(4)2+24当且仅当美国位于非洲.(5)函数f(x)在x0可导的充要条件是它在x0连续.它们的真值是显而易见的(1)(3)为真,(2)(4)(5)为假).例：设p:是无理数，q:3是奇数，r:苹果是方的，s:太阳绕地球转则复合命题(pq)(rs)p)是假命题.联结词的运算顺序为：,(同级则由左到右的顺序),16,第二节命题公式及其赋值一、命题变项与合式公式1.命题变项（或命题变元）(1)命题常项（命题常元）:一个命题(2)命题变项（命题变元）:真值可以变化的陈述句(即一簇命题)例.记p:x+25,则p是一个命题变元.(3)常项与变项均用p,q,r,pi,qi,ri,等表示.命题公式与数学表达式类似：简单的算术表达式中有常数、变量、运算符（加减乘除），对应地命题公式中有命题常项、命题变项、命题联结词（合取、析取、否定、条件、双条件）。数学的变量x表示任意一个数，而命题公式中的命题变项表示任意一个命题。代数式的书写有规律，命题公式也有规律与约束，称满足这些规则的公式为“合式公式”，也称为“命题公式”，简称为“公式”。数学表达式的结果值可以是任何一个具体的数，而命题公式的结果值只可能是0，1（假或真）。,17,2合式公式（简称公式）定义1.6合式公式(简称公式)的递归定义：(1)原子合式公式（单个命题变项）(2)若A是合式，则(A)也是.(3)若A,B是合式，则(AB),(AB),(AB),(AB)也是.(4)只有有限次地应用（1）-（3）形成的符号串才是公式.例.(p1)q是合式公式。因为p、1是合公式，则(p1)是合式公式，而r是合式公式，故(p1)q是合式公式。(p1)r不是合式公式。因为要求左右两端均有公式，而此处右端没有。,18,二、公式的赋值（或解释）与真值表1.公式的赋值当x,y的值不确定时，代数式x2+y+10的值是不确定的。类似地,对于命题公式(p1)q，当p,q值不确定时此命题公式不确定，因而不是命题。只有当p,q的值确定后，公式(p1)q的值才能确定。一个命题公式全部变元的一组赋值，称为该公式的一个赋值（解释）。使得公式的结果值为真的赋值称为成真赋值，使得结果值为假的赋值称为成假赋值。对于一个命题公式，列出其全部赋值及对应的结果值，所得表格称为此公式的真值表。,19,含n个变项的公式有2n个赋值.罗列全部2n个赋值的一个方法：将一个赋值看作一个二进制数，则可从000开始，依次增加1，最后以111结束.,例给出公式(p1)q的真值表。,20,2.公式的类型定义1.9(1)重言式(永真式）:对所有赋值均为真的公式.(2)矛盾式(永假式）:对所有赋值均为假的公式.(3)可满足式(不是矛盾式的公式):存在一组赋值使公式为真的公式.注意：重言式是可满足式，但反之不真.易知(pp)q,(pp)q,pq分别为重言式、矛盾式、可满足式.进一步的问题：（1）如何判断公式的类型？（2）如何求出公式A的全部成真与成假赋值？,21,解决方法：给出公式的真值表，利用真值表即可得到此公式的全部成真赋值和全部成假赋值，也可判定其公式类型。例写出下列公式pq、(pq)的真值表:(可逐列进行计算),22,例写出下列公式的真值表，从而(1)求出其全部成真赋值和全部成假赋值;(2)判定公式类型：A=(pq)rB=(qp)qpC=(pq)q,23,24,25,26,例给出公式p(qr)、(pq)(pr)的真值表，证明两公式是等值的。,注意：右边两大列的计算中，先算出左右两列，再计算出中间列（带框）的最后结果。,27,第三节等值式1.等值式定义若对于每个赋值公式A,B的结果值都相同，则称公式A与公式B等值，记作AB，并称AB是等值式.用真值表可验证两个公式是否等值.例pqpq（由前面的例子知）例证明：pqqp(逆否命题与原命题等值).,28,2.基本的等值式双重否定律AA幂等律AAA,AAA交换律ABBA,ABBA结合律(AB)CA(BC),(AB)CA(BC)分配律A(BC)(AB)(AC),A(BC)(AB)(AC)德摩根律(AB)AB(AB)AB吸收律A(AB)A,A(AB)A,29,零律A11,A00同一律A0A.A1A排中律AA1矛盾律AA0条件式等值式ABAB双条件式等值式AB(AB)(BA)逆否命题与原命题等值ABBA等价否定等值式ABAB归谬论(AB)(AB)A注意：要牢记各个等值式，这是继续学习的基础.区别：“”是联结词，而“”不是。“AB”是判断“A当且仅当B”的命题，但尚未证实；而“AB”已证实命题“A当且仅当B”成立，即“AB”为重言式。,30,二、等值演算与置换规则1.等值演算由已知的等值式推演出新的等值式的过程2.等值演算的基础：（1）等值关系的性质：自反、对称、传递性（2）基本的等值式(见前面)（3）置换规则（见3)3.置换规则：若BC，则将公式A中的子公式B换成C得到公式D后，那么AD。即将一个公式的局部进行等值替换后，新公式仍与原公式等值。不断对公式进行局部等值替换的操作，公式可不断作等价变形。如果能朝希望的方向演变下去，公式最终可变为预定的形式。,31,三、等值演算的应用举例1证明两个公式等值例证明(pq)r(pr)(qr)。(pq)r(pq)r条件式的等值式(pq)r德摩律(pr)(qr)分配律(pr)(qr)条件式等值式几点说明：也可以从右边开始演算因为每一步都用置换规则，故可不写出.熟练后，基本等值式也可以不写出.用等值演算不能直接证明两个公式不等值.,32,例证明p(qr)与(pq)r不等值。证方法一.观察赋值法.易知000,010等是左边的成真赋值，是右边的成假赋值.方法二.用等值演算先化简两个公式，再观察:左为p(qr),右为(pq)r)(pq)r),故取010时左为真、右为假，由此知两公式不等值。方法三.真值表法（列出两个公式的真值表,如果对于每一组赋值两公式的值均一致,则两公式等值,否则两公式不等值.）,33,34,2.判断公式类型例用等值演算法判断下列公式的类型（1）(pq)p)q（2）(p(pq)r（3）(pq)(pq)r解（1）(pq)p)q(pq)p)q(条件式的等值式)(pq)p)q(条件式的等值式)(pq)p)q(德摩律)(pq)p)q(德摩律)(pq)(pq)(结合律)(pq)(pq)(逆用德摩律)AA(A=(pq)1由最后一步可知，（1）为重言式.,35,（2）(p(pq)r(p(pq)r(条件式的等值式)(pp)q)r(结合律)(1q)r(零律)1r(零律)0r(的定义)0(零律)由最后一步可知，（2）为矛盾式.,36,（3）(pq)(pq)r(p(qq)r（分配律）p1r（排中律）pr（同一律）由最后一步可知，（3）不是矛盾式，也不是重言式，它是可满足式，其实(1,0,1),(1,1,1)是成真赋值，(0,0,0),(0,1,0)等是成假赋值.小结：从此例可看出A为矛盾式当且仅当A0A为重言式当且仅当A1,37,第四节析取范式与合取范式一、析取范式与合取范式1.基本概念（1）文字命题变项及其否定的总称(如p,q).（2）简单析取式有限个文字构成的析取式.如p,q,pq,pqr,（3）简单合取式有限个文字构成的合取式如p,q,pq,pqr,（4）析取范式由有限个简单合取式组成的析取式A1A2Ar(r1,A1,A2,Ar均为简单合取式).（5）合取范式由有限个简单析取式组成的合取式A1A2Ar(r1,A1,A2,Ar均为简单析取式).（6）范式析取范式与合取范式的总称.,38,说明：单个文字既是简单析取式，又是简单合取式。如pqr,pqr的公式既是析取范式，又是合取范式简单析取式与简单合取式的性质定理2.1(1)一个简单析取式是重言式当且仅当它同时含某命题变元p及其否定式p；(2)一个简单合取式是矛盾式当且仅当它同时含某命题变元p及其否定式p。析取范式与合取范式的性质定理2.2(1)一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式；(2)一个合取式是重言式当且仅当它的每个简单析取式都是重言式。,39,2.命题公式的范式（1）公式A的析取范式：与A等值的析取范式（2）公式A的合取范式：与A等值的合取范式（3）公式范式存在定理定理2.3任何命题公式都存在着与之等值的析取范式与合取范式（4）求公式A的范式的步骤：1.消去A中的,（若存在）2.否定联结词的内移或消去3.使用分配律对分配（析取范式）对分配（合取范式）（5）公式的范式存在，但不惟一，这是它的局限性。,40,3.求公式的范式举例例求下列公式的析取范式与合取范式（1）A=(pq)r（2）B=(pq)r解（1）(pq)r(pq)r（消去）pqr（结合律）注意：最后结果既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）,41,（2）(pq)r(pq)r（消去第一个）(pq)r（消去第二个）(pq)r（否定号内移德摩根律）最后一步已为析取范式（两个简单合取式构成）继续：B(pq)r(pr)(qr)（对分配律）最后一步已为合取范式（由两个简单析取式构成）,42,二、主析取范式与主合取范式1.极小项与极大项定义2.4在含有n个命题变项的简单合取式（简单析取式）中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i（1in）个文字出现在左起第i位上，称这样的简单合取式（简单析取式）为极小项（极大项）.例p1p2p3为极小项，p1p2p3为极大项，但p1p3和p1p1p3均不是。几点说明：n个命题变项产生2n个极小项和2n个极大项.2n个极小项（极大项）均互不等值.用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示.Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示,mi（Mi）称为极小项（极大项）的名称.,43,44,45,2.主析取范式与主合取范式定义2.5（1）主析取范式由极小项构成的析取范式（2）主合取范式由极大项构成的合取范式例如，n=3,命题变项为p,q,r时，(pqr)(pqr)m1m3主析取范式(pqr)(pqr)M7M1主合取范式3.命题公式A的主析取范式与主合取范式（1）与A等值的主析取范式称为A的主析取范式；与A等值的主合取范式称为A的主合取范式.（2）主析取范式的存在惟一定理定理2.5任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是惟一的.,46,4.用等值演算法求公式的主范式的步骤：（1）先求析取范式（合取范式）（2）将不是极小项（极大项）的简单合取式（简单析取式）化成与之等值的若干个极小项之析取（极大项之合取），利用的等值式为同一律（零律）、排中律（矛盾律）、分配律、幂等律等.（3）极小项（极大项）用名称mi（Mi）表示，并按角标从小到大顺序排序.例求公式A=(pq)r的主析取范式与主合取范式.,47,（1）求主析取范式(pq)r(pq)r（析取范式）(pq)(pq)(rr)(pqr)(pqr)m6m7r(pp)(qq)r(pqr)(pqr)(pqr)(pqr)m1m3m5m7,代入并排序，得(pq)rm1m3m5m6m7（主析取范式）,48,（2）求A的主合取范式(pq)r(pr)(qr)（合取范式）prp(qq)r(pqr)(pqr)M0M2qr(pp)qr(pqr)(pqr)M0M4,代入并排序，得(pq)rM0M2M4（主合取范式）,49,3.主范式的用途与真值表相同.（1）用于求公式成真或成假的赋值.例(pq)rm1m3m5m6m7，其成真赋值为001,011,101,110,111(直接由主范式表达式(下标)可知);成假赋值为000,010,100(成真赋值以外的全部赋值).类似地，由主合取范式也立即求出成假或成真赋值.,50,（2）判断公式的类型设A含n个命题变项.A为重言式A的主析取范式含2n个极小项A的主合取范式为1.A为矛盾式A的主析取范式为0A的主合析取范式含2n个极大项A为非重言式的可满足式A的主析取范式中至少含一个（但不是全部）极小项A的主合取范式中至少含一个（但不是全部）极大项,51,（3）判断两个公式是否等值例用主析取范式判两个公式是否等值p(qr)与(pq)rp(qr)与(pq)r解p(qr)=m0m1m2m3m4m5m7(pq)r=m0m1m2m3m4m5m7(pq)r=m1m3m4m5m7显见，中的两公式等值，而的不等值.（4）解实际问题（见书上例2.12）6.最后说明两点：由公式A的主析取范式可确定它的主合取范式，反之亦然.用公式A的真值表可求A的主范式，反之亦然.,52,第三节联结词的完备集一、真值函数1.问题的提出问：含n个命题变项的所有公式共产生多少个互不相同的真值表？答案为个，为什么？2.真值函数的定义称定义域为000,001,111，值域为0,1的函数为n元真值函数，定义域中的元素为2n个长为n的0,1组成的符号串.常用F:0,1n0,1表示F是n元真值函数.易知，全体n元函数共有个.例设F:0,1n0,1，且F(00)=F(01)=F(11)=0，F(01)=1，则F为一个确定的2元函数.,53,3.命题公式与真值函数对于任何一个含n个命题变项的命题公式A，都存在惟一的一个n元真值函数F为A的真值表，等值的公式对应的真值函数相同.于是解决了1提出的问题.n=2时，每个命题公式的真值表都可以在书上表2.6中找到.例如：pq,pq,(pq)(pq)q),都对表2.6中的,54,55,二、联结词的完备集1.定义定义2.7设S是一个联结词集合，如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集.说明：若S是联结词完备集，则任何命题公式都可由S中的联结词所表示.2.一些联结词完备集定理2.6S=,是联结词完备集.证明的关键：主析取（主合取）范式存在惟一性定理.,56,推论以下联结词集都是完备集（1）S1=,（2）S2=,（3）S3=,（4）S4=,（5）S5=,证明线索：若S是完备集，则S中再加入新的联结词后所得S仍为完备集，因而（1）,（2）得证.注意到：AB(AB)AB(AB)ABAB（3）,（4）,（5）得证.,57,三.复合联结词与1.定义2.8设p,q为两个命题（1）pq(pq),称为与非联结词.（2）pq(pq),称为或非联结词.我们可以称与为复合联结词.定理2.7与均为联结词完备集.证明线索：,为完备集，而ppp(pp)pppq(pq)pq(pp)(qq)pq(pq)(pq)(pq)(pq)由,作为归纳基础，可知为完备集.2与在计算机硬件设计中均有应用,58,第三章命题逻辑的推理理论本章的主要内容为推理的形式结构和自然推理系统P。第一节推理的形式结构一、推理与证明1.例子（1）正项级数收敛当且仅当部分和上有界。（2）若AB且CD，则ACBD。（3）若今天是星期一，则明天是星期二。（4）若ACBD，则AB且CD。2.推理从前提出发推出结论的思维过程上例中，(1)(2)(3)是正确的推理，而(4)是错误的推理.3证明描述推理正确或错误的过程。严格定义见下页.,59,二、推理的形式结构及证明方法1推理的正确与错误定义3.1设A1,A2,Ak,B为命题公式。（1）若对于每组赋值，A1A2Ak均为假，或当A1A2Ak为真时,B也为真,则称推理正确。（2）否则称推理不正确（错误）.由定义不难看出：定理3.1命题公式A1,A2,Ak推B的推理正确当且仅当A1A2AkB为重言式.注意:这里的正确推理与生活中的推理有所区别.,60,2.推理的形式结构（多种形式）（1）设=A1,A2,Ak,B.（2）A1A2AkB.（3）前提：A1,A2,Ak结论：B（4）说明：当推理正确时,(1)中记为B,(2)中记为A1A2AkB.,61,3.判断推理是否正确的方法（1）真值表法（2）等值演算法（3）主析取范式法（4）构造证明法（见下节）,62,例判断下面推理是否正确（1）若今天是1号，则明天是5号.今天是1号.所以明天是5号.（2）若今天是1号，则明天是5号.明天是5号.所以今天是1号.解设p：今天是1号，q：明天是5号.则要证明:（1）(pq)pq（2）(pq)qp证（1）（用等值演算法）(pq)pq(pq)p)qpqq1,由定理3.1可知推理正确.,63,证（2）（用主析取范式法）(pq)qp(pq)qp(pq)q)pqp(pq)(pq)(pq)(pq)m0m2m3结果不含m1,故01时成假赋值，所以推理不正确.,64,4.推理定律（1）推理定律重言蕴涵式.（2）重要的推理定律A(AB)附加律(AB)A化简律(AB)AB假言推理(AB)BA拒取式(AB)BA析取三段论(AB)(BC)(AC)假言三段论(AB)(BC)(AC)等价三段论(AB)(CD)(AC)(BD)构造性二难(AB)(AB)(AA)B构造性二难（特殊形式）(AB)(CD)(BD)(AC)破坏性二难,65,关于推理定律的几点说明：A,B,C为元语言符号若某推理符合某条推理定律，则它自然是正确的AB产生两条推理定律,66,第二节自然推理系统P一、形式系统1形式系统的定义定义3.2一个形式系统I由下面四个部分组成：（1）非空的字母表，记作A(I).（2）A(I)中符号构造的合式公式集，记作E(I).（3）E(I)中一些特殊的公式组成的公理集，记作AX(I).（4）推理规则集，记作R(I).2形式系统的分类（1）自然推理系统（2）公理系统,67,二、自然推理系统P定义3.3P的定义如下1.字母表（1）命题变项符号：p,q,r,pi,qi,ri,（2）联结词符号：,（3）括号与逗号：(,),，2.合式公式（同定义1.6）3.推理规则（1）前提引入规则:可以随时使用前提（2）结论引入规则:任何结论都可作为下步推理的前提（3）置换规则,68,（4）假言推理规则ABA_B（5）附加规则：A_AB（6）化简规则：ABA（7）拒取式规则：ABB_A,69,（8）假言三段论规则：ABBCAC（9）析取三段论规则：ABBA（10）构造性二难推理规则：ABCDACBD,70,(11)破坏性二难推理规则：ABCDBDAC（12）合取引入规则：AB_AB,71,三、在自然推理系统P中构造证明1直接证明法例用构造证明法构造下面推理的证明：若明天是星期一或星期三，我就有课.若有课，今天必备课.我今天下午没备课.所以，说明天是星期一或星期三是不对的.构造证明（1）设p：明天是星期一，q：明天是星期三，r：我有课，s：我备课（2）形式结构前提：(pq)r,rs,s结论：pq,72,（3）证明rs前提引入s前提引入r拒取式(pq)r前提引入(pq)拒取式pq置换,73,2.附加前提证明法（1）欲证：前提：A1,A2,Ak结论：CB（2）等价地证明前提：A1,A2,Ak,C结论：B（3）理由：(A1A2Ak)(CB)(A1A2Ak)(CB)(A1A2AkC)B,74,例构造下面推理的证明2是素数或合数.若2是素数，则是无理数.若是无理数，则4不是素数.所以，如果4是素数，则2是合数.用附加前提证明法构造证明（1）设p：2是素数，q：2是合数，r：是无理数，s：4是素数（2）形式结构前提：pq,pr,rs结论：sq,75,（3）证明s附加前提引入pr前提引入rs前提引入ps假言三段论p拒取式pq前提引入q析取三段论,76,3.归谬法（或称反证法）（1）欲证A1A2AkB前提：A1,A2,Ak结论：B（2）将B当前提，推出矛盾，得证（1）正确.（3）理由A1A2AkB(A1A2Ak)B(A1A2AkB)括号内部为矛盾式当且仅当(A1A2AkB)为重言式.,77,例前提：(pq)r,rs,s,p结论：q证明（用归缪法）q结论否定引入rs前提引入s前提引入r拒取式(pq)r前提引入(pq)析取三段论pq置换p析取三段论p前提引入pp合取,78,第四章一阶逻辑基本概念第一节一阶逻辑命题符号化一、基本概念个体词、谓词、量词1.个体（个体词）所研究对象中可以独立存在的具体或抽象的客体（名词或代词充当）（1）个体常项：具体的事务，用a,b,c表示.（2）个体变项：抽象的事物，用x,y,z表示.（3）各体域个体变项的取值范围.有限个体域，如a,b,c,1,2.无限个体域，如N,Z,R,全总个体域宇宙间一切事物组成.,79,2.谓词表示个体词性质或相互之间关系的词（1）谓词常项：F:是人，F(a)：a是人（2）谓词变项：F:具有性质F，F(x)：x具有性质F（3）n（n1）元谓词n=1，一元谓词表示性质n2，多元谓词表示事物之间的关系L(x,y)：x与y有关系L，L(x,y)：xy，（4）0元谓词不含个体变项的谓词命题常项3.量词表示数量的词（1）全称量词：“”，x（2）存在量词：“”，x,80,二、一阶逻辑中命题符号化例用0元谓词将命题符号化:（1）墨西哥位于南美洲（2）是无理数仅当是有理数（3）如果23，则3y，G(x,y)：xyx(F(x)y(G(y)L(x,y)xy(F(x)(G(y)L(x,y)（以后讨论）（2）令F(x)：x是无理数，G(y)：y是有理数，L(x,y)：xyx(F(x)y(G(y)L(x,y)xy(F(x)G(y)L(x,y)（以后讨论）,83,几点注意：1元谓词与多元谓词的区分若无特别要求，则用全总个体域量词顺序一般不要随便颠倒否定式的使用没有不呼吸的人不是所有的人都喜欢吃糖不是所有的火车都比所有的汽车快以上命题应如何符号化？,84,第二节一阶逻辑公式及解释一阶语言用于一阶逻辑公式的形式语言一、一阶语言F与合式公式1F的字母表定义4.1一阶语言F的字母表定义如下：（1）个体常项：a,b,c,ai,bi,ci,i1（2）个体变项：x,y,z,xi,yi,zi,i1（3）函数符号：f,g,h,fi,gi,hi,i1（4）谓词符号：F,G,H,Fi,Gi,Hi,i1（5）量词符号：,（6）联结词符号：,（7）括号与逗号：(,),，,85,2F的项定义4.2F的项的定义如下：（1）个体常项和个体变项是项.（2）若(x1,x2,xn)是任意的n元函数，t1,t2,tn是任意的n个项，则(t1,t2,tn)是项.（3）所有的项都是有限次使用（1），（2）得到的其实，个体常项、变项是项，由它们构成的n元函数和复合函数还是项.3F的原子公式定义4.3设R(x1,x2,xn)是F的任意n元谓词，t1,t2,tn是F的任意的n个项，则称R(t1,t2,tn)是F的原子公式.其实，原子公式是由项组成的n元谓词.例如，F(x,y),F(f(x1,x2),g(x3,x4)等均为原子公式.,86,4F的合式公式定义4.4.F的合式公式定义如下：（1）原子公式是合式公式.（2）若A是合式公式，则(A)也是合式公式.（3）若A,B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式.（4）若A是合式公式，则xA,xA也是合式公式.（5）只有有限次地应用（1）（4）形成的符号串才是合式公式.请举出几个合式公式的例子（合式公式简称公式）.,87,二、封闭的公式（简称闭式）1.量词的辖域、个体变项的约束与自由出现定义4.5在公式xA和xA中，称x为指导变元，A为相应量词的辖域.在x和x的辖域中，x的所有出现都称为约束出现，A中不是约束出现的其他变项均称为是自由出现的.在公式x(F(x,y)G(x,z)中，设A=(F(x,y)G(x,z)（也可记为A(x)）则x为指导变元，A为x的辖域，A中x的两次出现均为约束出现，y与z均为自由出现.,88,2.闭式定义4.6若公式A中不含自由出现的个体变项，则称A为闭式.例如，xy(F(x)G(y)H(x,y)为闭式，而x(F(x)G(x,y)则不是闭式.关于闭式的性质，后面讨论.,89,三、解释与公式的分类1给定公式对它们进行解释（易接受，非正式）（1）给出公式x(F(x)G(x)一个成真解释，一个成假解释（2）给出公式x(F(x)G(x)一个成真解释，一个成假解释（3）xF(x)xF(x)有成真解释吗？（4）xF(x)xF(x)有成假解释吗？下面给出F中的解释.,90,2.F中的解释定义4.7F的解释I由下面4部分组成：(a)非空个体域DI(b)DI中一些特定元素的集合(c)DI上特定函数集合(d)DI上特定谓词的集合下面对解释I做几点说明：在解释的定义中引进了几个元语言符号，如.被解释的公式A中的个体变项均取值于DI若A中含个体常项ai，就解释成.,91,为第i个n元函数，例如，i=1,n=2时，表示第一个二元函数，它出现在解释中，可能是等，一旦公式中出现f1(x,y)就解释成，出现g1(x,y)就解释成.为第i个n元谓词，例如，i=2,n=3时，表示第2个3元谓词，它可能以的形式出现在解释中,公式A中若出现F2(x,y,z)就解释成.被解释的公式不一定全部包含解释中的4部分.,92,例4.8给定解释I如下:(a)个体域D=N;(b)a=0;(c)f(x,y)=x+y,g(x,y)=xy;(d)F(x,y):x=y.写出下列公式在I下的解释,指出哪些公式为真、哪些公式为假，哪些真值不能确定：(1)F(f(x,y),g(x,y)此公式解释为“x+y=xy”,不是命题,真值不确定；(2)F(f(x,a),y)F(g(x,y),z);此公式解释为“(x+0=y)(xy=z)”,不是命题,真值不确定；(3)F(g(x,y),g(y,z)此公式解释为“xyyz”，不是命题，真值不确定；(4)xF(g(x,y),z)此公式解释为“x(xy=z)”,不是命题,真值不确定；,93,(5)xF(g(x,a),x)F(x,y);此公式解释为“x(x0=x)(x=y)”，是真命题；(6)xF(g(x,a),x)此公式解释为“x(x0=x)”，是假命题；(7)xy(F(f(x,a),y)F(f(y,a),x);此公式解释为“xy(x+0=y)(y+0=x)”，是真命题；(8)xyzF(f(x,y),z);此公式解释为“xyz(x+y=z)”，是真命题；(9)xF(f(x,x),g(x,x);此公式解释为“x(x+x=xx)”，是真命题.,94,3闭式的性质.定理4.1闭式在任何解释下都是命题注意：不是闭式的公式在某些解释下也可能是命题.4公式的类型定义4.8（1）永真式（逻辑有效式）（2）矛盾式（永假式）（3）可满足式几点说明：永真式为可满足式，但反之不真.判断公式是否为永真式不是易事.某些代换实例可判公式类型.,95,定义4.9设A0是含命题变项p1,p2,pn的命题公式，A1,A2,An是n个谓词公式，用Ai(1in)处处代替A0中的pi，所得公式A称为A0的代换实例.例如，F(x)G(x),xF(x)yG(y)等都是pq的代换实例，而x(F(x)G(x)等不是pq的代换实例.定理4.2重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式.,96,例判断下列公式中，哪些是永真式，哪些是矛盾式？（1）x(F(x)G(x)（2）x(F(x)G(x)（3）xF(x)(xyG(x,y)xF(x)（4）(xF(x)yG(y)yG(y)解（1），（2）为可满足式.（3）为p(qp)（重言式）的代换实例，故为永真式.（4）为(pq)q（矛盾式）的代换实例，故为永假式.,97,第五章一阶逻辑等值演算与推理本章的主要内容有一阶逻辑等值式、前束范式和一阶逻辑推理理论。第一节一阶逻辑等值式与置换规则一、等值式与基本的等值式1等值式定义5.1AB当且仅当AB为永真式（A与B为任意的一阶逻辑公式）注意：与定义2.1的区别与联系2基本等值式第一组：命题逻辑中16组基本等值式的代换实例。例如，xF(x)yG(y)xF(x)yG(y)为pqpq的代换实例,98,第二组：(本章新给出)（1）消去量词等值式若D=a1,a2,an,则xA(x)A(a1)A(a2)A(an)xA(x)A(a1)A(a2)A(an)（2）量词否定等值式xA(x)xA(x)xA(x)xA(x),99,（3）量词辖域收缩与扩张等值式设A(x)是含x的公式，B中不含x的出现。关于全称量词的基本等值式：x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x)BxA(x)关于存在量词的基本等值式：x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x)BxA(x),100,（4）量词分配等值式x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)注意：对无分配律，对无分配律。,101,二、置换规则、换名及代替规则1.置换规则（同命题逻辑）2.换名规则设A为一公式，将A中某量词辖域中约束变项的所有出现及相应的指导变元，改成该量词辖域中未曾出现过的某个体变项符号，公式中其余部分不变，设所得公式为A，则AA.3.代替规则设A为一公式，将A中某个自由出现的个体变项的所有出现用A中未曾出现过的某个体变项符号代替，A中其余部分不变，设所得公式为A，则AA.,102,例将下面命题用两种形式符号化:（1）没有不犯错误的人.（2）不是所有的人都爱看电影.解（1）令F(x)：x是人，G(x)：x犯错误.x(F(x)G(x)x(F(x)G(x)请给出演算过程，并说明理由.（2）令F(x)：x是人，G(x)：爱看电影.x(F(x)G(x)x(F(x)G(x)给出演算过程，并说明理由.,103,第二节一阶逻辑前束范式一、前束范式与命题公式的前束范式1.前束范式定义5.2设A为一个一阶逻辑公式，若A具有如下形式:Q1x1Q2x2QkxkB,则称A为前束范式，其中Qi(1ik)为或，B为不含量词的公式.例如，x(F(x)y(G(y)H(x,y)不是前束范式，xy(F(x)(G(y)H(x,y)是前束范式.又如，x(F(x)G(x)不是前束范式,x(F(x)G(x)是前束范式.,104,2.公式的前束范式定理5.1（前束范式存在定理）一阶逻辑中的任何公式都存在与之等值的前束范式（不惟一）.3.如何求公式的前束范式利用重要等值式、置换规则、换名规则、代替规则进行等值演算.,105,例求下列公式的前束范式:（1）x(M(x)F(x)（2）xF(x)xG(x)（3）xF(x)xG(x)（4）xF(x)y(G(x,y)H(y)（5）x(F(x,y)y(G(x,y)H(x,z)解（1）x(M(x)F(x)x(M(x)F(x)（量词否定等值式）x(M(x)F(x)两步结果都是前束范式，说明不惟一性.,106,（2）xF(x)xG(x)xF(x)xG(x)（量词否定等值式）x(F(x)G(x)（量词分配等值式）另有一种形式:xF(x)xG(x)xF(x)xG(x)xF(x)yG(y)xy(F(x)G(y)两种形式是等值的.（3）xF(x)xG(x)xF(x)xG(x)x(F(x)G(x),（为什么？）或xy(F(x)G(y).（为什么？）,107,（4）xF(x)y(G(x,y)H(y)zF(z)y(G(x,y)H(y)（换名规则）zy(F(z)(G(x,y)H(y)（为什么？）或xF(x)y(G(z,y)H(y)（代替规则）xy(F(x)(G(z,y)H(y)（5）可用换名规则，也可用代替规则，这里用代替规则x(F(x,y)y(G(x,y)H(x,z)x(F(x,u)y(G(x,y)H(x,z)xy(F(x,u)G(x,y)H(x,z)注意：x与