离散数学+高等里离散数学 课件 CHAPT14

1、2 数理逻辑是一门用数学方法来研究推数理逻辑是一门用数学方法来研究推理过程的数学分支，包含着逻辑演算、理过程的数学分支，包含着逻辑演算、证明论、递归论、模型论、公理集合论证明论、递归论、模型论、公理集合论等丰富的内容。逻辑方法在数学中用于等丰富的内容。逻辑方法在数学中用于定理证明，在计算机科学中，用来证明定理证明，在计算机科学中，用来证明程序是在做它应该做的事。程序是在做它应该做的事。 本篇只介绍数理逻辑中最基础的逻辑本篇只介绍数理逻辑中最基础的逻辑演算部分，主要包括命题逻辑和一阶逻演算部分，主要包括命题逻辑和一阶逻辑。辑。 34n14.1 命题与逻辑连接词命题与逻辑连接词n14.2 命题公式

2、与等值演算命题公式与等值演算n14.3 对偶与范式对偶与范式n14.4 推理理论推理理论n14.5 命题演算的公理系统命题演算的公理系统514.1 命题与逻辑连接词命题与逻辑连接词本节的知识点：本节的知识点：1.1. 命题的概念命题的概念2.2. 简单命题与复杂命题的概念简单命题与复杂命题的概念3.3. 五种常用的连接词五种常用的连接词61.命题的概念命题的概念 凡具有真假意义的陈述句均称为命题。凡具有真假意义的陈述句均称为命题。 若一个命题是真的，则称该命题的真若一个命题是真的，则称该命题的真值为值为“真真”，用或表示；如果一个，用或表示；如果一个命题是假的，则称为该命题的真值为命题是假的，

3、则称为该命题的真值为“假假”，用或表示。，用或表示。 由于一个命题的真值只可能取由于一个命题的真值只可能取“真真”或或“假假”两种值，因此，命题逻辑又称两种值，因此，命题逻辑又称为为“二值逻辑二值逻辑”。7下面三类是命题：下面三类是命题： 1) 现实可判断真假的陈述句。现实可判断真假的陈述句。 2) 有些陈述句，目前还不知道真假，但它们有些陈述句，目前还不知道真假，但它们本身是具有真假意义的。本身是具有真假意义的。 3) 其真假与讨论问题范围（论域）有关的陈其真假与讨论问题范围（论域）有关的陈述句。述句。下面的不是命题：下面的不是命题： 感叹句感叹句 ，疑问句，祈使句。，疑问句，祈使句。8举例

4、说明：举例说明：1)1) 地球绕着月亮转。地球绕着月亮转。2)2) 1+1=31+1=3。3)3) 禁止烟火！禁止烟火！4)4) 地球有一天会爆炸。地球有一天会爆炸。5)5) 明天会下雨吗？明天会下雨吗？6)6) 如果明天天气晴朗，我就出去散步。如果明天天气晴朗，我就出去散步。 92. 2.简单命题与复合命题简单命题与复合命题n复合命题复合命题命题可以通过命题逻辑命题可以通过命题逻辑连接词构成新的命题，即复合命题。复连接词构成新的命题，即复合命题。复合命题的子命题也可以是复合命题。合命题的子命题也可以是复合命题。n简单命题简单命题不是复合命题的命题。不是复合命题的命题。它不含任何连接词。在命题

5、逻辑中，简它不含任何连接词。在命题逻辑中，简单命题被看作是一个整体，不再分析其单命题被看作是一个整体，不再分析其内部的逻辑形式。内部的逻辑形式。 显然，复合命题的真值依赖于其中显然，复合命题的真值依赖于其中简单命题的真值。简单命题的真值。10n为了对命题做逻辑演算，需要将命题符号化。为了对命题做逻辑演算，需要将命题符号化。n命题符号命题符号( (分为命题常元和命题变元分为命题常元和命题变元) )用大写字母，用大写字母，表示命题。这些字表示命题。这些字母就称为命题符号。母就称为命题符号。 如：如： ：加等于。：加等于。 这时表示一个具体的命题，称为一个这时表示一个具体的命题，称为一个命题常元。命

6、题常元。 如果表示任何一个命题，则称为命题如果表示任何一个命题，则称为命题变元。命题变元不是命题。变元。命题变元不是命题。 为方便记，用为方便记，用1 1表示一个抽象的真命题，表示一个抽象的真命题，用用0 0表示一个抽象的假命题。表示一个抽象的假命题。113.3.五种常用的连接词五种常用的连接词1)1) 否定连接词否定连接词“ ”的定义的定义(14.1.1)(14.1.1)设是命题，复合命题设是命题，复合命题“ ”是是的否定，规定的否定，规定 为真当且仅当为为真当且仅当为假。即假。即为，则为，则 为；为；为，则为，则 为。为。例：例：今天出太阳。：今天出太阳。 ：今天不出太阳。：今天不出太阳。

7、122)2) 合取连接词合取连接词“”的定义的定义(14.1.2)(14.1.2)设，是命题，复合命题设，是命题，复合命题“并且并且”称为和的合取。规定称为和的合取。规定为真当且为真当且仅当与同时为真。真值表如下：仅当与同时为真。真值表如下：例：例： ：是偶数。：是偶数。 ：是质数。：是质数。：既是偶数又是质数。：既是偶数又是质数。133)3) 析取连接词析取连接词“”的定义的定义(14.1.3)(14.1.3) 设，是命题，复合命题设，是命题，复合命题“或者或者”称为和的析取。规定称为和的析取。规定为真当且为真当且仅当与至少有一个为真。真值表如下：仅当与至少有一个为真。真值表如下：例：下午我

8、看书。例：下午我看书。：下午我玩电游。：下午我玩电游。：下午我看书，或者玩电游。：下午我看书，或者玩电游。144)4) 蕴涵连接词蕴涵连接词“”的定义的定义(14.1.4)(14.1.4) 设，是命题，复合命题设，是命题，复合命题“如果，则如果，则”称为蕴涵。称为条件，为结称为蕴涵。称为条件，为结论。规定论。规定为假当且仅当为真而为假当且仅当为真而为假。真值表如下：为假。真值表如下：例：他晚上有事。例：他晚上有事。：他不参加会议。：他不参加会议。：如果他晚上有事：如果他晚上有事, ,他就不参加会议。他就不参加会议。155)5) 等价连接词等价连接词“”的定义的定义(14.1.5)(14.1.5

9、) 设，是命题，复合命题设，是命题，复合命题“当且仅当且仅当当”称为等价于。规定称为等价于。规定为为真当且仅当与同时为真或同时为假。真当且仅当与同时为真或同时为假。真值表如下：真值表如下：例：彗星撞地球。例：彗星撞地球。：太阳从西边升起。：太阳从西边升起。：彗星撞地球当且仅当太阳从西边升起。：彗星撞地球当且仅当太阳从西边升起。1614.214.2命题公式与等值演算命题公式与等值演算本节知识点：本节知识点：1. 命题公式的定义命题公式的定义2. 什么叫解释什么叫解释3. 等值演算及其公式等值演算及其公式17n 上节定义的五个联结词，他们各自可以表示自然语言中的一些常用语句。要表达更复杂的语句，就

10、必须将这五个联结词综合起来考虑，形成更复杂的复合命题，当复合命题中有两个以上的联结词时，其真值就与运算次序有关。这样，由命题符号，连接词以及括号所组成的复合命题，我们称为命题公式（简称公式）。其严格定义如下。181.1.命题公式的定义命题公式的定义q定义定义14.2.114.2.1 命题公式是如下定义的一个符号串。i.单个命题符号是命题公式（原子公式）；ii. 若A是命题公式，则（A ）也是命题公式；iii.若A、B是命题公式，则（AB），（AB），（AB）以及（AB）也是命题公式；iv. 仅当有限次地使用以上三条所得到的符号串才是命题公式。 这个递归定义给出了生成和识别命题公式的一般规则。其

11、中前三条给出了生成规则，第四条则用来识别那些符号串不是命题公式。19q例：以下符号串是命题公式，可按定义生成。例：以下符号串是命题公式，可按定义生成。q （ P）（P Q） R） Q）约定：约定：1.1.五种连接词的运算优先级的次序由高到五种连接词的运算优先级的次序由高到低如下：低如下： ， ， ， 多个同类连接词按从左到右的优先次序。多个同类连接词按从左到右的优先次序。2.2.公式（公式（ A A ）的括号可省略）的括号可省略3.3.整个公式的最外层括号可省略整个公式的最外层括号可省略20n 命题公式是由命题符号，逻辑连接词命题公式是由命题符号，逻辑连接词以及括号按规定组成的符号串。以及括号

12、按规定组成的符号串。n 因为命题符号可以是一个命题变元因为命题符号可以是一个命题变元（它表示任意一个命题），所以，如果（它表示任意一个命题），所以，如果不对命题变元指定一个真值，则整个命不对命题变元指定一个真值，则整个命题公式就无真值可言，故命题公式不一题公式就无真值可言，故命题公式不一定是命题。定是命题。212 2）解释解释解释的定义解释的定义( (定义定义14.2.2)14.2.2)：设设G G是命题公是命题公式，式，A A1 1，A A2 2，A An n是出现在是出现在G G中的所有命中的所有命题变元，指定题变元，指定A A1 1,A,A2 2, ,A An n的一组真值的一组真值（a

13、 a1 1,a,a2 2, ,a an n),a),ai i 0,1,i=1,0,1,i=1,n,n,则则这组真值称为这组真值称为G G的一个解释。的一个解释。由定义知，含n(n1)个命题变元的命题公式共有2n个不同的解释。这是因为该命题公式的每个命题变元只能取真值0或1这两种选择，于是命题公式的所有解释共有2n种不同的组合。可以采用真值表的方法，将一个命题公式的所有解释与公式的真值对应起来，形成该命题公式的真值表。22例：例：G=G=，G G在解释（在解释（0 0，0 0）（）（0 0，1 1）（）（1 1，1 1）下为真，在其他解释下为）下为真，在其他解释下为假。假。 根据各种解释下公式的

14、取值情况，命题根据各种解释下公式的取值情况，命题公式有如下分类：公式有如下分类：23命题公式的分类：定义定义14.2.314.2.3 设设G G是一个命题公式。是一个命题公式。 1)1)若若G G在它的所有解释下均为真，则称在它的所有解释下均为真，则称G G是永真是永真 的，或称的，或称G G为重言式；为重言式； 2)2)若若G G在它的所有解释下均为假，则称在它的所有解释下均为假，则称G G是永假是永假的，或称的，或称G G为矛盾式；为矛盾式； 3)3)若至少有一个解释使若至少有一个解释使G G为真，则称为真，则称G G是可满足是可满足的，或称的，或称G G为可满足式。为可满足式。 显然，G

15、是永真的，当且仅当G是永假的；重言式一定是可满足式，反之不然。 若公式G在解释I下为真，则称I满足G，若公式G在解释I下为假，则称I弄假G.24例如：例如：n设P，Q，R是命题变元，n命题公式G为： PP 显然，G是重言式。n若命题公式G为： PP， 于是G是矛盾式。n而G为(PQ) R时，G是可满足式。因为解释（0，0，1）使G为真，即满足G。253.3.等值演算等值演算v定义定义14.2.414.2.4 两个命题公式两个命题公式A A，B B，如果在其任，如果在其任何解释何解释 下，其相应的真值均相同，则称下，其相应的真值均相同，则称A A与与B B等值，记为等值，记为A AB B。v符号

16、“”是关系符，不是连接词。约定A=B当且仅当A与B是两个符号串相同的命题公式。显然，若A=B,则AB，反之不然。v易证AB当且仅当AB是重言式。等值关系是等价关系。v等值演算等值演算从某个公式从某个公式G G出发，经有限次使出发，经有限次使用基本等值和已知的等值式，推演出另外一用基本等值和已知的等值式，推演出另外一些等值，这一过程为等值演算。些等值，这一过程为等值演算。26基本的等值公式：基本的等值公式：1. 双重否定律：PP2. 等幂律：PPP PPP3. 交换律：PQQP PQQP4. 结合律：(PQ)RQ(PR) (PQ)RQ(PR)5. 分配律：P(QR)(PQ)(PR) P(QR)(

17、PQ)(PR)276. De Morgan律：（PQ） PQ （PQ） PQ7. 吸收律：P（PQ）P P（PQ）P8. 零律： P11 P009. 同一律：P0P P1P10.补余律：PP1 PP0 补充：PQPQ PQ(PQ)(QP) 以上等值式，由于P,Q,R表示任意命题公式，因此，他们可以代表任意多个同类型的命题公式，如由补余律PP1可得(PQ)(PQ)1， (P)(P)1等任意多个等值式。 28例：证明公式P（QP）Q）为重言式。 P（QP）Q）P（QQ）（PQ） （分配律）P（0（PQ） （补余律）P（PQ） （同一律）P（PQ） （De Morgan律）（PP）Q （结合律）1Q

18、 （补余律）1 （零律） 证毕。2914.3 14.3 对偶与范式对偶与范式本节知识点：本节知识点：1.1. 对偶式与内否式对偶式与内否式2.2. 求析取范式、合取范式求析取范式、合取范式3.3. 求主析取范式求主析取范式4.4. 求主合取范式求主合取范式301.1.对偶式对偶式 定义定义14.3.1 14.3.1 在仅含连接词在仅含连接词 ， ， 的命题的命题公式公式A A中，若将所有的中，若将所有的“ ”换成换成“ ”，所有的，所有的“ ”换成换成“ ”, ”, 则称所得的命题公式为则称所得的命题公式为A A的对的对偶式，记为偶式，记为A A* *。 特别，命题常元特别，命题常元1 1和和

19、0 0互为对偶式。即互为对偶式。即1 1* *=0=0，0 0* *=1=1。显然。显然A A是是A A* *的对偶式，即的对偶式，即(A(A* *) )* *=A=A 由等值式由等值式PQPQ及及PQ(PQ) (QP)(PQ)(QP)知，可以将任何知，可以将任何命题公式化成等值的且仅含联结词命题公式化成等值的且仅含联结词，的的公式，因此，任何命题公式均存在对偶式。以公式，因此，任何命题公式均存在对偶式。以下涉及到对偶式，不妨设公式中不含联结词下涉及到对偶式，不妨设公式中不含联结词和和。 31内否式：内否式：定义定义14.3.214.3.2 设设A A是命题公式，若将是命题公式，若将A A中各

20、命中各命题变元的所有肯定形式的出现换成其否定，题变元的所有肯定形式的出现换成其否定，所有否定形式的出现换成其肯定，则所得的所有否定形式的出现换成其肯定，则所得的公式称为内否式，记为公式称为内否式，记为A.A. 显然，定义中的显然，定义中的A A也是也是A A的内否式即（的内否式即（A A）=A=An例如：设A=(PQ)R ，则其 对偶式：A*=(PQ)R 内否式：A=(PQ)R32命题14.3.1 设A*，B*分别是命题公式A，B的对偶式，于是：1) (A*）=（A)*2) （AB)* =A*B*3) （AB)* =A*B*命题14.3.2 设A，B是命题公式，则1) (A）=（A）2) （A

21、B）=AB3) （AB）=AB33n定理 14.3.1 对任何命题公式 A，均有 A= A*证明：（对公式中的联结词的个数n用归纳法）i. 当n=0时，A中无连接词，有A=A*，A=A，则 A* =A =A 故 A* =Aii.设nk时定理成立iii.当n=k+1时，A中至少有一个连接词，故A可写成下列三种形式之一： A=A1，A=A1A2， A=A1A2 且A1，A2中的连接词个数都小于n，则由归纳假设有 A1=A1* A2=A2*34由归纳假设有 A1=A1*，A2=A2*a)当A=A1时， A=(A1) =(A1*) （由归纳假设） =(A1*) （由命题14.3.2之(1)） =(A1

22、)* （由命题14.3.1之(1)） =A* （由A=A1）35b) 当A=A1A2时 A =(A1A2） =A1A2 (由De Morgan律） =A1* A2* （由归纳假设） =A1*A2* （由命题14.3.2之(2) =（A1A2)* （由命题14.3.1之(3) = A* (由A=A1A2)c）当A=A1A2时，证明同b）,结论成立。总之，由归纳法，本定理成立。36定理14.3.2（对偶原理） 设A、B是两个命题公式，于是，若A B，则A*B*证明：若AB，则AB，由定理14.3.1 知 A= A*，B= B*，于是，A* B*， 从而 A* B* 由对偶原理可知，若A为重言式，则

23、A*为矛盾式。因为1与0互为对偶式，若A为重言式，则A1,由对偶原理，A* 1* 即A* 0，也即A*为矛盾式。 当命题公式比较复杂时，采用真值表法或等值演算法来判定一个命题是重言式、矛盾时还是可满足式，和判定两个命题是否等值，有时都不很方便。下面介绍一种有效方法。372.2.析取范式与合取范式析取范式与合取范式( (定义14.3.3,14.3.4)q文字文字命题变元命题变元P P及其否定式及其否定式 P P统称为文字统称为文字. .q析取式析取式有限个文字的析取为析取式。有限个文字的析取为析取式。q合取式合取式有限个文字的合取为合取式。有限个文字的合取为合取式。q析取范式析取范式有限个合取式

24、的析取称为析取范有限个合取式的析取称为析取范式。式。q合取范式合取范式有限个析取式的合取称为合取范有限个析取式的合取称为合取范式。式。 析取范式和合取范式统称为范式。 特别，一个文字既可称为一个析取式，也可称为一个合取式。既可称为一个析取范式，也可称为一个合取范式。一个析取式或合取式，既可看作是合取范式，也可看作是析取范式。38例子：设P,Q,R是命题变元1.P，P，Q，R是文字。2.PQR是一个析取式； PQ R是一个合取式。3.P、Q、R中的每个文字既是析取式，又是合取式。4.(PQ) (Q R)是一个析取范式；(PQ) (QR)是一个合取范式。5.(PQ) R)S既不是析取范式，也不是合

25、取范式。 显然，任何析取范式的对偶式是合取范式，合取范式的对偶式是析取范式。 范式是一种形式规范的命题公式。39n定理定理14.3.314.3.3 对于任意命题公式，都对于任意命题公式，都存在与等值的析取范式和合取范式。存在与等值的析取范式和合取范式。 证明：依次执行如下步骤，可求得与等值的范式：1.利用PQ和PQ (PQ)(QP),将中的连接词“”和“”消去。2.利用( P)P以及De Morgan律，将中所有否定词“”放在命题变元之前。3.反复使用分配律，若求析取范式， 则使用对的分配，即P(QR)(PQ) (PR)；若求合取范式，则使用对的分配，即P(QR)(PQ)(PR)。最后可得到与

26、等值的范式。 注：此定理的证明可作为求范式的方法。40举例说明：举例说明：n试求(PQ)R)S的析取范式和合取范式解：1. 求析取范式 （PQ)R)S (PQ)R)S (PQ)R)S (PQ)R)S (PR)(QR)S 2. 求合取范式 （PQ)R)S （PQ)R)S (PQS)(RS)显然，一个命题公式的范式形式不是唯一的。因此，需要在范式的基础上，进一步定义唯一的标准形式。413.3.主析取范式主析取范式定义定义14.3.514.3.5：在含个命题变元在含个命题变元P P1 1, ,P,Pn n的合的合取式中，若每个文字恰好出现一次，且取式中，若每个文字恰好出现一次，且P Pi i出出现在

27、从左起的第位上，则称此合取式为关现在从左起的第位上，则称此合取式为关于于P P1 1, ,P,Pn n的一个极小项。的一个极小项。例如：n=3时，P1P2P3, P1P2P3都是关于P1,P2,P3 的极小项，而合取式 P1P3 P2,的变元未按顺序排列；P1 P2 中P3未出现：P1P2P3 P1, P1，P1出现在一个合取式中，故都不是关于P1,P2,P3 的极小项。v 如命题变元无下标，则按字母顺序排列。42v对于含n个命题变元的任何极小项m，在所有2n个解释中，有且只有一个解释使m为真，则将此解释(0,1数字串)对应的二进制数所对应的十进制数作为下标i，该极小项m记为mi。v例如：n=

28、2时,4个极小项的取值及表示。P1 P2 P1 P2 P1 P2P1 P2P1 P2 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1记为记为 m0 m1 m2 m343主析取范式：主析取范式：n定义定义14.3.614.3.6 设是含有个命题设是含有个命题变元变元P P1 1, ,P,Pn n的命题公式。的命题公式。是是的一个析取范式，若的一个析取范式，若G G中的合取式全中的合取式全是关于是关于P P1 1, ,P,Pn n的极小项，则称的极小项，则称为为G G的主析取范式。的主析取范式。n定理定理14.3.4 14.3.4 对于任意可满足的命

29、对于任意可满足的命题公式题公式G G，都存在与，都存在与G G等值的主析取范等值的主析取范式。式。44定理定理14.3.414.3.4的证明的证明证明：设G中含命题变元P1,Pn.由定理14.3.3，存在与G等值的析取范式 G=G1 G2 Gr.设Gi为可满足式,且下标由小到大排列.i=1,r对任意G，若G不是关于P1,Pn的极小项，则G中必缺少命题变元Pj1,Pjk.由于 G G（Pj1Pj1） (PjkPjk) (根据补余律和同一律) mi1mi2k于是， G化成了极小项之析取。最后将重复出现的极小项合并，就得到与G等值的主析取范式。45举例说明举例说明n试求PQ的主析取范式解： PQ P

30、Q (P(Q Q)(PP)Q) (PQ)(PQ)(PQ)(PQ ) (PQ)(PQ)(PQ) m0m1m3 （而m2没有出现在该式中） 只要知道一命题公式G的主析取范式，就可立即写出G的真值表,反之，若已知G的真值表，则表中所有使G为真的解释所对应的极小项的析取，便是G主析取范式。46主析取范式的用途主析取范式的用途n由于任何极小项恰有一个解释使其为真，因此，结合定理14.3.4不难证明，任意可满足的命题公式的主析取范式（在不考虑各极小项的次序的意义下）是唯一的。n有以上讨论可知，主析取范式有以下用途：1.判断两个命题公式是否等值。设A,B是命题公式，AB当且仅当A与B有相同的主析取范式。47

31、2.判断命题公式的类型。设A是含有n个命题变元的命题公式，于是：1)A为重言式，当且仅当A的主析取范式含全部2n个极小项。2)A为矛盾式，当且仅当A不存在主析取范式。3)A为可满足式，当且仅当A存在主析取范式。3.求满足或弄假命题公式的解释。设命题公式Ami1mi2 mik，则与下标等值的二进制所对应的解释满足A，其他解释弄假A。n主析取范式的对偶形式，称为主合取范式。主析取范式的对偶形式，称为主合取范式。484.主合取范式主合取范式定义定义14.3.7 在含个命题变元在含个命题变元P P1 1, ,P,Pn n的析取的析取式中，若每个文字恰好出现一次，且式中，若每个文字恰好出现一次，且P P

32、i i出现出现在左起的第位上，则称此析取式为关于在左起的第位上，则称此析取式为关于P P1 1, ,P,Pn n的一个极大项。的一个极大项。如：P1P2P3, P1P2P3.v 如命题变元无下标，则按字母顺序排列。v 与极小项类似，对于含n个命题变元的任何极大项，在所有的2n个解释中，有且只有一个解释M使该极大项为假，则将M对应的二进制数所对应的十进制数作为下标i，该极大项记为Mi。49主合取范式之定义主合取范式之定义定义定义14.3.814.3.8 设是含有个命题变元设是含有个命题变元P P1 1, ,P,Pn n的命题公式。的命题公式。是的一个是的一个合取范式，合取范式，G G中的析取式全

33、是关于中的析取式全是关于P P1 1, ,P,Pn n的极大项，则称的极大项，则称为为G G的的的的主合取范式。主合取范式。 50n定理定理 14.3.5 14.3.5 对于任意非重言式对于任意非重言式G G，都存在与，都存在与G G等值的主合取范式。等值的主合取范式。证明：设G中含命题变元P1,Pn.由定理14.3.3，存在与G等值的析取范式 G=G1 G2 Gr.设Gi为可满足式,且下标由小到大排列i=1,r。对任意G，若G不是关于P1,Pn的极大项，则G中必缺少命题变元Pj1,Pjk.由于 G G（Pj1Pj1）(Pjk Pjk) Mi1 Mi2k于是， G化成了极大项之合取。合并重复出

34、现的极大项，就得到与G等值的主合取范式。51举例说明：举例说明：n求求P Q Q的主合取范式的主合取范式解：解：P P Q Q (P(P (Q Q) ) (Q(Q (P P) (P(P Q) (P(PQ) (Q(Q P) (Q(QP) (P(P Q) (P(PQ) ( ( P Q Q) M M0 0 M M1 1 M M2 252主析取范式与主合取范式之关系主析取范式与主合取范式之关系n由于主合取范式与主析取范式在形式上对偶，所以可以通过主析取范式来求得对应的主合取范式。反之亦然。n首先注意到mi与Mi有关系：miMi，Mimi n例：M3=PQR,(被解释(0,1,1)弄假)，则 M3=PQ

35、R=m3 (被解释(0,1,1)满足）n不妨设含n个命题变元的公式G的主析取范式为 G=mj1mjK （含k个极小项） 因为GG1，是重言式即对2n个解释全为真。所以设 Gmi1mi2mi2n-K (2n-k个极小项)53n于是 G(G) （mi1mi2mi2n-K） mi1mi2 mi2n-K Mi1Mi2 Mi2n-Kn例：G=PQ 其主析取范式为 G=m3 其主合取范式为 G=M0 M1 M2n所以我们求得了主析取范式后，可相应的求得所以我们求得了主析取范式后，可相应的求得主合取范式。反之，一样。主合取范式。反之，一样。n主合取范式有类似于主析取范式的用途。 54n练习题：求（练习题：求

36、（ P PQ Q）（P PQ Q）的主析取）的主析取范式及主合取范式。范式及主合取范式。n解：解： 求主析取范式求主析取范式 （ P PQ Q）（P PQ Q） （ P PQ Q）（ P PQ Q） （P P Q Q） （ P PQ Q） （ P PQ Q） （P P Q Q） （P P Q Q） （ P PQ Q） （P P Q Q） （P P Q Q） （ P PQ Q） P P） （ P PQ Q） Q Q） （P P Q Q） （ P P P P） （ Q Q P P） （ P P Q Q） （ Q Q Q Q） （ P P Q Q） （P PQ Q ） （P P Q Q） m m1

37、1 m m2 2 m m3 3 55n求主合取范式 （PQ）（PQ） （PQ）（PQ）（PQ） （PQ）（PQ）（PQ） （PQ）（PQ）（PQ） （P（PQ）（PQ）（Q （PQ）（PQ） （PPQ）（PPQ）（QPQ）（QPQ） （PQ） M05614.4 推理理论推理理论n本节知识点：本节知识点： 本节主要掌握判断推理是否正确的三本节主要掌握判断推理是否正确的三种方法：种方法： 真值表法真值表法 等值演算法等值演算法 构造证明法构造证明法57定义定义14.4.1 14.4.1 设设G G和和H H是两个命题公式。如果是两个命题公式。如果G GH H是重言式，则称是重言式，则称H H是是G

38、 G的逻辑结果，的逻辑结果，或称或称G G蕴涵蕴涵H H，记为，记为G GH.H.这里的符号“”是一个关系词，而不是逻辑联结词。由联结词“”的定义知：GH是重言式，当且仅当对G，H的任意解释I，若I满足G,则I也满足H，因此，GH的充要条件是，满足G的解释均满足H.58定义定义14.4.214.4.2 设设G G1 1, ,G,Gn n，H H是命题公式，是命题公式，n n 1 1，若，若 G G1 1 G Gn n H H 则称则称H H是是G G1 1, ,G,Gn n 的逻辑结果，或称的逻辑结果，或称G G1 1, ,G,Gn n 共同蕴涵共同蕴涵H H。记为。记为 G G1 1，G G

39、n n H Hn其中，G1，Gn称为前提，H称为结论所谓推理正确，就是指由一组前提G1，Gn ，能逻辑地推出结论H。59n下面举例说明用真值表法与等值演算下面举例说明用真值表法与等值演算两种方法来判断推理是否正确两种方法来判断推理是否正确n例：如果我进城，我就去书店我没有进城所以我没有去书店n解：我进城：我去书店前提：PQ, P 结论：n推理的形式结构 （PQ） P）Q601.1. 真值表法真值表法(PQ) Q11100100由表知，使(PQ)为真的解释（，）使为假所以推理不正确n推理的形式结构 （PQ） P）Q612.2. 等值演算法等值演算法推理的形式结构 （PQ） P）Q (PQ)P Q

40、 (PQ)P) Q (PQ)P)Q (PQ)PQ PQ由于PQ不是重言式所以(PQ)P Q也不是重言式故推理不正确62 构造证明法构造证明法n构造证明法需在给定的规则下进构造证明法需在给定的规则下进行有时需要用到一些基本的蕴涵行有时需要用到一些基本的蕴涵式（见式（见P203P203）1. 附加：P(PQ) Q(PQ)2. 化简：(PQ)P (PQ)Q3. 合取：P,QPQ4. 假言推理：PQ,PQ5. 析取三段论：PQ, PQ6. 拒取式：PQ, QP7. 假言三段论：PQ,QRPR8. 构造性二难: PQ,RS,PRQS63n在构造证明法中常用的规则有：在构造证明法中常用的规则有：前提引入规

41、则：在证明的任何步骤中，前提引入规则：在证明的任何步骤中，都可以引入前提。都可以引入前提。结论引入规则：在证明的任何步骤中，结论引入规则：在证明的任何步骤中，所证明的结论都可以作为后续证明的所证明的结论都可以作为后续证明的前提。前提。置换规则：在证明的任何步骤中，命置换规则：在证明的任何步骤中，命题公式中的任何子公式都可以用等值题公式中的任何子公式都可以用等值的命题公式置换。的命题公式置换。 64n所谓命题公式的子公式G，是指在生成公式G的某一步所产生的符号串（也是命题公式）。例如，公式PQR的子公式有P，Q，R，QR,PQR,而PQ就不是它的子公式。n在数理逻辑中，证明是一个描述推理过程的命

42、题公式序列，其中每个命题公式，或者是已知的前提，或者是由某些前提应用推理规则得到的结论。下面通过例子来介绍构造证明法下面通过例子来介绍构造证明法65例：如果今天是星期日，则我去商场购物，例：如果今天是星期日，则我去商场购物，或在家看书如果今天下雨，则我不去或在家看书如果今天下雨，则我不去商场今天是星期日且下雨，所以我在商场今天是星期日且下雨，所以我在家看书家看书解：今天是星期日解：今天是星期日：我去商场购物：我去商场购物：我在家看书：我在家看书：今天下雨：今天下雨前提：前提：P P( (Q Q R), R), S SQ,P,SQ,P,S结论：结论：66前提：前提：P P( (Q Q R), R

43、), S SQ,P,S Q,P,S 结论：结论：n证明：1) P（Q） 前提引入2) P 前提引入3) 假言推理，根据(),() (假言推理规则：AB,AB)4) Q 前提引入5) 前提引入6) 假言推理，根据(4),(5)7) 析取三段论，根据(3),() (析取三段论规则：AB，AB) 运用构造证明法的两种技巧：附加前提证明法，归谬法。67附加前提证明法附加前提证明法n定理定理14.4.114.4.1设设H H1 1, ,H,Hm m,P,P共同蕴涵，则共同蕴涵，则 H H1 1, ,H Hm m，共同蕴涵，共同蕴涵P PQ Qn证明:由假设 (H1 Hm P)Q,即 (H1 Hm P)Q

44、 是重言式,又 (H1 Hm P)Q(H1 Hm P) Q(H1 Hm )(PQ)(H1 Hm )(PQ)所以, (H1 Hm )(PQ)也是重言式,于是 (H1 Hm )(PQ)故H1Hm 共同蕴涵PQ 68n注注: :若要证明若要证明P PQ Q是是H H1 1 HmHm的逻辑结果的逻辑结果, ,则只则只需证明需证明Q Q是是H H1 1Hm,PHm,P的逻辑结果，其中的逻辑结果，其中P P为附为附加前提加前提. .故此证明方法称为附加前提法。故此证明方法称为附加前提法。n例: 用附加前提证明法证明以下推理. 前提:PQ, QR 结论:PR证明:1. PQ 前提引入2. P 附加前提引入3

45、. Q 假言推理,(1)(2)4. QR 前提引入5. R 假言推理,(3)(4)用附加前提证明法可知,推理正确.69归谬法归谬法n定义定义14.4.314.4.3 设设H H1 1 H Hm m 是是m m个命题公式个命题公式. .若若H H1 1 H Hm m 是可满足的是可满足的, ,则称则称H H1 1 H Hm m是相容的是相容的. .否则称为不相容的否则称为不相容的. .n由定义知，H1 Hm 不相容，当且仅当 H1 HmPP(矛盾式），其中P为任意命题公式。70n定理定理14.4.214.4.2 设命题公式设命题公式H H1 1 H Hm m是相容的是相容的. .于于是是, (H

46、, (H1 1 H Hm m ) )G G当且仅当当且仅当H H1 1, ,H,Hm m, , G G是是不相容的不相容的. . 证明:因为 (H1 Hm )G (H1 Hm )G (H1 HmG) 所以, (H1 Hm )G当且仅当 (H1 HmG)PP当且仅当H1,Hm,G不相容.故定理成立.n注:此种将G作为附加前提,进而推出矛盾的证明称为归缪法。数学中的反证法属此类方法。71n例例: :用归谬法用归谬法, ,构造推理的证明构造推理的证明前提前提:P:P( ( (R(R S)S) Q Q),P,),P, S S 结论结论: : Q Q证明:1. P(RS) Q) 前提引入 2. P 前提

47、引入3. (RS)Q 假言推理,根据(1)，(2) 4. (Q) 否定结论作附加前提引入5. Q 置换规则，根据(4)6. RS 拒取式,根据(3)，(5)7. S 前提引入8. S 化简，根据(6)9. SS 合取，根据(7)，(8)由由(9)(9)得出矛盾得出矛盾, ,根据归谬法可知推理正确根据归谬法可知推理正确. .7214.5 命题演算的公理系统命题演算的公理系统n本节的知识点：本节的知识点： 1 1、公理系统、公理系统 2 2、证明、证明 3 3、演绎、演绎 731、公理系统、公理系统n 所谓公理系统，就是从一些最简单的概念出发，只承认一些再显然不过的事实（公理），使用极少数的逻辑规

48、则演绎出一些定理，如此形成的演绎系统就叫公理系统。相对古典公理而言，由命题逻辑的重言式组成的公理系统属于现代公理系统，系统中的每一个演绎过程中所遵循的公理和推演规则必须是极其明确的，不允许有任何含混。此外，作为公理，它必须能充分确定所要研究的事物的特征和满足一些必要的条件。74n 在命题逻辑中，判断两个公式是否等值，判断一个推理是否正确，都归结为判断一个公式是否为重言式。因此，重言式表示了命题逻辑中一个重要逻辑规律。然而，命题逻辑中的重言式有无穷多个。为了掌握重言式的规律，就必须将所有重言式作为一个整体来研究，公理系统就是这样一个整体。n 本书所讨论的公理化方法是一种语法方法，既不使用解释，也

49、不使用真值和真值表，而是用形式推演来证明一些等值公式。75公理系统的定义公理系统的定义n定义定义14.5.114.5.1 公理系统公理系统L L定义如下：定义如下：1)字母表：P1,P2,Pn,(,)。2)合式公式：i.Pi是合式公式，i=1,2,；ii.如果A,B是合式公式，则(A),(AB)也是合式公式；iii.所有合式公式均为有限次地使用所得到的符号串。76定义定义14.5.114.5.1的续的续3)公理：设A,B,C为任意的合式公式： L1：(A(BA) L2:(A(BC)(AB)(AC) L3： (A)(B)(BA)4)推理规则：从A和(AB)可以推得B，称为分离规则，简称MP规则，记为 mp A,AB B 当规定“”的优先级高于“”时，约定，以上公理集合式公式中最外层括号以及(A)的括号可以省略。772、证明的定义、证明的定义n定义定义14.5.214.5.2 L中的证明是一个由合式公式A1,A2,An组成的有穷非空序列，使得对于每个i(1in)，Ai或者是公理，或者是由序列中的两个合式公式Aj，Ak (j,ki)应用MP规则直接推出的结论。此序列称作An在L中的证明，并称An为L的定理，记为An。78证明的例子证明的例子n例例1. 给出下面定理的证明：给出下面定理的证明：a)(A A)解：其证明序列如下：1)(A (A A)A)(A (AA) (A A) (L2)2