01　数理逻辑.ppt

《01　数理逻辑.ppt》由会员分享，可在线阅读，更多相关《01　数理逻辑.ppt（151页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、PPT模板下载：/moban/ 行业PPT模板：/hangye/ 节日PPT模板：/jieri/ PPT素材下载：/sucai/PPT背景图片：/beijing/ PPT图表下载：/tubiao/ 优秀PPT下载：/xiazai/ PPT教程： /powerpoint/ Word教程： /word/ Excel教程：/excel/ 资料下载：/ziliao/ PPT课件下载：/kejian/ 范文下载：/fanwen/ 试卷下载：/shiti/ 教案下载：/jiaoan/ 字体下载：/ziti/ 01数理逻辑LOGO第1篇数理逻辑数理逻辑 逻辑学分为辨证逻辑与形式逻辑两种 。 用数学方法来研究

2、推理的规律称为数理逻辑 现代数理逻辑分为四论、两演算 四论：证明论，递归论（它们与形式语言语法有关），模型论，公理化集合论（它们与形式语言的语义有关）。 两演算：命题演算、谓词演算 第第 1 章章 命题逻辑命题逻辑 1.1 命题及其表示 1.2 逻辑联结词 第第 1 章章 命题逻辑命题逻辑1.1 命题及其表示命题及其表示 定义定义1.1.1 能够判断真假的陈述句称为命题命题（Proposition）。命题的判断结果称为命题的真值，常用 1 （或大写字母 T ）表示真，用 0 （或大写字母 F ）表示假。凡是与事实相符的陈述句即真值为真的命题称为真命题，而与事实不符合的陈述句即真值为假的命题称为

3、假命题。 从这个定义可以看出命题有两层含义： (1) 命题是陈述句。其他的语句，如疑问句、祈使句、感叹句均不是命题； (2) 这个陈述句表示的内容可以分辨真假，而且不是真就是假，不能不真也不假，也不能既真又假。 第第 1 章章 命题逻辑命题逻辑1.1 命题及其表示命题及其表示 例1：判断下列语句是否为命题，若是并指出其真值。 （ 1 ）北京是中国的首都。 真命题 （ 2 ）2是偶数且3也是偶数。 假命题 （ 3 ）2+2=5 。 假命题 （ 4 ）请勿吸烟! 不是命题 （ 5 ）乌鸦是黑色的吗？ 不是命题 （ 6 ）这个小男孩多勇敢啊！ 不是命题 （ 7 ）地球外的星球上存在生物 。是命题，真

4、假值客观存在 （ 8 ）1+101=110。二进制中为真命题，二进制中为假命题 （ 9 ）x + y=5。不是命题 （10 ）我正在说谎。悖论 ，不是命题第第 1 章章 命题逻辑命题逻辑1.1 命题及其表示命题及其表示 定义定义1.1.2 不能被分解为更简单的陈述语句的命题称为原子命题(Simple Proposition )。由两个或两个以上原子命题通过联结词组合而成的命题称为复合命题(Compound Proposition )。 例1.1.1中的命题(1)(3)(7)(8)为原子命题，而命题(2)是复合命题，是由“2是偶数。”与“3是偶数。”两个原子命题由联结词“且”组成的，该命题的真值

5、不仅依赖于这两个组成它的命题，而且还依赖于这个联结词的意义。像这样的联结词称为逻辑联结词逻辑联结词（logical connectives）。 约定用大写字母P，Q，R，S等表示原子命题（为了避免与真值T及F混淆，建议不用T及F表示原子命题）。例如，用P表示“北京是中国的首都”，Q表示“5可以被2整除”等。 第第 1 章章 命题逻辑命题逻辑1.1 命题及其表示命题及其表示 定义定义1.1.3 表示原子命题的符号称为命题标识符命题标识符(Identifier)。 定义定义1.1.4用一个确定的命题代入一个命题标识符（如P），称为对P进行指派指派（赋值，或解释）。 如果命题标识符P代表命题常元则意

6、味它是某个具体原子命题的符号化，如果P代表命题变元则意味着它可指代任何具体原子命题。本书中如果没有特别指明，通常来说命题标识符P等是指命题变元，即可指代任何原子命题。 第第 1 章章 命题逻辑命题逻辑1.2 逻辑联结词逻辑联结词 定义定义1.2.1 设P表示一个命题，P的否定(Negation)是一个新的命题，记为P（读作非P）。规定若P为1，则P为0；若P为0，则P为1。 P的取值情况依赖于P的取值情况，真值情况见表1-1。表表1-1联结词联结词“”的定义的定义PP1001第第 1 章章 命题逻辑命题逻辑1.2 逻辑联结词逻辑联结词 定义定义1.2.2 设P、Q为两个命题，P和Q的合取(Co

7、njunction)是一个复合命题，记为PQ（读作P与Q），称为P与Q的合取式。规定P与Q同时为1时，PQ为1，其余情况下，PQ均为0。 日常用语中的“与”、“和”、“也”、“并且”、“而且”、“既，又”、“一面，一面”等可用合取词表示。 联结词“”的定义见表1-2。PQPQ000010100111第第 1 章章 命题逻辑命题逻辑1.2 逻辑联结词逻辑联结词 定义定义1.2.3 设P、Q为两个命题，P和Q的析取(Disjunction)是一个复合命题，记为PQ（读作P或Q），称为P与Q的析取式。规定当且仅当P与Q同时为0时，PQ为0，否则PQ均为1。 日常用语中的“或”，“要么要么”等可用析取

8、词表示。表表1-3 联结词联结词“”的定义的定义PQPQ000011101111第第 1 章章 命题逻辑命题逻辑1.2 逻辑联结词逻辑联结词 定义定义1.2.4 设P、Q为两个命题，P和Q的条件(Conditional)命题是一个复合命题，记为PQ（读作若P则Q），其中P称为条件的前件，Q称为条件的后件。规定当且仅当前件P为1， 后件Q为0时，PQ为0，否则PQ均为1。 日常用语中的“若则”，“如果那么”，“只有才”等可用条件词表示。 表表1-4 联结词联结词“”的定义的定义PQPQ001011100111第第 1 章章 命题逻辑命题逻辑1.2 逻辑联结词逻辑联结词 定义定义1.2.5 设P、

9、Q为两个命题，其复合命题PQ称为双条件(Biconditional)命题，PQ读作P当且仅当Q。规定当且仅当P与 Q真值相同时，PQ为1，否则PQ均为0。 表表1-5联结词联结词“”的定义的定义PQPQ001010100111第第 1 章章 命题逻辑命题逻辑1.3 命题公式与翻译命题公式与翻译 定义定义1.3.1 命题公式归纳定义如下： （1）单个命题变元是命题公式； （2）如果A是命题公式，则A也是命题公式； （3）如果A和B是命题公式，则(AB)，(AB)，(AB)，(AB)均是命题公式； （4）当且仅当能够有限次地应用（1）、（2）、（3）所得到的包含命题变元、联结词和括号的符号串是命题

10、公式（又称为合式公式，或简称为公式）。 定义是以递归的形式给出的，其中（1）称为基础，（2）、（3）称为归纳，（4）称为界限。定义中的符号A,B不同于具体公式里的P、Q、R等符号（一般P、Q、R来表示原子命题标识符），它可以用来表示任意的命题公式。 第第 1 章章 命题逻辑命题逻辑1.3 命题公式与翻译命题公式与翻译 命题公式是没有真假的,如果把公式中的命题变元代以确定的命题命题，则该公式便是一个命题，才有确定的真值。因此，对复合命题的研究可化为对公式的研究，今后我们将以公式为主要研究对象。 为了减少命题公式中使用括号的数量，规定： （1）逻辑联结词的优先级别由高到低依次为、。 （2）具有相同

11、级别的联结词，按出现的先后次序进行计算，括号可以省略。 （3）命题公式的最外层括号可以省去。 例例1.3.1 （PQ）R也可以写成PQR，（PQ）R也可写成PQR，（PQ）R）也可写成（PQ）R，而P（QR）中的括号不能省去。 定义定义1.3.2 设B是命题公式A的一部分，且B也是命题公式，则称B为A的子公式子公式。第第 1 章章 命题逻辑命题逻辑1.3 命题公式与翻译命题公式与翻译 把一个文字描述的命题相应地写成由命题标识符、逻辑联结词和圆括号表示的命题形式称为命题的符号化或翻译。 命题符号化的一般步骤： （1）明确给定命题的含义； （2）找出命题中的各原子命题，分别符号化。 （3）使用合适

12、的逻辑联结词，将原子命题分别连接起来，组成复合命题的符号化形式。 把命题符号化，是不管具体内容而突出思维形式的一种方法。注意在命题符号化时，要正确地分析和理解自然语言命题，不能仅凭文字的字面意思进行翻译。第第 1 章章 命题逻辑命题逻辑1.3 命题公式与翻译命题公式与翻译例例1.3.2 将下列用自然语言描述的命题符号化。（1）我和他既是弟兄又是同学。 解解 令P：我和他是弟兄；Q：我和他是同学，则该语句可符号化为PQ。 （2）我和你之间至少有一个要去海南岛。 解解 令P：我去海南岛；Q：你去海南岛，则该语句可符号化为PQ。 （3）如果他没来见你，那么他或者是生病了，或者是不在本地。 解解 令P

13、：他来见你；Q：他生病；R：他在本地，则该语句可符号化为P(QR)。 （4）n是偶数当且仅当它能被2整除。 解解 令P：n是偶数；Q：n能被2整除，则该语句可符号化为PQ。第第 1 章章 命题逻辑命题逻辑1.3 命题公式与翻译命题公式与翻译（5）只有你走，我才留下。解解这个命题的意义也可以理解为：如果我留下了，那么你一定走了。令P：你走。Q：我留下。则该语句可符号化为：QP。与原命题类似的命题如：仅当你走我才留下。我留下仅当你走。当我留下你得走。（6）仅当天不下雨且我有时间，我才上街。解解设P：天下雨。Q：我有时间。R：我上街。该语句可符号化为：R（PQ）。第第 1 章章 命题逻辑命题逻辑1.

14、3 命题公式与翻译命题公式与翻译（7）你将失败，除非你努力。解解这个命题的意义可以理解为：如果你不努力，那么你将失败。令P：你努力。Q：你失败。则该语句可符号化为：PQ。含有“除非”的命题，“非”是充分条件，译成条件命题时，“非”是条件的前件。（8）A中没有元素，A就是空集。解解令P：A中有元素。Q：A是空集。则该语句可符号化为：PQ。（9）张三与李四是表兄弟。解解此命题是一个原子命题，“与是表兄弟。”表示两个对象之间的关系。“张三是表兄弟。”及“李四是表兄弟。”都不是命题。所以上述命题只能符号化为P的形式。其中P：张三与李四是表兄弟。 第第 1 章章 命题逻辑命题逻辑1.4 真值表与命题公式

15、分类真值表与命题公式分类 定义定义1.4.1 设P1，P2，Pn是出现在命题公式中的全部命题变元，给P1，P2，Pn各指定一个真值，称为对公式的一个赋值赋值（或解释解释或真值指派真值指派）。 若指定的一组值使公式的真值为1，则这组值称为公式的成真赋值成真赋值。 若指定的一组值使公式的真值为0，则这组值称为公式的成假赋值成假赋值。 定义定义1.4.2 设A是含有n个命题变元的命题公式，将命题公式A在所有赋值之下取值的情况汇列成表，称为命题公式命题公式A的真值表的真值表。 为方便构造真值表，特约定如下： 命题变元按字典序排列。 对每组赋值，以二进制数从小到大或从大到小顺序列出。 若公式较复杂，可先

16、列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。 第第 1 章章 命题逻辑命题逻辑1.4 真值表与命题公式分类真值表与命题公式分类 例例1.4.1 利用真值表求命题公式(P(QR)的成真赋值和成假赋值。 PQRQRP(QR) (P(QR)000011110011001101010101011101111111011100001000第第 1 章章 命题逻辑命题逻辑1.4 真值表与命题公式分类真值表与命题公式分类 例例1.4.2利用真值表求命题公式（PQ）Q的成真赋值和成假赋值。PQPQ（PQ）（PQ）Q00100011001001011100第第 1 章章 命题逻

17、辑命题逻辑1.4 真值表与命题公式分类真值表与命题公式分类 利用真值表求命题公式（PQ）（PQ）的成真赋值和成假赋值。 PQPQ（PQ）PQ（PQ）（PQ）000111010111100111111001第第 1 章章 命题逻辑命题逻辑1.4 真值表与命题公式分类真值表与命题公式分类 定义定义1.4.3 设A为任一命题公式。 （1）若对公式A的命题变元所有赋值均是成真指派，则公式A称为重言式重言式或永真式永真式； （2）若对公式A的命题变元所有赋值均是成假指派，则公式A称为矛盾式矛盾式或永假式永假式； （3）若公式A中至少有一个成真赋值，则公式A称为可满足式可满足式。 从定义不难看出以下几点：

18、 1）重言式一定是可满足式，但反之不真。因而，若公式A是可满足式，且它至少存在一个成假指派，则称A为非重言式的可满足式。 2）真值表可用来判断公式的类型： 若真值表最后一列全为1，则公式为重言式； 若真值表最后一列全为0，则公式为矛盾式； 若真值表最后一列中至少有一个1，则公式为可满足式。 第第 1 章章 命题逻辑命题逻辑1.4 真值表与命题公式分类真值表与命题公式分类 例例1.4.4 判断下列公式的类型。 （1）(PQ)Q重言式 （2）(QP) (PQ) 矛盾式 (3)(PQ)(PQR)可满足式 从以上的讨论可知，真值表不但能准确地给出公式的成真赋值和成假赋值，而且能判断公式的类型。但当命题

19、变元较多时，计算量大，在后面的章节中还要介绍其他的方法。 第第 1 章章 命题逻辑命题逻辑1.5 等价公式与蕴含式等价公式与蕴含式 定义定义1.5.1 给定两个命题公式A和B，设P1，P2，Pn是出现在命题公式A和B中的全部命题变元，若对所有命题变元P1，P2，Pn任一组赋值，公式A和B的真值都对应相同，则称公式A与B等价或逻辑相等(Equivalence)，记作式AB。 定理定理1.5.1 对命题公式A和B，AB当且仅当AB是重言式。证明 若AB是重言式，则在任一解释下，AB的真值都为真。依AB的定义知，当AB为真时，A和B必有相同的真值。于是，在任一解释下，A和B都有相同的真值，从而有AB

20、。反过来，若AB，则在任一解释下A和B都有相同的真值，依AB的定义知，此时AB为真，从而AB是重言式。 第第 1 章章 命题逻辑命题逻辑1.5 等价公式与蕴含式等价公式与蕴含式 需要注意的是，“”不是逻辑联结词，因而“AB”不是命题公式，只是表示两个命题公式之间的一种等价关系，即若AB，A和B没有本质上的区别，最多只是A和B具有不同的形式而已。 “”具有如下的性质：（1）自反性：AA。（2）对称性：若AB，则BA。（3）传递性：若AB，BC，则AC。 给定n个命题变元，根据公式的形成规则，可以形成许多个形式各异的公式，但是有很多形式不同的公式具有相同的真值表。因此引入公式等价的概念，其目的就是

21、将复杂的公式简化。 第第 1 章章 命题逻辑命题逻辑1.5 等价公式与蕴含式等价公式与蕴含式 下面介绍两种证明公式等价的方法。 1真值表法真值表法 由公式等价的定义可知，利用真值表可以判断任何两个公式是否等价。例例1.5.1 证明PQ(PQ)(QP)证明证明 命题公式PQ与(PQ)(QP)的真值表见表1-12。由表1-12可知，在任意赋值下PQ与(PQ)(QP)两者的真值均对应相同。因此 PQ(PQ)(QP)表表1-12 PQ与(PQ)(QP)的真值表的真值表PQPQQP(PQ)(QP)PQ001111011000100100111111第第 1 章章 命题逻辑命题逻辑1.5 等价公式与蕴含式

22、等价公式与蕴含式 常用等价式（1）双重否定律： PP（2）结合律： (PQ)RP(QR)，(PQ)RP(QR)，(PQ)RP(QR)（3）交换律： PQQP，PQQP，PQQP（4）分配律： P(QR) (PQ) (PR)， P(QR) (PQ) (PR)（5）幂等律： PPP，PPP（6）吸收律： P(PQ)P，P(PQ)P（7）德.摩根律：(PQ)PQ，(PQ)PQ（8）同一律： P0P，P1P（9）零律： P11，P00第第 1 章章 命题逻辑命题逻辑1.5 等价公式与蕴含式等价公式与蕴含式 常用等价式（10）否定律： PP1，PP0（11）蕴含律： PQPQ（12）等价律： PQ( P

23、Q)(QP) PQ（13）输出律：(PQ)RP(QR)（14）归谬律：(PQ)(PQ) P（15）逆反律：PQQP第第 1 章章 命题逻辑命题逻辑1.5 等价公式与蕴含式等价公式与蕴含式 2等值演算法等值演算法 定理定理1.5.2（代入规则）（代入规则）在一个永真式A中，任何一个原子命题变元R出现的每一处用另一个公式代入，所得的公式B仍为永真式。 证明：因为永真式对于任何指派，其真值都是1，与每个命题变元指派的真假无关，所以，用一个命题公式代入到原子命题变元R出现的每一处，所得到的命题公式的真值仍为1。 定理定理1.5.3（置换规则）（置换规则） 设X是命题公式A的一个子公式，若XY，如果将公

24、式中的X用Y来置换，则所得到的公式B与公式A等价，即AB。 证明：因为XY，所以在相应变元的任一种指派情况下，X与Y的真值相同，故以Y取代X后，公式B与公式A在相应的指派情况下真值也必相同，因此AB。 第第 1 章章 命题逻辑命题逻辑1.5 等价公式与蕴含式等价公式与蕴含式有了上述的15组等价公式及代入规则和置换规则后，就可以推演出更多的等价式。由已知等价式推出另外一些等价式的过程称为等值演算等值演算(Equivalent Calculation)。 例例1.5.3 证明下列公式等价。 （1）(PQ)RP(QR)（2）(PQ) (PQ) (PQ)( PQ)证明证明 （1） (PQ)R PQRP

25、(QR) P(QR)P (QR) （2） (PQ) (PQ) (PQ) P)( (PQ) Q) (PP)( QP)(PQ)( QQ) 1( P Q)(PQ)1 (PQ) ( P Q) (PQ) (PQ) 第第 1 章章 命题逻辑命题逻辑1.5 等价公式与蕴含式等价公式与蕴含式 等值演算还可以用来解决常见的推理题。 例例1.5.4 某件事情是甲、乙、丙、丁4人中某一个人干的。询问4人后回答如下：（1）甲说是丙干的；（2）乙说我没干；（3）丙说甲讲的不符合事实；（4）丁说是甲干的。若其中3人说的是真话，一人说假话，问是谁干的？ 例例1.5.5 A、B、C、D 4人进行百米竞赛，观众甲、乙、丙对比赛

26、的结果进行预测。甲：C第一，B第二；乙：C第二，D第三；丙：A第二，D第四。比赛结束后发现甲、乙、丙每个人的预测结果都各对一半。试问实际名次如何（假如无并列者）？第第 1 章章 命题逻辑命题逻辑1.5 等价公式与蕴含式等价公式与蕴含式 蕴含式蕴含式 定义定义1.5.2 设A、B为两个命题公式，若AB为重言式，则称“A蕴含( Implication)B”，记作AB。 蕴含关系具有如下的性质： (1) A为重言式，AB，则B必为重言式； (2) 自反性 AA； (3) 反对称性 若AB且 BA 则AB； (4) 传递性 若AB且 BC 则AC； (5) 若A B且 A C 则A B C 。 (6)

27、 若AB且CB，故A CB。第第 1 章章 命题逻辑命题逻辑1.5 等价公式与蕴含式等价公式与蕴含式 定理定理1.5.4 AB的充分必要条件是AB且BA。 证明：若AB，则AB为重言式，而AB(AB)( BA)，故AB且BA均为重言式，即AB且BA。 反之，若AB且BA，则AB且BA均为重言式，于是(AB)( BA)为重言式，即AB为重言式，故AB。 要证明AB，只需证明AB为重言式即可。因此，前面介绍的真值表法和等值演算法均可应用。 第第 1 章章 命题逻辑命题逻辑1.5 等价公式与蕴含式等价公式与蕴含式 证明AB的各种方法 1真值表法真值表法 2等值演算法等值演算法 3逻辑分析法逻辑分析法

28、 逻辑分析法包括以下两种形式：逻辑分析法包括以下两种形式：（1）肯定前件法：假定前件）肯定前件法：假定前件A为真，推出后件为真，推出后件B为真，则为真，则AB。（2）否定后件法：假定后件）否定后件法：假定后件B为假，推出前件为假，推出前件A为假，则为假，则AB。理由是：对于条件式理由是：对于条件式AB，根据条件联结词的运算规则可知：，根据条件联结词的运算规则可知： 只有前件只有前件A为真，后件为真，后件B为假时为假时AB为假，其余情况均为为假，其余情况均为真。真。第第 1 章章 命题逻辑命题逻辑1.5 等价公式与蕴含式等价公式与蕴含式 因此有因此有（1）若从假设前件）若从假设前件A为真时能推导

29、出后件为真时能推导出后件B一定也为真，说一定也为真，说明无论前件明无论前件A为真为假，为真为假，AB都为真，即都为真，即AB为重言式，为重言式，也即也即AB。（2）若从假设后件）若从假设后件B为假时能推导出前件为假时能推导出前件A一定也为真，说一定也为真，说明无论前件明无论前件A为真为假，为真为假，AB都为真，即都为真，即AB为重言式，为重言式，也即也即AB。 第第 1 章章 命题逻辑命题逻辑1.5 等价公式与蕴含式等价公式与蕴含式 例例1.5.8 逻辑证明下列蕴含式。（1）Q(PQ)P（2）P (PQ)Q证明证明 （1）假设前件Q(PQ)为真，则Q为真，PQ为真；由此有Q为假，P为真。因此Q

30、(PQ)P。（2）假设后件Q为假，若P为真，则PQ为假，有P (PQ)为假。若P为假，则PQ为真，有P (PQ)为假。综上，若后件Q为假，无论P为真还是假，前件P (PQ)均为假。因此P (PQ)Q。第第 1 章章 命题逻辑命题逻辑1.5 等价公式与蕴含式等价公式与蕴含式 常用的蕴含式 (1) PQP，PQQ；(2) PPQ，QPQ；(3) P PQ；(4) QPQ；(5) (PQ)P；(PQ)Q；(6) P(PQ)Q； (7) Q(PQ)P；(8) P(PQ)Q ；(9) (PQ)(QR) PR；(10) (PQ)(PR) (QR) R；(11) (PQ) (RS)(PR)(QS)；(12)

31、 (PQ) (Q R) P R第第 1 章章 命题逻辑命题逻辑1.7 对偶与范式对偶与范式 对偶式对偶式 定义定义1.7.1 在只含有逻辑联结词，的命题公式A中，若把将换成，换成，如果A中有T（或1）或者F（或0）就分别换成F（或0）或T（或1），所得到的新公式A* 称为A的对偶式对偶式(Dualistic Formula)。 显然A*与A互为对偶式。 例例1.7.1 写出下列公式的对偶式。(1) (PR)(PQRQ)；(2) (PQ)F；(3) P(QT)解解 (1) 令A=(PR)(PQRQ)，则 A=(PR)(PQ)RQ)。故 A* =(PR)(PQ)RQ)。(2)，(3)中二式的对偶式

32、分别为(PQ)T，P(QF)。第第 1 章章 命题逻辑命题逻辑1.7 对偶与范式对偶与范式对偶原理对偶原理 定理定理1.7.1设P1，P2，P n 是公式A和A*中出现的原子命题变元，现采用函数记法分别为 A(P1，P2，P n )，A*(P1，P2，P n )，则A(P1，P2，P n ) A*(P1，P2，P n)，A(P1，P2，P n)A*(P1，P2，P n )。定理定理1.7.2（对偶原理）（对偶原理）设A，B为合式命题公式，若AB，则A*B* 。证明：设P1，P2，P n 是出现在A，B中的原子命题变元。因A(P1，P2，P n ) B(P1，P2，P n )，故A(P1，P2，

33、P n ) B(P1，P2，P n )是重言式。即：A（P1，P2，P n）B(P1，P2，P n)是重言式，故A(P1，P2，P n)B(P1，P2，P n)。由定理1.7.1有 A(P1，P2，P n) A*(P1，P2，P n )，B(P1，P2，Pn)B*(P1，P2，Pn )，由合式公式的等价具有传递性，可得 A*（P1，P2，Pn ）B*(P1，P2，Pn )。从而A*B*。第第 1 章章 命题逻辑命题逻辑1.7 对偶与范式对偶与范式 命题公式的范式命题公式的范式 1简单析取式与简单合取式简单析取式与简单合取式 定义定义1.7.2 单个的命题变元及其否定形式称为文字。如P，Q等。

34、定义定义1.7.3 仅由有限个文字组成的析取式称为简单析取式。仅由有限个文字组成的合取式称为简单合取式。 例如P Q，PQ，PQ ，PQ，P，Q等都是简单析取式；P Q，PQ，PQ，PQ，P，Q等都是简单合取式。一个文字既是简单析取式，又是简单合取式。 定理定理1.7.3 简单析取式是重言式当且仅当它同时含有某个命题变元及其否定形式。 定理定理1.7.4 简单合取式是矛盾式当且仅当它同时含有某个命题变元及其否定形式。 第第 1 章章 命题逻辑命题逻辑1.7 对偶与范式对偶与范式 2析取范式与合取范式析取范式与合取范式 定义定义1.7.4 由有限个简单合取式组成的析取式称为析取范析取范式式（Di

35、sjunctive Normal Form）。亦即该公式具有形式A1A2An，其中Ai(i=1,2,n)为简单合取式简单合取式。由有限个简单析取式组成的合取式称为合取范式合取范式（Conjunctive Normal Form）。亦即该公式具有形式B1B2Bm，其中Bj(j=1,2,m)为简单析取式简单析取式。析取范式与合取范式统称为范式范式。 定理定理1.7.5（范式存在定理范式存在定理）任何一个命题公式都存在着与之等价的析取范式和合取范式。第第 1 章章 命题逻辑命题逻辑1.7 对偶与范式对偶与范式 求任一公式的析取范式和合取范式的步骤：（1）利用蕴含等值式和等价等值式消去除，以外公式中出

36、现的所有逻辑联结词。（2）利用德摩根律和双重否定律将联结词“”向内深入，使之只作用于命题变元；（3）利用分配律、结合律将公式转化为合取范式或析取范式。 例例1.7.4求P(PQ)的合取和析取范式。解：解： P(PQ)P(PQ)P(P Q) （合析取范式）(PP)QTQ （合析取范式）TPP。 第第 1 章章 命题逻辑命题逻辑1.7 对偶与范式对偶与范式 3范式的应用范式的应用 利用析取范式和合取范式可以判定一个命题公式是重言式还是矛盾式。 定理定理1.7.6 一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。第第 1 章章 命题

37、逻辑命题逻辑1.7 对偶与范式对偶与范式 命题公式的主析取范式和主合取范式命题公式的主析取范式和主合取范式 1主析取范式主析取范式 定义定义1.7.5 在含有n个命题变元的简单合取式中，若每个命题变元与其否定不同时存在，而二者之一必出现且仅出现一次，且第i个命题变元或其否定出现在从左算起的第i位上(若命题变元无下标,则按字典顺序排序)，则称该简单合取式为极小项极小项。第第 1 章章 命题逻辑命题逻辑1.7 对偶与范式对偶与范式表表1-20 两个命题变元两个命题变元P和和Q生成的生成的4个极小项的真值表个极小项的真值表m（二进制）m00m01m10m11PQPQPQPQPQ00100001010

38、0100010110001m（十进制）m0m1m2m3第第 1 章章 命题逻辑命题逻辑1.7 对偶与范式对偶与范式 由真值表可得到极小项具有如下性质：（1）各极小项的真值表都不相同。（2）每个极小项当其真值指派与对应的二进制编码相同时，其真值为真，在其余2n-1种指派情况下，其真值均为假。（3）任意两个极小项的合取式是矛盾式。例如m0 m1(PQ) (PQ)0。（4）全体极小项的析取式为永真式。 定义定义1.7.6 由若干个不同的极小项组成的析取式称为主析取范式(The Principal Disjunctive Normal Form )。与公式等价的主析取范式称为的主析取范式。 定理定理1

39、.7.7 任意含n个命题变元的非永假式命题公式都存在着与之等价的主析取范式，并且其主析取范式是唯一的。 第第 1 章章 命题逻辑命题逻辑1.7 对偶与范式对偶与范式 一个命题公式的主析取范式可通过两种方法求得，一是由公式的真值表得出，即真值表法；另一是由基本等价公式推出，即等值演算法。 （1）真值表法 定理定理1.7.8 在真值表中，命题公式A的真值为真的赋值所对应的极小项的析取即为命题公式A的主析取范式。 利用真值表法求主析取范式的基本步骤为：（1）列出公式的真值表。（2）将真值表中的最后一列中的1的赋值所对应的极小项写出。（3）将这些极小项进行析取。第第 1 章章 命题逻辑命题逻辑1.7

40、对偶与范式对偶与范式例例1.7.8 利用真值表法求（PQ）的主析取范式。解解 （PQ）的真值表见表1-21。表表1-21 （P Q）的真值表）的真值表PQ（PQ）001011101110从表1-21中可以看出，该公式在其真值表的00行、01行、10行处取真值1，所以（PQ）m0 m1 m2（PQ）（PQ）（PQ）。第第 1 章章 命题逻辑命题逻辑1.7 对偶与范式对偶与范式例例1.7.9用真值表法求用真值表法求 (PQ)R的主析取范式。解解 (PQ)R的真值表见表1-22。表表1-22(P Q)R的真值的真值表表PQRPQ(PQ)R0000000101010000110110000 10101

41、1101111111从表1-22中可以看出，该公式在其真值表的001行、011行、101行、110行和111行处取真值1，所以 (PQ)Rm1m3m5m6m7(PQR) (PQR) (PQR) (PQR) (PQR)。第第 1 章章 命题逻辑命题逻辑1.7 对偶与范式对偶与范式 （2）等值演算法）等值演算法 除了用真值表法来求一个命题公式的主析取范式外，还可以利用公式的等值演算方法来推导。具体的求解步骤如下：（1）利用蕴含等值式和等价等值式消去公式中的联结词“”和“”；（2）利用德摩根律和双重否定律将联结词“”向内深入，使之只作用于命题变元；（3）利用分配律将公式化为析取范式；（4）利用同一律

42、消去矛盾的简单合取式； （5）利用等幂律消去相同的简单合取式以及简单合取式中相同的合取项；（6）利用同一律、分配律将不包含某一命题变元的简单合取式置换为包含这一命题变元的简单合取式，直到每一简单合取式成为极小项为止。例如P QP Q (RR) ( PQR) ( PQR)。并将极小项按顺序排列。第第 1 章章 命题逻辑命题逻辑1.7 对偶与范式对偶与范式 例例1.7.11 求（PQ）Q的主析取范式。 解解 （PQ）Q （PQ）Q （PQ） Q （PQ） (PP) Q ) （PQ） (P Q) (P Q) （PQ） (P Q) m1 m3 第第 1 章章 命题逻辑命题逻辑1.7 对偶与范式对偶与范

43、式 例例1.7.12 求A=(PQ)(QR)(PR)的主析取范式。 解解 A=(PQ)(QR)(PR) (PQ)Q)( (PQ)R) (PR) （结合律，分配律） (Q (PR) (QR) (PR) （吸收律，分配律） (Q (PR) (PR) （吸收律，交换律） (Q(PR) (PR) (PR) （分配律） (QP) ( QR) ( PR(PR) （分配律，结合律） (QP) ( QR) ( PRP) ( PRR) （分配律） (QP) ( QR) ( PR) （吸收律） (PQ(RR) (PP)QR) ( P(QQ)R) (交换律，同一律) (PQR) ( PQR) (PQR) (PQR)

44、 (PQR) (PQR) (PQR) ( PQR) (PQR) (PQR) m2 m3 m5 m7第第 1 章章 命题逻辑命题逻辑1.7 对偶与范式对偶与范式 2主合取范式主合取范式 定义定义1.7.7 在含有n个命题变元的简单析取式中，若每个命题变元与其否定不同时存在，而二者之一必出现且仅出现一次，且第i个命题变元或其否定出现在从左算起的第i位上(若命题变元无下标,则按字典顺序排序)，则称该简单析取式为极大项。 第第 1 章章 命题逻辑命题逻辑1.7 对偶与范式对偶与范式表表1-24 两个命题变元两个命题变元P和和Q生成的生成的4个极大项的真值表个极大项的真值表M（二进制）M00M01M10

45、M11P Q P QPQPQPQ0 001110 110111 011011 11110M（十进制）M0M1M2M3第第 1 章章 命题逻辑命题逻辑1.7 对偶与范式对偶与范式 由真值表可得到极大项具有如下性质：1）各极大项的真值表都不相同。2）每个极大项当其真值指派与对应的二进制编码相同时，其真值为假，在其余2n-1种指派情况下，其真值均为真。3）任意两个不同极大项的析取式是永真式。例如M0 M2(PQ) (PQ)1。4）全体极大项的合取式必为永假式。 定义定义1.7.8 由若干个不同的极大项组成的合取式称为主合取范式(The Principal Conjunctive Normal For

46、m)。与公式等价的主合取范式称为的主合取范式。 定理定理1.7.9 任意含n个命题变元的非永真式命题公式都存在着与之等价的主合取范式，并且其主合取范式是唯一的。 第第 1 章章 命题逻辑命题逻辑1.7 对偶与范式对偶与范式 与主析取范式的求解方法相类似，主合取范式同样可通过真值表法或等值演算法求得。 （1）真值表法 定理定理1.7.10 在真值表中，命题公式A的真值为假的赋值所对应的极大项的合取即为命题公式A的主合取范式。 证明方法与定理1.7.8的证明相类似。 利用真值表法求主合取范式的基本步骤为：（1）列出公式的真值表。（2）将真值表中的最后一列中的0的赋值所对应的极大项写出。（3）将这些

47、极大项进行合取。第第 1 章章 命题逻辑命题逻辑1.7 对偶与范式对偶与范式 （2）等值演算法 具体的求解步骤如下：（1）利用蕴含等值式和等价等值式消去公式中的联结词“”和“”；（2）利用德摩根律和双重否定律将联结词“”向内深入，使之只作用于命题变元；（3）利用分配律将公式化为合取范式；（4）利用同一律消去矛盾的简单析取式； （5）利用等幂律消去相同的简单析取式以及简单析取式中相同的析取项；（6）利用同一律、分配律将不包含某一命题变元的简单析取式置换为包含这一命题变元的简单析取式，直到每一简单析取式成为极大项为止。例如P QPQ (RR) ( PQR) ( PQR)。将极大项按顺序排列。 第第

48、 1 章章 命题逻辑命题逻辑1.7 对偶与范式对偶与范式 3主析取范式和主合取范式关系主析取范式和主合取范式关系设Z为命题公式A的主析取范式中所有极小项的足标集合，R为命题公式A的主合取范式中所有极大项的足标集合，则有 R0,1,2, ,2n-1Z或 Z0,1,2, ,2n-1R。故已知命题公式A的主析取范式，可求得其主合取范式；反之亦然。事实上，注意到极小项mi与极大项Mi满足mi Mi ， mi Mi。（例：m5：PQR，M5：PQR）。 如例1.7.14 中的主合取范式为M0M2M4M5已求出，则主析取范式为m1m3m6m7，然后写出相应的极小项即可。 第第 1 章章 命题逻辑命题逻辑1

49、.7 对偶与范式对偶与范式 4主范式的应用主范式的应用 （1）命题公式等价性的判定）命题公式等价性的判定 由于每个命题公式都存在着与之等价的唯一的主析取范式和主合取范式，因此，如果两个命题公式等价，则相应的主范式也对应相同。 ( 2) 命题公式类型的判定命题公式类型的判定 定理定理1.7.11 设A是含n个命题变元的命题公式，则1）A为永真式当且仅当A的主析取范式中含有全部2n个极小项。2）A为矛盾式当且仅当A的主合取范式中含有全部2n个极大项。3）若A的主析取范式中至少含有一个极小项，则A是可满足式。第第 1 章章 命题逻辑命题逻辑1.7 对偶与范式对偶与范式 （3） 解决实际问题解决实际问

50、题 例例1.7.18某科研所要从名科研骨干A,B,C中挑选12名出国进修。由于工作原因，选派时要满足以下条件：（）若A去，则C同去。（）若B去，则C不能去。（）若C不去，则A或B可以去。问应如何选派他们去？第第 1 章章 命题逻辑命题逻辑1.8 命题逻辑的推理理论命题逻辑的推理理论 数理逻辑的主要任务是用数学的方法来研究数学中的推理。推理就是由已知的命题得到新命题的思维过程。任何一个推理都是由前提和结论两部分组成。前提就是推理所根据的已知命题，结论则是从前提出发应用推理规则推出的新命题。 定义定义1.8.1设H1，H2，Hn，C都是命题公式。若(H1H2Hn)C是重言式，则称由前提H1，H2，