《精品课程《离散数学(全)》PPT课件.ppt》由会员分享，可在线阅读，更多相关《精品课程《离散数学(全)》PPT课件.ppt（213页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学计 算 机 科 学 系授课教师：王静1引 言 1为什么学习离散数学？离散数学是现代数学的一个重要分支，是计算机科学与技术的理论基础，所以又称为计算机数学，是计算机科学与技术专业的核心、骨干课程。离散数学是什么课？它以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。离散数学的主要内容是什么？内容包含：数理逻辑、集合论、代数结构与布尔代数、图论等。离散数学是随着计算机科学的发展而逐步建立的，它形成于七十年代初期，是一门新兴的工具性学科。2引 言 2 学习该课程的目的：一方面，它给后继课，如数据结构、编译系统、操作系统、数
2、据库原理、软件工程与方法学、计算机网络和人工智能等，提供必要的数学基础；另一方面，通过学习离散数学，可以培养和提高自己的抽象思维和逻辑推理能力，为以后的软、硬件学习和研究开发工作，打下坚实的数学基础。3引 言 3教学要求：通过该课程的学习，学生应当了解并掌握计算机科学中普遍采用的离散数学中的一些基本概念、基本思想、基本方法。自学要求：通过反复看书及做课后习题，来加深对该课程中的一些基本概念的理解，逐步提高自己的抽象思维和逻辑推理能力。4第一章 命题逻辑v数理逻辑是研究推理（即研究人类思维的形式结构和规律）的科学，起源于17世纪，它采用数学符号化的方法，因此也称为符号逻辑。v从广义上讲，数理逻辑
3、包括四论、两演算 即集合论、模型论、递归论、证明论和命题演算、谓词演算，但现在提到数理逻辑，一般是指命题演算和谓词演算。本书也只研究这两个演算。5v数理逻辑的创始人是Leibniz，为了实现把推理变为演算的想法，他把数学引入了形式逻辑。其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。v上个世纪30年代以后，数理逻辑进入一个崭新的发展阶段，逻辑学不仅与数学结合，还与计算机科学等密切关联。v1931年Godel不完全性定理的提出，以及递归函数可计算性的引入，促使了1936年tUring机的产生，十年后，第一台电子计算机问世。第一章 命题逻辑6v数理逻辑与计算机学、控制论、人工智能的相互渗透
4、推动了其自身的发展，模糊逻辑、概率逻辑、归纳逻辑、时态逻辑等都是目前比较热门的研究领域。v本篇我们只从语义出发，对数理逻辑中的命题演算与谓词演算等作一简单的、直接的、非形式化的介绍，将不涉及任何公理系统。第一章 命题逻辑71.1 命题符号化及联结词基本概念 命题：能够判断真假的陈述句。命题的真值：命题的判断结果。真值只取 两个值：真、假。真命题：真值为真的命题。假命题：真值为假的命题。判断命题的两个步骤：1、是否为陈述句；2、是否有确定的、唯一的真值。8例1：判断下列句子是否为命题。1、雪是白色的。2、2是偶数且3也是偶数。3、陈胜吴广起义那天杭州下雨。4、大于2的偶数均可分解为两个质数的和（
5、哥德巴赫猜想）。5、真舒服啊！6、别的星球上有生物存在。7、您去学校吗？8、x+y09、我正在说谎。10、1+101=1101.1 命题符号化及联结词91.1 命题符号化及联结词命题符号化及联结词区别区别 命题都是陈述句，但陈述句不都是命题都是陈述句，但陈述句不都是命题。只有陈述句所表达的判断结果命题。只有陈述句所表达的判断结果是唯一确定的（正确的或错误的），是唯一确定的（正确的或错误的），它才是命题。它才是命题。10命题及其真值的抽象化 在本书中，用小写英文字母p,q,r,p1,p2,p3等表示命题，用“1”、“0”分别表示真值的真、假。如：p：罗纳尔多是球星。q：5是负数。p3：明天天气晴
6、。皆为符号化的命题，其真值依次为1、0、1或0。1.1 命题符号化及联结词11命题的分类简单/原子命题：由不能再分解为更简单的陈述句的陈述句构成。如上例中的命题。复合命题：由简单命题通过联结词联结而成的陈述句。例2：1）3不是偶数。2）2是素数和偶数。3）林芳学过英语或日语。1.1 命题符号化及联结词121.1 命题符号化及联结词l命题常项或常元：真值是唯一确定的 即：0，1 l命题变项或变元：真值是不确定的 即：p，q，r区别区别命命题题与与命命题题变变项项含含义义是是不不同同的的，命命题题指指具具体体的的陈陈述述句句，是是有有确确定定的的真真值值，而而命命题题变变项项的的真真值值不不定定，
7、只只当当将将某某个个具具体体命命题题代代入入命命题题变变项项时时，命命题题变变项项化为命题，方可确定其真值。化为命题，方可确定其真值。131.1 命题符号化及联结词命题与命题变项象程序语言中常量与变量的关系一样。命题与命题变项象程序语言中常量与变量的关系一样。例：例：5是一个常量，是一个确定的数字，而是一个常量，是一个确定的数字，而x是一个变量，是一个变量，赋给它一个什么值它就代表什么值，即赋给它一个什么值它就代表什么值，即x的值是不定的。的值是不定的。例例3 3：判断下列句子是否为命题？：判断下列句子是否为命题？1 1张校长的头发有一万根。张校长的头发有一万根。2 2我所说的是假的。我所说的
8、是假的。（是）（否）14常用联结词1.否定词 设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作 p，符号称为否定联结词。运算规则：p p10011.1 命题符号化及联结词152.合取词 设p,q为二命题，复合命题“p并且q”（或“p与q”）称为p与q的合取式，记作p q，符号称为合取联结词。运算规则：pqp q0000101001111.1 命题符号化及联结词16合取运算特点：只有参与运算的二命题全为真时，运算结果才为真，否则为假。自然语言中的表示“并且”意思的联结词，如“既又”、“不但而且”、“虽然但是”、“一面一面”等都可以符号化为。注意：不要见到“与”或“和”就使用联结
9、词！1.1 命题符号化及联结词171.1 命题符号化及联结词例4：将下列命题符号化。(1)2既是偶数又是素数。(2)6不仅能被2整除，而且能被3整除。(3)8能被2整除，但不能被6整除。(4)5是奇数，6是偶数。(5)2与3的最小公倍数是6。(6)王丽和王娟是亲姐妹。181.1 命题符号化及联结词解：(1)(2)(3)(4)都是合取式命题，(5)(6)是简单命题。(1)p q，令p：2是偶数，q：2是素数。(2)p q，令p：2|6，q：3|6。(3)p q，令p：2|8，q：6|8。(4)p q，令p：5是奇数，q：6是偶数。(5)p:2与3的最小公倍数是6。(6)p:王丽和王娟是亲姐妹。1
10、93.析取词 设p,q为二命题，复合命题“p或q”称为p与q的析取式，记作p q，符号称为析取联结词。运算规则：pqp q0000111011111.1 命题符号化及联结词20析取运算特点：只有参与运算的二命题全为假时，运算结果才 为假，否则为真。相容或：相容或：二者至少有一个发生，也可二者都发生二者至少有一个发生，也可二者都发生排斥或：排斥或：二者只有一个发生，即非此即彼二者只有一个发生，即非此即彼例如：（1）小王爱打球或爱跑步。设p：小王爱打球。q：小王爱跑步。则上述命题可符号化为：p q（2）张晓静是江西人或湖南人。设p：江西人。q：湖南人。则上述命题就不可简单符号化为：p q 而应描述
11、为(p q)(pq)(也可用异或联接词)1.1 命题符号化及联结词214.蕴涵词 设p,q为二命题，复合命题“如果p，则q”称为p与q的蕴涵式，记作p q，并称p为蕴涵式的前件，q为蕴涵式的后件，符号称为蕴涵联结词。运算规则：pqp q0010111001111.1 命题符号化及联结词22l例：一位父亲对儿子说：“如果星期天天气好，就一定带你去动物园。”问：在什么情况下父亲食言？解：有以下四种可能情况：（1）星期天天气好，带儿子去了动物园；（2）星期天天气好，却没带儿子去动物园；（3）星期天天气不好，却带儿子去了动物园；（4）星期天天气不好，没带儿子去动物园。23蕴涵运算p q表示的逻辑关系是
12、：p是q的充分条件或者q是p的必要条件。自然语言中可用p q蕴涵式表述命题格式有：“只要p，就q”“因为p，所以q”、“p仅当q”、“只有q才p”、“除非q才p”、“除非q，否则非p”等。与自然语言的不同：前件与后件可以没有任何内在联系！1.1 命题符号化及联结词241.1 命题符号化及联结词例5：将下列命题符号化，并指出各复合命题的真值。(1)如果3+36，则雪是白色的。(2)如果3+36，则雪是白色的。解：令p：3+36，q：雪是白色的。(1)符号化为 p q (2)符号化为 p q真值为1真值为1251.1 命题符号化及联结词以下命题中出现的a是给定的一个正整数：(3)只有 a能被2整除
13、，a才能被4整除。(4)只有 a能被4整除，a才能被2整除。解：令r：a能被4整除，s：a能被2整除。(3)符号化为 s r (4)符号化为 r s真值不确定真值为1265.等价词 设p,q为二命题，复合命题“p当且仅当q”称为p与q的等价式，记作p q，符号称为等价联结词。运算规则：pqp q0010101001111.1 命题符号化及联结词27等价运算p q表示的逻辑关系是：p与q互为充分必要条件。相当于(p q)(q p)例6：将下列命题符号化，并讨论各命题的真值。(1)雪是白色的当且仅当法国的首都是里昂。(2)n是奇数的充分必要条件是n2是奇数。解:(1)令p：雪是白色的，q：法国的首
14、都是里昂；符号化为p q，因为p为真，q为假，所以真值为0。(2)令p：n是奇数，q：n2是奇数；符号化为p q，因为p和q同真或同假，所以真值为1。1.1 命题符号化及联结词281.2 命题公式及其分类1.命题公式合式公式/命题公式：将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串。当使用联结词集，时，合式公式（well formed formula）定义如下：（1）单个命题变项是合式公式，并称为原子命题公式。）单个命题变项是合式公式，并称为原子命题公式。（2）若若A是是合合式式公公式式，则则(A)，(AB),(AB)，(AB)，(AB)，(AB)也是合式公式。也是合式公式。（3）
15、只只有有有有限限次次地地应应用用(1)(2)形形成成的的符符号号串串才才是是合合式式公公式。式。合式公式也称合式公式也称为命命题公式或命公式或命题形式，并形式，并简称称为公式。公式。29例子：(1)(p q),(r t)e,p，(p)(p q),(r t)e,p，(p)等均为合式公式。(2)pq t,(p w)q)pq t,(p w)q)等不是合式公式。1.2 命题公式及其分类30注意：为了方便，下面给出有关省略括号的一些约定。公式的最外层括号可以省略.并且，（A）的括号可省略，记为 A.规定联结词的优先级为按，的顺序递减，若省略括号后按此优先顺序得到的公式与原公式一致，则允许省略.相同的联接
16、词按从左到右的顺序计算时括号可以省略.1.2 命题公式及其分类312.公式层次（1）若公式A是单个的命题变项，则称A为0层合式公式。（2）称A是n+1(n0)层公式是指下列情况之一：(a)A=B,B是n层公式;(b)A=BC,其中B,C分别为i层和j层公式,且n=max(i,j)；(c)A=B C,其中B,C的层次及n同(b);(d)A=B C,其中B,C的层次及n同(b);(e)A=B C,其中B,C的层次及n同(b);(f)A=B C,其中B,C的层次及n同(b);（3）若公式A的层次为k，则称A是k层公式。1.2 命题公式及其分类32例:公式p pq(p q)r(pq)(q p)的层次分
17、别为 0、1、3、41.2 命题公式及其分类331.公式赋值设p1，p2，pn是出现在公式A中的全部的命题变项，给p1，p2，pn各指定一个真值，称为对A的一个赋值或解释。比如：对公式(p q)r一组赋值为011(意即令p=0,q=1,r=1)可得真值为1，另一组赋值为010可得真值为0；还有000，001，111考虑：含有n个命题变项的公式共有多少个不同的赋值？1.2 命题公式及其分类34若指定的一组值使A的真值为1，则称这组值为A的成真赋值。如对公式(p q)r赋值011，还有?若指定的一组值使A的真值为0，则称这组值为A的成假赋值。如对公式(p q)r赋值010，还有?1.2 命题公式及
18、其分类35公式的又一种分类方式设A为任一命题公式，（1）若A在其各种赋值下的取值均为真，则称A是重言式或永真式。（2）若A在其各种赋值下的取值均为假，则称A是矛盾式或永假式。（3）若A不是矛盾式，则称A为可满足式。1.2 命题公式及其分类361.2 命题公式及其分类l用命题形式q1，q2，qn 分别替换命题形式A中的命题变项p1，p2，pn所得到的命题形式，称为A的一个替换实例（substitution instance）。l注意：一个替换应该是处处替换，而不是部分替换。l定理1.1 设A命题形式，则（1）设A是重言式，则A的任何替换实例都是重言式;（2）设A是矛盾式，则A的任何替换实例都是矛
19、盾式。见例1.11371 真值表将命题公式A在所有赋值下取值情况列成表，称做A的真值表。对公式A构造真值表的具体步骤为：（1）找出公式中所有的全体命题变项p1，p2，pn，列出2n个赋值。（2）按从低到高的顺序写出公式的各个层次。（3）对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。1.3 真值表和真值函数38例：构造公式(p q)r 真值表。pqrpq(p q)r00010001110101001111100001010011010111111.3 真值表和真值函数39练习1：构造公式(pq)(q p)真值表。p q p qpq q p(pq)(q p)0 0111110 1101
20、111 0010011 1001111.3 真值表和真值函数40练习2：构造公式 (p q)q 真值表。pq(p q)(p q)(p q)q001000110010010111001.3 真值表和真值函数41真值表的作用：（1）表示出公式的成真或成假赋值。（2）判断公式类型：(a)若真值表最后一列全为1，则为重言式；(b)若真值表最后一列全为0，则为矛盾式；(c)若真值表最后一列至少有一个1，则为可满足式；1.3 真值表和真值函数42考虑：含有n个命题变项的公式的真值表有?种不同的情况？因此，必有很多公式具有相同的真值表。如：pqp q p q00110111100011111.3 真值表和真
21、值函数431.3 真值表和真值函数2 真值函数 定义 以真,假为定义域和值域的函数为真值函数。如由五个逻辑联接词产生的所有wff都是真值函数，因此有无穷多个真值函数，显然最基本而重要的还是六个联接词。当真值函数的变元为n个时，共有2n个指派，通过列出真值表也可以定义真值函数。441.3 真值表和真值函数例 确定下列真值表对应的真值函数。PQRf1(P,Q,R)f2(P,Q,R)1111111000101101001001100010000011000001注意：由真值表确定的真值函数不一定是最简单的wff，且不一定只有一个表达式。451.3 真值表和真值函数例如 列出下列公式的真值表(P R)
22、(P Q)(Q R)由此可见，这个公式的真值表与f1(P,Q,R)的相比较，可以看出这两个公式代表同一个真值函数。461.4 等值式与等值演算 等值式设A,B是两个命题公式，若A，B构成的等价式A B为重言式，则称A与B是等值的，记作A B。即A B的充要条件是A B为重言式。判断两个公式等值的方法1：真值表法。47例：判断公式 p(qr)、(p q)r是否等价。pqrp qqrp(qr)(p q)r00001110010111010001101101111000111101011111010001111111由真值表可知，两个公式为等值式。由真值表可知，两个公式为等值式。1.4 等值式与等值
23、演算48需要记忆的16组重要的等值式 参见课本p13。等等值值演演算算：由由已已知知的的等等值值式式推推演演出出另另外外一一些些等等值值式的过程。式的过程。等值演算中使用的一条重要规则：等值演算中使用的一条重要规则：置换规则置换规则设设(A)是是含含公公式式A的的命命题题公公式式，(B)是是用用公公式式B置置换换了了(A)中中所所有有的的A后后得得到到的的命命题题公公式式(不不一一定定是是每每一一处处)，若若BA，则则(A)(B)。1.4 等值式与等值演算49等值演算的用途一：证明等值式。例：验证p(qr)(p q)r 右 (p q)r (蕴涵等值式、置换规则)p q r (德摩根律、置换规则
24、)p (q r)(结合律、置换规则)p (q r)(蕴涵等值式、置换规则)p (q r)(蕴涵等值式、置换规则)练：1.(pq)(pr)p(q r)2.(p q)(p q)(p q)(p q)1.4 等值式与等值演算50等值演算的用途二：判断公式类型。例：判断公式(pq)p q的类型 原式 (pq)p)q (p q)p)q (p q)p q (p q)p q (p p)(p q)q 1 (p q)q (p q)q p (q q)p 1 1 所以为永真式。1.4 等值式与等值演算51等值演算的用途二：判断公式类型。练：判断下列公式的类型。1、(p (pq)r 2、(p p)(q q)r）3、(p
25、 q)p1.4 等值式与等值演算521.4 等值式与等值演算香农（Shanon)定理 用命题形式A只含有命题变项p1,p2,pn，命题常项0，1和联结词、，若将A表示成A(p1,p2,pn,0,1,)，则A的非可以通过对其所有命题变项取非，并将其中的命题常量0，1互换，联结词、互换而得到，即 A(p1,p2,pn,0,1,)A(p1,p2,pn,1,0,)531.4 等值式与等值演算对偶式对偶式1定定义义:在在仅仅含含有有联联结结词词、的的公公式式A A中中，将将换换成成，换换成成，若若A A中中含含0 0或或1 1，就就将将0 0换换成成1 1，1 1换成换成0 0，所得到的公式称为，所得到
26、的公式称为A A的对偶式，记作的对偶式，记作A A*说明说明 AA是是A A*的对偶式，即对偶式是相互的，又（的对偶式，即对偶式是相互的，又（A A*）*=A=A 0 0与与1 1互为对偶式互为对偶式 例例1 1：写出下列公式的对偶式。：写出下列公式的对偶式。pp（qqr）（pqpq）00 解：解：pp（qqr）（pqpq）11 54对偶定理：对偶定理：设设A A和和A A*互互为为对对偶偶式式，p p1 1，p p2 2，p pn n是是出出现现在在A A和和A A*中中的的全全部的命题变项，则部的命题变项，则AA（p p1 1，p p2 2，p pn n）A A*（pp1 1，pp2 2，
27、ppn n）AA（pp1 1，pp2 2，ppn n）A A*（p p1 1，p p2 2，p pn n）说明说明 表明：公式表明：公式A A的否定等价于其命题变元否定的对偶式的否定等价于其命题变元否定的对偶式 表明：命题变元否定的公式等价于对偶式之否定表明：命题变元否定的公式等价于对偶式之否定 对偶原理：对偶原理：设设A，B为两命题公式，若为两命题公式，若ABB，则，则A*BB*。1.4 等值式与等值演算551.4 等值式与等值演算例 证明A BCA B C.例 化简语句：“情况并非如此：如果他不来，那么我也不去”。例 小李或小张是先进工作者；如果小李是先进工作者，你是会知道的；如果小张是先
28、进工作者，小赵也是；你不知道小李是先进工作者，问谁是先进工作者。561.5 联结词完备集联结词完备集一一.联结词的扩充联结词的扩充1.排斥或（异或）排斥或（异或）设设p、q为为命命题题，则则“p、q之之中中恰恰有有一一个个成成立立”称称为为p与与q的的排排斥斥或或，记记为为p q。p q为为真真当当且仅当且仅当p与与q有且只有一个为真。有且只有一个为真。pq（pq）（pq）性质：性质：pqqpp（qr）（pq）rp（qr）（pq）（pr）pp0 00 0pp 1p 1pp p 572与非词与非词设设p、q为为命命题题，则则“p与与q的的否否定定”称称为为p与与q的的与与非非式式，记为记为pq。
29、pq为真当且仅当为真当且仅当p与与q不时为真。不时为真。pq （pq）性质：性质：pqqppp p p p（pq）（pq）pq（pp）（qq）pq1.5 联结词完备集联结词完备集583或非词或非词设设p、q为为命命题题，则则“p或或q的的否否定定”称称为为p与与q的的或非式，记为或非式，记为pq。pq为真当且仅当为真当且仅当p与与q同时为假。同时为假。pq （pq）性质：性质：pqqppp p p p（pq）（pq）pqq（pp）（qq）pq 1.5 联结词完备集联结词完备集59二二.联结词的全功能集联结词的全功能集定义定义称称F：0，1n0，1为为n元真值函数。元真值函数。定定义义：设设s是
30、是一一个个联联结结词词集集合合，如如果果任任何何n元元真真值值函函数数都都可可以以由由仅仅含含s中中的的联联结结词词构构成成的的公公式式表表示示，则称则称s是联结词全功能集。是联结词全功能集。如如果果全全功功能能集集合合不不含含冗冗余余联联接接词词则则是是极极小小全全功功能能。定理定理s=,是联结词的全功能集。是联结词的全功能集。1.5 联结词完备集联结词完备集60析取范式与合取范式 含n个命题变项的公式两种规范表示方法定义文字（literal）:命题变元及它们的否定。简单析取式：仅由有限个文字构成的析取式。如：p ,q,p q,p q r简单合取式：仅由有限个文字定构成的合取式。如：p ,q
31、,p q,p q r1.6 范式61为方便起见，有时用Ai表示一个简单析取/合取式。设Ai为：p q r s t p或设Ai为：p q r s t p结论：（1）一个简单析取式是重言式它同时含有某个命题变项及其否定式。（2）一个简单合取式是矛盾式它同时含有某个命题变项及其否定式。1.6 范式62定义析取范式：由有限个简单合取式构成的析取式。如：p q ，(p q)(p q r)合取范式：由有限个简单析取式构成的合取式。如：p q,（p q）（p q r）范式：析取范式与合取范式统称为范式。1.6 范式63设Ai(i=1,2,3,n)为简单合取式，则A=A1 A2 An就是析取范式，而B=A1
32、A2 An就是合取范式。结论：（1）一个析取范式是矛盾式它的每个简单合取式都是矛盾式。（2）一个合取范式是重言式它的每个简单析取式都是重言式。1.6 范式64定理 (范式存在定理)任一个命题公式都存在着与之等值的析取范式与合取范式。求取步骤：（1）消去对,来说冗余的联结词，即，。利用下列等值式：A B(A B)A B(A B)(A B)1.6 范式65（2）否定词的消去或内移。利用下列等值式：A B(A B)(A B)A B (A B)A B（3）利用分配律：C(A B)（C A）（C B）C(A B)（C A）（C B）1.6 范式66例：求(p q)r的析取/合取范式。原式(p q)r)(
33、r(p q)(p q)r)(r(p q)(p q)r)(r p q)(p q)r)(r p q)(pr)(qr)(rpq)(合取范式)(p q)(rp q)(r(rpq)(p q)(r p q)(r(rpq)(p q r)(r p)(r q)(析取范式)1.6 范式67练习：求析取/合取范式。1、(p q)(p r)2、(p q)(p r).1.6 范式68解：1、(p q)(p r)(p q)(p r)(合取范式)(p q)p)(p q)r)(p p)(q p)(p r)(q r)(q p)(p r)(q r)(析取范式)1.6 范式69解：2、(p q)(p r)(p q)(p r)p q
34、(p r)(析取范式)(p r)p)q (p p)(p r)q (p p q)(p r q)(合取范式)(1 q)(p r q)p r q1.6 范式70定义 在含有n个命题变项的简单合（析）取式中，若每个命题变项和它的否定不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第i位上（若命题变项无角标，就按字母顺序），称这样的简单合（析）取式为极小（大）项。考虑：n个命题变项可产生多少个极小（大）项？1.6 范式71可以观察到：每个极小项，如p1 p2 p3 pn,有且仅有一个成真赋值，若成真赋值所对应的二进制数转化为十进制数为i，就将所对应的极小项记作mi。
35、每个极大项，如p1 p2 p3 pn,有且仅有一个成假赋值，若成假赋值所对应的二进制数转化为十进制数为i，就将所对应的极大项记作Mi。1.6 范式721.6 范式例：例：p p、q q形成的所有极小项形成的所有极小项公式公式成真赋值成真赋值名称名称pq00m0pq01m1pq10m2 pq11m3例：例：p p、q q形成的所有极大项形成的所有极大项 公式公式 成假赋值成假赋值 名称名称 pq 0 0 M0 pq 0 0 M0 pq 0 1 M1 pq 0 1 M1 pq 1 0 M2 pq 1 0 M2 pq 1 1 M3 pq 1 1 M373定义 设由n个命题变项构成的析（合）取范式中所
36、有的简单合（析）取式都是极小（大）项，则称该析（合）取范式为主析（合）取范式。主析（合）取范式的性质见书P19 1.6 范式74定理 任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是唯一的。关键之处：Ai Ai 1 Ai(pj pj)(Ai pj)(Ai pj)Ai Ai 0 Ai(pj pj)(Ai pj)(Ai pj)1.6 范式751.6 范式主析取范式的求法主析取范式的求法主析取范式的求法有两种主析取范式的求法有两种:真值表法和等值演算法真值表法和等值演算法等值演算法的步骤如下等值演算法的步骤如下:求求A的析取范式的析取范式AA若若AA的的某某简简单单合合取取式式B B中中
37、含含命命题题变变项项p pi i或或其其否否定定,则将则将B B展成如下形式展成如下形式:BB1 B(p BB1 B(pi ippi i)(Bp)(Bpi i)(Bp)(Bpi i)将将重重复复出出现现的的命命题题变变元元、极极小小项项和和矛矛盾盾式式都都消消去。去。如：用如：用pppp用用p p代，代，pppp用用0 0代，代，m mi immi i用用m mi i代代将将极极小小项项按按由由小小到到大大的的顺顺序序排排列列，并并用用表表示示之。之。如：如：m1m2m5m1m2m5用用（1 1，2 2，5 5）表示）表示761.6 范式例题例题:求求(pq)q(pq)q的主析取范式的主析取范
38、式 解解:(1):(1)用真值表法求之用真值表法求之:p q (pq)(pq)qp q (pq)(pq)q 0 0 1 00 0 1 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1由真值表可求出由真值表可求出:(pq)qm1m3(1,3)(pq)qm1m3(1,3)771.6 范式(2)(2)用等值演算法求之用等值演算法求之 (pq)q(pq)q (pq)q(pq)q (pq)(qq)(pq)(qq)(pq)(q(pp)(pq)(q(pp)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)m1m3(1,3)m1m
39、3(1,3)78练习：求主析取/合取范式。1、(p q)(p r)2、(p q)(p r)1.6 范式79解：1、接上 (p q)(p r)(合取范式)(p q)(r r)(p r)(q q)(p q r)(p q r)(pq r)(pq r)(p q r)(p q r)(pq r)(pq r)(主合取范式)M0M1M4 M61.6 范式80解：1、接上 (q p)(p r)(q r)(析取范式)(p r)(q q)(pq)(r r)(qr)(p p)(p qr)(p q r)(pq r)(pq r)(主析取范式)m2 m3m5 m7 1.6 范式81解：2、接上 p q(p r)(析取范式)
40、(p(q q)(pp)q)(pr)(q q)(p qr)(p qr)(pq r)(pqr)(pqr)(p qr)(p qr)(主析取范式)m0 m1 m2 m3m5 m6 m71.6 范式82解：2、接上 (p p q)(p r q)(合取范式)(1 q)(p r q)p q r (主合取范式)M41.6 范式83主析取范式的用途（主合取范式类似讨论）：1、求公式的成真/成假赋值：若公式A中含有n个命题变项，且A的主析取范式含s 个极小项，则A有s个成真赋值，有2n-s个成假赋值。1.6 范式842、判断公式的类型：设公式A中含有n个命题变项，则：（1）A为重言式 A的主析取范式含全部2n个极
41、小项。（2）A为矛盾式 A的主析取范式不含任何极小项，记A的主析取范式为0。（3）A为可满足式 A的主析取范式至少含一个极小项。1.6 范式853、判断两个命题是否等值：设公式A、B中共含有n个命题变项，按n个命题变项求出A、B的主析取范式A、B。若A=B，则A B，否则A、B不等值。练习：1、(p q)(p r)与 p(q r)2、p(q r)与 p(q r)1.6 范式86解：1、(p q)(p r)(p q)(p r)p(q r)m0 m1 m2 m3m7 p(q r)p(q r)m0 m1 m2 m3m7所以(p q)(p r)p(q r)1.6 范式87解：2、p(q r)p(q r
42、)m0 m1 m2 m3m7 p(q r)p q r m0 m1 m3 m4 m5m6 m7所以(p q)(p r)与 p(q r)不等值。1.6 范式884、解决实际问题：练习：某勘探队有3名队员，有一天取得一块矿样，3人判断如下：甲说：这不是铁，也不是铜。乙说：这不是铁，是锡。丙说：这不是锡，是铁。经实验室鉴定发现，其中一人的两个判断全对，一人判对一半，另一人全错。试根据以上情况，判断矿样的种类。1.6 范式89解:设 p:矿样是铁。q:矿样是铜。r:矿样是锡。根据题设知有六种情况：甲正确，乙对一半，丙全错；甲正确，乙全错，丙对一半；甲对一半，乙正确，丙全错；甲对一半，乙全错，丙正确；甲全
43、错，乙正确，丙对一半；甲全错，乙对一半，丙正确。1.6 范式90以上六种情况对应公式分别为：(pq)(pr)(pr)(pr)0(pq)(pr)(pr)(p r)0(pq)(pq)(pr)(pr)pq r(pq)(pq)(pr)(p r)p q r(pq)(pr)(pr)(p r)0(pq)(pr)(pr)(p r)01.6 范式91解:设 判断经过为F，则：F (pq r)(p q r)但不能同时为铜又为锡，因而只能对应p q r，即不是铜，也不是锡，而是铁。1.6 范式92关于主合取范式1、由公式的主析取范式求主合取范式 设公式A中含有n个命题变项，且A的主析取范式含s 个极小项，即A mi
44、1 mi2 mis，0ij 2n-1,j=1,2,s.没出现的极小项为mj1,mj2 mjs,它们的脚标的二进制表示为A的成真赋值，因而A的主析取范式为A=mj1 mj2 mjs1.6 范式93由定理知 A A (mj1 mj2 mjs)mj1 mj2 mjs Mj1 Mj2 Mjs1.6 范式94例题例题:求求(pq)q(pq)q的主合取范式的主合取范式 解解:(1):(1)用真值表法求之用真值表法求之:p q (pq)(pq)qp q (pq)(pq)q 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1由真值表可
45、求出由真值表可求出:(pq)qM0M2(0,2)(pq)qM0M2(0,2)1.6 范式95(2)(2)用等值演算法求之用等值演算法求之 (pq)q(pq)q (pq)q(pq)q (pq)(q (pq)(q（pppp）)(pq)(qp)(pq)(qp)（qpqp）(pq)(pq)(pq)(pq)M0 M0 M2(0,2)M2(0,2)1.6 范式962、重言式与矛盾式的主合取范式设公式A中含有n个命题变项，则：（1）A为矛盾式 A的主合取范式含全部2n个极大项。（2）A为重言式 A的主合取范式不含任何极大项，记A的主合取范式为1。（3）A为可满足式 A的主合取范式中极大项的个数一定小于2n。
46、1.6 范式97定理 极小项与极大项关系 设mi和Mi是命题变项p1，p2，pn形成的极小项和极大项，则 mi Mi ，Mi mi1.6 范式981.7 命题逻辑的推理理论 推理的形式结构定义 推理的一般形式设A1，A2，Ak，B都是命题公式，若对于A1，A2，Ak，B 中出现的命题变项的任意一组赋值，或者A1，A2，Ak为假，或者当A1，A2，Ak为真时，B也为真，则称由前提A1，A2，Ak 推出B的推理是有效的或正确的，并称B是有效的结论。99说明：（1）由前提A1，A2，Ak推B的推理记作A1，A2，Ak|-B,这称为推理的形式结构。如果推理是正确的，记作A1，A2，Ak|=B，否则记作
47、A1，A2，Ak|B。（2）对于任一组赋值，前提和结论的取值有以下四种情况：A1，A2，Ak为0，B为0。A1，A2，Ak为0，B为1。A1，A2，Ak为1，B为0。A1，A2，Ak为1，B为1。1.7 命题逻辑的推理理论100推理的另一种形式：定理 命题公式A1，A2，Ak推B的推理正确当且仅当 (A1 A2 Ak)B为重言式。（证明参见课本）于是推理的一般形式可转化为：(A1 A2 Ak)B推理正确转化为：A1 A2 Ak=B1.7 命题逻辑的推理理论101于是，以后推理的形式就写作：前提：p,p q 结论：q推理的形式结构：(p(p q)q即只需证明蕴涵式(p(p q)q为重言式。三种方
48、法：1、真值表法；2、等值演算法；3、主析取范式法。1.7 命题逻辑的推理理论102例：判断下列推理是否正确。1、今天小李或去网吧或去教室。他没去教室，所以他去网吧了。设 p：小李去网吧。q：小李去教室。则，前提：p q,q 结论：p 推理的形式结构：(p q)q)p1.7 命题逻辑的推理理论103pqp qq(p q)q(p q)q)p000101011001101111111001真值表法真值表法1.7 命题逻辑的推理理论104等值演算法：(p q)q)p (p q)(q q)p (p q)p (p q)p p q p 1所以，推理正确，即（(p q)q)=p1.7 命题逻辑的推理理论10
49、5主析取范式法：(p q)q)p (p q)q)p (p q)q p (p q)q p(p q)q(p p)p(q q)(p q)(q p)(q p)(pq)(p q)m0 m1 m2 m3 所以，推理正确，即（(p q)q)=p1.7 命题逻辑的推理理论106例：判断下列推理是否正确。2、若a能被4整除，则天下雨。现天下雨。所以a能被4整除。设 p：a能被4整除。q：天下雨。则，前提：p q,q 结论：p 推理的形式结构：(p q)q)p 答案：此推理不正确。1.7 命题逻辑的推理理论107经过长期的研究推理，人们发现一些重要的重言蕴涵式，我们将这些重言蕴涵式称为推理定律。十条推理定律：1.
50、7 命题逻辑的推理理论1081 1）附加律）附加律 A=(AB)A=(AB)2 2）化简律）化简律 (AB)=A (AB)=A3 3）假言推理）假言推理 (AB)A=B (AB)A=B4 4）拒取式）拒取式 (AB)B=A (AB)B=A5 5）析取三段论）析取三段论 (AB)B=A (AB)B=A6 6）假言三段论）假言三段论 (AB)(BC)=(AC)(AB)(BC)=(AC)7 7）等价三段论）等价三段论 (A (AB)(BB)(BC)=(AC)=(AC)C)8 8）构造性二难）构造性二难 (AB)(CD)(AC)=(BD)(AB)(CD)(AC)=(BD)(特殊形式特殊形式)(AB)(