哲学命题逻辑等值演算

,*,Click to edit Master text styles,Second level,Third level,Fourth level,Click to edit Master title style,*,Home,目录,Home,目录,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,哲学命题逻辑等值演算,两公式什么时候代表了同一个命题呢？,抽象地看，它们的真假取值完全一样时即代表了一样的命题。,设公式A,B共同含有n个命题变项，可能对A或B有哑元，假设A与B有一样的真值表，那么说明在2n个赋值的每个赋值下，A与B的真值都一样。于是等价式AB应为重言式。,2,.,1,等值,式,1,、,等值的定义及说明,设A,B是两个命题公式，假设A,B构成的等价式AB为重言式,那么称A与B是等值的,记作AB。,说明,注意,与,的区别。,A,或,B,中可能有哑元出现。,pq, (,pq)(,rr)r,为左边公式中的哑元。,用真值表可以验证两个公式是否等值。,例2.1,判断下面两个公式是否等值,(,pq),与 ,pq,解答,说明,在用真值表法判断,A,B,是否为重言式时，真值表的最后一列可以省略,。,等值,判断以下各组公式是否等值(1)p(qr)与(pq)r (2)(pq)r与(pq)r,解答,等值,不等值,2、根本等值式,A A,2.幂等律A AA,A AA,3.交换律AB BA，AB BA,4.结合律(AB)C A(BC) (AB)C A(BC),5.分配律A(BC) (AB)(AC) 对的分配律A(BC) (AB)(AC)对的分配律,摩根律(AB) AB(AB) AB,7.吸收律A(AB) A，A(AB) A,8.零律A1 1,A0 0,9.同一律A0 A，A1 A,10.排中律AA 1,11.矛盾律AA 0,12.蕴涵等值式AB AB,13.等价等值式AB (AB)(BA),14.假言易位AB BA,15.等价否认等值式 AB AB,16.归谬论(AB)(AB) A,3,、对偶原理,一个逻辑等值式，如果只含有、,、0、1,那么同时,把,和互换把0和1互换,得到的还是等值式。,4、等值演算与置换规那么,各等值式都是用元语言符号书写的，其中A,B,C可以代表任意的公式，称这样的等值式为等值式模式。,每个等值式模式都给出了无穷多个同类型的具体的等值式。例如，在蕴涵等值式 ABAB 中，取A=p，B=q时，得等值式 pqpq 取A=pqr，B=pq时，得等值式(pqr)(pq) (pqr)(pq),这些具体的等值式都被称为原来的等值式模式的代入实例。,由的等值式推演出另外一些等值式的过程为等值演算。,置换规那么 设(A)是含公式A的命题公式，(B)是用公式B置换了(A)中所有的A后得到的命题公式，假设BA，那么(B)(A)。,关于等值演算的说明,等值演算的根底,等值关系的性质：自反性：AA。对称性：假设AB，那么BA。传递性：假设AB且BC，那么AC。,根本的等值式,置换规那么,等值演算的应用,证明两个公式等值,判断公式类型,解判定问题,等值演算的应用举例,证明两个公式等值(,pq)r,(,pr)(qr),(pq)r (pq)r蕴含等值式、置换规那么, (pq)r蕴含等值式、置换规那么, (pq)r德摩根律、置换规那么, (pr)(qr)分配律、置换规那么,说明,也可以从右边开场演算,因为每一步都用置换规那么，故可不写出,熟练后，根本等值式也可以不写出,通常不用等值演算直接证明两个公式不等值,解答,用等值演算法验证等值式,(pq)r,(pr)(qr),(p,r)(q,r),(p,r,)(q,r,)(,蕴含等值式,),(,pq,)r(,分配律,),(pq)r,(,德摩根律,),(pq)r(,蕴含等值式,),解答,例题2.4 用等值演算判断以下公式的类型：,1 (p(pq)r 2p(pq)p)q),3(pq)pq,(1) (p,(pq)r,(ppq)r,(,pp,q)r,0,r,0,(,2) p(pq)p),q), p(pq),p,)q), p(,(pp),(qp)q),p(,(,0,(qp)q), p(,q,p,q,),p1 p,解答,(3) (pq)pq, (pq)pq 蕴涵等值式, (pq)p)q 蕴涵等值式, (pq)p)q 德摩根律, (pq)p)q德摩根律, (pp)(qp)q 分配律, (1(qp)q 排中律, (qq)p 同一律, 1p排中律, 1 零律,定义1 命题变项及其否认统称作文字。仅由有限个文字构成的析取式称作简单析取式。仅由有限个文字构成的合取式称作简单合取式。,简单析取式举例：p,qpp，pq pqr,pqr,简单合取式举例：p,qpp，pqpqr,ppq,2,.,2,析取范式和合取范式,1,、简单析取式与简单合取式,一个文字既是简单析取式，又是简单合取式。,为讨论方便，有时用A1,A2,As表示s个简单析取式或s个简单合取式。,定理1,(1)一个简单析取式是重言式当且仅当它同时含有某个命题变项及它的否认式。,(2)一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它的否认式。,定义2,(1)由有限个简单合取式构成的析取式称为,析取范式,。,(2)由有限个简单析取式构成的合取式称为,合取范式,。,(3)析取范式与合取范式统称为,范式,。,2,、析取范式与合取范式,设Ai(i=1,2,s)为简单合取式，那么A=A1A2As为析取范式。例如，A1=pq，A2=qr，A3=p，那么由A1,A2,A3构造的析取范式为A=A1A2A3=(pq)(qr)p,设Ai(i=1,2,s)为简单析取式，那么A=A1A2As为合取范式。例如，取A1=pqr，A2=pq，A3=r，那么由A1,A2,A3组成的合取范式为A=A1A2A3=(pqr)(pq)r,定理,2,(1),一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。,(2),一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。,定理3,任一命题公式都存在着与之等值的析取范式与合取范式。,3,、析取范式和合取范式的性质,说明,研究范式的目的在于，将给定公式化成与之等值的析取范式或合取范式，进而将公式化成与之等值的主析取范式或主合取范式。,4,、求给定公式范式的步骤,(1)消去联结词、(假设存在)。AB ABAB (AB)(AB),(2)否认号的消去(利用双重否认律)或内移(利用德摩根律)。A A(AB) AB(AB)AB,(3)利用分配律：利用对的分配律求析取范式， 对的分配律求合取范式。A(BC) (AB)(AC)A(BC) (AB)(AC),例题,1,求下面公式的析取范式与合取范式：,(,pq),r,(1) 求合取范式,(pq) r, (pq) r 消去, (pq)r)(r(pq) 消去, (pq)r)(rpq)消去, (pq)r)(pqr) 否认号内移, (pr)(qr)(pqr)对分配律,解答,(2),求析取范式,(,pq),r,(,(,pq),r),(p,q,r),(,pqp)(pqq)(pqr) (rp)(rq)(rr),(,pqr)(pr)(qr),说明,由此例可知,，,命题公式的析取范式不唯一。,同样,，,合取范式也是不唯一的。,5、范式的标准化形式,定义3 在含有n个命题变项的简单合取式简单析取式中，假设每个命题变项和它的否认式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否认式出现在从左算起的第i位上假设命题变项无角标，就按字典顺序排列，称这样的简单合取式简单析取式为极小项极大项。,n个命题变项共可产生2n个不同的极小项。其中每个极小项都有且仅有一个成真赋值。假设成真赋值所对应的二进制数转换为十进制数i，就将所对应极小项记作mi 。,类似地，n个命题变项共可产生2n个极大项，每个极大项只有一个成假赋值，将其对应的十进制数i做极大项的角标，记作Mi。,表,1,p,q,形成的极小项与极大项,P Q,PQ,P,Q,PQ,P,Q,0 0,0 1,1 0,1 1,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,P Q,P,Q,P,Q,P,Q,P,Q,0 0,0 1,1 0,1 1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,表2,p,q,r,形成的极小项与极大项,定理4 设mi与Mi是命题变项p1,p2,pn形成的极小项和极大项，那么 mi Mi， Mi mi,定义4 设由n个命题变项构成的析取范式合取范式中所有的简单合取式简单析取式都是极小项极大项，那么称该析取范式合取范式为主析取范式主合取范式.,定理5,任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是唯一的。,定理5的证明,(1)证明存在性。,设A是任一含n个命题变项的公式。,由定理2.3可知，存在与A等值的析取范式A，即AA，假设A的某个简单合取式Ai中既不含命题变项pj，也不含它的否认式pj，那么将Ai展成如下形式：,Ai Ai1 Ai(pjpj) (Aipj)(Ajpj),继续这个过程，直到所有的简单合取式都含任意命题变项或它的否认式。,假设在演算过程中出现重复的命题变项以及极小项和矛盾式时，都应“消去：如用p代替pp，mi代替mimi，0代替矛盾式等。最后就将A化成与之等值的主析取范式A。,(2)证明唯一性。,假设某一命题公式A存在两个与之等值的主析取范式B和C，,即AB且AC，那么BC。,由于B和C是不同的主析取范式，不妨设极小项mi只出现在B中而不出现在C中。,于是，角标i的二进制表示为B的成真赋值，而为C的成假赋值。这与BC矛盾，因而B与C必一样。,6,、求公式,A,的主析取范式的方法与步骤,方法一、等值演算法,(1)化归为析取范式。,(2)除去析取范式中所有永假的析取项。,(3)将析取式中重复出现的合取项和一样的变元合并。,(4)对合取项补入没有出现的命题变元，即添加如(pp)式，然后应用分配律展开公式。,方法二、真值表法,(1)写出A的真值表。,(2)找出A的成真赋值。,(3)求出每个成真赋值对应的极小项用名称表示，按角标从小到大顺序析取。,方法一、等值演算法,(1)化归为合取范式。,(2)除去合取范式中所有永真的合取项。,(3)将合取式中重复出现的析取项和一样的变元合并。,(4)对析取项补入没有出现的命题变元，即添加如(pp)式，然后应用分配律展开公式。,方法二、真值表法,(1)写出A的真值表。,(2)找出A的成假赋值。,(3)求出每个成假赋值对应的极大项用名称表示，按角标从小到大顺序析取。,7,、求公式,A,的主合取范式的方法与步骤,(1)求主合取范式,pq pq M2,(2)求析取范式,pq pq, pqq (pp)q, (pq)(pq)(pq)(pq), (pq)(pq)(pq), m0m1m3,解答,p,q,p,q,0,0,1,0,1,1,1,0,0,1,1,1,例2 求命题公式,pq,的主析取范式和主合取范式。,例,3,求 的主析取范式和主合取范式。,解：,(1),列真值表,(2),成真赋值有,010,，,100,，,101,，,110,，,111,(3),成假赋值有,000,，,001,，,011,主析取范式为,主合取范式为,方法一、真值表法,方法二、等值演算法 主析取范式,方法二、等值演算法 主合取范式,一种主范式,求另一种主范式,分析,:,主析取范式中没有出现的极小项有,主合取范式为,主析取范式的用途,求公式的成真赋值与成假赋值,判断公式的类型,判断两个命题公式是否等值,应用主析取范式分析和解决实际问题,求公式的成真赋值与成假赋值,假设公式A中含n个命题变项，A的主析取范式含s(0s2n)个极小项，那么A有s个成真赋值，它们是所含极小项角标的二进制表示，其余2n-s个赋值都是成假赋值。,在例2.8中，(pq)r m1m3m4m7,各极小项均含三个文字，因而各极小项的角标均为长为3的二进制数，它们分别是001，011，100，111，这四个赋值为该公式的成真赋值,其余的为成假赋值。,在例2.9中，pq m0m1m3，这三个极小项均含两个文字，它们的角标的二进制表示00，01，11为该公式的成真赋值，10是它的成假赋值。,判断公式的类型,设公式,A,中含,n,个命题变项，容易看出：,A,为,重言式,当且仅当,A,的主析取范式含全部2,n,个极小项。,A,为,矛盾式,当且仅当,A,的主析取范式不含任何极小项。此时，记,A,的主析取范式为0。,A,为,可满足式,当且仅当,A,的主析取范式至少含一个极小项。,判断公式的类型,用公式的主析取范式判断公式的类型：,(1) (,pq)q,(2),p(pq),(3) (,pq)r,解答,(1)(pq)q pqq, (pq)q 0,(2)p(pq) m0m1m2m3,(3)(pq)r m0m1m3m5m7,矛盾式,重言式,可满足式,判断两个命题公式是否等值,设公式A,B共含有n个命题变项，按n个命题变项求出A与B的主析取范式A与B。假设AB,那么AB；否那么，A与B不等值。,判断下面两组公式是否等值：,(1) p与(pq)(pq) (2)(pq)r与(q)r,(1),p,p(qq),(pq)(pq),m,2,m,3,(,pq)(pq),m,2,m,3,两公式等值。,(2),(,pq)r,m,1,m,3,m,4,m,5,m,7,(,q)r,m,0,m,1,m,2,m,3,m,4,m,5,m,7,两公式不等值。,解答,应用主析取范式分析和解决实际问题,某科研所要从3名科研骨干A,B,C中挑选12名出国进修。由于工作原因，选派时要满足以下条件：(1)假设A去，那么C同去。(2)假设B去，那么C不能去。(3)假设C不去，那么A或B可以去。问应如何选派他们去？,分析：(1)将简单命题符号化,(2)写出各复合命题,(3)写出由(2)中复合命题组成的合取式前提,(4)将(3)中公式化成析取式最好是主析取范式,(5)这样每个小项就是一种可能产生的结果。去掉不符合题意的小项，即得结论。,应用主析取范式分析和解决实际问题,设 p:派A去，q:派B去，r:派C去,由条件可得公式,(pr)(qr)(r(pq),经过演算可得,(pr)(qr)(r(pq) m1m2m5,由于 m1=pqr, m2=pqr, m5=pqr,可知，选派方案有3种：,(a)C去，而A,B都不去。(b)B去，而A,C都不去。(c)A,C去，而B不去。,解答,由公式的主析取范式求主合取范式,设公式,A,含,n,个命题变项。,A,的主析取范式含,s(0s2,n,),个极小项，即,没有出现的极小项设为,它们的角标的二进制表示为,A,的成真赋值，因而,A,的主析取范式为,由公式的主析取范式，求主合取范式：,(1),A,m,1,m,2,(A,中含两个命题变项,p,q),(2) B, m,1,m,2,m,3,(B,中含两个命题变项,p,q,r),解答,(1),A,M,0,M,3,(2) B, M,0,M,4,M,5,M,6,M,7,重言式与矛盾式的主合取范式,设,n,为公式中命题变项个数,矛盾式无成真赋值，因而矛盾式的主合取范式含2,n,个极大项。,重言式无成假赋值，因而主合取范式不含任何极大项。,将重言式的主合取范式记为1。,可满足式的主合取范式中极大项的个数一定小于2,n,。,真值表与范式的关系,AB当且仅当A与B有一样的真值表，又当且仅当A与B有一样的主析取范式主合取范式。,真值表与主析取范式主合取范式是描述命题公式标准形式的两种不同的等价形式。,n个命题变项共可产生2n个极小项极大项,可以产生的主析取范式主合取范式数目为：,本章主要内容,等值式与等值演算。,根本的等值式，其中含：双重否认律、幂等律、交换律、结合律、分配律、德摩根律、吸收律、零律、同一律、排中律、矛盾律、蕴含等值式、等价等值式、假言易位、等价否认等值式、归谬论。,与主析取范式及主合取范式有关的概念：简单合取式、简单析取式、析取范式、合取范式、极小项、极大项、主析取范式、主合取范式。,本章学习要求,深刻理解等值式的概念。,牢记24个根本等值式，这是等值演算的根底；能熟练地应用它们进展等值演算。,了解简单析取式、简单合取式、析取范式、合取范式的概念。,深刻理解极小项及极大项的定义及它们的名称，及名称下角标与成真赋值的关系。,熟练掌握求公式的主析取范式的方法。,熟练掌握由公式的主析取范式求公式的主合取范式的方法。,会用公式的主析取范式主合取范式求公式的成真赋值、成假赋值。,本章典型习题,用等值演算法证明重言式和矛盾式,用等值演算法证明等值式,求公式的主析取范式和主合取范式,用主范式判断两个公式是否等值,求解实际问题,求公式(,pq)(pr),的主析取范式和主合取范式。,解答,p,q,r,(,pq)(pr),0,0,0,0,0,0,1,1,0,1,0,0,0,1,1,1,1,0,0,0,1,0,1,0,1,1,0,1,1,1,1,1,主析取范式为,(,p,qr)(,pqr)(pq,r),(,pqr),主合取范式为,(pqr)(p,qr)(,pqr),(,pq,r),甲、乙、丙、丁四个人有且只有两个人参加围棋比赛。关于谁参加比赛，以下四个判断都是正确的：(1)甲和乙只有一人参加比赛。(2)丙参加，丁必参加。(3)乙或丁至多参加一人。(4)丁不参加，甲也不会参加。请推断出哪两个人参加围棋比赛。,设,a：,甲参加了比赛。,b：,乙参加了比赛。,c：,丙参加了比赛。,d：,丁参加了比赛。,(1) (,a,b)(,ab),(2),cd,(3),(,bd)(4),d,a,解答,(,(,a,b)(,ab),)(,cd,)(,(bd),)(,d,a,),(,a,b,cd,)(,a,bd,)(,ab,c,d,),根据题意条件，有且仅有两人参赛，,故,abcd,为0,，,所以,(,abcd,)(,abd,),为1，,即甲和丁参加了比赛。,(,ab)(cd),(,ac)(bc)(ad)(bd),说明,本章作业,习题二,4,(3),、7、8,(1),、9,(2),、23、29,同学们学习愉快！,下次课再见！,汇报结束,谢谢大家,!,请各位批评指正,