《命题公式分类及等值演算2.ppt》由会员分享，可在线阅读，更多相关《命题公式分类及等值演算2.ppt（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、命题公式及分类命题公式及分类等值演算等值演算福建师范大学数学与计算机科学学院福建师范大学数学与计算机科学学院1.2命题公式及其赋值命题公式及其赋值简单命题是真值唯一确定的命题逻辑中最基本的研简单命题是真值唯一确定的命题逻辑中最基本的研究单位，所以也称简单命题为究单位，所以也称简单命题为命题常项命题常项或或命题常元命题常元。用用p,q,r,等小写字母表示命题常项。等小写字母表示命题常项。称真值可以变化的陈述句为称真值可以变化的陈述句为命题变项命题变项或或命题变元命题变元。也用也用p,q,r,表示命题变项。表示命题变项。当当p,q,r,表示命题变项时，它们就成了取值表示命题变项时，它们就成了取值0
2、或或1的的变项，因而变项，因而命题变项已不是命题命题变项已不是命题。这样一来，这样一来，p,q,r,既可以表示命题常项，也可以表既可以表示命题常项，也可以表示命题变项。在使用中，需要由上下文确定它们表示命题变项。在使用中，需要由上下文确定它们表示的是常项还是变项。示的是常项还是变项。将命题变项用联结词和圆括号按一定的逻辑关系联将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串称为结起来的符号串称为合式公式合式公式或或命题公式命题公式。定义定义1.6合式公式的递推定义合式公式的递推定义(1)单个命题变项是合式公式，并称为单个命题变项是合式公式，并称为原子命题公原子命题公式式。(2)若若A
3、是合式公式，则是合式公式，则(A)也是合式公式。也是合式公式。(3)若若A，B是合式公式，则是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式。也是合式公式。(4)只有有限次地应用只有有限次地应用(1)(3)形式的符号串才是形式的符号串才是合式公式。合式公式。合式公式也称为合式公式也称为命题公式命题公式或或命题形式命题形式，并简称，并简称为为公式公式。设设A为合式公式，为合式公式，B为为A中一部分，若中一部分，若B也是合也是合式公式，则称式公式，则称B为为A的的子公式子公式。关于合式公式的说明关于合式公式的说明(A)、(AB)等公式单独出现时，外层括号可以省等公式单独出现时，外层
4、括号可以省去，写成去，写成A、AB等。等。公式中不影响运算次序的括号可以省去，公式中不影响运算次序的括号可以省去，如公式如公式(pq)(r)可以写成可以写成pqr。合式公式的例子：合式公式的例子：(pq)(qr)(pq)rp(qr)不是合式公式的例子不是合式公式的例子pqr(p(rq)定义定义1.7公式层次公式层次 (1)(1)若公式若公式A是单个的命题变项，则称是单个的命题变项，则称A为为0层合式层合式。(2)称称A是是n+1(n0)层公式层公式是指下面情况之一：是指下面情况之一：(a)AB，B是是n层公式；层公式；(b)ABC，其中其中B,C分别为分别为i层和层和j层公式，且层公式，且n=
5、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层公式层公式公式的解释公式的解释在命题公式中，由于有命题符号的出现，因而真值在命题公式中，由于有命题符号的出现，因而真值是不确定的。当将公式中出现的全部命题符号都解是不确定的。当将公式中出现的全部命题符号都解释成具体的命题释成具体的命题(真值唯一确定真值唯一确定)之后，
6、公式就成了之后，公式就成了真值确定的命题了。真值确定的命题了。例如：例如：(pq)r若若p：2是素数，是素数，q：3是偶数，是偶数，r：是无理数，则是无理数，则p、r被解释成真命题，被解释成真命题，q被解释成假命题，此时公式被解释成假命题，此时公式(pq)r被解释成：若被解释成：若2是素数或是素数或3是偶数，则是偶数，则是是无理数。（真命题）无理数。（真命题）r被解释为：被解释为：是有理数，则是有理数，则(pq)r被解释成：若被解释成：若2是素数或是素数或3是偶数，则是偶数，则是有理数。（假命题）是有理数。（假命题）定义定义1.8赋值或解释赋值或解释设设p1,p2,pn是出现在公式是出现在公式
7、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,
8、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)个命题变项的公式共有个命题变项的公式共
9、有2n个不同的赋值。个不同的赋值。真值表真值表将命题公式将命题公式A在所有赋值下取值情况列成表，在所有赋值下取值情况列成表，称作称作A的的真值表真值表。q构造真值表的具体步骤如下：构造真值表的具体步骤如下：(1)(1)找出公式中所含的找出公式中所含的全体全体命题变项命题变项p p1 1,p,p2 2,p pn n(若无下角标就若无下角标就按字典顺序排列按字典顺序排列)，列出，列出2 2n n个赋值。本书规定，赋值从个赋值。本书规定，赋值从00000 0开始，然后按二进制加法依次写出各赋值，直到开始，然后按二进制加法依次写出各赋值，直到11111 1为止。为止。(2)(2)按从低到高的顺序写出公
10、式的各个层次。按从低到高的顺序写出公式的各个层次。(3)(3)对应各个赋值计算出各层次的真值，直到最后计算出公式的对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。真值。公式公式A与与B具有相同的或不同的真值表，是指真值表的最具有相同的或不同的真值表，是指真值表的最后一列是否相同，而不考虑构造真值表的中间过程。后一列是否相同，而不考虑构造真值表的中间过程。说说明明例例求下列公式的真值表，并求成真赋值和成假赋值。求下列公式的真值表，并求成真赋值和成假赋值。(1)(pq)r(2)(pp)(qq)(3)(pq)qr 定义定义1.9重言式、永真式、可满足式重言式、永真式、可满足式设设A为任一命
11、题公式为任一命题公式(1)若若A在它的各种赋值下取值均为真在它的各种赋值下取值均为真,则称则称A是是重言式重言式或或永真式（永真式（Tautology）。(2)若若A在它的各种赋值下取值均为假在它的各种赋值下取值均为假,则称则称A是是矛盾式矛盾式或或永假式永假式(Contradiction)。(3)若若A不是矛盾式不是矛盾式,则称则称A是是可满足式可满足式。定义定义1.9的进一步说明的进一步说明A是可满足式的等价定义是：是可满足式的等价定义是：A至少存在一个成真赋至少存在一个成真赋值。值。重言式一定是可满足式，但反之不真。因而，若公重言式一定是可满足式，但反之不真。因而，若公式式A是可满足式，
12、且它至少存在一个成假赋值，则称是可满足式，且它至少存在一个成假赋值，则称A为非重言式的可满足式。为非重言式的可满足式。真值表可用来判断公式的类型真值表可用来判断公式的类型:若真值表最后一列全为若真值表最后一列全为1，则公式为重言式。，则公式为重言式。若真值表最后一列全为若真值表最后一列全为0，则公式为矛盾式。，则公式为矛盾式。若真值表最后一列中至少有一个若真值表最后一列中至少有一个1，则公式为可满，则公式为可满足式。足式。例题例题例例下列各公式均含两个命题变项下列各公式均含两个命题变项p与与q，它们中哪些它们中哪些具有相同的真值表具有相同的真值表?(1)pq(4)(pq)(qp)(2)pq(5
13、)qp(3)(pq)例题例题例例下列公式中下列公式中,哪些具有相同的真值表哪些具有相同的真值表?(1)pq(2)qr(3)(pq)(pr)p)(4)(qr)(pp)两公式什么时候代表了同一个命题呢？两公式什么时候代表了同一个命题呢？抽象地看，它们的真假取值完全相同时抽象地看，它们的真假取值完全相同时即代表了相同的命题。即代表了相同的命题。设公式设公式A,B共同含有共同含有n个命题变项，若个命题变项，若A与与B有相同的真值表，则说明在有相同的真值表，则说明在2n个赋值个赋值的每个赋值下，的每个赋值下，A与与B的真值都相同。于的真值都相同。于是等价式是等价式AB应为重言式。应为重言式。等值的定义及
14、说明等值的定义及说明定义定义1.10 1.10 设设A,BA,B是两个命题公式，若是两个命题公式，若A,BA,B构成的等构成的等价式价式A AB B为重言式，则称为重言式，则称A A与与B B是等值的，记作是等值的，记作A AB B。说说明明q不能写成不能写成=，逻辑演算与数学演算不同逻辑演算与数学演算不同。q在在A A或或B B中命题变项可能不同。中命题变项可能不同。pq(pq)(rr)q用真值表可以验证两个公式是否等值。用真值表可以验证两个公式是否等值。例题例题例例判断下面两个公式是否等值判断下面两个公式是否等值(pq)与与pq解答解答说说明明q在用真值表法判断在用真值表法判断A AB B
15、是否为重言式时，真值是否为重言式时，真值表的最后一列可以省略表的最后一列可以省略。等值等值例题例题例例判断下列各组公式是否等值判断下列各组公式是否等值(1)p(qr)与与(pq)r(2)(pq)r与与(pq)r 解答解答等值等值不等值不等值常用的等值式常用的等值式1.双重否定律双重否定律AA2.幂等律幂等律AAA,AAA3.交换律交换律ABBA，ABBA4.结合律结合律(AB)CA(BC)(AB)CA(BC)5.分配律分配律A(BC)(AB)(AC)（对对的分配律）的分配律）A(BC)(AB)(AC)（对对的分配律）的分配律）6.德德摩根律摩根律(AB)AB(AB)AB7.吸收律吸收律A(AB
16、)A，A(AB)A 8.零律零律A11,A009.同一律同一律A0A，A1A10.排中律排中律AA111.矛盾律矛盾律AA012.蕴涵等值式蕴涵等值式 ABAB13.等价等值式等价等值式AB(AB)(BA)14.假言易位假言易位ABBA15.等价否定等值式等价否定等值式ABAB16.归谬论归谬论(AB)(AB)A等值演算与置换规则等值演算与置换规则每个等值式模式都给出了无穷多个同类型的具体的每个等值式模式都给出了无穷多个同类型的具体的等值式。等值式。例：在蕴涵等值式例：在蕴涵等值式ABAB中，其中中，其中A,B,C可可以代表任意的公式，以代表任意的公式，例如例如取取A=p，B=q时，得等值式时
17、，得等值式pqpq取取A=pqr，B=pq时，得等值式时，得等值式(pqr)(pq)(pqr)(pq)这些具体的等值式都被称为原来的等值式模式的这些具体的等值式都被称为原来的等值式模式的代入实例代入实例。由已知的等值式推演出另外一些等值式的过程为由已知的等值式推演出另外一些等值式的过程为等值演算等值演算。置换规则置换规则设设(A)是含公式是含公式A的命题公式，的命题公式，(B)是是用公式用公式B置换了置换了(A)中所有的中所有的A后得到的命题公式，后得到的命题公式，若若BA，则则(B)(A)。关于等值演算的说明关于等值演算的说明等值演算的基础等值演算的基础等值关系的性质：等值关系的性质：自反性
18、：自反性：AA。对称性：若对称性：若AB，则则BA。传递性：若传递性：若AB且且BC，则则AC。基本的等值式基本的等值式置换规则置换规则等值演算的应用等值演算的应用证明两个公式等值证明两个公式等值判断公式类型判断公式类型解判定问题解判定问题等值演算的应用举例等值演算的应用举例证明两个公式等值证明两个公式等值(pq)r(pr)(qr)(pqpq)r)r (pq)pq)rr（蕴含等值式、置换规则）蕴含等值式、置换规则）(pq)pq)r r（蕴含等值式、置换规则）蕴含等值式、置换规则）(pq)pq)rr（德摩根律、置换规则）德摩根律、置换规则）(pr)(qrpr)(qr)（分配律、置换规则）分配律、
19、置换规则）说说明明q也可以从右边开始演算也可以从右边开始演算q因为每一步都用置换规则，故可不写出因为每一步都用置换规则，故可不写出q熟练后，基本等值式也可以不写出熟练后，基本等值式也可以不写出q通常不用等值演算直接证明两个公式不等值通常不用等值演算直接证明两个公式不等值解答解答例例用等值演算法验证等值式用等值演算法验证等值式(pq)r(pr)(qr)(p pr)(qr)(qr r)(p prr)(q)(qrr)(蕴含等值式蕴含等值式)(pqpq)r)r(分配律分配律)(pq)rpq)r(德摩根律德摩根律)(pq)rpq)r(蕴含等值式蕴含等值式)解答解答例证明：证明：(pq)r与与p(qr)不
20、等值不等值方法一、方法一、真值表法。真值表法。方法二、方法二、观察法。观察法。易知，易知，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
21、）(pq)pq（2）(p(pq)r（3）p(pq)p)q)(1)(1)(pq)pqpq)pq (pq)ppq)pq（蕴涵等值式）(pq)p)qpq)p)q （蕴涵等值式）蕴涵等值式）(pq)pq)p)qp)q （德摩根律）德摩根律）(pq)pq)pp)q)q（德摩根律）德摩根律）(pppp)(qp)q)(qp)q （分配律）分配律）(1(q1(qp)p)q q（排中律）排中律）(qqqq)p)p （同一律）同一律）11pp（排中律）排中律）1 1 （零律）（零律）解答解答(2)(2)(p p(pq)r(pq)r (ppq)rppq)r (ppppq)rq)r 0r0r 0 0(3)(3)p(pq)p)p(pq)p)qq)p(pq)p(pq)pp)q)q)p(p(pp)pp)(qp)q(qp)q)p(p(00(qp)q)(qp)q)p(p(qqppq q)p1 p1 p p习题习题P.331.7(1)(4)(7)(10)1.8(1)(2)1.9(2)(3)