命题公式分类及等值演算2ppt课件

1、命题公式及分类命题公式及分类等值演算等值演算福建师范大学数学与计算机科学学院福建师范大学数学与计算机科学学院1.2 命题公式及其赋值命题公式及其赋值 简单命题是真值独一确定的命题逻辑中最根本的研简单命题是真值独一确定的命题逻辑中最根本的研讨单位，所以也称简单命题为命题常项或命题常元。讨单位，所以也称简单命题为命题常项或命题常元。用用p,q,r,等小写字母表示命题常项。等小写字母表示命题常项。 称真值可以变化的陈说句为命题变项或命题变元称真值可以变化的陈说句为命题变项或命题变元 。也用也用p,q,r,表示命题变项。表示命题变项。 当当p,q,r,表示命题变项时，它们就成了取值表示命题变项时，它们

2、就成了取值0或或1的的变项，因此命题变项已不是命题。变项，因此命题变项已不是命题。 这样一来，这样一来，p,q,r,既可以表示命题常项，也可以表既可以表示命题常项，也可以表示命题变项。在运用中，需求由上下文确定它们表示命题变项。在运用中，需求由上下文确定它们表示的是常项还是变项。示的是常项还是变项。 将命题变项用结合词和圆括号按一定的逻辑关系结将命题变项用结合词和圆括号按一定的逻辑关系结合起来的符号串称为合式公式或命题公式。合起来的符号串称为合式公式或命题公式。定义定义1.6 合式公式的递推定义合式公式的递推定义(1)单个命题变项是合式公式，并称为原子命题公单个命题变项是合式公式，并称为原子命

3、题公式。式。(2)假设假设A是合式公式，那么是合式公式，那么(A)也是合式公式。也是合式公式。 (3)假设假设A，B是合式公式，那么是合式公式，那么(AB)，(AB)，(AB)，(AB)也是合式公式。也是合式公式。(4)只需有限次地运用只需有限次地运用(1)(3)方式的符号串才是合方式的符号串才是合式公式。式公式。合式公式也称为命题公式或命题方式，并简称为合式公式也称为命题公式或命题方式，并简称为公式。公式。设设A为合式公式，为合式公式，B为为A中一部分，假设中一部分，假设B也是合也是合式公式，那么称式公式，那么称B为为A的子公式。的子公式。 关于合式公式的阐明关于合式公式的阐明 (A)、(A

4、B)等公式单独出现时，外层括号可以省等公式单独出现时，外层括号可以省去，写成去，写成A、AB等。等。 公式中不影响运算次序的括号可以省去，公式中不影响运算次序的括号可以省去，如公式如公式(pq)(r)可以写成可以写成pqr。 合式公式的例子：合式公式的例子：(pq)(q r)(pq)rp(qr) 不是合式公式的例子不是合式公式的例子pqr(p(rq) 定义定义1.7 公式层次公式层次 (1) (1)假设公式假设公式A A是单个的命题变项，那么称是单个的命题变项，那么称A A为为0 0层合式。层合式。 (2) (2)称称A A是是n+1(n0)n+1(n0)层公式是指下面情况之一：层公式是指下面

5、情况之一： (a) A (a) ABB，B B是是n n层公式；层公式； (b) A (b) ABCBC，其中，其中B,CB,C分别为分别为i i层和层和j j层公式，且层公式，且n=max(i,j)n=max(i,j)； (c) A (c) ABCBC，其中，其中B,CB,C的层次及的层次及n n同同(b)(b)； (d) A (d) ABCBC，其中，其中B,CB,C的层次及的层次及n n同同(b)(b)； (e) A (e) AB BC C，其中，其中B,CB,C的层次及的层次及n n同同(b)(b)。 (3) (3)假设公式假设公式A A的层次为的层次为k k，那么称，那么称A A是是

6、k k层公式。层公式。例如：例如：(pq)r(pq)r，(pq)(rs)(pq)(rs)p)p)分别为分别为3 3层和层和4 4层公式层公式 公式的解释公式的解释 在命题公式中，由于有命题符号的出现，因此真值在命题公式中，由于有命题符号的出现，因此真值是不确定的。当将公式中出现的全部命题符号都解是不确定的。当将公式中出现的全部命题符号都解释成详细的命题释成详细的命题(真值独一确定真值独一确定)之后，公式就成了之后，公式就成了真值确定的命题了。真值确定的命题了。 例如：例如：(pq)r 假设假设p：2是素数，是素数，q：3是偶数，是偶数，r：是无理数，那是无理数，那么么p、r被解释成真命题，被解

7、释成真命题，q被解释成假命题，此时公被解释成假命题，此时公式式(pq)r被解释成：假设被解释成：假设2是素数或是素数或3是偶数，那是偶数，那么么是无理数。真命题是无理数。真命题 r被解释为：被解释为：是有理数，那么是有理数，那么(pq)r被解释成：被解释成：假设假设2是素数或是素数或3是偶数，那么是偶数，那么是有理数。假命是有理数。假命题题定义定义1.8 赋值或解释赋值或解释 设设p1,p2,pn是出如今公式是出如今公式A中的全部命题变项，给中的全部命题变项，给p1,p2,pn各指定一个真值，称为对各指定一个真值，称为对A的一个赋值或解的一个赋值或解释。假设指定的一组值使释。假设指定的一组值使

8、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,

9、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在一切赋值下取值情况列成表，在一切赋值下取值情况列成表，称

10、作称作A的真值表。的真值表。 q 构造真值表的详细步骤如下：构造真值表的详细步骤如下： q (1)(1)找出公式中所含的全体命题变项找出公式中所含的全体命题变项p1,p2,pn (p1,p2,pn (假设无下假设无下角标就按字典顺序陈列角标就按字典顺序陈列) )，列出，列出2n2n个赋值。本书规定，赋值从个赋值。本书规定，赋值从000000开场，然后按二进制加法依次写出各赋值，直到开场，然后按二进制加法依次写出各赋值，直到111111为止。为止。 q (2)(2)按从低到高的顺序写出公式的各个层次。按从低到高的顺序写出公式的各个层次。 q (3)(3)对应各个赋值计算出各层次的真值，直到最后计

11、算出公式对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。的真值。 公式公式A与与B具有一样的或不同的真值表，是指真值表的最具有一样的或不同的真值表，是指真值表的最后一列能否一样，而不思索构造真值表的中间过程。后一列能否一样，而不思索构造真值表的中间过程。 例例 求以下公式的真值表，并求成真赋值和成假赋值。求以下公式的真值表，并求成真赋值和成假赋值。(1)(pq)r (2)(pp)(qq) (3)(pq)qr 定义定义1.9 重言式、永真式、可满足式重言式、永真式、可满足式设设A为任一命题公式为任一命题公式 (1)假设假设A在它的各种赋值下取值均为真在它的各种赋值下取值均为真,那那么称

12、么称A是重言式或永真式是重言式或永真式Tautology。 (2)假设假设A在它的各种赋值下取值均为假在它的各种赋值下取值均为假,那那么称么称A是矛盾式或永假式是矛盾式或永假式(Contradiction)。 (3)假设假设A不是矛盾式不是矛盾式,那么称那么称A是可满足式。是可满足式。 定义定义1.9的进一步阐明的进一步阐明 A是可满足式的等价定义是：是可满足式的等价定义是：A至少存在一个成真赋至少存在一个成真赋值。值。 重言式一定是可满足式，但反之不真。因此，假设重言式一定是可满足式，但反之不真。因此，假设公式公式A是可满足式，且它至少存在一个成假赋值，是可满足式，且它至少存在一个成假赋值，

13、那么称那么称A为非重言式的可满足式。为非重言式的可满足式。 真值表可用来判别公式的类型真值表可用来判别公式的类型: 假设真值表最后一列全为假设真值表最后一列全为1，那么公式为重言式。，那么公式为重言式。 假设真值表最后一列全为假设真值表最后一列全为0，那么公式为矛盾式。，那么公式为矛盾式。 假设真值表最后一列中至少有一个假设真值表最后一列中至少有一个1，那么公式为可，那么公式为可满足式。满足式。 例题例题例例 以下各公式均含两个命题变项以下各公式均含两个命题变项p与与q，它们中哪些，它们中哪些具有一样的真值表具有一样的真值表? (1) pq(4) (pq)(qp)(2) pq(5) qp(3)

14、 (pq) 例题例题 例例 以下公式中以下公式中,哪些具有一样的真值表哪些具有一样的真值表?(1)pq (2)qr (3)(pq)(pr)p) (4)(qr)(pp) 两公式什么时候代表了同一个命题呢？两公式什么时候代表了同一个命题呢？ 笼统地看，它们的真假取值完全一样时笼统地看，它们的真假取值完全一样时即代表了一样的命题。即代表了一样的命题。 设公式设公式A,B共同含有共同含有n个命题变项，假设个命题变项，假设A与与B有一样的真值表，那么阐明在有一样的真值表，那么阐明在2n个个赋值的每个赋值下，赋值的每个赋值下，A与与B的真值都一样。的真值都一样。于是等价式于是等价式AB应为重言式。应为重言

15、式。 等值的定义及阐明等值的定义及阐明定义定义1.10 1.10 设设A,BA,B是两个命题公式，假设是两个命题公式，假设A,BA,B构成构成的等价式的等价式A AB B为重言式，那么称为重言式，那么称A A与与B B是等值的是等值的，记作，记作A AB B。 q 不能写成不能写成=，逻辑演算与数学演算不同。，逻辑演算与数学演算不同。q在在A或或B中命题变项能够不同。中命题变项能够不同。pq (pq)(rr)q用真值表可以验证两个公式能否等值。用真值表可以验证两个公式能否等值。例题例题例例 判别下面两个公式能否等值判别下面两个公式能否等值(pq) 与与 pq 解解答答q在用真值表法判别在用真值

16、表法判别A AB B能否为重言式时，真值能否为重言式时，真值表的最后一列可以省略。表的最后一列可以省略。等值等值例题例题例例 判别以下各组公式能否等值判别以下各组公式能否等值(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.德德摩根律摩根律

17、(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可以代表恣意的公式，可以代表恣意

18、的公式， 例如例如取取A=p，B=q时，得等值式时，得等值式 pqpq 取取A=pqr，B=pq时，得等值式时，得等值式(pqr)(pq) (pqr)(pq) 这些详细的等值式都被称为原来的等值式方式的这些详细的等值式都被称为原来的等值式方式的代入实例。代入实例。 由知的等值式推上演另外一些等值式的过程为等由知的等值式推上演另外一些等值式的过程为等值演算。值演算。 置换规那么置换规那么 设设(A)是含公式是含公式A的命题公式，的命题公式，(B)是用公式是用公式B置换了置换了(A)中一切的中一切的A后得到的命题后得到的命题公式，假设公式，假设BA，那么，那么(B)(A)。关于等值演算的阐明关于等

19、值演算的阐明 等值演算的根底等值演算的根底 等值关系的性质：等值关系的性质：自反性：自反性：AA。对称性：假设对称性：假设AB，那么，那么BA。传送性：假设传送性：假设AB且且BC，那么，那么AC。 根本的等值式根本的等值式 置换规那么置换规那么 等值演算的运用等值演算的运用 证明两个公式等值证明两个公式等值 判别公式类型判别公式类型 解断定问题解断定问题等值演算的运用举例等值演算的运用举例证明两个公式等值证明两个公式等值(pq)r (pr)(qr)(pq)r (pq)r (pq)r (pq)r蕴含等值式、置换规那么蕴含等值式、置换规那么 (pq)r (pq)r蕴含等值式、置换规那么蕴含等值式

20、、置换规那么 (pq)r (pq)r德摩根律、置换规那么德摩根律、置换规那么 (pr)(qr) (pr)(qr) 分配律、置换规那么分配律、置换规那么q 也可以从右边开场演算也可以从右边开场演算q 由于每一步都用置换规那么，故可不写出由于每一步都用置换规那么，故可不写出q 熟练后，根本等值式也可以不写出熟练后，根本等值式也可以不写出q 通常不用等值演算直接证明两个公式不等值通常不用等值演算直接证明两个公式不等值解解答答例例 用等值演算法验证等值式用等值演算法验证等值式(pq)r (pr)(qr) (pr)(qr) (pr)(qr) (pr)(qr) (pr)(qr)( (蕴含等值式蕴含等值式) ) (pq)r (pq)r( (分配律分配律) ) (pq)r (pq)r( (德摩根律德摩根律) ) (pq)r (pq)r( (蕴含等值式蕴含等值式) ) 解解答答例 证明：(pq)r 与 p(qr) 不等值方法一、真值表法。方法一、真值表法。 方法二、察看法。易知，方法二、察看法。易知，010是是(pq)r的成假赋值，而的成假赋值，而010是是p(qr)的成真赋值，所以原不等值式成立。的成真赋值，所以原不等值式成立。 方法三、经过