第二章命题逻辑等值演算

1、第二章 命题逻辑等值演算2.1 2.1 等值式等值式定义定义2.1 A B为重言式为重言式等值等值A B从表中可知它是重言式，即(pq) (pq)p (qr) (pq)r(pq)r (pq)r等值演算等值演算1616组重要的等值式组重要的等值式: :1. 双重否定律双重否定律 A A 2. 幂等律幂等律 A AA , A AA 3. 交换律交换律 AB BA ， AB BA4. 结合律结合律 (AB)C A(BC) (AB)C A(BC)7. 吸收律吸收律 A(AB) A ， A(AB) A 8. 零律零律 A1 1 , A0 0 9. 同一律同一律 A0 A ， A1 A 10. 排中律排中

2、律 AA 1 11. 矛盾律矛盾律 AA 0 12. 蕴涵等值式蕴涵等值式 AB AB 13. 等价等值式等价等值式 (A B) (AB)(BA) 14. 假言易位假言易位 AB BA 15. 等价否定等值式等价否定等值式 A B A B 16. 归谬论归谬论 (AB)(AB) A 由于A,B,C可以代表任意的公式，称这样的等值式为等值式模式等值式模式，每个等值式模式都给出了无穷多个同类型的具体的等值式。例如，在蕴涵等值式中，取A=p，B=q时，得等值式 pq pq 当取A=pqr，B=pq时，得等值式 (pqr)(pq) (pqr)(pq) 这些具体的等值式都被称为原来的等值式模式的代入实例

3、代入实例。 置换规则置换规则 设(A)是含公式A的命题公式，(B)是用公式B置换了(A)中所有的A后得到的命题公式，若BA，则(B) (A). 例如：(pq)r (pq)r （蕴含等值式、置换规则）AB (pq)r （蕴含等值式、置换规则）(pq)r （得摩根律、置换规则）(pr)(qr) （分配律、置换规则）公式之间的等值关系具有自反性 A A对称性 若AB，则 B A传递性 若AB，B C ，则 A C所以上述演算中得到的公式彼此之间都是等值的。 在演算的每一步都用到了置换规则，因而在以下的演算中，置换规则均不标出。等值演算的用途： (1) 验证等值式例例2.3 用等值演算法验证等值式：

4、(pq)r (pr)(qr) 证证: 可以从左边开始演算，也可以从右边开始演算。 现在从右边开始演算。 (pr)(qr) （ p r)(q r)(p q ) r (p q ) r (pq)r 一般情况下，不能用等值演算法直接验证两个公式不等值。例2.4 证明：(pq)r p(qr)证：证： 方法一：真值表法。 方法二：观察法。易知，010是(pq)r的成假赋值，而010是p(qr)的成真赋值，所以原不等值式成立。方法三：设A=(pq)r, B=p(qr)A= (pq)r (pq)r (pq)r (pq)r B= p(qr) p(qr) pqr 容易观察到，000，010是A的成假赋值，而它们是

5、B的成真赋值。(2) 将命题公式化简及判断公式类型例2.5 用等值演算法判断下列公式的类型。永真式永真式 (pq) p q (pq) p q (p q) p) q( (p q) p) q( (p q) p) q(p p)(q p)q(1 (q p) q(q p) q(q q ) p1 p1矛盾式矛盾式(2) (p (p q) ) r (p p q ) r (p p q ) r 0 r 0 最后结果说明(3)中公式不是重言式，00，01都是成假赋值，并且也不是矛盾式，因为10，11都是成真赋值。(3) p (p q ) p)q) p (p q ) p) q) p (p p) (q p) ) q)

6、 p (0 (q p) ) q) p (q p q) p 1 p例2.6 在某次研讨会的中间休息时间，3名与会者根据王教授的口音对他是哪个省市的人进行了判断： 甲说王教授不是苏州人，是上海人 乙说王教授不是上海人，是苏州人 丙说王教授既不是上海人，也不是杭州人听完以上3人的判断后，王教授笑着说，你们3人中有一人说得全对，有一人说对了一半，另一人说得全不对。试用逻辑演算法分析王教授到底是哪里的人？解 设命题 p：王教授是苏州人。 q：壬教授是上海人。 r：王教授是杭州人。p, q, r 中必有一个真命题，两个假命题，要通过逻辑演算将真命题找出来。 设每种数字标准形都能提供很多信息，如代数式的因式

7、分解可判断代数式的根情况。逻辑公式在等值演算下也有标准形-范式 （公式的规范化）2.2 析取范式与合取范式定义定义2.22.2 命题变项及其否定统称作文字文字。仅由有限个文字构成的析取式称作简单析取式简单析取式。仅由有限个文字构成的合取式称作简单合取式简单合取式。如：p、p、pqr等是简单析取式p、p、 pqr 等是简单合取式 注注: :一个文字既是简单析取式，又是简单合取式。 为方便起见，有时用A1,A2,As表示s个简单析取式或s个简单合取式。 定理定理2.1 2.1 （1）一个简单析取式是重言式重言式当且仅当它同时含某个 命题变项及它的否定式。 （2）一个简单合取式是矛盾式矛盾式当且仅当

8、它同时含有某 个命题变项及它的否定式。证明：证明： 设Ai是含n个文字的简单析取式，若Ai中既含有某个命题变项pj，又含有它的否定式pj，由交换律、排中律和零律可知，Ai为重言式。反之，若Ai为重言式，则它必同时含某个命题变项及它的否定式，否则，若将Ai中的不带否定号的命题变项都取0，带否定号的命题变项都取1，此赋值为Ai的成假赋值，这与Ai是重言式相矛盾。如：pp，ppr都是重言式 , pq，pqr都不是重言式。 定义定义2.32.3 （1）由有限个简单合取式构成的析取式称为析取范式析取范式。 （2）由有限个简单析取式构成的合取式称为合取范式合取范式。 （3）析取范式与合取范式统称为范式范式

9、。 设Ai(i=1,2,s)为简单合取式，A=A1A2As为析取范式。 设Ai(i=1,2,s)为简单析取式，A=A1A2As为合取范式 如：A1=pq，A2=qr，A3=p则由A1,A2,A3构造的析取范式为A=A1A2A3=(pq)(qr)p 同样，取A1=pqr，A2=pq，A3=r，则由A1,A2,A3组成的合取范式为A=A1A2A3=(pqr)(pq)r 注意： pqr 既是一个简单合取式构成的析取范式，又是由三个简单析取式构成的合取范式。 同样如 pqr范式有如下性质: 定理定理2.22.2 （1）一个析取范式是矛盾式矛盾式当且仅当它的每个简单每个简单合取式都是矛盾式合取式都是矛盾

10、式。 （2）一个合取范式是重言式重言式当且仅当它的每个简单每个简单析取式都是重言式析取式都是重言式。 定理定理2.32.3 （范式存在定理范式存在定理）任一命题公式都存在着与之等值的析取范式与合取范式。 证明证明 首先，我们观察到在范式中不出现联结词与 。由蕴涵等值式与等价等值式可知 AB AB A B (AB)(AB) （第1步）因而在等值的条件下，可消去任何公式中的联结词和 其次，在范式中不出现如下形式的公式： A, (AB), (AB)对其利用双重否定律和德摩根律，可得 A A， (AB) AB， (AB) AB （第2步）再次，在析取范式中不出现如下形式的公式： A(BC) 在合取范式

11、中不出现如下形式的公式： A(BC) 利用分配律，可得 A(BC) (AB)(AC) A(BC) (AB)(AC) （第3步）由第1、2、3步，可将任一公式化成与之等值的析取范式或合取范式。 据此定理，求范式可使用如下步骤： 1.消去联结词 ， 2.否定号的消去（利用双重否定律）或内移（利用德摩根律）。 3.利用分配律：利用对的分配律求析取范式，对的分配律求合取范式。 例例2.7 求公式 (pq) r 的析取范式与合取范式： 1）先求合取范式(pq) r (pq) r （消去） (pq)r)(r(pq) （消去 ） (pq)r)(rpq) （消去） (pq)r)(pqr) （否定号内移） (p

12、r)(qr)(pqr) （对分配律）2）求析取范式 求析取范式与求合取范式的前两步是相同的，只是在利用分配律时有所不同。因而可以用（1）中前四步的结果，接着进行对分配律演算。 (pq) r (pq)r)(pqr) (pqp)(pqq)(pqr) (rp)(rq)(rr) (pqr)(pr)(qr) 第二步和第三步结果都是析取范式，这正说明命题公式的析取范式是不唯一的。同样，合取范式也是不唯一的。为了求出命题公式的唯一规范化的形式，再进一为了求出命题公式的唯一规范化的形式，再进一步的加以约束，得到主范式。步的加以约束，得到主范式。定义定义2.42.4 在含有n个命题变项的简单合取式（简单析取式）

13、中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第i位上（若命题变项无角标，就按字典顺序排列），称这样的简单合取式（简单析取式）为极小项极小项（极大项极大项）。 如： p q r , p q r极小项极小项是简单合取式，反之呢？是简单合取式，反之呢？n个命题变项共可产生2n个不同的极小项。(极大项)每个极小项都有且仅有一个成真赋值。若成真赋值所对应的二进制数转换为十进制数i，就将所对应极小项记作mi.类似地，每个极大项只有一个成假赋值，将其对应的十进制数i做极大项的角标，记作Mi。p,q形成的极小项与极大 项 p,q,r形成的

14、极小项与极大项观察一下极大项与极小项的关系？定理定理2.4 设设mi与与Mi是命题变项是命题变项p1,p2,pn形形成的极小项和极大项，则成的极小项和极大项，则 mi Mi ，Mimi 定义定义2.5 2.5 设由设由n n个命题变项构成的析取范式（合个命题变项构成的析取范式（合取范式）中所有的简单合取式（简单析取式）都是取范式）中所有的简单合取式（简单析取式）都是极小项（极大项），则称该析取范式（合取范式）极小项（极大项），则称该析取范式（合取范式）为主析取范式为主析取范式（主合取范式主合取范式）。）。 定理定理2.5 任何命题公式都存在着与之等值的主析取任何命题公式都存在着与之等值的主析取

15、 范式和主合取范式，并且是唯一的。范式和主合取范式，并且是唯一的。 证证: : 这里只证主合取范式的存在性和唯一性。 首先证明存在性。 设A是任一含n个命题变项的公式。由范式存在定理可知，存在与A等值的合取范式A，即A A，若A的某个简单析取式Ai中既不含命题变项pj，也不含它的否定式pj，则将Ai展成如下形式： Ai Ai0 Ai(pjpj) (Aipj)(Ajpj)继续这一过程，直到所有的简单析取式都含任意命题变项或它的否定式。若在演算过程中出现重复的命题变项以及极大项和重言式时，都应“消去”：如用p代替pp，Mi代替MiMi，1代替重言式等。最后就将A化成与之等值的主合取范式A。 下面再

16、证明唯一性： 假设某一命题公式A存在两个与之等值的主合取范式B和C，即AB且AC，则BC。由于B和C是不同的主合取范式，不妨设极大项Mi只出现在B中而不出现在C中。于是，角标i的二进制表示为B的成假赋值，而为C的成真赋值。这与 BC矛盾，因而B与C必相同。 为了醒目和便于记忆，求出某公式的主析取范式（主合取范式）后，将极小项（极大项）都用名称写出，并且按极小项（极大项）名称的角标由小到大顺序排列。 例例2.8 求例2.7中公式的主析取范式和主合取范式。 解解 （1）求主析取范式 :在例2.7中已给出的公式的析取范式，即（pq） r(pqr)(pr)(qr)注意，因为公式含三个命题变项，所以极小

17、项均由三个文字组成。 （pr）p（qq）r (pqr)(pqr) m1m3 qr (pp)qr (pqr）(pqr)m3m7于是 (pq) r m1m3m4m7 记作 (1，3，4，7）(2)再求主合取范式：由例2.7已求出公式的合取范式，即(pq） r (pr)(qr)(pqr)(pr) (p(qq)r)(pqr)(pqr)M0M2(qr) (pp)qr)(pqr)(pqr) M2M6 于是，(pq）r M0M2M5M6 记作（0，2，5，6）对应一个确定的命题公式，它的成真成假赋值个数是确定的，根据定理4，一旦求出公式的所有极小项，就能写出公式的所有极大项，即极小项没有出现的下标，就是极大

18、项的下标。几点说明：1、由公式的主析取范式求主合取范式。设公式A含n个命题变项， A的主析取范式含s(0s2n)个极小项即：Ami1 mi2 mi3 mis (0ij2n-1 ;j=1,2, ,s;)没出现的极小项为 mj1,mj2 ,mj2n-s,它们的角标的二进制表示为A的成真赋值，因而A的主析取范式为 Amj1 mj2 mj3 mj2n-s由双重否定定律：AA(mj1 mj2 mj3 mj2n-s) mj1 mj2 mj3 mj2n-s Mj1 Mj2 Mj3 Mj2n-s （定理4）同理，由主合取范式也可求出主析取范式。2重言式与矛盾式的主合取范式 重言式无成假赋值，因而主合取范式不含

19、任何极大项。将重言式的主合取范式记为1。而主析取范式含全部2n个极小项。矛盾式无成真赋值，因而主析取范式不含任何极小项。将矛盾式的主析取范式记为0。而主合取范式含全部2n个极大项。可满足式，它的主析取范式中至少含一个极小项。3主析取范式有多少种不同的情况 ？这与真值表相同，可以看出，真值表与主析取范式（主合取范式）是描述命题公式标准形式的两种不同的等价形式。由主析取范式（主合取范式）立刻能确定 A的真值表，反之亦然。n个命题变项2n个极小项 22n种主析取范式用途：判断两命题公式是否等值；判断命题公式的类型；求命题公式的成真、成假赋值；应用。例2.9 分析和解决实际问题。某科研所要从3名科研骨

20、干A，B，C中挑选12名出国进修。由于工作需要，选派时要满足下面3个条件，问所里应如何选派他们? ()若A去，则C同去; (2)若B去，则C不能去; (3)者C不去，则A或B可以去。2.3 联结词的完备集联结词的完备集 元函数就是有个自变量的函数。 元真值函数元真值函数就是自变量和函数值都是真值（即或）的函数。其中F的自变量为n个命题变项记作：F：0，1n 0，1定义域： 0，1n =000,001,111值域：0，1； 具体如下：元真值函数2元真值函数 2.3 联结词的完备集联结词的完备集 一般地，n元真值函数共有多少个呢？ 每个自变量有2个取值方式，n个自变量共有2n 个不同取值方式。对n

21、个自变量的每个取值方式，函数值有2个取值方式，即为0或1，故n元真值函数共22n个。 每个真值函数，都可以找到许多与之等值的命题公式。例如，3元真值函数共有256个 F13 (2)pq (pq) (pq) (pq)(pq)(pq) 。但每个真值函数与唯一的主析取（合取）范式等值。反过来，每个主析取范式对应无穷多个与之等值的公式，所以每个真值函数对应无穷多个与之等值的命题公式。由定理2.5可知，每个命题公式对应唯一的与之等值的真值函数。2.3 联结词的完备集联结词的完备集 定义定义2.7 设S是一个联结词集合，如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集联结词完备集。 定理定理2.6 S=,是联结词完备集。 2.3 联结词的完备集联结词的完备集 证证: 因为任何n(n1)元真值函数都与唯一的一个主析取范式等值，而在主析取范式中仅含联结词,，所以S=,是联结词完备集。 推论推论 以下联结词集都是完备集：(1) S1=, (2) S2=, (3) S3=, (4) S4=, (5) S5=, 证证: (1)，(2)的成立是显然的。 (3) 由于S=,是联结词完备集，因而任何真值函数都可以由仅含S中的联结词的公式表示。同时对于任意公式A,B,AB(AB) (AB),因而任意真值函数都可以由仅含S3 = ,