《离散数学》PPT课件（全

1、1,离散数学,计 算 机 科 学 系 授课教师：王静,2,引 言 1,为什么学习离散数学？ 离散数学是现代数学的一个重要分支，是计算机科学与技术的理论基础，所以又称为计算机数学，是计算机科学与技术专业的核心、骨干课程。 离散数学是什么课？ 它以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。 离散数学的主要内容是什么？ 内容包含：数理逻辑、集合论、代数结构与布尔代数、图论等。 离散数学是随着计算机科学的发展而逐步建立的，它形成于七十年代初期，是一门新兴的工具性学科,3,引 言 2,学习该课程的目的： 一方面，它给后继课，如数

2、据结构、编译系统、操作系统、数据库原理、软件工程与方法学、计算机网络和人工智能等，提供必要的数学基础； 另一方面，通过学习离散数学，可以培养和提高自己的抽象思维和逻辑推理能力，为以后的软、硬件学习和研究开发工作，打下坚实的数学基础,4,引 言 3,教学要求： 通过该课程的学习，学生应当了解并掌握计算机科学中普遍采用的离散数学中的一些基本概念、基本思想、基本方法。 自学要求： 通过反复看书及做课后习题，来加深对该课程中的一些基本概念的理解，逐步提高自己的抽象思维和逻辑推理能力,5,第一章 命题逻辑,数理逻辑是研究推理（即研究人类思维的形式结构和规律）的科学，起源于17世纪，它采用数学符号化的方法

3、，因此也称为符号逻辑。 从广义上讲，数理逻辑包括四论、两演算 即集合论、模型论、递归论、证明论和命题演算、谓词演算，但现在提到数理逻辑，一般是指命题演算和谓词演算。本书也只研究这两个演算,6,数理逻辑的创始人是Leibniz，为了实现把推理变为演算的想法，他把数学引入了形式逻辑。其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。 上个世纪30年代以后，数理逻辑进入一个崭新的发展阶段，逻辑学不仅与数学结合，还与计算机科学等密切关联。 1931年Godel不完全性定理的提出，以及递归函数可计算性的引入，促使了1936年tUring机的产生，十年后，第一台电子计算机问世,第一章 命题逻辑,7,

4、数理逻辑与计算机学、控制论、人工智能的相互渗透推动了其自身的发展，模糊逻辑、概率逻辑、归纳逻辑、时态逻辑等都是目前比较热门的研究领域。 本篇我们只从语义出发，对数理逻辑中的命题演算与谓词演算等作一简单的、直接的、非形式化的介绍，将不涉及任何公理系统,第一章 命题逻辑,8,1.1 命题符号化及联结词,基本概念 命题：能够判断真假的陈述句。 命题的真值：命题的判断结果。真值只取 两个值： 真、假。 真命题：真值为真的命题。 假命题：真值为假的命题。 判断命题的两个步骤： 1、是否为陈述句； 2、是否有确定的、唯一的真值,9,例1：判断下列句子是否为命题。 1、雪是白色的。 2、2是偶数且3也是偶数

5、。 3、陈胜吴广起义那天杭州下雨。 4、大于2的偶数均可分解为两个质数的和（哥德巴赫猜想）。 5、真舒服啊！ 6、别的星球上有生物存在。 7、您去学校吗？ 8、x+y0 9、我正在说谎。 10、1+101=110,1.1 命题符号化及联结词,10,1.1 命题符号化及联结词,区别 命题都是陈述句，但陈述句不都是命题。只有陈述句所表达的判断结果是唯一确定的（正确的或错误的），它才是命题,11,命题及其真值的抽象化 在本书中，用小写英文字母p,q,r,p1,p2,p3等表示命题，用“1”、“0”分别表示真值的真、假。 如： p：罗纳尔多是球星。 q：5是负数。 p3：明天天气晴。 皆为符号化的命题

6、，其真值依次为1、0、1或0,1.1 命题符号化及联结词,12,命题的分类 简单/原子命题：由不能再分解为更简单的陈述句的陈述句构成。 如上例中的命题。 复合命题：由简单命题通过联结词联结而成的陈述句。 例2： 1）3不是偶数。 2）2是素数和偶数。 3）林芳学过英语或日语,1.1 命题符号化及联结词,13,1.1 命题符号化及联结词,命题常项或常元：真值是唯一确定的 即：0，1 命题变项或变元：真值是不确定的 即：p，q，r,区别 命题与命题变项含义是不同的，命题指具体的陈述句，是有确定的真值，而命题变项的真值不定，只当将某个具体命题代入命题变项时，命题变项化为命题，方可确定其真值,14,1

7、.1 命题符号化及联结词,命题与命题变项象程序语言中常量与变量的关系一样。 例：5是一个常量，是一个确定的数字，而x是一个变量，赋给它一个什么值它就代表什么值，即x的值是不定的,例3：判断下列句子是否为命题？ 1张校长的头发有一万根。 2我所说的是假的,是） （否,15,常用联结词 1.否定词 设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作 p，符号称为否定联结词。 运算规则,1.1 命题符号化及联结词,16,2.合取词 设p,q为二命题，复合命题“p并且q”（或“p与q”）称为p与q的合取式，记作p q，符号称为合取联结词。 运算规则,1.1 命题符号化及联结词,17,合

8、取运算特点：只有参与运算的二命题全为真时，运算结果才为真，否则为假。 自然语言中的表示“并且”意思的联结词，如“既又”、“不但而且”、“虽然但是”、“一面一面”等都可以符号化为 。 注意：不要见到“与”或“和”就使用联结词,1.1 命题符号化及联结词,18,1.1 命题符号化及联结词,例4： 将下列命题符号化。 (1) 2既是偶数又是素数。 (2) 6不仅能被2整除，而且能被3整除。 (3) 8能被2整除，但不能被6整除。 (4) 5是奇数，6是偶数。 (5) 2与3的最小公倍数是6。 (6) 王丽和王娟是亲姐妹,19,1.1 命题符号化及联结词,解： (1)(2)(3)(4)都是合取式命题，

9、(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:王丽和王娟是亲姐妹,20,3.析取词 设p,q为二命题，复合命题“p或q” 称为p与q的析取式，记作p q，符号称为析取联结词。 运算规则,1.1 命题符号化及联结词,21,析取运算特点：只有参与运算的二命题全为假时，运算结果才 为假，否则为真。 相容或：二者至少有一个发生，也可二者都发生 排斥或：二者只有一个发生，即

10、非此即彼 例如： （1）小王爱打球或爱跑步。 设p：小王爱打球。 q：小王爱跑步。 则上述命题可符号化为：p q （2）张晓静是江西人或湖南人。 设p：江西人。 q：湖南人。 则上述命题就不可简单符号化为：p q 而应描述为(p q) ( pq)(也可用异或联接词,1.1 命题符号化及联结词,22,4.蕴涵词 设p,q为二命题，复合命题“如果p，则q” 称为p与q的蕴涵式，记作p q，并称p为蕴涵式的前件，q为蕴涵式的后件，符号称为蕴涵联结词。 运算规则,1.1 命题符号化及联结词,23,例：一位父亲对儿子说：“如果星期天天气好，就一定带你去动物园。”问：在什么情况下父亲食言？ 解：有以下四种

11、可能情况： （1）星期天天气好，带儿子去了动物园； （2）星期天天气好，却没带儿子去动物园； （3）星期天天气不好，却带儿子去了动物园； （4）星期天天气不好，没带儿子去动物园,24,蕴涵运算p q表示的逻辑关系是：p是q的充分条件或者q是p的必要条件。 自然语言中可用p q蕴涵式表述命题格式有：“只要p，就q”“因为p，所以q”、“p仅当q”、“只有q才p”、“除非q才p”、“除非q，否则非p”等。 与自然语言的不同：前件与后件可以没有任何内在联系,1.1 命题符号化及联结词,25,1.1 命题符号化及联结词,例5： 将下列命题符号化，并指出各复合命题的真值。 (1) 如果3+36，则雪是白

12、色的。 (2) 如果3+36，则雪是白色的。 解： 令p： 3+36， q：雪是白色的。 (1)符号化为 p q (2)符号化为 p q,真值为1 真值为1,26,1.1 命题符号化及联结词,以下命题中出现的a是给定的一个正整数： (3) 只有 a能被2整除， a才能被4整除。 (4) 只有 a能被4整除， a才能被2整除。 解： 令r： a能被4整除， s： a能被2整除。 (3)符号化为 s r (4)符号化为 r s,真值不确定 真值为1,27,5.等价词 设p,q为二命题，复合命题“p当且仅当q” 称为p与q的等价式，记作p q，符号称为等价联结词。 运算规则,1.1 命题符号化及联结

13、词,28,等价运算p q表示的逻辑关系是：p与q互为充分必要条件。相当于(p q) (q p) 例6： 将下列命题符号化，并讨论各命题的真值。 (1)雪是白色的当且仅当法国的首都是里昂。 (2)n是奇数的充分必要条件是n2是奇数。 解:(1)令p：雪是白色的，q：法国的首都是里昂； 符号化为p q，因为p为真，q为假，所以真值为0。 (2)令p： n是奇数， q： n2是奇数； 符号化为p q，因为p和q同真或同假，所以真值为1,1.1 命题符号化及联结词,29,1.2 命题公式及其分类,1.命题公式 合式公式/命题公式：将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串。 当使用联结

14、词集 ，时，合式公式（well formed formula）定义如下,1）单个命题变项是合式公式，并称为原子命题公式。 （2）若A是合式公式，则( A) ，(A B), (A B)， (A B)，(A B)，(A B)也是合式公式。 （3）只有有限次地应用(1)(2)形成的符号串才是合式公式。 合式公式也称为命题公式或命题形式，并简称为公式,30,例子： (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 命题公式及其分类,31,注意：

15、为了方便，下面给出有关省略括号的一些约定。 公式的最外层括号可以省略.并且，（ A）的括号可省略，记为 A. 规定联结词的优先级为按， ， ， ，的顺序递减，若省略括号后按此优先顺序得到的公式与原公式一致，则允许省略. 相同的联接词按从左到右的顺序计算时括号可以省略,1.2 命题公式及其分类,32,2.公式层次 （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

16、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 命题公式及其分类,33,例:公式 p pq (p q) r (pq)( q p) 的层次分别为 0、1、3、4,1.2 命题公式及其分类,34,1.公式赋值 设p1 ， p2 ， ， pn是出现在公式A中的全部的命题变项，给p1 ， p2 ， ， pn各指定一个真值，称为对A的一个赋值或解释。 比如： 对公式(p q) r一组赋值为011(意即令p=0,q=1,r=1)可得真值为1，另一组赋值为010可得

17、真值为0；还有000，001，111 考虑：含有n个命题变项的公式共有多少个不同的赋值,1.2 命题公式及其分类,35,若指定的一组值使A的真值为1，则称这组值为A的成真赋值。 如对公式(p q) r赋值011，还有? 若指定的一组值使A的真值为0，则称这组值为A的成假赋值。 如对公式(p q) r赋值010，还有,1.2 命题公式及其分类,36,公式的又一种分类方式 设A为任一命题公式， （1）若A在其各种赋值下的取值均为真，则称A是重言式或永真式。 （2）若A在其各种赋值下的取值均为假，则称A是矛盾式或永假式。 （3）若A不是矛盾式，则称A为可满足式,1.2 命题公式及其分类,37,1.2

18、 命题公式及其分类,用命题形式q1 ，q2，qn 分别替换命题形式A中的命题变项p1 ，p2，pn所得到的命题形式，称为A的一个替换实例（substitution instance）。 注意：一个替换应该是处处替换，而不是部分替换 。 定理1.1 设A命题形式，则 （1）设A是重言式，则A的任何替换实例都是重言式; （2）设A是矛盾式，则A的任何替换实例都是矛盾式。见例1.11,38,1 真值表 将命题公式A在所有赋值下取值情况列成表，称做A的真值表。 对公式A构造真值表的具体步骤为： （1）找出公式中所有的全体命题变项p1 ， p2 ， ， pn，列出2n个赋值。 （2）按从低到高的顺序写出

19、公式的各个层次。 （3）对应各个赋值计算出各层次的真值，直到最后计算出公式的真值,1.3 真值表和真值函数,39,例：构造公式 (p q) r 真值表,1.3 真值表和真值函数,40,练习1：构造公式 (pq)( q p)真值表,1.3 真值表和真值函数,41,练习2：构造公式 (p q) q 真值表,1.3 真值表和真值函数,42,真值表的作用： （1）表示出公式的成真或成假赋值。 （2）判断公式类型： (a)若真值表最后一列全为1，则为重言式； (b)若真值表最后一列全为0，则为矛盾式； (c)若真值表最后一列至少有一个1，则为可满足式,1.3 真值表和真值函数,43,考虑：含有n个命题变

20、项的公式的真值表有 ? 种不同的情况？ 因此，必有很多公式具有相同的真值表。 如,1.3 真值表和真值函数,44,1.3 真值表和真值函数,2 真值函数 定义 以真,假为定义域和值域的函数为真值函数。 如由五个逻辑联接词产生的所有wff都是真值函数，因此有无穷多个真值函数，显然最基本而重要的还是六个联接词。 当真值函数的变元为n个时，共有2n个指派，通过列出真值表也可以定义真值函数,45,1.3 真值表和真值函数,例 确定下列真值表对应的真值函数,注意：由真值表确定的真值函数不一定是最简单的wff，且不一定只有一个表达式,46,1.3 真值表和真值函数,例如 列出下列公式的真值表 (P R)

21、( P Q) ( Q R) 由此可见，这个公式的真值表与f1(P,Q,R)的相比较，可以看出这两个公式代表同一个真值函数,47,1.4 等值式与等值演算,等值式 设A,B是两个命题公式，若A，B构成的等价式A B为重言式，则称A与B是等值的，记作A B。 即A B的充要条件是A B为重言式。 判断两个公式等值的方法1：真值表法,48,例：判断公式 p(qr)、(p q) r是否等价,由真值表可知，两个公式为等值式,1.4 等值式与等值演算,49,需要记忆的16组重要的等值式 参见课本p13,等值演算：由已知的等值式推演出另外一些等值式的过程。 等值演算中使用的一条重要规则：置换规则 设(A)是

22、含公式A的命题公式， (B)是用公式B置换了(A)中所有的A后得到的命题公式(不一定是每一处)，若B A，则(A) (B,1.4 等值式与等值演算,50,等值演算的用途一：证明等值式。 例：验证p(qr) (p q) r 右 (p q) r (蕴涵等值式、置换规则) p q r (德摩根律、置换规则) 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 等值式与等值演算,51,等值演算的用途二：判断公式类型。 例：

23、判断公式(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 等值式与等值演算,52,等值演算的用途二：判断公式类型。 练：判断下列公式的类型。 1、 (p (pq ) r 2、 (p p) (q q) r） 3、 (p q ) p,1.4 等值式与等值演算,53,1.4 等值式与等值演算,香农（Shanon)定理 用命题形式A只含有命题变项p1,p2,pn，命题常项0，1和联结词 、，若将A表示成A(p1,p2,p

24、n ,0,1, ,)，则A的非可以通过对其所有命题变项取非，并将其中的命题常量0，1互换，联结词、互换而得到，即,A(p1,p2,pn ,0,1, ,) A( p1, p2, pn,1,0 ,54,1.4 等值式与等值演算,对偶式 1定义:在仅含有联结词、的公式A中，将换成，换成，若A中含0或1，就将0换成1，1换成0，所得到的公式称为A的对偶式，记作A* 说明 A是A*的对偶式，即对偶式是相互的，又（A*）*=A 0与1互为对偶式,例1：写出下列公式的对偶式。 p（qr） （pq）0,解：p（qr） （pq）1,55,对偶定理： 设A和A*互为对偶式，p1，p2，pn是出现在A和A*中的全部

25、的命题变项，则 A（p1，p2，pn） A*（p1，p2，pn）A（p1，p2，pn） A*（p1，p2，pn,说明 表明：公式A的否定等价于其命题变元否定的对偶式 表明：命题变元否定的公式等价于对偶式之否定,对偶原理： 设A，B为两命题公式，若AB，则A*B,1.4 等值式与等值演算,56,1.4 等值式与等值演算,例 证明A BCA B C. 例 化简语句：“情况并非如此：如果他不来，那么我也不去”。 例 小李或小张是先进工作者；如果小李是先进工作者，你是会知道的；如果小张是先进工作者，小赵也是；你不知道小李是先进工作者，问谁是先进工作者,57,1.5 联结词完备集,一.联结词的扩充 1.

26、 排斥或（异或） 设p、q为命题，则“p、q之中恰有一个成立”称为p与q的排斥或，记为p q。p q为真当且仅当p与q有且只有一个为真。 pq （pq）（pq） 性质： pq qp p（qr）（pq）r p（qr）（pq）（pr） pp0 0pp 1pp,58,2与非词 设p、q为命题，则“p与q的否定”称为p与q的与非式，记为pq。 pq为真当且仅当p与q不时为真。 pq （pq） 性质： pq qp pp p （pq）（pq）pq （pp）（qq）pq,1.5 联结词完备集,59,3或非词 设p、q为命题，则“p或q的否定”称为p与q的或非式，记为pq。 pq为真当且仅当p与q同时为假。

27、pq （pq） 性质： pq qp pp p （pq）（pq）pq （pp）（qq）pq,1.5 联结词完备集,60,二.联结词的全功能集 定义称F：0，1n0，1为n元真值函数。 定义：设s是一个联结词集合，如果任何n元真值函数都可以由仅含s中的联结词构成的公式表示，则称s是联结词全功能集。 如果全功能集合不含冗余联接词则是极小全功能。 定理 s= , 是联结词的全功能集,1.5 联结词完备集,61,析取范式与合取范式 含n个命题变项的公式两种规范表示方法 定义 文字（literal）:命题变元及它们的否定。 简单析取式：仅由有限个文字构成的析取式。 如：p , q , p q , p q

28、r 简单合取式：仅由有限个文字定构成的合取式。 如：p , q , p q , p q r,1.6 范式,62,为方便起见，有时用Ai表示一个简单析取/合取式。 设Ai为： p q r s t p 或设Ai为： p q r s t p 结论： （1）一个简单析取式是重言式它同时含有某个命题变项及其否定式。 （2）一个简单合取式是矛盾式它同时含有某个命题变项及其否定式,1.6 范式,63,定义 析取范式：由有限个简单合取式构成的析取式。 如：p q ， (p q) (p q r) 合取范式：由有限个简单析取式构成的合取式。 如：p q , （p q）（ p q r） 范式：析取范式与合取范式统称

29、为范式,1.6 范式,64,设Ai(i=1,2,3,n)为简单合取式，则 A=A1 A2 An就是析取范式， 而 B=A1 A2 An就是合取范式。 结论： （1）一个析取范式是矛盾式它的每个简单合取式都是矛盾式。 （2）一个合取范式是重言式它的每个简单析取式都是重言式,1.6 范式,65,定理 (范式存在定理) 任一个命题公式都存在着与之等值的析取范式与合取范式。 求取步骤： （1）消去对 ,来说冗余的联结词，即， 。利用下列等值式： A B ( A B) A B ( A B) (A B,1.6 范式,66,2）否定词的消去或内移。 利用下列等值式： A B ( A B) ( A B) A

30、B ( A B) A B （3）利用分配律： C ( A B) （C A） （C B） C ( A B) （C A） （C B,1.6 范式,67,例：求(p q) r的析取/合取范式。 原式(p q) r) (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 范式,68,练

31、习：求析取/合取范式。 1、( p q) (p r) 2、(p q) (p r,1.6 范式,69,解： 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 范式,70,解： 2、(p q) (p r) ( p q) ( p r ) p q ( p r ) (析取范式) (p r) p) q (p p) ( p r) q (p p q ) ( p r q ) (合取范式) (1 q ) ( p r q ) p r q,1.6 范式,71

32、,定义 在含有n个命题变项的简单合（析）取式中，若每个命题变项和它的否定不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第i位上（若命题变项无角标，就按字母顺序），称这样的简单合（析）取式为极小（大）项。 考虑： n个命题变项可产生多少个极小（大）项,1.6 范式,72,可以观察到： 每个极小项，如p1 p2 p3 pn,有且仅有一个成真赋值，若成真赋值所对应的二进制数转化为十进制数为i，就将所对应的极小项记作mi。 每个极大项，如p1 p2 p3 pn,有且仅有一个成假赋值，若成假赋值所对应的二进制数转化为十进制数为i，就将所对应的极大项记作Mi,1.6

33、 范式,73,1.6 范式,例：p、q形成的所有极小项 公式 成真赋值 名称 pq 0 0 m0 pq 0 1 m1 pq 1 0 m2 pq 1 1 m3,例：p、q形成的所有极大项 公式 成假赋值 名称 pq 0 0 M0 pq 0 1 M1 pq 1 0 M2 pq 1 1 M3,74,定义 设由n个命题变项构成的析（合）取范式中所有的简单合（析）取式都是极小（大）项，则称该析（合）取范式为主析（合）取范式。 主析（合）取范式的性质见书P19,1.6 范式,75,定理 任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是唯一的。 关键之处： Ai Ai 1 Ai (pj pj)

34、(Ai pj ) (Ai pj) Ai Ai 0 Ai (pj pj) (Ai pj ) (Ai pj,1.6 范式,76,1.6 范式,主析取范式的求法 主析取范式的求法有两种:真值表法和等值演算法 等值演算法的步骤如下: 求A的析取范式A 若A的某简单合取式B中含命题变项pi或其否定,则将B展成如下形式: BB1 B(pipi) (Bpi)(Bpi) 将重复出现的命题变元、极小项和矛盾式都消去。 如：用pp用p代，pp用0代，mimi用mi代 将极小项按由小到大的顺序排列，并用表示之。 如：m1m2m5用（1，2，5）表示,77,1.6 范式,例题:求(pq)q的主析取范式 解:(1)用真

35、值表法求之: p q (pq) (pq)q 0 0 1 0 0 1 1 1 1 0 0 0 1 1 1 1 由真值表可求出: (pq)qm1m3(1,3,78,1.6 范式,2)用等值演算法求之 (pq)q(pq)q (pq)(qq) (pq)(q(pp) (pq)(pq)(pq) (pq)(pq) m1m3(1,3,79,练习：求主析取/合取范式。 1、( p q) (p r) 2、(p q) (p r,1.6 范式,80,解：1、接上 (p q) ( p r) (合取范式) (p q) (r r ) ( p r) (q q ) (p q r ) (p q r )(pq r) (pq r)

36、(p q r ) (p q r )(pq r) (pq r) (主合取范式) M0M1M4 M6,1.6 范式,81,解：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 范式,82,解：2、接上 p q ( p r ) (析取范式) ( p(q q)(pp)q)(pr) (q q) ( p qr) ( p qr) ( pq r) ( pqr) (pqr) ( p qr) ( p qr) (主析取范式

37、) m0 m1 m2 m3m5 m6 m7,1.6 范式,83,解：2、接上 (p p q ) ( p r q ) (合取范式) (1 q ) ( p r q ) p q r (主合取范式) M4,1.6 范式,84,主析取范式的用途（主合取范式类似讨论）： 1、求公式的成真/成假赋值： 若公式A中含有n个命题变项，且A的主析取范式含s 个极小项，则A有s个成真赋值，有2n-s个成假赋值,1.6 范式,85,2、判断公式的类型： 设公式A中含有n个命题变项，则： （1）A为重言式 A的主析取范式含全部2n个极小项。 （2）A为矛盾式 A的主析取范式不含任何极小项，记A的主析取范式为0。 （3）

38、A为可满足式 A的主析取范式至少含一个极小项,1.6 范式,86,3、判断两个命题是否等值： 设公式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 范式,87,解：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 范式,88,解： 2、 p (q r) p (

39、q r) 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 范式,89,4、解决实际问题： 练习：某勘探队有3名队员，有一天取得一块矿样，3人判断如下： 甲说：这不是铁，也不是铜。 乙说：这不是铁，是锡。 丙说：这不是锡，是铁。 经实验室鉴定发现，其中一人的两个判断全对，一人判对一半，另一人全错。试根据以上情况，判断矿样的种类,1.6 范式,90,解: 设 p:矿样是铁。q :矿样是铜。r :矿样是锡。 根据题设知有六种情况： 甲正确，乙对一半，丙全错； 甲正确，乙全错，丙对一半；

40、甲对一半，乙正确，丙全错； 甲对一半，乙全错，丙正确； 甲全错，乙正确，丙对一半； 甲全错，乙对一半，丙正确,1.6 范式,91,以上六种情况对应公式分别为： (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) 0,1.6 范式,92,解: 设 判断经过为F，则： F (pq r) (p q r) 但不能同时为铜又为锡，因而只能对应p q r，即不是铜，也不是锡，而是铁,1.6 范式,9

41、3,关于主合取范式 1、由公式的主析取范式求主合取范式 设公式A中含有n个命题变项，且A的主析取范式含s 个极小项，即 A mi1 mi2 mis，0ij 2n-1,j=1,2, ,s. 没出现的极小项为mj1 , mj2 mjs,它们的脚标的二进制表示为A的成真赋值，因而A的主析取范式为 A= mj1 mj2 mjs,1.6 范式,94,由定理知 A A ( mj1 mj2 mjs) mj1 mj2 mjs Mj1 Mj2 Mjs,1.6 范式,95,例题:求(pq)q的主合取范式 解:(1)用真值表法求之: p q (pq) (pq)q 0 0 1 0 0 1 1 1 1 0 0 0 1

42、1 1 1 由真值表可求出: (pq)qM0M2(0,2,1.6 范式,96,2)用等值演算法求之 (pq)q(pq)q (pq)(q（pp）) (pq)(qp)（qp） (pq)(pq) M0 M2(0,2,1.6 范式,97,2、重言式与矛盾式的主合取范式 设公式A中含有n个命题变项，则： （1）A为矛盾式 A的主合取范式含全部2n个极大项。 （2）A为重言式 A的主合取范式不含任何极大项，记A的主合取范式为1。 （3）A为可满足式 A的主合取范式中极大项的个数一定小于2n,1.6 范式,98,定理 极小项与极大项关系 设mi和Mi是命题变项p1 ， p2 ， pn形成的极小项和极大项，则

43、 mi Mi ， Mi mi,1.6 范式,99,1.7 命题逻辑的推理理论,推理的形式结构 定义 推理的一般形式 设A1，A2，Ak，B都是命题公式，若对于A1，A2，Ak，B 中出现的命题变项的任意一组赋值， 或者A1，A2，Ak为假， 或者当A1，A2，Ak为真时，B也为真， 则称由前提A1，A2，Ak 推出B的推理是有效的或正确的，并称B是有效的结论,100,说明： （1）由前提A1，A2，Ak推B的推理记作A1，A2，Ak|-B ,这称为推理的形式结构。如果推理是正确的，记作A1，A2，Ak|=B ，否则记作A1，A2，Ak|B。 （2）对于任一组赋值，前提和结论的取值有以下四种情况

44、： 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 命题逻辑的推理理论,101,推理的另一种形式： 定理 命题公式A1，A2，Ak推B的推理正确当且仅当 (A1 A2 Ak) B 为重言式。（证明参见课本） 于是推理的一般形式可转化为： (A1 A2 Ak) B 推理正确转化为： A1 A2 Ak = B,1.7 命题逻辑的推理理论,102,于是，以后推理的形式就写作： 前提：p , p q 结论：q 推理的形式结构： (p (p q) q 即只需证明蕴涵式(p (p q) q为重言式。 三种方法： 1、真

45、值表法； 2、等值演算法； 3、主析取范式法,1.7 命题逻辑的推理理论,103,例：判断下列推理是否正确。 1、今天小李或去网吧或去教室。他没去教室，所以他去网吧了。 设 p：小李去网吧。q：小李去教室。则， 前提：p q , q 结论：p 推理的形式结构： (p q) q) p,1.7 命题逻辑的推理理论,104,真值表法,1.7 命题逻辑的推理理论,105,等值演算法： (p q) q) p (p q ) (q q) p (p q ) p (p q ) p p q p 1 所以，推理正确，即（(p q) q) = p,1.7 命题逻辑的推理理论,106,主析取范式法： (p q) q)

46、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) = p,1.7 命题逻辑的推理理论,107,例：判断下列推理是否正确。 2、若a能被4整除，则天下雨。现天下雨。所以a能被4整除。 设 p： a能被4整除。q：天下雨。则， 前提：p q , q 结论：p 推理的形式结构： (p q) q) p 答案： 此推理不正确,1.7 命题逻辑的推理理论,108,经过长期的研究推理，人们发现一些重要的重言蕴涵式，我

47、们将这些重言蕴涵式称为推理定律。 十条推理定律,1.7 命题逻辑的推理理论,109,1）附加律 A = (AB) 2）化简律 (AB) = A 3）假言推理 (AB)A = B 4）拒取式 (AB)B = A 5）析取三段论 (AB)B = A 6）假言三段论 (AB)(BC) = (AC) 7）等价三段论 (AB)(BC) = (AC) 8）构造性二难 (AB)(CD)(AC) = (BD) (特殊形式) (AB)(AB)(AA) = B 9）破坏性二难 (AB)(CD)(BD) = (AC) 10）A,B均仅含有联接词如, ,如果A=B,则B*=A,1.7 命题逻辑的推理理论,110,1.

48、7 命题逻辑的推理理论,自然推理系统P 定义 自然推理系统P定义如下： （1）字母表：p ,q ,r,1,0; 、 、 ,(,); （2）合式公式：见定义1.7； （3）推理规则： 前提引入规则P:在证明的任何步骤上，都可以引入前提； 结论引用规则T:在证明的任何步骤上所得结论都可作为后续证明的前提； 置换规则E:在证明的任何步骤上，命题的任何形式都可进行等值置换； 所有的推理定律构成相应的推理规则（I,111,例1：在自然推理系统中构造下列推理的证明。 前提：p q , p r ,s t , s r , t 结论：q （前提、结论已明确给出） 证明： s t 前提引入 P t 前提引入 P

49、s 拒取式 T I s r 前提引入 P r 假言推理 T I p r 前提引入 P p 假言推理 T I p q 前提引入 P q 析取三段论T I,1.7 命题逻辑的推理理论,112,1.7 命题逻辑的推理理论,在以上证明中，中间是构成证明的命题序号，右边两列是每个命题得以引入的根据，通常只要选择一种即可。 应用前提引入规则用P表示； 应用结论引用规则用T表示； 使用了推理定律，表示为I； 使用了置换规则，表示为E； 同时必须写出推理前提,113,练习1：在自然推理系统中构造下列推理的证明。 1、前提：p r , q s , pq 结论：r s 2、前提：q p, q s , s t ,

50、tr 结论：p q,1.7 命题逻辑的推理理论,114,参考答案: 1、前提：p r, q s , pq 结论：r s 证明： pq 前提引入 P p 化简规则 T I q 化简规则 T I p r 前提引入 P r 假言推理 T I q s 前提引入 P s 假言推理 TI r s 附加规则 T I,1.7 命题逻辑的推理理论,115,参考答案: 2、前提：q p, q s , s t , tr 结论：p q 证明： tr 前提引入 P t 化简规则 T I s t 前提引入 P (s t) (t s) 置换 T E t s 化简规则 T I s 假言推理 T I,1.7 命题逻辑的推理理论

51、,116,q s 前提引入 P (s q) (q s) 置换 T E s q 化简规则 T I q 假言推理 T I (11) q p 前提引入 P p (11)假言推理 T (11)I p q (12) 合取 T (12)I,1.7 命题逻辑的推理理论,117,例2：在自然推理系统中构造下列推理的证明。 如果今天是星期一,则要进行英语或离散数学考试.如果英语老师有会,则不考英语.今天星期一,英语老师有会.所以进行离散数学考试. （前提、结论未明确给出,需要自己构造。) 解：首先将命题符号化： p: 今天是星期一。 q: 进行英语考试. r: 进行离散数学考试。 s: 英语老师有会,1.7 命

52、题逻辑的推理理论,118,1.7 命题逻辑的推理理论,前提：p (q r) , s q , p , s 结论：r 证明： p (q r ) 前提引入 p 前提引入 q r 假言推理 s q 前提引入 s 前提引入 q 假言推理 r 析取三段论,119,1.7 命题逻辑的推理理论,例3：一个侦探在调查某珠宝店的钻石项链盗窃案后，根据以下事实： （1）营业员A或B盗窃了钻石项链； （2）若A作案，则作案不在营业时间内； （3）若B提供的证明正确，则货柜未上锁； （4）若B提供的证明不正确，则作案在营业时间内； （5）货柜是上了锁的。 推出B盗窃了钻石项链，试验证推理的正确性,120,1.7 命题逻

53、辑的推理理论,符号化 p: A盗窃了钻石项链， q：B盗窃了钻石项链， r：作案在营业时间内， s: B提供的证明正确，t:货柜上了锁； 前提 p q, p r, s t, s r, t 结论 q,121,练习2：在自然推理系统中构造下列推理的证明。 1、如果今天是星期六，我们就要到颐和园或圆明园去玩。如果颐和园游人太多，我们就不到颐和园去玩。今天是星期六。颐和园游人太多。所以我们到圆明园玩。 解：首先将命题符号化： p: 今天是星期六。 q: 我们到颐和园去玩。 r: 我们到圆明园去玩。 s: 颐和园游人多,1.7 命题逻辑的推理理论,122,前提：p (q r) , s q , p , s

54、 结论：r 证明： s q 前提引入 s 前提引入 q 假言推理 p 前提引入 p (q r ) 前提引入 q r 假言推理 r 析取三段论,1.7 命题逻辑的推理理论,123,两种特殊的证明方法1、附加前提法(CP规则) 适用于此类蕴涵式的证明 (A1 A2 Ak ) (A B ) (*) 欲证明(*)式，只需证明 (A1 A2 Ak A ) B 即可，因为,1.7 命题逻辑的推理理论,124,*) 式 (A1 A2 Ak ) (A B ) (A1 A2 Ak ) ( A B ) (A1 A2 Ak ) ( A B ) A1 A2 Ak A B (A1 A2 Ak A ) B (A1 A2

55、Ak A) B (A1 A2 Ak A) B,1.7 命题逻辑的推理理论,125,例3： 前提：p (q r) , s p , q 结论：s r 证明： s p 前提引入 s 附加前提引入 p 析取三段论 p (q r) 前提引入 q r 假言推理 q 前提引入 r 假言推理,1.7 命题逻辑的推理理论,126,练习： 前提：(p q) ( r s), (s t) U 结论：p U 证明： p 附加前提引入 p q 附加规则 (p q) ( r s) 前提引入 r s 假言推理 s 化简规则 s t 附加规则 (s t) U 前提引入 U 假言推理,1.7 命题逻辑的推理理论,127,两种特殊

56、的证明方法2、归谬法 适用于此类蕴涵式的证明 (A1 A2 Ak ) B (*) 欲证明(*)式，只需将 B作为前提能推出矛盾来即可。因为： (*) (A1 A2 Ak ) B (A1 A2 Ak B） 若 (A1 A2 Ak B）为矛盾式，则 (A1 A2 Ak ) B 为重言式 ，即 (A1 A2 Ak ) = B,1.7 命题逻辑的推理理论,128,例4： 前提：p q , r q , r s 结论： p 证明： p 结论否定引入 p q 前提引入 q 假言推理 r q 前提引入 r 析取三段论 r s 前提引入 r 化简规则 r r 合取,1.7 命题逻辑的推理理论,129,练习：前提

57、：p q ， p r , q s 结论：r s 证明： (r s) 结论否定引入 r s 置换规则 r 化简规则 p r 前提引入 p 拒取 s 化简规则 q s 前提引入,1.7 命题逻辑的推理理论,130,q 拒取 p q 合取 (p q ) 置换规则 (11) p q 前提引入 (12) (p q ) (p q ) 11 合取,1.7 命题逻辑的推理理论,131,第二章 一阶逻辑,命题逻辑的局限性： 下列推理： 凡是人都是 要死的。 苏格拉底是人。 苏格拉底是要死的。 众所周知，这是真命题。但在命题逻辑中 （p q ） r 难证其为重言式。 原因：命题逻辑不考虑命题之间的内在联系和数量关

58、系。 办法：将命题再次细分,132,2.1 谓词与量词,2.1 一阶逻辑基本概念 基本概念： 在一阶逻辑中，简单命题被分解成个体词和谓词 1、个体：可以独立存在的具体的或抽象的客体 常元：具体的或特定，一般用a,b,c,表示 变元：抽象的或泛指的，一般用x,y,z,表示 个体域：个体变项的取值范围： 全总个体域,133,2、谓词 用来描述个体词性质或个体词之间相互关系的词。 例: (1)3是有理数。 (2)x是无理数。 (3)阿杜与阿寺同岁。 (4)x与y有关系L。 其中“是有理数”、“是无理数”、“与同岁”、 “与有关系L”均为谓词,2.1 谓词与量词,134,将上述谓词分别记作大写字母F、

59、G、H、L，则上述可表示为： (1)F(3) (2)G(x) (3)H(a,b) a:阿杜。b:阿寺。 (4)L(x,y,2.1 谓词与量词,135,谓词分类： 谓词常项：表示具体性质或关系的谓词 如上例中F、G、H等命题 谓词变项：表示抽象或泛指性质或关系的谓词 如上例中L命题,2.1 谓词与量词,136,一般地，用 p(x1 , x2 , , xn) 表示含有n个命题变项的n元谓词，也可以看作是以个体域为定义域，以0，1为值域的n元函数或关系。 但它不是命题。只有p是谓词常项， x1 , x2 , , xn为个体常项时，它才是命题。 不带任何个体变项的谓词称为0元谓词,2.1 谓词与量词,

60、137,3、量词 用来表示个体常项或变项之间数量关系的词。 量词分为两种： 全称量词：“一切”、“所有”、“凡”、“每一个”、“任意”等意，符号记作。如：x 表示个体域内所有的x。 存在量词：“有一个”、“有的”、“存在”、“至少有一个”等，符号记作。如:y表示个体域内有的y,2.1 谓词与量词,138,2.1 谓词与量词,4、特性谓词 特性谓词的引入： 1）对于全称量词特性谓词作为前提引入 2）对于存在量词特性谓词作为合取引入,139,例：在一阶逻辑中将下列命题符号化。 （1）凡是人都呼吸。 （2）有的人是左撇子。 当个体域为人类集合时： 令F(x): x呼吸。G(x): x是左撇子。则 （