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