第二章 命题逻辑等值演算

1、第二章第二章 命题逻辑等值演算命题逻辑等值演算本章的主要内容：本章的主要内容：v 等值式与重言蕴涵式等值式与重言蕴涵式v 公式的标准型公式的标准型-范式范式v 联结词完备集联结词完备集本章与其他各章的联系本章与其他各章的联系v是第一章的抽象与延伸是第一章的抽象与延伸v是后续各章的先行准备是后续各章的先行准备 2.12.1等值式和重言蕴涵式和重言蕴涵式一、等值式与基本的等值式1 1等值式等值式定义定义2.12.1 若等价式若等价式AB是重言式，则称是重言式，则称A与与B等值，等值，记作记作AB，并称，并称AB是等值式。是等值式。注意：注意：（1 1）符号）符号“”与与“”的区别与联系。的区别与联

2、系。 “”不是联结词，不是联结词，AB不表示一个公式，它不表示一个公式，它表示两个公式间的一种关系，即等值关系。表示两个公式间的一种关系，即等值关系。 “”是联结词，是联结词，AB是一个公式。是一个公式。 AB当且仅当当且仅当AB是重言式。是重言式。（2）可以验证等值关系是等价关系。）可以验证等值关系是等价关系。（3）当）当A是重言式时，是重言式时，A1；当；当A是矛盾式时，是矛盾式时，则则A0。可传递性：可传递性：对任意公式对任意公式A,B,C，若，若AB，BC，则则AC。 对称性：对称性：对任意公式对任意公式A,B，若，若AB，则，则BA。自反性：自反性：对任意公式对任意公式A，有，有AA

3、。2. 基本的等值式双重否定律双重否定律 AA幂等律幂等律 A AA, A AA交换律交换律 A BB A, A BB A结合律结合律 (A B) CA (B C), (A B) CA (B C)分配律分配律 A (B C) (A B) (A C), A (B C) (A B) (A C)德摩根律德摩根律 (A B)AB (A B)AB吸收律吸收律 A (A B)A, A (A B)A零律零律 A 11, A 00同一律同一律 A 0A. A 1A排中律排中律 AA1矛盾律矛盾律 AA0蕴涵等值式蕴涵等值式 ABA B等价等值式等价等值式 AB(AB) (BA)假言易位假言易位 ABBA等价否

4、定等值式等价否定等值式 ABAB归谬论归谬论 (AB) (AB) A注意：要牢记各个等值式，这是继续学习的基础注意：要牢记各个等值式，这是继续学习的基础3. 3. 等值式的判别等值式的判别例例 用真值表法证明用真值表法证明 ： (p q) pq解解 令：令：A= (p q)，B= pq，构造，构造A，B 以及以及A B的真值表如下：的真值表如下：由于公式由于公式AB所标记的列全为所标记的列全为1，因此，因此AB。 pqp q (p q) p q pqAB00011111011010011110010110100001(1)(1)真值表法真值表法例例 用真值表法证明：用真值表法证明：p pq q

5、p p q q解解 令令A=pq，B= p q 构造构造A，B以及以及AB的真值表如下：的真值表如下：由于公式由于公式AB所标记的列全为所标记的列全为1，因此，因此AB.pq p p qpqAB001111011111100001110111例例 用真值表法判断用真值表法判断pqpq是否成立是否成立.解解 令令A=pq，B= pq 构造构造A，B以及以及AB的真值表的真值表由于公式由于公式AB所标记的列不全为所标记的列不全为1，AB不不是重言式，因此是重言式，因此AB不成立。不成立。pq p q pqpqAB0011111011001001100101100111 代入规则代入规则 对于重言式

6、中的任一命题变元出对于重言式中的任一命题变元出现的现的每一处每一处均用均用同一命题公式同一命题公式代入，得到的仍代入，得到的仍是重言式。是重言式。(2)(2)等值演算法等值演算法例：例： ( p q )( q p )AB AB 置换规则置换规则 设设 (A)是含公式是含公式A的命题公式，的命题公式， (B)是用公式是用公式B置换了置换了 (A)中的所有的中的所有的A后得到后得到的命题公式，若的命题公式，若BA，则，则 (B)(A)等值演算等值演算 等值演算是指利用已知的一些等等值演算是指利用已知的一些等值式，根据值式，根据置换规则置换规则、代入规则代入规则以及以及等值关系等值关系的可传递性的可

7、传递性推导出另外一些等值式的过程。推导出另外一些等值式的过程。 (A)(pq) r (B)( pq) rpqpq(pq) r( pq) r例如：例如：例：例：证明下列等值式：证明下列等值式： (p q ) ( p ( p q ) ) p q证明：证明： (p q) ( p ( p q) (p q) ( ( p p ) q ) (结合律结合律) (p q) ( p q) (幂等律幂等律) ( p q ) ( p q ) (交换律交换律) p (q (p q) (结合律结合律) p q (吸收律吸收律) 例：例：证明等值式：证明等值式：（pq）（rq）（pr）q证明证明：(pq）（rq）（ pq）

8、( rq) (蕴涵等值式蕴涵等值式 )（ p r）q (分配律分配律) (pr)q (德摩根律德摩根律) (pr) q (蕴涵等值式蕴涵等值式 )所以所以（pq）（rq）（pr）q例：例：将下面程序语言进行化简：将下面程序语言进行化简：if A then if B then X else Y if B then X else Y解：解：该程序流程图如下：该程序流程图如下： StartABBXYEndFTFTFT执行执行X的条件：的条件：(AB)( AB)B (A A)B 执行执行Y的条件：的条件：(A B)( A B)B(A A)BStartBXYEndTF化简结果：化简结果：if B the

9、n X else Y练习：练习：用等值演算法证明下列等值式：用等值演算法证明下列等值式：(1)q(pr) (pq) r(2) （pq）（p q）（ pq）解（1） (pq) r （2）（）（p q）（ pq） (（ pq）（ qp）) (（pq）（qp）) （pq）(pq)r ( p q) r q( pr) q(pr) 二、重言蕴涵式与基本重言蕴涵式二、重言蕴涵式与基本重言蕴涵式注意：注意：符号符号“”和和 “ “”的区别和联系与的区别和联系与符号符号“”与与“”的区别和联系类似。的区别和联系类似。 “”不是联结词，不是联结词，“AB”不是公式，它表示不是公式，它表示公式公式A与与B之间存在之

10、间存在蕴涵关系。蕴涵关系。 “”是联结词，是联结词，AB是一个公式。是一个公式。 AB当且仅当当且仅当AB是重言式是重言式 。1.定义定义 设设A，B是两个公式，若公式是两个公式，若公式AB是重言是重言式，即式，即AB1，则称公式，则称公式A蕴涵公式蕴涵公式B，记作，记作AB。称。称“AB”为重言蕴涵式。为重言蕴涵式。 AB是偏序关系是偏序关系即即 自反性：自反性：AA 反对称性：反对称性：若若AB，BA，则，则AB 传递性：传递性：若若AB，BC，则，则 AC反对称性的证明：反对称性的证明：AB1且且BA1于是于是AB(AB) (BA) 1 1 1因此因此 AB设设AB且且BA， 传递性的证

11、明：传递性的证明：则则AB1，BC1 ( A B C) ( AB C) (AB) C) ( A (BC) (1 C) ( A 1) 1 1 1因此因此 AC.于是于是 AC A C ( A C) (BB) 设设AB，BC， 2.基本重言蕴涵式基本重言蕴涵式附加律附加律 A (A B) B (A B)化简律化简律 (A B) A (A B) B假言推理假言推理 (AB) A B 拒取式拒取式 (AB)B A析取三段论析取三段论 (A B)B A假言三段论假言三段论 (AB) (BC) (AC)等价三段论等价三段论 (AB) (BC) (AC)构造性二难构造性二难 (AB) (CD) (A C)

12、(B D) (AB) ( AB) (AA) B破坏性二难破坏性二难 (AB) (CD) ( BD) ( AC)3.3.重言蕴涵式的判别重言蕴涵式的判别 判定判定“A B”是否成立的问题可转化为判定是否成立的问题可转化为判定A B是否为重言式，有下述判定方法：是否为重言式，有下述判定方法：（1 1）真值表法；）真值表法； （2 2）等值演算法；）等值演算法；（3 3）假定前件）假定前件A A为真；（为真；（4 4）假定后件）假定后件B B为假。为假。(1) (1) 真值表法真值表法例例 证明证明 ：(（pq）（p r）（q r）) r证明证明 令令 F =（pq）（pr）（qr）r，公式公式F对

13、任意的一组赋值取值均为对任意的一组赋值取值均为1，故，故F是重言是重言式，所以上述重言蕴涵式成立。式，所以上述重言蕴涵式成立。p q rpq pr q r (pq) (pr）（ q r）F0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 10 00 01 11 11 11 11 11 11 11 11 11 10 01 10 01 11 11 10 01 11 11 10 01 10 00 00 01 10 01 10 01 11 11 11 11 11 11 11 11 1(2) (2) 等值演算法等值演算法例：例：证明证明 ：p（pq） q 证明：证明：（p（p

14、q） q （p（ pq） q （蕴涵等值式）（蕴涵等值式） （ p （ pq）q （德摩根律）（德摩根律） （ pq） （ pq）（交换律、结合律）（交换律、结合律） 1 （排中律）（排中律） 因此因此 p（pq） q (3)(3) 假定前件假定前件A A为真为真例：例：证明证明 : : q （pq） p证明：证明：令前件令前件 q（pq）为真，）为真，则则 q为真为真, 且且pq为真。为真。于是于是q为假，因而为假，因而p也为假。由此也为假。由此 p为真。为真。故重言蕴涵式故重言蕴涵式 q （pq） p成立。成立。 假定前件假定前件A为真为真,检查在此情况下检查在此情况下,其后件其后件B是否

15、也为真。是否也为真。 ABA B001011100111 1 1 1 (4) (4) 假定后件假定后件B B为假为假 假定后件假定后件B为假，检查在此情况下，其前件为假，检查在此情况下，其前件A是是否也为假否也为假. 0 0 1ABA B001011100111例：例： (pq) (rs) (p r) (q s)证明证明:令后件令后件(p r)(q s)为假，则为假，则p r为真，为真，q s为假为假,于是于是p、r均为真，而均为真，而q和和s至少一个为假。至少一个为假。 由此可知由此可知 pq与与rs中至少一个为假中至少一个为假, 因此因此(pq) (rs)为假为假.故上述重言蕴涵式成立。故

16、上述重言蕴涵式成立。练习：练习：判定判定p（qr） （pq）（pr）是否成立）是否成立.(1)(1)真值表法真值表法: : 令令F=p（qr） （pq）（pr）p q r pq pr qr p(qr) (pq)(pr) F0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1111100111111010111011101111111011111110111111111(2)等值演算法p(qr)(pq)(pr)( p ( q r) ( ( p q) ( p r)(p (qr) (pq) ( p r) (p qr) (pp r) ( qp r) (p qr) ( pq

17、r) (p qr) (p q r)1(3)(3)假定后件（假定后件（pq）（pr）为假）为假则则pq为真，为真，pr为假。为假。由由pr为假为假,得得p为真，为真，r为假。为假。又又pq为真，故得为真，故得q为真。为真。于是于是p为真，为真，qr为假。为假。从而从而 前件前件p（qr）为假。）为假。因此重言蕴涵式成立。因此重言蕴涵式成立。(4)(4)假定前件假定前件p(qr)为真为真经过分析之后，经过分析之后，p,q,r的取值分别如下表所示：的取值分别如下表所示：p q rpqpr(pq)(pr)（后件后件）0 0 01110 0 11110 1 01110 1 11111 0 00011 0

18、 10111 1 1111后件为真，从而重言蕴涵式成立。后件为真，从而重言蕴涵式成立。等值和重言蕴涵的关系：等值和重言蕴涵的关系：证明等值式证明等值式A AB B的方法：的方法：AB 当且仅当当且仅当A B且且 B A .1) 真值表法真值表法2) 等值演算法等值演算法3) 证明证明A B且且 B A练习：练习：不构造真值表证明下式：不构造真值表证明下式：(1)(ab)(bc)(ca)(ab)(bc)(ca)(2) (pq) qpq解：解： (1)(ab)(bc)(ca)(b(ac)(ca)(b(ca)(ac)(ca)(bc)(ba)(ac)(ab)(bc)(ca)(2)假定后件假定后件pq为

19、假，则为假，则p,q均为假，所以均为假，所以pq为为真，从而前件真，从而前件(pq) q为假，因此为假，因此(pq) qpq成立。成立。 由等值式可知，同一命题公式可以有各种相互由等值式可知，同一命题公式可以有各种相互等值的表达形式，为了把命题公式规范化，需等值的表达形式，为了把命题公式规范化，需要研究公式的范式问题。要研究公式的范式问题。 如果公式中的变元数目较大时，对于公式的判如果公式中的变元数目较大时，对于公式的判定问题，真值表将非常繁琐。每增加一个变元，定问题，真值表将非常繁琐。每增加一个变元，计算将增加一倍。研究公式的标准型问题变得计算将增加一倍。研究公式的标准型问题变得十分重要。十

20、分重要。 给定任意一个命题公式，我们希望寻找其某种给定任意一个命题公式，我们希望寻找其某种一般的标准的形式，即范式一般的标准的形式，即范式(normal form) 。2.2 2.2 公式的标准型公式的标准型-范式范式1.1.基本概念基本概念（1）文字）文字命题变项及其否定的总称命题变项及其否定的总称（2）简单析取式）简单析取式有限个文字构成的析取式有限个文字构成的析取式p, q, pq, p q r, （3）简单合取式）简单合取式有限个文字构成的合取式有限个文字构成的合取式p, q, pq, p q r, （4）析取范式）析取范式由有限个简单合取式组成的析取由有限个简单合取式组成的析取式式

21、A1 A2Ar (r 1)（5）合取范式）合取范式由有限个简单析取式组成的合取由有限个简单析取式组成的合取式式 A1 A2Ar (r 1)（6）范式）范式析取范式与合取范式的总称析取范式与合取范式的总称一、析取范式与合取范式一、析取范式与合取范式说明：说明：（1）单个文字既是简单析取式，又是简）单个文字既是简单析取式，又是简单合取式单合取式（2）形如）形如pq r, p qr的公式既是的公式既是析取范式，又是合取范式析取范式，又是合取范式.2.2.主要性质主要性质定理定理2.12.1 （1）一个简单析取式是重言式当且仅当它同时）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式。含

22、某个命题变项及它的否定式。（2）一个简单合取式是矛盾式当且仅当它同时）一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定式。含某个命题变项及它的否定式。定理定理2.22.2 （1）一个析取范式是矛盾式当且仅当它的每个）一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。简单合取式都是矛盾式。（2）一个合取范式是重言式当且仅当它的每个）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。简单析取式都是重言式。3 3定理定理2.3 (2.3 (范式存在定理范式存在定理) )任何命题公式都存在着与之等值的析取范任何命题公式都存在着与之等值的析取范式与合取范式式与合取范式. .求

23、公式求公式A A的范式的步骤：的范式的步骤：（1）消去）消去A中的中的, （若存在）（若存在）（2）否定联结词）否定联结词 的内移或消去的内移或消去（3）使用分配律）使用分配律 对对 分配（析取范式）分配（析取范式） 对对 分配（合取范式）分配（合取范式）例例: :求下列公式的析取范式、合取范式求下列公式的析取范式、合取范式（1） ( p (qr) ) s解：解：( p (qr) ) s ( p ( q r) ) s (p ( q r) s p ( q r) s p (q r) s 析取范式析取范式 （ p s) (q r) （ p s q ) ( p s r) 合取范式合取范式（2） (p

24、q) (p q)解：解： (p q) (p q) (p q) (p q) (p q) (p q) ( pq) (p q) (p q) ( pq) pq p q (pp) (pq) (qp) (qq) ( 0 0 ) 0 (pq) (qp) 0 (pq) (qp) 析取范式析取范式(p q) ( pq) 合取范式合取范式（1）一个命题公式的合取、析取范式不是唯一）一个命题公式的合取、析取范式不是唯一的。的。 例如：例如：p (q r) (p q) (p r) (p p) (p r) (q p) (q r) 仍然得到公式的不同等值形式。仍然得到公式的不同等值形式。（2）为了使任意一个公式，化成惟一

25、的等值）为了使任意一个公式，化成惟一的等值形式，引入主范式的概念。形式，引入主范式的概念。注意：注意：定义定义2.4 2.4 在含有在含有n个命题变项的简单合取式（简单析取个命题变项的简单合取式（简单析取式）中，若每个命题变项均以文字的形式在式）中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第其中出现且仅出现一次，而且第i（1 i n）个文字出现在左起第个文字出现在左起第i位上，称这样的简单合位上，称这样的简单合取式（简单析取式）为极小项（极大项）取式（简单析取式）为极小项（极大项）.二、主析取范式与主合取范式二、主析取范式与主合取范式1.1.极小项与极大项极小项与极大项几点说明

26、：几点说明：(1) n个命题变项产生个命题变项产生2n个极小项和个极小项和2n个极大项个极大项;(2) 2n个极小项（极大项）均互不等值个极小项（极大项）均互不等值;(3) 用用mi表示第表示第i个极小项，其中个极小项，其中i是该极小项成是该极小项成真赋值的十进制表示真赋值的十进制表示. Mi表示第表示第i个极大项，其个极大项，其中中i是该极大项成假赋值的十进制表示是该极大项成假赋值的十进制表示, mi（Mi）称为极小项（极大项）的名称称为极小项（极大项）的名称. 由p, q两个命题变项形成的极小项与极大项由下表给出极小项极大项公式成真赋值名称公式成假赋值名称pqpqpqpq 0 0 0 1

27、1 0 1 1 m0m1m2m3 pq pq pqpq 0 0 0 1 1 0 1 1M0M1M2M3由p, q, r三个命题变项形成的极小项与极大项由下表给出. mi与Mi的关系：mi Mi, Mi mi 极小项极大项公式成真赋值名称公式成假赋值名称p q rp q rp q rp q rp q rp q rp q rp q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 m0m1m2m3m4m5m6m7 p q r p q r p q r p q r p q r p q r p q r p q r0 0 00 0 10 1 00 1 11 0 01 0

28、11 1 01 1 1M0M1M2M3M4M5M6M72 2主析取范式与主合取范式主析取范式与主合取范式（1 1）定义）定义2.52.5 主析取范式主析取范式由极小项构成的析取范式由极小项构成的析取范式主合取范式主合取范式由极大项构成的合取范式由极大项构成的合取范式例如，例如，n=3, 命题变项为命题变项为p, q, r时，时，( p q r) ( p q r) m1 m3 主析取范式主析取范式 ( p q r) (p q r) M7 M1 主合取范式主合取范式（2 2）主范式的存在惟一定理）主范式的存在惟一定理定理定理2.52.5 任何命题公式都存在着与之等值的主任何命题公式都存在着与之等值

29、的主析取范式和主合取范式析取范式和主合取范式,并且是惟一的。并且是惟一的。（3 3）主析取范式与主合取范式的求法）主析取范式与主合取范式的求法在真值表中，一个公式的真值为在真值表中，一个公式的真值为1（0）的赋值）的赋值所对应的极小（大）项的析（合）取，即为此所对应的极小（大）项的析（合）取，即为此公式的公式的主析（合）取范式。主析（合）取范式。pq rG0 000001 10 10001111000101011011 111 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 1（1）求主析取范式）求主析取范式(pq)r (p q) r （析取范式）（析取范式） (p q) (p q

30、) ( r r)(p qr) (p q r)m6 m7 r ( p p) ( q q) r ( pq r) ( p q r) (pq r) (p q r) m1 m3 m5 m7 , 代入代入并排序，得并排序，得(pq)r m1 m3 m5 m6 m7 （主析取范式）（主析取范式）例例 求公式 A=(pq)r的主析取范式与主合取范式.（2）求）求A的主合取范式的主合取范式(pq)r (p r) (q r) （合取范式）（合取范式） p r p (qq) r (p q r) (pq r) M0 M2 q r (pp) q r (p q r) ( p q r)M0 M4 , 代入代入并排序，得并排

31、序，得(pq)r M0 M2 M4 （主合取范式）（主合取范式）3. 3. 范式的用途范式的用途（1）求公式的成真与成假赋值）求公式的成真与成假赋值 (pq)r m1 m3 m5 m6 m7， 其成真赋值为001, 011, 101, 110, 111，当然成假赋值为000, 010, 100. 类似地，由主合取范式也立即求出成假或成真赋值. （2）判断公式的类型）判断公式的类型设设A含含n个命题变项个命题变项. A为重言式为重言式 A的主析取范式含的主析取范式含2n个极小项个极小项 A的主合取范式为的主合取范式为1.A为矛盾式为矛盾式 A的主析取范式为的主析取范式为0 A的主合析取范式含的主

32、合析取范式含2n个极大项个极大项A为非重言式的可满足式为非重言式的可满足式 A的主析取范式中至少含一个（但不是全部）极小项的主析取范式中至少含一个（但不是全部）极小项 A的主合取范式中至少含一个（但不是全部）极大项的主合取范式中至少含一个（但不是全部）极大项（3）判断两个公式是否等值）判断两个公式是否等值例例 用主析取范式判断两个公式是否等值用主析取范式判断两个公式是否等值 p(qr) 与与 (p q)r p(qr) 与与 (pq)r解：解： p(qr) = m0 m1 m2 m3 m4 m5 m7 (p q)r = m0 m1 m2 m3 m4 m5 m7 (pq)r = m1 m3 m4

33、m5 m7显见，显见，中的两公式等值，而中的两公式等值，而的不等值的不等值.（4）解实际问题）解实际问题例：某科研所要从例：某科研所要从3名科研骨干名科研骨干A,B,C中挑选中挑选12名出国进修。由于工作需要，选派时要名出国进修。由于工作需要，选派时要满足以下条件：满足以下条件：（1）若）若A去，则去，则C同去；同去；（2）若）若B去，则去，则C不能去；不能去；（3）若）若C不去，则不去，则A或或B可以去。可以去。问所里应如何选派他们？问所里应如何选派他们？三、对偶三、对偶命题等价公式多数成对出现，是对偶性质的体命题等价公式多数成对出现，是对偶性质的体现。现。例如：例如： p (p q)p；p

34、 (p q)p利用对偶性质，可以扩大等价公式的个数，减利用对偶性质，可以扩大等价公式的个数，减少证明次数。少证明次数。1. 1. 定义定义 (p 0) (p 1) 3.3.由公式的主析取范式求主合取范式，反之亦然。由公式的主析取范式求主合取范式，反之亦然。例：例：由公式的主析取范式，求主合取范式：由公式的主析取范式，求主合取范式：（1）Am1 m2 (A中含两个命题变项中含两个命题变项p,q)（2）B m1 m2 m3 (B中含命题变项中含命题变项p,q,r)解：解：（1）AM0 M3 （2）B M0 M4 M5 M6 M72.3 2.3 联结词的完备集联结词的完备集一、真值函数一、真值函数1问题的提出问题的提出问：含问：含n个命题变项的所有公式共产生多少个命题变项的所有公式共产生多少个互不相同的真值表？个互不相同的真值表？n22答案为 个，为什么？2真值函数的定义称定义域为称定义域为000, 001, , 111，值域为，值域为0,1的函数为的函数为n元真值函数，定义域中的元素元真值函数，定义域中的元素为为2n个长为个长为n的的0,1组成的符号串组成的符号串. 常用常用F:0,1n0,1 表示表示F是是n元真值函数元真值函数. 易知，全体易知，全体n元函数共有元函数共有 个个. 设设F:0,1n0,1，且，且F(0