命题公式分类及等值演算2.ppt
命题公式及分类等值演算,福建师范大学数学与计算机科学学院,1.2 命题公式及其赋值,简单命题是真值唯一确定的命题逻辑中最基本的研究单位，所以也称简单命题为命题常项或命题常元。用p,q,r,等小写字母表示命题常项。称真值可以变化的陈述句为命题变项或命题变元。也用p,q,r,表示命题变项。当p,q,r,表示命题变项时，它们就成了取值0或1的变项，因而命题变项已不是命题。这样一来，p,q,r,既可以表示命题常项，也可以表示命题变项。在使用中，需要由上下文确定它们表示的是常项还是变项。将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串称为合式公式或命题公式。,定义1.6 合式公式的递推定义,(1)单个命题变项是合式公式，并称为原子命题公式。(2)若A是合式公式，则(A)也是合式公式。(3)若A，B是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式。(4)只有有限次地应用(1)(3)形式的符号串才是合式公式。合式公式也称为命题公式或命题形式，并简称为公式。设A为合式公式，B为A中一部分，若B也是合式公式，则称B为A的子公式。,关于合式公式的说明,(A)、(AB)等公式单独出现时，外层括号可以省去，写成A、AB等。公式中不影响运算次序的括号可以省去，如公式(pq)(r)可以写成pqr。合式公式的例子：(pq)(q r)(pq)rp(qr)不是合式公式的例子pqr(p(rq),定义1.7 公式层次,(1)若公式A是单个的命题变项，则称A为0层合式。(2)称A是n+1(n0)层公式是指下面情况之一：(a)AB，B是n层公式；(b)ABC，其中B,C分别为i层和j层公式，且n=max(i,j)；(c)ABC，其中B,C的层次及n同(b)；(d)ABC，其中B,C的层次及n同(b)；(e)ABC，其中B,C的层次及n同(b)。(3)若公式A的层次为k，则称A是k层公式。例如：(pq)r，(pq)(rs)p)分别为3层和4层公式,公式的解释,在命题公式中，由于有命题符号的出现，因而真值是不确定的。当将公式中出现的全部命题符号都解释成具体的命题(真值唯一确定)之后，公式就成了真值确定的命题了。例如：(pq)r若p：2是素数，q：3是偶数，r：是无理数，则p、r被解释成真命题，q被解释成假命题，此时公式(pq)r被解释成：若2是素数或3是偶数，则是无理数。（真命题）r被解释为：是有理数，则(pq)r被解释成：若2是素数或3是偶数，则是有理数。（假命题）,定义1.8 赋值或解释,设p1,p2,pn是出现在公式A中的全部命题变项，给p1,p2,pn各指定一个真值，称为对A的一个赋值或解释。若指定的一组值使A的真值为1，则称这组值为A的成真赋值；若使A的真值为0，则称这组值为A的成假赋值。对含n个命题变项的公式A的赋值情况做如下规定：(1)若A中出现的命题符号为p1,p2,pn，给定A的赋值12,n 是指p11，p22,，pnn。(2)若A中出现的命题符号为p,q,r.,给定A的赋值1,2,n是指p1，q2,，最后一个字母赋值n。上述i取值为0或1，i1,2,n。,赋值举例,在公式(p1p2p3)(p1p2)中，000(p10，p20，p30)，110(p11，p21，p30)都是成真赋值，001(p10，p20，p31)，011(p10，p21，p31)都是成假赋值。在(pq)r中，011(p10，p21，p31)为成真赋值，100(p11，p20，p30)为成假赋值。重要结论：含n(n1)个命题变项的公式共有2n个不同的赋值。,真值表,将命题公式A在所有赋值下取值情况列成表，称作A的真值表。,构造真值表的具体步骤如下：(1)找出公式中所含的全体命题变项p1,p2,pn(若无下角标就按字典顺序排列)，列出2n个赋值。本书规定，赋值从000开始，然后按二进制加法依次写出各赋值，直到111为止。(2)按从低到高的顺序写出公式的各个层次。(3)对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。,公式A与B具有相同的或不同的真值表，是指真值表的最后一列是否相同，而不考虑构造真值表的中间过程。,说明,例,求下列公式的真值表，并求成真赋值和成假赋值。(1)(pq)r(2)(pp)(qq)(3)(pq)qr,定义1.9 重言式、永真式、可满足式,设A为任一命题公式(1)若A在它的各种赋值下取值均为真,则称A是重言式或永真式（Tautology）。(2)若A在它的各种赋值下取值均为假,则称A是矛盾式或永假式(Contradiction)。(3)若A不是矛盾式,则称A是可满足式。,定义1.9的进一步说明,A是可满足式的等价定义是：A至少存在一个成真赋值。重言式一定是可满足式，但反之不真。因而，若公式A是可满足式，且它至少存在一个成假赋值，则称A为非重言式的可满足式。真值表可用来判断公式的类型:若真值表最后一列全为1，则公式为重言式。若真值表最后一列全为0，则公式为矛盾式。若真值表最后一列中至少有一个1，则公式为可满足式。,例题,例 下列各公式均含两个命题变项p与q，它们中哪些具有相同的真值表?(1)pq(4)(pq)(qp)(2)pq(5)qp(3)(pq),例题,例 下列公式中,哪些具有相同的真值表?(1)pq(2)qr(3)(pq)(pr)p)(4)(qr)(pp),两公式什么时候代表了同一个命题呢？抽象地看，它们的真假取值完全相同时即代表了相同的命题。设公式A,B共同含有n个命题变项，若A与B有相同的真值表，则说明在2n个赋值的每个赋值下，A与B的真值都相同。于是等价式AB应为重言式。,等值的定义及说明,定义1.10 设A,B是两个命题公式，若A,B构成的等价式AB为重言式，则称A与B是等值的，记作AB。,说明,不能写成=，逻辑演算与数学演算不同。在A或B中命题变项可能不同。pq(pq)(rr)用真值表可以验证两个公式是否等值。,例题,例 判断下面两个公式是否等值(pq)与 pq,解答,说明,在用真值表法判断AB是否为重言式时，真值表的最后一列可以省略。,等值,例题,例 判断下列各组公式是否等值(1)p(qr)与(pq)r(2)(pq)r与(pq)r,解答,等值,不等值,常用的等值式,1.双重否定律A A2.幂等律A AA,A AA 3.交换律AB BA，AB BA4.结合律(AB)C A(BC)(AB)C A(BC)5.分配律A(BC)(AB)(AC)（对的分配律）A(BC)(AB)(AC)（对的分配律）6.德摩根律(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 AB13.等价等值式AB(AB)(BA)14.假言易位AB BA15.等价否定等值式AB AB16.归谬论(AB)(AB)A,等值演算与置换规则,每个等值式模式都给出了无穷多个同类型的具体的等值式。例：在蕴涵等值式 ABAB 中，其中A,B,C可以代表任意的公式，例如取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),(pr)(qr)(pr)(qr)(蕴含等值式)(pq)r(分配律)(pq)r(德摩根律)(pq)r(蕴含等值式),解答,例 证明：(pq)r 与 p(qr)不等值,方法一、真值表法。,方法二、观察法。易知，010是(pq)r的成假赋值，而010是p(qr)的成真赋值，所以原不等值式成立。,方法三、通过等值演算化成容易观察真值的情况，再进行判断。A=(pq)r(pq)r（蕴涵等值式）(pq)r（蕴涵等值式）(pq)r（德摩根律）B=p(qr)p(qr)（蕴涵等值式）pqr（结合律）000，010是A的成假赋值，而它们是B的成真赋值。,解答,例 用等值演算判断下列公式的类型：（1）(pq)pq（2）(p(pq)r（3）p(pq)p)q),(1)(pq)pq(pq)pq（蕴涵等值式）(pq)p)q（蕴涵等值式）(pq)p)q（德摩根律）(pq)p)q（德摩根律）(pp)(qp)q（分配律）(1(qp)q（排中律）(qq)p（同一律）1p（排中律）1（零律）,解答,(2)(p(pq)r(ppq)r(ppq)r 0r 0(3)p(pq)p)q)p(pq)p)q)p(pp)(qp)q)p(0(qp)q)p(qpq)p1 p,习题 P.34 1.7(1)(4)(7)(10)1.8(1)(2)1.9(2)(3),
