1、第二章第二章 命题逻辑的等值和推理演算命题逻辑的等值和推理演算 o 推理形式推理形式和和推理演算推理演算是数理逻辑研究的基本是数理逻辑研究的基本内容内容 o 推理形式推理形式是由前提和结论经蕴涵词联结而成是由前提和结论经蕴涵词联结而成的的o 推理过程是从推理过程是从前提前提出发，根据所规定的出发，根据所规定的规则规则来推导出来推导出结论结论的过程的过程 o 重言式重言式是重要的逻辑规律，正确的推理形式、是重要的逻辑规律，正确的推理形式、等值式都是重言式等值式都是重言式1谢谢观赏2019-8-23o 本章对命题等值和推理演算进行讨论，是以本章对命题等值和推理演算进行讨论，是以语义的观点进行的非形
2、式的描述语义的观点进行的非形式的描述，不仅直观，不仅直观且容易理解，也便于实际问题的逻辑描述和且容易理解，也便于实际问题的逻辑描述和推理。推理。o 严格的形式化严格的形式化的讨论见第三章所建立的公理的讨论见第三章所建立的公理系统。系统。2谢谢观赏2019-8-23等值演算等值演算(考察逻辑关系符考察逻辑关系符(=)o 等值定理、公式等值定理、公式o 联结词的完备集联结词的完备集(由个别联结词表示所有联由个别联结词表示所有联结词的问题结词的问题)o 对偶式对偶式(命题公式的对偶性命题公式的对偶性)o 范式范式(命题公式的统一标准命题公式的统一标准)由真值表写命题公式由真值表写命题公式(由由T写、
3、由写、由F写写)3谢谢观赏2019-8-23推理演算推理演算(考察逻辑关系符考察逻辑关系符)o 推理形式推理形式(正确推理形式的表示正确推理形式的表示)o 基本推理公式基本推理公式(各种三段论及五种证明方法各种三段论及五种证明方法)o 推理演算推理演算(证明推理公式的第六种方法，使证明推理公式的第六种方法，使用推理规则用推理规则)o 归结推理法归结推理法(证明推理公式的第七种方法，证明推理公式的第七种方法，常用反证法常用反证法)4谢谢观赏2019-8-232.1 等值定理等值定理 o 若把初等数学里的、等运算符看作是若把初等数学里的、等运算符看作是数与数之间的联结词，那么由这些联结词所表达的数
4、与数之间的联结词，那么由这些联结词所表达的代数式之间，可建立许多等值式如下：代数式之间，可建立许多等值式如下：x2y2=(xy)(xy)(xy)2=x22xyy2 sin2xcos2x=1在命题逻辑里也同样可建立一些重要在命题逻辑里也同样可建立一些重要的等值式的等值式 5谢谢观赏2019-8-232.1.1 等值的定义等值的定义 o 给定两个命题公式给定两个命题公式A和和B,而而P1Pn是出现于是出现于A和和B中的所有命题变项中的所有命题变项,那么公式那么公式A和和B共有共有2n个解个解释释,若对其中的任一解释若对其中的任一解释,公式公式A和和B的真值都相等的真值都相等,就称就称A和和B是等值
5、的是等值的(或等价的或等价的)。记作记作A=B或或ABo 显然，可以根据真值表来判明任何两个公式是否是显然，可以根据真值表来判明任何两个公式是否是等值的等值的 6谢谢观赏2019-8-23例例1:证明证明(P P)Q=Q证明证明:画出画出(P P)Q与与Q的真值表可看出的真值表可看出等式是成立的。等式是成立的。7谢谢观赏2019-8-23例例2:证明证明P P=Q Qo 证明证明:画出画出P P,Q Q的真值表的真值表,可看可看出它们是等值的出它们是等值的,而且它们都是重言式。而且它们都是重言式。8谢谢观赏2019-8-23o 从例从例1、2还可说明还可说明,两个公式等值并不一定两个公式等值并
6、不一定要求它们一定含有相同的命题变项要求它们一定含有相同的命题变项n 若仅在等式一端的公式里有变项若仅在等式一端的公式里有变项P出现出现,那么等那么等式两端的公式其真值均与式两端的公式其真值均与P无关。无关。n 例例1中公式中公式(P P)Q与与Q的真值都同的真值都同P无关无关n 例例2中中P P,Q Q都是重言式都是重言式,它们的真值它们的真值也都与也都与P、Q无关。无关。说明说明9谢谢观赏2019-8-232.1.2 等值定理等值定理 对公式对公式A和和B,A=B的充分必要条件是的充分必要条件是AB是重言式。是重言式。o A、B不一定都是简单命题不一定都是简单命题,可能是由简单可能是由简单
7、命题命题P1,Pn构成的构成的.对对A,B的一个解释的一个解释,指的是对指的是对P1,Pn的一组具体的真值设定的一组具体的真值设定.o 若若AB为重言式为重言式,则在任一解释下则在任一解释下A和和B都都只能有相同的真值只能有相同的真值,这就是定理的意思。这就是定理的意思。10谢谢观赏2019-8-23证明证明若若A B是重言式是重言式,即在任一解释下即在任一解释下,A B的真值都为的真值都为Tn 依依A B的定义只有在的定义只有在A、B有相同的值时有相同的值时,才才有有A B=T。于是在任一解释下于是在任一解释下,A和和B都有都有相同的真值相同的真值,从而有从而有A=B。n 反过来，若有反过来
8、，若有A=B,即在任一解释下即在任一解释下A和和B都都有相同的真值有相同的真值,依依A B的定义的定义,A B只有为只有为真真,从而从而A B是重言式。是重言式。注：根据该等值定理，证明两个公式等值，只要证注：根据该等值定理，证明两个公式等值，只要证明由这两个公式构成的双条件式是重言式即可明由这两个公式构成的双条件式是重言式即可11谢谢观赏2019-8-23“”作为逻辑关系符是一种等价关系作为逻辑关系符是一种等价关系o 不要将不要将“”视作联结词，在合式公式定义视作联结词，在合式公式定义里没有里没有“”出现出现o A=B是表示公式是表示公式A与与B的一种关系。这种的一种关系。这种关系具有三个性
9、质关系具有三个性质:1.自反性自反性 A=A2.对称性对称性 若若A=B,则则B=A3.传递性传递性 若若A=B,B=C,则则A=C 这三条性质体现了这三条性质体现了“”的实质含义。的实质含义。12谢谢观赏2019-8-232.2 等值公式等值公式2.2.1 基本的等值公式基本的等值公式(命题定律命题定律,P和和Q是任意的命题公式是任意的命题公式)1.双重否定律双重否定律P=P2.结合律结合律(PQ)R=P(QR)(PQ)R=P(QR)(P Q)R=P (Q R)注注:所有这些公式，都可使用真值表加以验证所有这些公式，都可使用真值表加以验证13谢谢观赏2019-8-233.交换律交换律PQ=Q
10、PPQ=QPP Q=Q P4.分配律分配律P(QR)=(PQ)(PR)P(QR)=(PQ)(PR)P(QR)=(PQ)(PR)5.等幂律等幂律(恒等律恒等律)PP=PPP=PPP=TPP=T14谢谢观赏2019-8-236.吸收律吸收律P(PQ)=PP(PQ)=P7.摩根律摩根律(PQ)=P Q(PQ)=P Q对蕴涵词、双条件词作否定有对蕴涵词、双条件词作否定有(PQ)=P Q(PQ)=PQ=PQ=(PQ)(P Q)15谢谢观赏2019-8-238.同一律同一律PF=PPT=PTP=PTP=P还有还有PF=PFP=P16谢谢观赏2019-8-23 9.零律零律PT=TPF=F还有还有PT=TF
11、P=T10.补余律补余律P P=TP P=F还有还有PP=P PP=PPP=F 17谢谢观赏2019-8-23Venn图图(理解等式理解等式)o 将将P、Q理解为某总体论域上的子集合，并理解为某总体论域上的子集合，并规定：规定：n PQ为两集合的公共部分为两集合的公共部分(交集合交集合)n PQ为两集合的全部为两集合的全部(并集合并集合)n P为总体论域为总体论域(如矩形域如矩形域)中中P的余集的余集18谢谢观赏2019-8-23Venn图图(理解等式理解等式)从从Venn 图，因图，因PQ较较P来得来得“小小”,PQ较较P来得来得“大大”，从而有，从而有P(PQ)=PP(PQ)=P19谢谢观
12、赏2019-8-23理解等理解等式式:Venn图，自然语言图，自然语言(PQ)=P Qo Venn图图(理解集合间、命题逻辑中、理解集合间、命题逻辑中、部分部分信息量间的一些关系信息量间的一些关系)o 对这些等式使用自然用语加以说明，将有助对这些等式使用自然用语加以说明，将有助于理解于理解n 如如P表示张三是学生表示张三是学生,Q表示李四是工人表示李四是工人,那么那么(PQ)就表示并非就表示并非“张三是学生或者李四是张三是学生或者李四是工人工人”。这相当于说，。这相当于说，“张三不是学生而且李张三不是学生而且李四也不是工人四也不是工人”，即可由，即可由 P Q表示表示,从而有从而有(PQ)=P
13、 Q20谢谢观赏2019-8-232.2.2 常用的等值公式常用的等值公式 o 由于人们对由于人们对、更为熟悉，常将含有更为熟悉，常将含有和和的公式化成仅含有的公式化成仅含有、的公式。的公式。这也是证明和理解含有这也是证明和理解含有，的公式的一般的公式的一般方法方法o 公式公式11-18是等值演算中经常使用的是等值演算中经常使用的,也该也该掌握它们掌握它们,特别是能直观地解释它们的成立特别是能直观地解释它们的成立21谢谢观赏2019-8-2311.PQ=P Qo 通常对通常对PQ进行运算时进行运算时,不如用不如用 PQ来来得方便。而且以得方便。而且以 PQ表示表示PQ帮助我们帮助我们理解如果理
14、解如果P则则Q的逻辑含义的逻辑含义o 问题是这种表示也有缺点，丢失了问题是这种表示也有缺点，丢失了P、Q间间的因果关系的因果关系 22谢谢观赏2019-8-2312.PQ=QPo 逆否定理，假言易位逆否定理，假言易位o 如将如将PQ视为正定理视为正定理,那么那么 QP就是就是相应的逆否定理相应的逆否定理,它们必然同时为真它们必然同时为真,同时同时为假为假,所以是等值的所以是等值的23谢谢观赏2019-8-2313.P(QR)=(PQ)Ro 前提合并前提合并o P是是(QR)的前提的前提,Q是是R的前提的前提,于是可于是可将两个前提的合取将两个前提的合取PQ作为总的前提。作为总的前提。即即如果如
15、果P则如果则如果Q则则R,等价于如果等价于如果P与与Q则则R24谢谢观赏2019-8-2314.PQ=(PQ)(P Q)o 从取真来描述双条件从取真来描述双条件o 这可解释为这可解释为PQ为真为真,有两种可能的情形有两种可能的情形,即即(PQ)为真或为真或(P Q)为真。而为真。而PQ为真为真,必是在必是在P=Q=T的情况下出现的情况下出现;P Q为真为真,必是在必是在P=Q=F的情况下的情况下出现。从而可说出现。从而可说,PQ为真为真,是在是在P、Q同同时为真或同时为假时成立。这就是从取真来时为真或同时为假时成立。这就是从取真来描述这等式描述这等式 25谢谢观赏2019-8-2315.PQ=
16、(P Q)(PQ)o 从取假来描述双条件从取假来描述双条件o 这可解释为这可解释为PQ为假为假,有两种可能的情形有两种可能的情形,即即(P Q)为假或为假或(PQ)为假为假,而而P Q为假为假,必是在必是在P=F,Q=T的情况的情况下出现下出现;PQ为假为假,必是在必是在P=T,Q=F的情况下出现。从而可说的情况下出现。从而可说PQ为假为假,是在是在P真真Q假或假或P假假Q真时成立。这就是从取假来描真时成立。这就是从取假来描述这等式述这等式 26谢谢观赏2019-8-2316.PQ=(PQ)(QP)o 从蕴含词来描述双条件从蕴含词来描述双条件o 这表明这表明PQ成立成立,等价于正定理等价于正定
17、理PQ和逆和逆定理定理QP都成立都成立 27谢谢观赏2019-8-2317.P(QR)=Q(PR)o 前提交换前提交换o 前提条件前提条件P、Q可交换次序可交换次序 28谢谢观赏2019-8-2318.(PR)(QR)=(PQ)Ro 左端说明的是由左端说明的是由P而且由而且由Q都有都有R成立。从成立。从而可以说由而可以说由P或或Q就有就有R成立成立,这就是等式右这就是等式右端端29谢谢观赏2019-8-23补充补充o 等价否定等值式等价否定等值式PQ=PQo 归谬论归谬论(PQ)(PQ)=P30谢谢观赏2019-8-232.2.3 置换规则置换规则 o 置换定义置换定义对公式对公式A的子公式的
18、子公式,用与之用与之等值等值的公式来代换便称的公式来代换便称置换置换o 置换规则置换规则n公式公式A的子公式置换后的子公式置换后A化为公式化为公式B,必有必有A=Bn当当A是重言式时是重言式时,置换后的公式置换后的公式B必也是重言式必也是重言式o 置换与代入是有区别的。置换只要求置换与代入是有区别的。置换只要求A的某一子公的某一子公式作代换式作代换,不必对所有同一的子公式都作代换不必对所有同一的子公式都作代换31谢谢观赏2019-8-23代入规则回顾代入规则回顾 oA是一个公式，对是一个公式，对A使用代入规则得公式使用代入规则得公式B，若，若A是重言式，则是重言式，则B也是重言式也是重言式o为
19、保证重言式经代入规则仍得到保持，要求为保证重言式经代入规则仍得到保持，要求n公式中被代换的只能是命题变元公式中被代换的只能是命题变元(原子命题原子命题),而不能是而不能是复合命题复合命题n对公式中某命题变元施以代入，必须对该公式中出现的对公式中某命题变元施以代入，必须对该公式中出现的所有同一命题变元代换以同一公式所有同一命题变元代换以同一公式32谢谢观赏2019-8-232.2.4 等值演算举例等值演算举例 例例1:证明证明(P(QR)(QR)(PR)=R证明证明:左端左端=(P(QR)(QP)R)(分配律分配律)=(P Q)R)(QP)R)(结合律结合律)=(PQ)R)(QP)R)(摩根律摩
20、根律)=(PQ)(QP)R(分配律分配律)=(PQ)(PQ)R(交换律交换律)=TR(置置 换换)=R(同一律同一律)33谢谢观赏2019-8-23例例2:试证试证 (PQ)(P(Q R)(P Q)(P R)=T证明证明:左端左端=(PQ)(P(QR)(PQ)(PR)(摩根律摩根律)=(PQ)(PQ)(PR)(PQ)(PR)(分配律分配律)=(PQ)(PR)(PQ)(PR)(等幂律等幂律)=T举例举例 34谢谢观赏2019-8-23问题提出：问题提出：由命题公式写真值表是容易的，那么如由命题公式写真值表是容易的，那么如何由真值表写命题公式呢？何由真值表写命题公式呢？2.3 命题公式与真值表关系
21、命题公式与真值表关系35谢谢观赏2019-8-232.3.1 从从T来列写来列写o 记忆方法：各项间用记忆方法：各项间用，每项内用每项内用o 每项内书写方法：例每项内书写方法：例真值表中真值表中P=T且且Q=F等价于等价于P Q=To 简化方法：有时简化方法：有时A的表达通过的表达通过 A来描述来描述36谢谢观赏2019-8-232.3.2 从从F来列写来列写o 记忆方法：各项间用记忆方法：各项间用，每项内用每项内用o 每项内书写方法：例每项内书写方法：例真值表中真值表中P=T且且Q=F等价于等价于 PQ=Fo 简化方法：有时简化方法：有时A的表达通过的表达通过 A来描述来描述37谢谢观赏20
22、19-8-23举例举例o从从A的真值的真值Tn直接直接:A=(P Q)(P Q)(P Q)n间接间接:A=A=(P Q)=P Qo从从B的真值的真值FB=(P Q)(P Q)o当当C可取任意值可取任意值C与与P,Q=T,T无关无关,可适当选取可适当选取C的真值的真值,使其表达式简单使其表达式简单PQAABCFFTFTTFTTFTFTFFTFTTTTFFX38谢谢观赏2019-8-23作业作业(1)(P37)1(1,3),239谢谢观赏2019-8-232.4 联结词的完备集联结词的完备集 o问题的提出问题的提出对对n 个命题变项个命题变项P1Pn来说来说,共可定义出多少个共可定义出多少个联结词
23、联结词?在那么多联结词中有多少是相互独立的在那么多联结词中有多少是相互独立的?o3个新联结词：个新联结词：P QP QPQP Q(P Q)P Q(P Q)：=()()=()()=异异或或与与非非或或非非思考：考虑异或联结词与双条件联结词的关系思考：考虑异或联结词与双条件联结词的关系(可利用真值表可利用真值表)40谢谢观赏2019-8-232.4.1 命题联结词的个数命题联结词的个数o 第一个问题。可定义多少个联结词？第一个问题。可定义多少个联结词？o 由命题变项和命题联结词可以构成无限多个由命题变项和命题联结词可以构成无限多个合式公式合式公式o 把所有的合式公式把所有的合式公式分类分类：将等值
24、的公式视为：将等值的公式视为同一类，从中选一个作代表称之为真值函项。同一类，从中选一个作代表称之为真值函项。对一个真值函项，或者说对于该类合式公式对一个真值函项，或者说对于该类合式公式，就可定义一个联结词与之对应就可定义一个联结词与之对应例：等价类。自然数集合例：等价类。自然数集合N被被3除余数相同的除余数相同的自然数构成自然数构成3个集合个集合N0,N1,N241谢谢观赏2019-8-23o 一元联结词一元联结词是联结一个命题变项是联结一个命题变项(如如P)的的o P有真假有真假2种值，因此种值，因此P(自变量自变量)上可定义上可定义4种一种一元联结词元联结词fi 或说真值函项或说真值函项f
25、i(P),i=1,2,3,4一元联结词的个数一元联结词的个数42谢谢观赏2019-8-23由真值表写出真值函项的命题公式：由真值表写出真值函项的命题公式：f0(P)=F(永假式永假式)f1(P)=P(P自身自身)f2(P)=P(否定词否定词)f3(P)=T(永真式永真式)新的公式只有新的公式只有f2(P),与之对应的联结词是否定词与之对应的联结词是否定词一元联结词一元联结词43谢谢观赏2019-8-23o 二元联结词联结两个命题变项二元联结词联结两个命题变项(如如P、Q)o 两个变项共有两个变项共有4种取值情形种取值情形,于是于是P、Q上可上可建立起建立起16种不同的真值函项种不同的真值函项,
26、相应的可定义相应的可定义出出16个不同的二元联结词个不同的二元联结词g0,g1,g15 图图2.4.2给出了这些联结词给出了这些联结词gi或说真值函项或说真值函项gi(P,Q)的真值表定义的真值表定义二元联结词的个数二元联结词的个数44谢谢观赏2019-8-2345谢谢观赏2019-8-23根据真值表写出各真值函项的命题表达式根据真值表写出各真值函项的命题表达式:g0(P,Q)=F(永假式永假式)g1(P,Q)=PQ (合取式合取式)g2(P,Q)=P Q g3(P,Q)=(P Q)(PQ)=P(QQ)=Pg4(P,Q)=PQ g5(P,Q)=(PQ)(PQ)=(PP)Q=Qg6(P,Q)=P
27、 Q(异或式异或式)g7(P,Q)=PQ(析取式析取式)g8(P,Q)=P Q=P Q(或非式或非式)g9(P,Q)=P Q(双条件式双条件式)g10(P,Q)=(P Q)(P Q)=(PP)Q=Qg11(P,Q)=P Q=QP(蕴涵式蕴涵式)g12(P,Q)=(P Q)(PQ)=P(QQ)=Pg13(P,Q)=PQ=PQ(蕴涵式蕴涵式)g14(P,Q)=P Q=P Q(与非式与非式)g15(P,Q)=T(永真式永真式)46谢谢观赏2019-8-23o n元联结词元联结词对对n个命题变元个命题变元P1,Pn,每个每个Pi有两有两种取值种取值,从而对从而对P1Pn来说共有来说共有2n种取种取值情
28、形值情形于是相应的于是相应的真值函项就有真值函项就有22n个个,或说可或说可定义定义22n个个n元联结词元联结词n元联结词的个数元联结词的个数47谢谢观赏2019-8-232.4.2 联结词的完备集联结词的完备集 o 第二个问题。联结词是否都是独立的，或者第二个问题。联结词是否都是独立的，或者说能否相互表示说能否相互表示?o 联结词的完备集定义联结词的完备集定义:设设C是联结词的集合，是联结词的集合，如果对任一命题公式如果对任一命题公式(能直接使用能直接使用T和和F)都都有由有由C中的联结词表示出来的公式中的联结词表示出来的公式(不能直不能直接使用接使用T和和F)与之等值，就说与之等值，就说C
29、是完备的联是完备的联结词集合，或说结词集合，或说C是联结词的完备集。是联结词的完备集。48谢谢观赏2019-8-231.全体联结词的无限集合是完备的全体联结词的无限集合是完备的2.,是完备的联结词集合是完备的联结词集合 证明证明：从：从2.3节介绍的由真值表列写逻辑公式的过程节介绍的由真值表列写逻辑公式的过程可知可知,任一公式都可由任一公式都可由,表示出来表示出来,从而从而,是完备的是完备的3.是联结词的完备集是联结词的完备集(独立的完备集独立的完备集)证明证明：PQ=(P Q)，因此，因此可由可由,表示表示4.,是联结词的完备集是联结词的完备集(独立的完备集独立的完备集)证明证明：PQ=(P
30、 Q)，因此，因此可由可由,表示表示完备集完备集 49谢谢观赏2019-8-235.,是完备集是完备集(独立的完备集独立的完备集)因为：因为：PQ=PQ6.是完备集是完备集(独立的完备集独立的完备集)7.是完备集是完备集(独立的完备集独立的完备集)8.,是完备的是完备的 因为它包含了因为它包含了2中的集合中的集合完备集完备集 50谢谢观赏2019-8-23o,不是完备的不是完备的因为因为F不能仅由该集合的联结词表达出不能仅由该集合的联结词表达出o ,不是完备的不是完备的o,的任何子集都是不完备的的任何子集都是不完备的 ,的任何子集也是不完备的的任何子集也是不完备的(如果一个联结词的集合是不完备
31、的，那如果一个联结词的集合是不完备的，那么它的任何子集都是不完备的么它的任何子集都是不完备的)o,不是完备的不是完备的不完备集不完备集 51谢谢观赏2019-8-23最小的联结词的完备集最小的联结词的完备集基底基底 o 基底：完备的联结词集合的联结词是独立的，基底：完备的联结词集合的联结词是独立的，也就是说这些联结词不能相互表示也就是说这些联结词不能相互表示o 任取四个一元或二元联结词，它们必组不成任取四个一元或二元联结词，它们必组不成基底基底52谢谢观赏2019-8-23基底基底 o 只含一个联结词的只含一个联结词的:NK;NAo 含两个联结词的含两个联结词的:N,C;N,K;N,A;N,N
32、C;F,C;T,NC;C,NE;E,NC;C,NCo 含三个联结词的含三个联结词的:F,K,E;F,A,E;T,K,NE;T,A,NE;K,E,NE;A,E,NE其中：其中：A-K-E-C-N-53谢谢观赏2019-8-232.5 对偶式对偶式 o 研究目的研究目的n简化等值公式的讨论简化等值公式的讨论希望一个公式成立，能够导出与其希望一个公式成立，能够导出与其“相像相像”的公式成立的公式成立n逻辑关系上看，是一种逻辑规律逻辑关系上看，是一种逻辑规律o 对偶式定义：将对偶式定义：将A中出现的中出现的、T、F分别以分别以、F、T代换代换,得到公式得到公式A*,则称则称A*是是A的对偶式的对偶式,
33、或说或说A和和A*互为对偶式互为对偶式注：这里假定注：这里假定A中仅出现中仅出现 、三个联结词三个联结词o 若若A=B，必有，必有A*=B*?54谢谢观赏2019-8-23p 新符号新符号“-”:(代入规则、内否式代入规则、内否式)若若A=A(P1,Pn)，令，令A=A(P1,Pn)p 关于等值的三个定理关于等值的三个定理定理定理2.5.1 (A*)=(A)*,(A)=(A)定理定理2.5.2 (A*)*=A,(A)=A定理定理2.5.3 A=A*(摩根律的另一种形式摩根律的另一种形式)更多：更多：(A B)*=A*B*，(A B)-=A-B-(A B)*=A*B*，(A B)-=A-B-对偶
34、式相关定理对偶式相关定理 55谢谢观赏2019-8-2356性质举例性质举例A=(P (Q R)TA*=(P (Q R)FA-=(P)(Q R)TA*-=(P)(Q R)FA-*=(P)(Q R)F谢谢观赏2019-8-23定理定理2.5.3 A=A*证明证明:可用数学归纳法可用数学归纳法,施归纳于施归纳于A中出现的中出现的 联结词个数联结词个数n来证明来证明基始基始:设设n=0,A中无联结词中无联结词,便有便有 A=P,从而从而 A=P但但 A*=P n=0时定理成立。时定理成立。57谢谢观赏2019-8-23归纳：归纳：设设n k时定理成立，来证时定理成立，来证n=k+1时定时定理也成立理
35、也成立 n=k+1 1,A中至少有一个联结词，中至少有一个联结词，可分为三种情形可分为三种情形A=A1,A=A1A2,A=A1A2 其中其中A1,A2中联结词个数中联结词个数k。依归纳法假设，依归纳法假设，A1=A1*,A2=A2*定理定理2.5.3 A=A*58谢谢观赏2019-8-23当当 A=A1时时 A=(A1)A=A1 =(A1*)归纳法假设归纳法假设 =(A1)*定理定理2.5.1,2.5.2 =A*A=A1定理定理2.5.3 A=A*59谢谢观赏2019-8-23当当 A=A1A2时，时，A=(A1A2)=A1 A2摩根律摩根律 =A1*A2*归纳法假设归纳法假设 =(A1*A2
36、*)A定义定义 =(A1A2)*A*定义定义 =A*另一种情况同理，从而定理得证。另一种情况同理，从而定理得证。定理定理2.5.3(摩根律摩根律)A=A*60谢谢观赏2019-8-23定理定理2.5.6(1)A与与A同永真同永真,同可满足同可满足 (2)A与与A*同永真同永真,同可满足同可满足注：注：“A和和B”同永真表示：同永真表示：A永真当且仅当永真当且仅当B永真永真证明：设证明：设A是由命题变项是由命题变项P1,Pn构成的命题公式。构成的命题公式。(1)如果如果A永真，根据代入规则，则永真，根据代入规则，则A-永真。永真。如果如果A-永真，则永真，则(A-)-永真，又根据定理永真，又根据
37、定理2.5.2有有 A=(A-)-,所以所以A永真永真(2)根据定理根据定理2.5.3，A=A*，所以根据，所以根据(1)可得可得(2)成立成立对偶式相关定理对偶式相关定理 61谢谢观赏2019-8-23定理定理 2.5.4 若若A=B，必有，必有A*=B*证明证明:因为因为A=B等价于等价于AB 永真等价于永真等价于 AB永真。永真。依定理依定理2.5.3,A=A*,B=B*于是于是A*B*永真，永真，则则(A*-B*-)-永真永真(根据代入规则，根据代入规则，A永真，永真，A-永真永真)亦即亦即 A*B*永真永真故故 A*=B*对偶式相关定理对偶式相关定理 62谢谢观赏2019-8-23定
38、理定理2.5.5 若若AB永真永真,必有必有B*A*永真永真或者，或者，AB和和B*A*同永真同永真证明证明:(1)如果如果AB永真，则永真，则 BA永真永真(逆否命题逆否命题)根据定理根据定理2.5.3，A=A*-,B=B*-所以所以B*-A*-永真，则永真，则(B*-A*-)-永真永真(代入规则代入规则)，即即B*A*永真永真(2)如果如果B*A*永真，根据永真，根据(1)有有:(A*)*(B*)*永真永真根据定理根据定理2.5.2，A=(A*)*,B=(B*)*所以所以AB永真永真 对偶式相关定理对偶式相关定理 63谢谢观赏2019-8-23作业作业(2)(P37)3，4(2)64谢谢观
39、赏2019-8-232.6 范式范式o n 个命题变项所能组成的具有不同真值的命题公式个命题变项所能组成的具有不同真值的命题公式仅有仅有22n个个,然而与任何一个命题公式等值而形式然而与任何一个命题公式等值而形式不同的命题公式可以有无穷多个不同的命题公式可以有无穷多个o 等值的公式，能否都可以化为某一个统一的标准形等值的公式，能否都可以化为某一个统一的标准形式？式？n希望这种标准形能为我们的讨论带来些方便，如借助于希望这种标准形能为我们的讨论带来些方便，如借助于标准形对任意两个形式上不同的公式，可判断它们的是标准形对任意两个形式上不同的公式，可判断它们的是否等值否等值n借助于标准形容易判断任一
40、公式是否为重言式或矛盾式借助于标准形容易判断任一公式是否为重言式或矛盾式65谢谢观赏2019-8-232.6.1 范式范式o 若干术语若干术语n 简单命题简单命题P及其否定式及其否定式 P统称为文字统称为文字n 一些文字的合取称为合取式一些文字的合取称为合取式n 一些文字的析取称为析取式一些文字的析取称为析取式(也称子句也称子句)n P与与 P称为互补对称为互补对n 析取范式，形如：析取范式，形如：A1A2 An其中其中Ai(i=1,n)为合取式为合取式n 合取范式，形如：合取范式，形如：A1A2 An其中其中Ai(i=1,n)为析取式为析取式66谢谢观赏2019-8-2367范式举例范式举例
41、o p,qo p1p2,q1q2谢谢观赏2019-8-23范式定理范式定理o 范式定理：任一命题公式都存在与之等范式定理：任一命题公式都存在与之等值的析取范式、合取范式值的析取范式、合取范式o 求范式三步曲：求范式三步曲：1)消去消去和和2)否定深入到命题变项否定深入到命题变项3)使用分配律的等值变换使用分配律的等值变换68谢谢观赏2019-8-23举例举例o 求求(PQ)(PQ)的析取范式的析取范式(PQ)(PQ)=(PQ)(PQ)(PQ)(PQ)=(PQPQ)(PQ)(PQ)=(PQPQ)(PP)(PQ)(QP)(QQ)(析取范式析取范式)=(PQ)(QP)(析取范式，简化析取范式，简化)
42、注：范式的不唯一性注：范式的不唯一性69谢谢观赏2019-8-23举例举例o 求求(PQ)(PQ)的合取范式的合取范式(PQ)(PQ)=(PQ)(QP)(析取范式，简化析取范式，简化)=(PQ)(PP)(QQ)(QP)(合取范式合取范式)=(PQ)(QP)(合取范式，简化合取范式，简化)注：已知一种范式，可以使用分配律求另一种范式注：已知一种范式，可以使用分配律求另一种范式70谢谢观赏2019-8-23p 判断重言式判断重言式合取范式中所有析取式都有互补对合取范式中所有析取式都有互补对p 判断矛盾式判断矛盾式析取范式中所有合取式都有互补对析取范式中所有合取式都有互补对p 判断两公式是否等值判断
43、两公式是否等值范式不唯一，引入唯一的主范式，范式不唯一，引入唯一的主范式，便于判别公式相等便于判别公式相等范式功能范式功能71谢谢观赏2019-8-232.6.2 主范式主范式o主析取范式主析取范式n极小项定义与编码极小项定义与编码Q1Qn是由是由n个命题变项个命题变项P1,Pn组成的公式组成的公式,其中其中Qi=Pi或者或者Pi,我们称其为极小项我们称其为极小项,一般用一般用mj表表示示例：例：P1,P2的极小项有四个的极小项有四个P1 P2(m0),P1 P2(m1),P1 P2(m2),P1P2(m3)n主析取范式定义主析取范式定义 仅由极小项构成的析取范式仅由极小项构成的析取范式n主析
44、取范式唯一性定理主析取范式唯一性定理任一含有任一含有n个命题变项的公式，都有唯一一个与之等值个命题变项的公式，都有唯一一个与之等值的恰仅含这的恰仅含这n个命题变项的主析取范式个命题变项的主析取范式极小项必须含有极小项必须含有Q1,Qn全部全部n个文字个文字72谢谢观赏2019-8-23o由真值表写主析取范式：从由真值表写主析取范式：从T写写P Q=(PQ)(PQ)=m0m3=0,3o由析取范式写主析取范式：填满命题变项法由析取范式写主析取范式：填满命题变项法,永真式永真式P=P(QQ)=(PQ)(PQ)Q=Q(PP)=(QP)(QP)PQ=PQ=(PQ)(PQ)(QP)(QP)=(PQ)(PQ
45、)(PQ)=m0m1m3 =0,1,3主析取范式主析取范式PQPQ m0FFT m1FTFm2TFFm3TTT73谢谢观赏2019-8-23p所有可能极小项的个数：所有可能极小项的个数：2np每个极小项只在一个解释下为真每个极小项只在一个解释下为真p对于每个解释只有一个极小项为真对于每个解释只有一个极小项为真 p极小项互不相等，且极小项互不相等，且mi mj=F(i j)p任一含有任一含有n个变项的公式，都可由个变项的公式，都可由k个个(k2n)极小项的析取来极小项的析取来表示；或者说所有的极小项可建立一个表示；或者说所有的极小项可建立一个“坐标系坐标系”p恰由恰由2n个极小项的析取构成的公式
46、，必为重言式个极小项的析取构成的公式，必为重言式 pA与与 A的主析取范式关系的主析取范式关系A由由k个极小项的析取组成，那么其余的个极小项的析取组成，那么其余的2n-k个极小项的析取必个极小项的析取必是是 A例如例如P1,P2,P3构成的构成的A=0,2,4,A=1,3,5,6,7极小项性质极小项性质n21ii1mT74谢谢观赏2019-8-23主合取范式主合取范式o极大项定义与编码极大项定义与编码Q1 Qn是由是由n个命题变项个命题变项P1,Pn组成的公式组成的公式,其中其中Qi=Pi或或者者Pi(i=1,n),我们称其为极大项我们称其为极大项,一般用一般用Mj表示表示(0j2n-1)例：
47、例：P1,P2的极大项有四个的极大项有四个P1P2(M0),P1P2(M1),P1P2(M2),P1P2(M3)o主合取范式定义主合取范式定义仅由极大项构成的合取范式仅由极大项构成的合取范式o主合取范式唯一性定理主合取范式唯一性定理任一含有任一含有n个命题变项的公式，都有唯一一个与之等值的恰仅含个命题变项的公式，都有唯一一个与之等值的恰仅含这这n个命题变项的主合取范式个命题变项的主合取范式o由真值表写主合取范式由真值表写主合取范式(从从F写写)o由合取范式写主合取范式由合取范式写主合取范式(填满命题变项法填满命题变项法,矛盾式矛盾式)极大项必须含有极大项必须含有Q1,Qn全部全部n个文字个文字
48、75谢谢观赏2019-8-23极大项性质极大项性质p所有可能极大项的个数：所有可能极大项的个数：2np每个极大项只在一个解释下为假每个极大项只在一个解释下为假p对于每个解释只有一个极大项为假对于每个解释只有一个极大项为假 p极大项互不相等，且极大项互不相等，且Mi Mj=T(i j)p任一含有任一含有n个变项的公式，都可由个变项的公式，都可由k个个(k2n)极大项的合取来极大项的合取来表示；或者说所有的极大项可建立一个表示；或者说所有的极大项可建立一个“坐标系坐标系”p恰由恰由2n个极大项的合取构成的公式，必为矛盾式个极大项的合取构成的公式，必为矛盾式pA与与 A的主合取范式关系的主合取范式关
49、系A由由k个极大项的合取组成，那么其余的个极大项的合取组成，那么其余的2n-k个极大项的合取必个极大项的合取必是是 A例如例如P1,P2,P3构成的构成的A=0,2,5,A=1,3,4,6,7n21ii1mF76谢谢观赏2019-8-23主析取范式与主合取范式的转换主析取范式与主合取范式的转换设设A是由命题变项是由命题变项P1,P2,P3构成的公式构成的公式o已知主析取范式已知主析取范式A=0,1,4,5,7=(0,1,7-0,1,4,5,7)补补=2,3,6补补=5,4,1o已知主合取范式已知主合取范式A=1,4,5=(0,1,7-1,4,5补补)=(0,1,7-6,3,2)=0,1,4,5
50、,7极小项编码极小项编码P1P2P3A极大项编码极大项编码m0FFFTMm1FFTTMm2FTFFMm3FTTFMm4TFFTMm5TFTTMm6TTFFMm7TTTTM77谢谢观赏2019-8-23主析取范式与主合取范式的转换主析取范式与主合取范式的转换注意注意o 从真值表列写公式的主析取范式和主合取范式时，从真值表列写公式的主析取范式和主合取范式时，除了分别从除了分别从T和和F列写外，在填写合取式和析取式列写外，在填写合取式和析取式时是取变项还是其否定是有区别的，这就是主合取时是取变项还是其否定是有区别的，这就是主合取范式、主析取范式转换过程要求补的原因范式、主析取范式转换过程要求补的原因
