第二章命题逻辑的等值和推理演算

第二章命题逻辑的等值和推理演算第一页，共六十五页，2022年，8月28日等值演算(考察逻辑关系符)：1)等值定理、公式2)由真值表写命题公式(由T写、由F写)3)联结词的完备集(由个别联结词表示所有联结词的问题)4)对偶式(命题公式的对偶性)

5)范式(命题公式的统一标准)第二页，共六十五页，2022年，8月28日推理演算(考察逻辑关系符)：1)推理形式(正确推理形式的表示)2)基本推理公式(各种三段论及五种证明方法)3)推理演算(证明推理公式的第六种方法，使用推理规则)4)归结推理法(证明推理公式的第七种方法，常用反证法)第三页，共六十五页，2022年，8月28日2.1.1等值的定义

等值的定义：给定两个命题公式A和B,而P1…Pn是出现于A和B中的所有命题变项,那么公式A和B共有2n个解释,若对其中的任一解释,公式A和B的真值都相等,就称A和B是等值的(或等价的)。记作A=B或AB。注意逻辑关系词2.1等值定理

第四页，共六十五页，2022年，8月28日例1:证明(P∧P)∨Q=Q证明:画出(P∧P)∨Q与Q的真值表可看出等式是成立的。第五页，共六十五页，2022年，8月28日例2:证明P∨P=Q∨Q

证明:画出P∨P,Q∨Q的真值表,可看出它们是等值的,而且它们都是重言式。第六页，共六十五页，2022年，8月28日等值定义补充说明：两个公式等值并不要求它们一定含有相同的命题变项。若仅在等式一端的公式里有变项P出现,那么等式两端的公式其真值均与P无关。例1中公式(P∨P)∨Q与Q的真值都同P无关,例2中P∨P,Q∨Q都是重言式,它们的真值也都与P、Q无关。

第七页，共六十五页，2022年，8月28日2.1.2等值定理

定理2.1.1对公式A和B,A=B的充分必要条件是AB是重言式。

即任意解释下，A和B都有相同的真值。证明：定理中的两部分都与上一行等同。第八页，共六十五页，2022年，8月28日“＝”作为逻辑关系符是一种

等价关系A=B是表示公式A与B的一种关系。这种关系具有三个性质:1.自反性A=A。2.对称性若A=B则B=A。3.传递性若A=B,B=C则A=C。这三条性质体现了“＝”的实质含义。

第九页，共六十五页，2022年，8月28日2.2等值公式

(真值表验证，Venn图理解)2.2.1基本的等值公式(特别注意蓝色字) 1.双重否定律

P=P 2.结合律 (P∨Q)∨R=P∨(Q∨R) (P∧Q)∧R=P∧(Q∧R)

(PQ)R=P(QR)

第十页，共六十五页，2022年，8月28日3.交换律 P∨Q=Q∨P P∧Q=Q∧P PQ=QP4.分配律 P∨(Q∧R)=(P∨Q)∧(P∨R) P∧(Q∨R)=(P∧Q)∨(P∧R) P(QR)=(PQ)(PR)5.等幂律(恒等律) P∨P=P P∧P=P PP=T PP=T第十一页，共六十五页，2022年，8月28日6.吸收律 P∨(P∧Q)=P P∧(P∨Q)=P7.摩根律

(P∨Q)=P∧Q

(P∧Q)=P∨Q

对蕴涵词、双条件词作否定有

(PQ)=P∧Q

(PQ)=PQ=PQ =(P∧Q)∨(P∧Q)第十二页，共六十五页，2022年，8月28日8.同一律 P∨F=P P∧T=P TP=P TP=P

还有 PF=P FP=P第十三页，共六十五页，2022年，8月28日9.零律 P∨T=T P∧F=F

还有 PT=T FP=T 10.补余律 P∨P=T P∧P=F

还有

PP=P

PP=P PP=F第十四页，共六十五页，2022年，8月28日Venn图这种图是将P、Q理解为某总体论域上的子集合,而规定P∧Q为两集合的公共部分(交集合),P∨Q为两集合的全部(并集合),P为总体论域(如矩形域)中P的余集。

第十五页，共六十五页，2022年，8月28日Venn图实例1.P∨(P∧Q)=P 2.P∧(P∨Q)=P3.(P∨Q)=P∧Q第十六页，共六十五页，2022年，8月28日Venn图可以用来理解集合间、命题逻辑中、部分信息量间的一些关系。第十七页，共六十五页，2022年，8月28日2.2.2若干常用的等值公式

等值演算中，由于人们对、∨、∧更为熟悉，常将含有和的公式化成仅含有、∨、∧的公式。这也是证明和理解含有，的公式的一般方法。但后面的推理演算中，更希望见到和.第十八页，共六十五页，2022年，8月28日12.逆否定理PQ=QP11.PQ=P∨Q第十九页，共六十五页，2022年，8月28日13.前提合并

P(QR)=(P∧Q)R17.前提交换P(QR)=Q(PR)18.另一种前提合并(PR)∧(QR)=(P∨Q)R第二十页，共六十五页，2022年，8月28日14.从取真来描述双条件词

PQ=(P∧Q)∨(P∧Q)15.从取假来描述双条件词

PQ=(P∨Q)∧(P∨Q)16.从蕴涵词描述双条件词

PQ=(PQ)∧(QP)第二十一页，共六十五页，2022年，8月28日2.2.3置换规则

(注意与代入规则p8的区别)置换定义：对公式A的子公式,用与之等值的公式来代换便称置换。置换规则：将公式A的子公式置换后，A化为公式B,必有A=B。置换与代入是有区别的：代入规则要求操作重言式、对所有同一命题变元都作代换第二十二页，共六十五页，2022年，8月28日2.2.4等值演算举例

例1:证明(P∧(Q∧R))∨(Q∧R)∨(P∧R)=R

证明:

左端=(P∧(Q∧R))∨((Q∨P)∧R) (分配律) =((P∧Q)∧R))∨((Q∨P)∧R) (结合律) =((P∨Q)∧R)∨((Q∨P)∧R) (摩根律) =((P∨Q)∨(Q∨P))∧R (分配律) =((P∨Q)∨(P∨Q))∧R (交换律) =T∧R (置

换) =R (同一律)

第二十三页，共六十五页，2022年，8月28日例2:试证((P∨Q)∧(P∧(Q∨R)))

∨(P∧Q)∨(P∧R)=T

证明:

左端=((P∨Q)∧(P∨(Q∧R)))∨((P∨Q)∧(P∨R)) (摩根律) =((P∨Q)∧(P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R)) (分配律) =((P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R)) (等幂律) =T (置换规则)

第二十四页，共六十五页，2022年，8月28日问题提出：由命题公式写真值表是容易的，那么如何由真值表写命题公式呢？2.3命题公式与真值表关系第二十五页，共六十五页，2022年，8月28日2.3.1从T来列写1.记忆方法：各项间用∨，每项内用∧2.每项内书写方法：例真值表中P=F且Q=F等价于P∧Q=T3.简化方法：有时A的表达通过A来描述第二十六页，共六十五页，2022年，8月28日2.3.2从F来列写1.记忆方法：各项间用∧

，每项内用∨2.每项内书写方法：例真值表中P=T且Q=F等价于P∨Q=F3.简化方法：有时A的表达通过A来描述4.任意值的问题(图2.3.1)第二十七页，共六十五页，2022年，8月28日2.4联结词的完备集

问题的提出：对n个命题变项P1…Pn来说,共可定义出多少个联结词?在那么多联结词中有多少是相互独立的?

介绍3个新型联结词：

异或

∨:P∨Q=(P∧Q)∨(P∧Q)与非

:PQ=(P∧Q)或非

:PQ=(P∨Q)第二十八页，共六十五页，2022年，8月28日2.4.1命题联结词的个数要解决本节提出的第一个问题，首先要把n个命题变项构造出的无限多个合式公式分类。将等值的公式视为同一类，从中选一个作代表称之为真值函项。对一个真值函项，或者说对于该类合式公式，就可定义一个联结词与之对应。

第二十九页，共六十五页，2022年，8月28日例：一元联结词是联结一个命题变项(如P)的。P有真假2种值，因此P(自变量)上可定义4种一元联结词(真值函项、函数)：真值表见图。 f0 f1 f2 f3或称 f0(P)f1(P)f2(P)f3(P)第三十页，共六十五页，2022年，8月28日由真值表写出真值函项的命题公式： f0(P)=F f1(P)=P f2(P)=P f3(P)=T第三十一页，共六十五页，2022年，8月28日例：二元联结词联结两个命题变项(如P、Q)，两个变项共有4种取值情形,于是P、Q上可建立起16种不同的真值函项,相应的可定义出16个不同的二元联结词g0,g1,…,g15

图2.4.2给出了这些联结词gi或说真值函项gi(P,Q)的真值表定义。

第三十二页，共六十五页，2022年，8月28日第三十三页，共六十五页，2022年，8月28日根据真值表写出各真值函项的命题表达式: g0(P,Q)=F g1(P,Q)=P∧Q g2(P,Q)=P∧Q g3(P,Q)=(P∧Q)∨(P∧Q)=P∧(Q∨Q)=P g4(P,Q)=P∧Q g5(P,Q)=(P∧Q)∨(P∧Q)=(P∨P)∧Q=Q g6(P,Q)=P∨Q g7(P,Q)=P∨Q g8(P,Q)=P∧Q=PQ g9(P,Q)=PQ g10(P,Q)=(P∧Q)∨(P∧Q)=(P∨P)∧Q=Q g11(P,Q)=P∨Q=QP g12(P,Q)=(P∧

Q)∨(P∧Q)=P∧(Q∨Q)=P g13(P,Q)=P∨Q=PQ g14(P,Q)=P∨Q=PQ g15(P,Q)=T第三十四页，共六十五页，2022年，8月28日联结词个数统计：对n个命题变元P1…Pn,,每个Pi有两种取值,从而对P1…Pn来说共有2n种取值情形。于是相应的直值函项就有22n个,或说可定义22n个n元联结词。第三十五页，共六十五页，2022年，8月28日2.4.2联结词的完备集

关于本节提出的第二个问题，也就是说这些联结词是否能相互通过组合来表示呢?联结词的完备集定义:

设C是联结词的集合，如果对任一命题公式(能直接使用T和F)都有由C中的联结词表示出来的公式(不能直接使用T和F)与之等值，就说C是完备的联结词集合，或说C是联结词的完备集。第三十六页，共六十五页，2022年，8月28日书上的8个完备集(提问)：1.显然全体联结词的无限集合是完备的。

2.定理:{,∨,∧}是完备的联结词集合。

证明：从2.3节介绍的由真值表列写逻辑公式的过程可知,任一公式都可由,∨,∧表示出来,从而{,∨,∧}是完备的。

8.{,∧,∨,,}是完备的,因为它包含了2中的集合。另外，{∨,∧,,}不是完备的，因为F不能仅由该集合的联结词表达出来。{,}也不是完备的。第三十七页，共六十五页，2022年，8月28日3.{,∨},4.{,∧}都是联结词的完备集。证明：P∧Q=(P∨Q) P∨Q=(P∧Q)这说明,∧可由{,∨}表示,∨可由{,∧}表示,故由定理2.4.1可证本结论。5.{,}是完备集。证明：

6.{}是完备集。证明：

7.{}是完备集。证明：第三十八页，共六十五页，2022年，8月28日特别注意如果一个联结词的集合是不完备的，那么它的任何子集都是不完备的。因此，{∨,∧,,}的任何子集都是不完备的。{,}的任何子集也是不完备的。由此可推知，集合3,4,5,6,7都是独立的完备集。事实上，6,7是仅有的两个只有一个联结词的完备集(不证).{∨,∧}不是完备的(不证).第三十九页，共六十五页，2022年，8月28日2.5对偶式

新符号“对偶式”：将A中出现的∨、∧、T、F分别以∧、∨、F、T代换,得到公式A*,则称A*是A的对偶式,或说A和A*互为对偶式。

若A=B必有A*=B*?对仅含、∨、∧三个联结词的公式考察相似性第四十页，共六十五页，2022年，8月28日新符号“-”：若A=A(P1,…,Pn)令A－=A(P1,…,Pn)关于等值的三个定理(这不是2.1节的等值定理)定理2.5.1(A*)=(A)*, (A－)=(A)－

定理2.5.2(A*)*=A,(A－)－=A定理2.5.3摩根律

A=A*－可用数学归纳法,施归纳于A中出现的联结词个数n来证明。第四十一页，共六十五页，2022年，8月28日定理2.5.4若A=B必有A*=B*证明:因为A=B等价于AB永真等价于AB永真。依定理2.5.3,A=A*－,B=B*－

于是A*－

B*－永真必有A*B* 永真故 A*=B*关于推理的三个定理第四十二页，共六十五页，2022年，8月28日定理2.5.5若AB永真,必有B*A*永真定理2.5.6A与A－同永真,同可满足

A与A*同永真,同可满足注意：“A与B同永真,同可满足”的意思是：A永真可推出B永真,反之亦然。第四十三页，共六十五页，2022年，8月28日2.6范式(命题的统一形式)n个命题变项所能组成的具有不同真值表的命题公式仅有22n个,然而与任何一个命题公式等值而形式不同的命题公式可以有无穷多个。这些等值的公式，能否都可以化为某一个统一的标准形式?第四十四页，共六十五页，2022年，8月28日2.6.1范式好多新概念文字、合取式、析取式、互补对、析取范式、合取范式范式定理：任一命题公式都存在与之等值的析取范式、合取范式。求范三步曲：1)消去和2)否定深入到变元3)使用分配律的等值变换第四十五页，共六十五页，2022年，8月28日范式功能：判断两公式是否等值(参主范式)；判断重言式：合取范式中所有析取式都有互补对；判断矛盾式：析取范式中所有合取式都有互补对；第四十六页，共六十五页，2022年，8月28日2.6.2主范式主析取范式极小项定义与编码：主析取范式定义主析取范式唯一性定理由真值表写主析取范式(从T写)，例3由析取范式写主析取范式，例4第四十七页，共六十五页，2022年，8月28日极小项性质所有极小项的个数极小项为真的唯一解极小项互不相同坐标系功能A与

A的主析取范式关系第四十八页，共六十五页，2022年，8月28日主合取范式极大项定义：主合取范式定义主合取范式唯一性定理由真值表写主合取范式(从F写)，例5由合取范式写主合取范式，例6第四十九页，共六十五页，2022年，8月28日极大项性质所有极大项的个数极大项为假的唯一解极大项互不相同坐标系功能A与

A的主合取范式关系第五十页，共六十五页，2022年，8月28日主析取范式与主合取范式的转化参见板书！！注意补集与数字补的不同含义。第五十一页，共六十五页，2022年，8月28日2.7推理形式1.通过蕴涵词建立正确(即条件真时，结论必真)或不正确的推理形式例：((PQ)∧P)Q是正确的推理形式

((PQ)∧Q)P是正确的推理形式

((PQ)∧P)Q是不正确的推理形式第五十二页，共六十五页，2022年，8月28日2.正确推理形式的书写方法使用逻辑关系词：重言蕴涵AB表示命题A为真时命题B一定为真3.重言蕴涵的进一步应用(与2.8.1推理公式不同，是一些推理规则即证明推理公式的方法)第五十三页，共六十五页，2022年，8月28日如果AB,A为重言式，则B也是重言式。如果AB，BA同时成立，必有A=B。如果AB，BC，则AC。如果AB，AC，则AB∧C。如果AC，BC，则AB

C。第五十四页，共六十五页，2022年，8月28日2.8基本的推理公式1.(PÙQ)

P

化简律2.Ø(P®Q)P3.Ø(P®Q)

ØQ4.P

(PÚQ)附加律5.ØPP®Q6.Q

P®Q7.(PÚQ)ÙØP

Q

析取三段论8.(P®Q)ÙP

Q假言推理、分离规则注意2、3、5、6的关系第五十五页，共六十五页，2022年，8月28日9.(P®Q)ÙØQ

ØP

拒取式10.(P®Q)Ù(Q®R)(P®R)假言三段论、三段论11.(P«Q)Ù(Q«R)(P«R)等价三段论12.(P®R)Ù(Q®R)Ù(PÚQ)

R

构造性二难(特殊形式)13.(P®Q)Ù(R®S)Ù(PÚR)(QÚS)构造性二难14.(P®Q)Ù(R®S)Ù(ØQÚØS)(ØPÚØR)破坏性二难15.(Q®R)((PÚQ)®(P

ÚR))16.(Q®R)((P®Q)®(P®R))第五十六页，共六十五页，2022年，8月28日2.8.2证明推理公式的5种方法定理2.8.1AB成立的充分必要条件是AB为重言式。注意：2)证明AB为重言式的方法：等值演算、主析取范式、真值表第五十七页，共六十五页，2022年，8月28日例1用等值演算法证明(p®q)Ùp®q为重言式

(p®q)Ùp®q

Û

Ø((ØpÚq)Ùp)ÚqÛ((pÙØq)ÚØp)Úq

Û

ØpÚØqÚq

ÛT第五十八页，共六十五页，2022年，8月28日例2用主析取范式法证明(p®q)Ùq®p不是重言式(p®q)Ùq®p

Û(ØpÚq)Ùq®p

Û

Ø((ØpÚq)Ùq)Úp

Û

ØqÚp

Û(ØpÙØq)Ú(pÙØq)Ú(pÙØq)Ú(pÙq)

Û

m0Úm2Úm3缺少m1即ØpÙq,所以(p®q)Ùq®p不是重言式，或者说推理形式(p®q)Ùq®p不正确。第五十九页，共六十五页，2022年，8月28日2.定理2.8.2AB