《精品课程离散数学PPT课件全》由会员分享，可在线阅读，更多相关《精品课程离散数学PPT课件全（213页珍藏版）》请在金锄头文库上搜索。
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：罗纳尔多是球
6、星。 q：5是负数。 p3：明天天气晴。 皆为符号化的命题，其真值依次为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张校长的头发有一万根。张校长的
8、头发有一万根。2 2我所说的是假的。我所说的是假的。（是）（否）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是
10、奇数， q： 6是偶数。(5) p: 2与3的最小公倍数是6。(6) p:王丽和王娟是亲姐妹。193.析取词 设p,q为二命题，复合命题“p或q” 称为p与q的析取式，记作p q，符号称为析取联结词。运算规则：pqp q0000111011111.1 命题符号化及联结词20析取运算特点：只有参与运算的二命题全为假时，运算结果才 为假，否则为真。相容或：相容或：二者至少有一个发生，也可二者都发生二者至少有一个发生，也可二者都发生排斥或：排斥或：二者只有一个发生，即非此即彼二者只有一个发生，即非此即彼例如：（1）小王爱打球或爱跑步。 设p：小王爱打球。 q：小王爱跑步。 则上述命题可符号化为：p
11、q（2）张晓静是江西人或湖南人。 设p：江西人。 q：湖南人。 则上述命题就不可简单符号化为：p q 而应描述为(p q) ( pq)(也可用异或联接词)1.1 命题符号化及联结词214.蕴涵词 设p,q为二命题，复合命题“如果p，则q” 称为p与q的蕴涵式，记作p q，并称p为蕴涵式的前件，q为蕴涵式的后件，符号称为蕴涵联结词。运算规则：pqp q0010111001111.1 命题符号化及联结词22l例：一位父亲对儿子说：“如果星期天天气好，就一定带你去动物园。”问：在什么情况下父亲食言？解：有以下四种可能情况：（1）星期天天气好，带儿子去了动物园；（2）星期天天气好，却没带儿子去动物园；
12、（3）星期天天气不好，却带儿子去了动物园；（4）星期天天气不好，没带儿子去动物园。23蕴涵运算p q表示的逻辑关系是：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
13、(2)符号化为 p q真值为1真值为1251.1 命题符号化及联结词以下命题中出现的a是给定的一个正整数：(3) 只有 a能被2整除， 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： 将下列命
14、题符号化，并讨论各命题的真值。(1)雪是白色的当且仅当法国的首都是里昂。(2)n是奇数的充分必要条件是n2是奇数。解:(1)令p：雪是白色的，q：法国的首都是里昂； 符号化为p q，因为p为真，q为假，所以真值为0。 (2)令p： n是奇数， q： n2是奇数； 符号化为p q，因为p和q同真或同假，所以真值为1。1.1 命题符号化及联结词281.2 命题公式及其分类1.命题公式合式公式/命题公式：将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串。 当使用联结词集 ，时，合式公式（well formed formula）定义如下：（1）单个命题变项是合式公式，并称为原子命题公式。）单
15、个命题变项是合式公式，并称为原子命题公式。（2）若若A是是合合式式公公式式，则则( A)，(AB),(AB)，(AB)，(AB)，(AB)也是合式公式。也是合式公式。（3）只只有有有有限限次次地地应应用用(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注意：为
16、了方便，下面给出有关省略括号的一些约定。公式的最外层括号可以省略.并且，（ A）的括号可省略，记为 A.规定联结词的优先级为按， ， ， ，的顺序递减，若省略括号后按此优先顺序得到的公式与原公式一致，则允许省略.相同的联接词按从左到右的顺序计算时括号可以省略.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的
17、层次及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)的层次分别为 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
18、考虑：含有n个命题变项的公式共有多少个不同的赋值？1.2 命题公式及其分类34若指定的一组值使A的真值为1，则称这组值为A的成真赋值。 如对公式(p q) r赋值011，还有?若指定的一组值使A的真值为0，则称这组值为A的成假赋值。 如对公式(p q) r赋值010，还有?1.2 命题公式及其分类35公式的又一种分类方式设A为任一命题公式，（1）若A在其各种赋值下的取值均为真，则称A是重言式或永真式。（2）若A在其各种赋值下的取值均为假，则称A是矛盾式或永假式。（3）若A不是矛盾式，则称A为可满足式。1.2 命题公式及其分类361.2 命题公式及其分类l用命题形式q1 ，q2，qn 分别替换命
19、题形式A中的命题变项p1 ，p2，pn所得到的命题形式，称为A的一个替换实例（substitution instance）。l注意：一个替换应该是处处替换，而不是部分替换 。l定理1.1 设A命题形式，则（1）设A是重言式，则A的任何替换实例都是重言式;（2）设A是矛盾式，则A的任何替换实例都是矛盾式。见例1.11371 真值表将命题公式A在所有赋值下取值情况列成表，称做A的真值表。对公式A构造真值表的具体步骤为：（1）找出公式中所有的全体命题变项p1 ， p2 ， ， pn，列出2n个赋值。（2）按从低到高的顺序写出公式的各个层次。（3）对应各个赋值计算出各层次的真值，直到最后计算出公式的真
20、值。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 1101111 0010011 1001111.3 真值表和真值函数40练习2：构造公式 (p q) q 真值表。pq (p q) (p q) (p q) q001000110010010111001.3 真值表和真值函数41真值表的作用：（1）表示出公式的成真或成假赋值。（2）判断公
21、式类型： (a)若真值表最后一列全为1，则为重言式； (b)若真值表最后一列全为0，则为矛盾式； (c)若真值表最后一列至少有一个1，则为可满足式；1.3 真值表和真值函数42考虑：含有n个命题变项的公式的真值表有 ? 种不同的情况？因此，必有很多公式具有相同的真值表。如：pqp q p q00110111100011111.3 真值表和真值函数431.3 真值表和真值函数2 真值函数 定义 以真,假为定义域和值域的函数为真值函数。 如由五个逻辑联接词产生的所有wff都是真值函数，因此有无穷多个真值函数，显然最基本而重要的还是六个联接词。 当真值函数的变元为n个时，共有2n个指派，通过列出真值
22、表也可以定义真值函数。441.3 真值表和真值函数例 确定下列真值表对应的真值函数。PQRf1(P,Q,R)f2(P,Q,R)1111111000101101001001100010000011000001注意：由真值表确定的真值函数不一定是最简单的wff，且不一定只有一个表达式。451.3 真值表和真值函数例如 列出下列公式的真值表(P R) ( P Q) ( Q R)由此可见，这个公式的真值表与f1(P,Q,R)的相比较，可以看出这两个公式代表同一个真值函数。461.4 等值式与等值演算 等值式设A,B是两个命题公式，若A，B构成的等价式A B为重言式，则称A与B是等值的，记作A B。 即
23、A B的充要条件是A B为重言式。判断两个公式等值的方法1：真值表法。47例：判断公式 p(qr)、(p q) r是否等价。pqrp qqrp(qr)(p q) r00001110010111010001101101111000111101011111010001111111由由真值表可知，两个公式为等值式。真值表可知，两个公式为等值式。1.4 等值式与等值演算48需要记忆的16组重要的等值式 参见课本p13。等等值值演演算算：由由已已知知的的等等值值式式推推演演出出另另外外一一些些等等值值式的过程。式的过程。等值演算中使用的一条重要规则：等值演算中使用的一条重要规则：置换规则置换规则设设(A
24、)是是含含公公式式A的的命命题题公公式式，(B)是是用用公公式式B置置换换了了(A)中中所所有有的的A后后得得到到的的命命题题公公式式(不不一一定定是是每每一一处处)，若若BA，则则(A)(B)。1.4 等值式与等值演算49等值演算的用途一：证明等值式。例：验证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
25、.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 q ) p1.4 等值式与等值演算521.4 等值式与等值演算香农（Shanon)定理 用命题形式A只含有命题变项p1,p2,pn，命题常项0
26、，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，所得到的公式称为，所得到的公式称为A A的对偶式，记作的对偶式，记作A A* *说明说明 AA是是A A* *的对偶式，即对偶式是相互的，
27、又（的对偶式，即对偶式是相互的，又（A A* *）* *=A=A 0 0与与1 1互为对偶式互为对偶式 例例1 1：写出下列公式的对偶式。：写出下列公式的对偶式。pp（qqr） （pqpq）0 0 解：解：pp（qqr） （ppq q）1 1 54对偶定理：对偶定理：设设A A和和A A* *互互为为对对偶偶式式，p p1 1，p p2 2，p pn n是是出出现现在在A A和和A A* *中中的的全全部的命题变项，则部的命题变项，则A A（p p1 1，p p2 2，p pn n） A A* *（p p1 1，p p2 2，p pn n）A A（p p1 1，p p2 2，p pn n） A
28、 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.例 化简语句：“情况并非如此：如果他不来，那么我也不去”。例 小李或小张是先进工作者；如果小李是先进工作者，你是会知道的；如果小张是先进工作者，小赵也是；你不知道小李是先进工作者
29、，问谁是先进工作者。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。pq为真当且仅当为真当且仅当p与与q不时为真
30、。不时为真。pq （pq）性质：性质：pqqpppp p p（pq）（pq）pq（pp）（qq）pq1.5 联结词完备集联结词完备集583或非词或非词设设p、q为为命命题题，则则“p或或q的的否否定定”称称为为p与与q的的或非式，记为或非式，记为pq。pq为真当且仅当为真当且仅当p与与q同时为假。同时为假。pq （pq）性质：性质：pqqpppp p p（pq）（pq）pqq（pp）（qq）pq 1.5 联结词完备集联结词完备集59二二.联结词的全功能集联结词的全功能集定义定义称称F：0，1n0，1为为n元真值函数。元真值函数。定定义义：设设s是是一一个个联联结结词词集集合合，如如果果任任何何
31、n元元真真值值函函数数都都可可以以由由仅仅含含s中中的的联联结结词词构构成成的的公公式式表表示示，则称则称s是联结词全功能集。是联结词全功能集。如如果果全全功功能能集集合合不不含含冗冗余余联联接接词词则则是是极极小小全全功功能能。定理定理s= ,是联结词的全功能集。是联结词的全功能集。1.5 联结词完备集联结词完备集60析取范式与合取范式 含n个命题变项的公式两种规范表示方法定义文字（literal）:命题变元及它们的否定。简单析取式：仅由有限个文字构成的析取式。 如：p , q , p q , p q r简单合取式：仅由有限个文字定构成的合取式。 如：p , q , p q , p q r1
32、.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 A
33、2 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 范式6
34、6例：求(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 范式67练习：求析取/合取范式。1、( p q) (p r)2、(p q) (p r).1.6 范式68解：1、 ( p q) (p r) (p q) ( p r) (合取范
35、式) (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 ( 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位上（若命题变项无角标
36、，就按字母顺序），称这样的简单合（析）取式为极小（大）项。考虑： n个命题变项可产生多少个极小（大）项？1.6 范式71可以观察到：每个极小项，如p1 p2 p3 pn,有且仅有一个成真赋值，若成真赋值所对应的二进制数转化为十进制数为i，就将所对应的极小项记作mi。每个极大项，如p1 p2 p3 pn,有且仅有一个成假赋值，若成假赋值所对应的二进制数转化为十进制数为i，就将所对应的极大项记作Mi。1.6 范式721.6 范式例：例：p p、q q形成的所有极小项形成的所有极小项公式公式成真赋值成真赋值名称名称pq00m0pq01m1pq10m2 pq11m3例：例：p p、q q形成的所有极大
37、项形成的所有极大项 公式公式 成假赋值成假赋值 名称名称 pqpq 0 0 M0 0 0 M0 pqpq 0 1 M1 0 1 M1 pqpq 1 0 M2 1 0 M2 pqpq 1 1 M3 1 1 M373定义 设由n个命题变项构成的析（合）取范式中所有的简单合（析）取式都是极小（大）项，则称该析（合）取范式为主析（合）取范式。主析（合）取范式的性质见书P19 1.6 范式74定理 任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是唯一的。 关键之处： Ai Ai 1 Ai (pj pj) (Ai pj ) (Ai pj) Ai Ai 0 Ai (pj pj) (Ai pj )
38、 (Ai pj)1.6 范式751.6 范式主析取范式的求法主析取范式的求法主析取范式的求法有两种主析取范式的求法有两种: :真值表法和等值演算法真值表法和等值演算法等值演算法的步骤如下等值演算法的步骤如下:求求A的的析取范式析取范式AA若若AA的的某某简简单单合合取取式式B B中中含含命命题题变变项项p pi i或或其其否否定定, ,则将则将B B展成如下形式展成如下形式: : BB1 BB1 B(pB(pi ippi i) () (BpBpi i)(Bp)(Bpi i) )将将重重复复出出现现的的命命题题变变元元、极极小小项项和和矛矛盾盾式式都都消消去。去。如：用如：用pppp用用p p代
39、，代，pppp用用0 0代，代，m mi immi i用用m mi i代代将将极极小小项项按按由由小小到到大大的的顺顺序序排排列列，并并用用表表示示之。之。如：如：m1m2m5m1m2m5用用（1 1，2 2，5 5）表示）表示761.6 范式例题例题: :求求( (pq)qpq)q的主析取范式的主析取范式 解解:(1):(1)用真值表法求之用真值表法求之: : p q (p q (pqpq) () (pq)qpq)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)qp
40、q)qm1m3(1,3)m1m3(1,3)771.6 范式(2)(2)用等值演算法求之用等值演算法求之 ( (pq)qpq)q(pq)qpq)q ( (pq)(qqpq)(qq) ) ( (pq)(q(pppq)(q(pp) ( (pq)(pq)(pqpq)(pq)(pq) ) ( (pq)(pqpq)(pq) ) m1m3(1,3) m1m3(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 )(
41、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 ) (析取范式) ( p(q q)(pp)q)(pr) (q q) ( p qr) ( p qr) ( pq r) ( pqr) (pqr) ( p qr) ( p qr
42、) (主析取范式) 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个极小项。（2）A为矛盾式 A的主析取范式不含任何极小项，记A的主析取范式为0。（3）A为可满
43、足式 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) m0 m1
44、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 :矿样是锡。根据题设知有六种情况：甲正确，乙对一半，丙全错；甲正确，乙全错，丙对一半； 甲对一半，乙正确，丙全错；甲对一半，乙全
45、错，丙正确； 甲全错，乙正确，丙对一半；甲全错，乙对一半，丙正确。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中
46、含有n个命题变项，且A的主析取范式含s 个极小项，即A mi1 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)qpq)q的主合取范式的主合取范式 解解:(1):(1)用真值表法求之用真值表法求之: : p q (p q (pqpq) () (pq)qpq)q 0 0 1 0 0 0 1 0 0 1 1 1
47、 0 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1由真值表可求出由真值表可求出: : ( (pq)qpq)qM0M2(0,2)M0M2(0,2) 1.6 范式95(2)(2)用等值演算法求之用等值演算法求之 ( (pq)qpq)q(pq)qpq)q ( (pq)(qpq)(q（pppp）) ) ( (pq)(qppq)(qp)（qpqp） (pq)(pqpq)(pq) ) M0 M0 M2(0,2)M2(0,2) 1.6 范式962、重言式与矛盾式的主合取范式设公式A中含有n个命题变项，则：（1）A为矛盾式 A的主合取范式含全部2n个极大项。（2）A为重言式 A的
48、主合取范式不含任何极大项，记A的主合取范式为1。（3）A为可满足式 A的主合取范式中极大项的个数一定小于2n 。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
49、，A2，Ak推B的推理记作A1，A2，Ak|-B ,这称为推理的形式结构。如果推理是正确的，记作A1，A2，Ak|=B ，否则记作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 命题
50、逻辑的推理理论101于是，以后推理的形式就写作： 前提：p , p q 结论：q推理的形式结构： (p (p q) q即只需证明蕴涵式(p (p q) q为重言式。三种方法： 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真值表法真值表法
51、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 命题逻辑的推理理论105主析取范式法：(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整除，则天下雨。现天下雨
52、。所以a能被4整除。 设 p： a能被4整除。q：天下雨。则， 前提：p q , q 结论：p 推理的形式结构： (p q) q) p 答案： 此推理不正确。1.7 命题逻辑的推理理论107经过长期的研究推理，人们发现一些重要的重言蕴涵式，我们将这些重言蕴涵式称为推理定律。 十条推理定律：1.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
53、(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)(AB)(AA) = B) (AB)(AB)(AA) = B9 9）破坏性二难破坏性二难 (AB)(CD)(BD) = (AB)(CD)(BD) = (AC)(AC)1010）A,BA,B均仅含有联接词如均仅含有联接词如 , , ,如果如果A=B,A=B,则则
54、B B* *=A=A* *. . 1.7 命题逻辑的推理理论1091.7 命题逻辑的推理理论自然推理系统P定义 自然推理系统P定义如下：（1）字母表：p ,q ,r,1,0; 、 、 ,(,); （2）合式公式：见定义1.7；（3）推理规则： 前提引入规则P:在证明的任何步骤上，都可以引入前提； 结论引用规则T:在证明的任何步骤上所得结论都可作为后续证明的前提； 置换规则E:在证明的任何步骤上，命题的任何形式都可进行等值置换； 所有的推理定律构成相应的推理规则（I）.110例1：在自然推理系统中构造下列推理的证明。前提：p q , p r ,s t , s r , t结论：q （前提、结论已明
55、确给出）前提、结论已明确给出）证明： s t 前提引入 P t 前提引入 P s 拒取式 T I s r 前提引入 P r 假言推理 T I p r 前提引入 P p 假言推理 T I p q 前提引入 P q 析取三段论T I1.7 命题逻辑的推理理论1111.7 命题逻辑的推理理论 在以上证明中，中间是构成证明的命题序号，右边两列是每个命题得以引入的根据，通常只要选择一种即可。l 应用前提引入规则用P表示； 应用结论引用规则用T表示；l使用了推理定律，表示为I；l使用了置换规则，表示为E；l同时必须写出推理前提。112练习1：在自然推理系统中构造下列推理的证明。1、前提：p r , q s
56、 , pq 结论：r s2、前提：q p, q s , s t , tr 结论：p q1.7 命题逻辑的推理理论113参考答案: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 I1.7 命题逻辑的推理理论114参考答案: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
57、s 假言推理 T I1.7 命题逻辑的推理理论115 q s 前提引入 P (s q) (q s) 置换 T E s q 化简规则 T I q 假言推理 T I(11) q p 前提引入 P(12)p (11)假言推理 T (11)I(13)p q (12) 合取 T (12)I1.7 命题逻辑的推理理论116例2：在自然推理系统中构造下列推理的证明。 如果今天是星期一,则要进行英语或离散数学考试.如果英语老师有会,则不考英语.今天星期一,英语老师有会.所以进行离散数学考试. （前提、结论未明确给出前提、结论未明确给出,需要自己构造。需要自己构造。)解：首先将命题符号化： p: 今天是星期一。
58、 q: 进行英语考试. r: 进行离散数学考试。 s: 英语老师有会。1.7 命题逻辑的推理理论1171.7 命题逻辑的推理理论前提：前提：p(qr),s q,p,s结论：结论：r证明：证明：p(qr)前提引入前提引入p前提引入前提引入qr假言推理假言推理s q前提引入前提引入s前提引入前提引入 q假言推理假言推理r析取三段论析取三段论1181.7 命题逻辑的推理理论例3：一个侦探在调查某珠宝店的钻石项链盗窃案后，根据以下事实：（1）营业员A或B盗窃了钻石项链；（2）若A作案，则作案不在营业时间内；（3）若B提供的证明正确，则货柜未上锁；（4）若B提供的证明不正确，则作案在营业时间内；（5）货
59、柜是上了锁的。 推出B盗窃了钻石项链，试验证推理的正确性。1191.7 命题逻辑的推理理论符号化 p: A盗窃了钻石项链， q：B盗窃了钻石项链， r：作案在营业时间内， s: B提供的证明正确，t:货柜上了锁；前提 p q, p r, s t, s r, t结论结论 q120练习2：在自然推理系统中构造下列推理的证明。1、如果今天是星期六，我们就要到颐和园或圆明园去玩。如果颐和园游人太多，我们就不到颐和园去玩。今天是星期六。颐和园游人太多。所以我们到圆明园玩。解：首先将命题符号化： p: 今天是星期六。 q: 我们到颐和园去玩。 r: 我们到圆明园去玩。 s: 颐和园游人多。1.7 命题逻辑
60、的推理理论121前提：p (q r) , s q , p , s结论：r证明： s q 前提引入 s 前提引入 q 假言推理 p 前提引入 p (q r ) 前提引入 q r 假言推理 r 析取三段论 1.7 命题逻辑的推理理论122两种特殊的证明方法1、附加前提法(CP规则) 适用于此类蕴涵式的证明 (A1 A2 Ak ) (A B ) (*)欲证明(*)式，只需证明 (A1 A2 Ak A ) B 即可，因为1.7 命题逻辑的推理理论123(*) 式 (A1 A2 Ak ) (A B ) (A1 A2 Ak ) ( A B ) (A1 A2 Ak ) ( A B ) A1 A2 Ak A
61、B (A1 A2 Ak A ) B (A1 A2 Ak A) B (A1 A2 Ak A) B1.7 命题逻辑的推理理论124例3：前提：p (q r) , s p , q结论：s r证明： s p 前提引入 s 附加前提引入 p 析取三段论 p (q r) 前提引入 q r 假言推理 q 前提引入 r 假言推理 1.7 命题逻辑的推理理论125练习：前提：(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 命题逻辑的
62、推理理论126两种特殊的证明方法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 ) = B1.7 命题逻辑的推理理论127例4：前提：p q , r q , r s结论： p证明： p 结论否定引入 p q 前提引入 q 假言推理 r q 前提引入 r 析取三段论 r s 前提引入 r 化简规则 r r 合取1.7 命题逻辑的推理理论128练习：前提：
63、p q ， p r , q s 结论：r s证明： (r s) 结论否定引入 r s 置换规则 r 化简规则 p r 前提引入 p 拒取 s 化简规则 q s 前提引入1.7 命题逻辑的推理理论129 q拒取拒取 p q合取合取 (pq)置换规则置换规则(11)pq前提引入前提引入(12) (pq)(pq)11合取合取1.7 命题逻辑的推理理论130第二章 一阶逻辑命题逻辑的局限性：下列推理： 凡是人都是 要死的。 苏格拉底是人。 苏格拉底是要死的。众所周知，这是真命题。但在命题逻辑中 （p q ） r 难证其为重言式。原因：命题逻辑不考虑命题之间的内在联系和数量关系。办法：将命题再次细分。1
64、312.1 谓词与量词2.1 一阶逻辑基本概念基本概念：在一阶逻辑中，简单命题被分解成个体词和谓词1、个体：可以独立存在的具体的或抽象的客体 常元：具体的或特定，一般用a,b,c,表示 变元：抽象的或泛指的，一般用x,y,z,表示 个体域：个体变项的取值范围： 全总个体域1322、谓词 用来描述个体词性质或个体词之间相互关系的词。例: (1)3是有理数。 (2)x是无理数。 (3)阿杜与阿寺同岁。 (4)x与y有关系L。其中“是有理数”、“是无理数”、“与同岁”、 “与有关系L”均为谓词。2.1 谓词与量词133将上述谓词分别记作大写字母F、G、H、L，则上述可表示为： (1)F(3) (2)
65、G(x) (3)H(a,b) a:阿杜。b:阿寺。 (4)L(x,y)2.1 谓词与量词134谓词分类：谓词常项：表示具体性质或关系的谓词 如上例中F、G、H等命题谓词变项：表示抽象或泛指性质或关系的谓词 如上例中L命题2.1 谓词与量词135一般地，用 p(x1 , x2 , , xn)表示含有n个命题变项的n元谓词，也可以看作是以个体域为定义域，以0，1为值域的n元函数或关系。 但它不是命题。只有p是谓词常项， x1 , x2 , , xn为个体常项时，它才是命题。 不带任何个体变项的谓词称为0元谓词。2.1 谓词与量词1363、量词 用来表示个体常项或变项之间数量关系的词。 量词分为两种
66、：全称量词：“一切”、“所有”、“凡”、“每一个”、“任意”等意，符号记作。如：x 表示个体域内所有的x。存在量词：“有一个”、“有的”、“存在”、“至少有一个”等，符号记作。如:y表示个体域内有的y。2.1 谓词与量词1372.1 谓词与量词4、特性谓词、特性谓词特性谓词的引入：特性谓词的引入：1）对于全称量词特性谓词作为）对于全称量词特性谓词作为前提前提引入引入2）对于存在量词特性谓词作为）对于存在量词特性谓词作为合取合取引入引入138例：在一阶逻辑中将下列命题符号化。（1）凡是人都呼吸。（2）有的人是左撇子。当个体域为人类集合时： 令F(x): x呼吸。G(x): x是左撇子。则（1）x
67、F(x) (2) xG(x)当个体域为全总个体域时： 令F(x): x呼吸。G(x): x是左撇子。M(x): x是人。则（1）x(M(x) F(x) (2) x(M(x) G(x)2.1 谓词与量词139说明：（1）在不同的个体域，同一命题的符号化形式可能相同也可能不同。（2）在不同的个体域，同一命题的真值可能相同也可能不同。（3）约定以后如不指定个体域，默认为全总个体域。2.1 谓词与量词140例：在一阶逻辑中将下列命题符号化，并讨论其真值。（1）所有的人都长着黑头发。（2）有的人吸烟。（3）没有人登上过木星。（4）清华大学的学生未必都是高素质的。解：令M(x): x是人。（1） 令F(x
68、): x长黑头发。则符号化为：x(M(x) F(x)真值为。2.1 谓词与量词141（2） 令s(x): x吸烟。则符号化为： x(M(x)s(x)真值为。 （3） 令D(x): x登上过木星。则符号化为： x(M(x)D(x)真值为。 （4）令q(x):x是清华大学的学生。H(x):x是高素质的。则符号化为： x(q(x) H(x) 真值为。2.1 谓词与量词142练：在一阶逻辑中将下列命题符号化，并讨论其真值。（1）凡正数都大于零。（2）存在小于2的素数。（3）没有不能表示成分数的有理数。（4）并不是所有参加考试的人都能取得好成绩。解：（1） 令F(x): x是正数。M(x):x大于零。则
69、符号化为：x(F(x) M(x)真值为1。2.1 谓词与量词143（2） 令e(x): x小于2。s(x):x是素数。则符号化为： x(e(x)s(x)真值为0。 （3） 令D(x): x是有理数。F(x):x能表示成分数。则符号化为： x(D(x) F(x) 或 x(D(x) F(x)真值为。 （4）令M(x)：x是人.q(x):x参加考试。H(x):x取得好成绩。则符号化为： x(M(x) q(x) H(x) 或 x(M(x) q(x) H(x) 真值不定。2.1 谓词与量词144例：例：在一阶逻辑中将下列命题符号化在一阶逻辑中将下列命题符号化1 1）没有不犯错误的人）没有不犯错误的人2
70、2）对于所有自然数，均有）对于所有自然数，均有x+yxx+yx解：解：1 1）M(x)M(x)：x x是人是人 F(x)F(x)：x x犯错误犯错误 符号化为：符号化为： x(M(x)F(x)x(M(x)F(x) 2 2）N(x)N(x)：x x是自然数是自然数 F(x,y)F(x,y)：x+yxx+yx x x y(N(x)N(y)F(x,y)y(N(x)N(y)F(x,y) 2.1 谓词与量词145例：在一阶逻辑中将下列命题符号化 。（1）（所有的）兔子比（所有的）乌龟跑得快。（2）有的兔子比所有的乌龟跑得快。（3）并不是所有的兔子都比乌龟跑得快。（4）没有两只跑得同样快的兔子。解：令H(
71、x): x是兔子。w(x):x是乌龟。 K(x,y):x比y跑得快。L(x,y):x和y跑得一样快。 则符号化为：（1）x y(H(x) w(y) K(x,y)2.1 谓词与量词146（2） x (H(x) y(w(y) K(x,y)（3） x y( H(x)w(y) K(x,y) 或 x y(H(x) w(y) K(x,y)（4） x y( H(x)H(y) L(x,y) 或 x y(H(x) H(y) L(x,y)2.1 谓词与量词147例：在一阶逻辑中将下列命题符号化 。（1）每列火车都比有些汽车跑得快。（2）某些汽车比所有火车慢。（3）每个人都喜爱自己的孩子。（4）对于任意给定的正实数
72、，都存在比它大的实数。解：（1）令H(x): x是火车。w(x):x是汽车。 K(x,y):x比y跑得快。 则符号化为： x (H(x) y(w(y) K(x,y)2.1 谓词与量词148（2）令H(x): x是火车。w(x):x是汽车。 K(x,y):x比y跑得慢。 则符号化为： x(w(x) y(H(y) K(x,y)（3）令M(x): x是人。H(x):x是孩子。 p(x,y):x是y的父母。 K(x,y):x喜爱y。 则符号化为： x y(M(x)H(y)p(x,y) K(x,y)（4）令M(x): x是实数。p(x,y): x y。 则符号化为： x(M(x)p(x,0)y(M(y)
73、 p(y,x)2.1 谓词与量词149说明：（1）分析命题中表示性质和关系的谓词，要分别符号化为一元和n(n 2)元谓词。（2）根据命题的实际意义选用 或 。（3）一般来说，当多个量词同时出现时，它们的顺序不能随意调换。如： 在实数域上用L(x,y)表示x+y=10命题为：对于任意的x,都存在y使得x+y=10。 可符号化为： xyL(x,y) 真值为1。 若调换顺序后为： yxL(x,y) 真值为0。2.1 谓词与量词150说明：（4）有些命题的符号化形式不止一种。至此，下列推理即可解决： 凡是人都是 要死的。 苏格拉底是人。 苏格拉底是要死的。设：M(x):x是人。D(x):x 是要死的。
74、a:苏格拉底。则符号化为： x(M(x)D(x) M(a) D(a)2.1 谓词与量词151定义2.1一阶语言的字母表定义如下：（1）个体常元：a , b , c , ai , bi , ci，i 1.（2）个体变元：x , y , z , xi , yi , zi，i 1.（3）函数符号：f , g , h , fi , gi , hi，i 1.（4）谓词符号：F , G , H,Fi , Gi , Hi，i 1.（5）量词符号： ， .（6）联结词符号： ，.（7）括号与逗号： （，），.2.2 2.2 一阶语言一阶语言152定义2.2一阶语言的项(term)的定义如下：（1）个体常项和个
75、体变项是项（2）若f(x1 , x2 , xn ) 是任意的n元函数， t1 , t2 , tn 是任意的n个项，则f(t1 , t2 , tn )是项。（3）所有的项都是有限次使用（1），（2）得到的。定义2.3若P为不能再分解的一元或n元谓词，则称P(x)或P (x1 , x2 , xn ) 为原子公式。2.2 一阶语言一阶语言 153定义2.4 的合式公式/谓词公式/公式定义如下：（1）原子公式是合式公式。（2）若A 是合式公式，则(A)也是合式公式。（3）若A，B是合式公式，则(A B)，(A B)，(A B)，(A B)也是合式公式。（4）若A是合式公式，x为任意变元，且A中无x、
76、x出现，则x A , x A，也是合式公式。 （5）只有有限次应用(1)(4)构成的符号串才是合式公式。2.2 一阶语言一阶语言154定义2.5在公式x A和x A中，称x为指导变元，A为相应量词的辖域。在x 和x的辖域中，x的所有出现都称为约束出现，A中不是约束出现的其它变项均称为是自由出现的。例： 1、x( H(x,y)y(w(y) L(x,y,z)2、 x( H(x)w(y) y( F(x) L(x,y,z)2.2 一阶语言一阶语言155定义2.6设A 是任意的公式，若A中不含自由出现的个体变项，则称A为封闭的公式，简称为闭式。2.2 一阶语言一阶语言例如： x(F(x) x(F(x)
77、G(x) G(x)）、）、 x x y(F(x) G(x,y) y(F(x) G(x,y) 都是都是闭式闭式 x(F(x) x(F(x) G(x G(x，y)y)）、）、 z z y(L(x,y,z) y(L(x,y,z) 都不是都不是闭式闭式156两 个 规 则约束变项改名规则约束变项改名规则 将量词辖域中出现的某个约束出现的个体变元及对应的知指导变元，改成另一个辖域中未曾出现过的个体变元符号，公式中其余部分不变。自由变项代入规则自由变项代入规则 对某自由出现的个体变元用原公式中所有个体变元符号不同的变元符号去代替，且处处代替。2.2 一阶语言一阶语言157例：将下列公式等值化，使其不含既是
78、约束出现又是自由出现的个体变项。(1) x F(x,y,z) y G(x,y,z) t F(t,y,z) y G(x,y,z) (改名规则) t F(t,y,z) r G(x,r,z) (改名规则)或 x F(x,y,z) y G(x,y,z) x F(x,t,z) y G(x,y,z) (代入规则) x F(x,t,z) y G(r,y,z) (代入规则)2.2 一阶语言一阶语言158练习：将下列公式等值化，使其不含既是约束出现又是自由出现的个体变项。(1) x F(x,y) y G(x,y)(2)xy(F(x,y)G(y,z) x H(x,y,z)2.2 一阶语言一阶语言159定义2.7
79、的解释的解释I由下列4部分组成：(1)非空个体域DI。(2)DI中 一 些 特 定 元 素 的 集 合a1,a2,ai,.(3)DI上特定函数集合fin|i,n 1.(4)DI上特定谓词的集合Fin|i,n 1.所谓一个解释不外乎指定个体域、个体域中一些特定的元素、特定的函数和谓词等。2.2 一阶语言一阶语言160例：设个体域为D=a,b,c,将下列各公式的量词去掉。(1) x(F(x)G(x)(2) x(F(x)y G(y)(3) xy F(x,y)解: (1)(F(a)G(a) (F(b)G(b)(F(c)G(c) (2)x F(x)y G(y) (F(a)F(b)F(c)(G(a) G(
80、b) G(c)(3) x( F(x,a)F(x,b)F(x,c)(F(a,a)F(a,b)F(a,c) (F(b,a)F(b,b)F(b,c) (F(c,a)F(c,b)F(c,c) 2.2 一阶语言一阶语言161例2.7：给定解释I如下：(a)个体域D=2,3(b)D中特定元素a=2(c) D上特定函数f(x):f(2)=3,f(3)=2(d) D上特定谓词G(x,y):G(2,2)= G(2,3)= G(3,2)=1,G(3,3)=0. L(x,y):L(2,2)= L(3,3)=1, L(2,3)= L(3,2)=0. F(x):F(2)=0,F(3)=1.在I下求下列各式的真值。 (1
81、) x(F(x) G(x,a)） (2) x(F(f(x)G(x,f(x) (3)xy L(x,y) (4)yx L(x,y)2.2 一阶语言一阶语言162解: (1)(F(2)G(2,2)(F(3)G(3,2) (01)(11) 0 (2)(F(f(2)G(2,f(2) (F(f(3)G(3,f(3) (F(3)G(2,3) (F(2)G(3,2) (11)(01) 1(3)(L(2,2)L(2,3) (L(3,2)L(3,3) (10)(01)1 (4) y( L(2,y) L(3,y) ) (L(2,2)L(3,2)(L(2,3) L(3,3) (10)(01) 02.2 一阶语言一阶语
82、言163练习：给定解释I如下：(a)个体域D=3,4(b) D上特定函数f(x):f(3)=4,f(4)=3(c)D上特定谓词F(x,y):F(3,3)= F(4,4)=0, F(3,4)=F(4,3)=1.在I下求下列各式的真值。 (1) x y F(x,y)(2) yx F(x,y)(3)x y( F(x,y) F(f(x),f(y) 2.2 一阶语言一阶语言164解: (1) x (F(x,3) F(x,4) (F(3,3) F(3,4)(F(4,3)F(4,4) (01)(10) 1 (2) y(F(3,y)F(4,y) (F(3,3)F(4,3) (F(3,4)F(4,4) (01)
83、 (10) 02.2 一阶语言一阶语言165解:(3)(F(3,3)F(f(3),f(3) (F(3,4)F(f(3),f(4) (F(4,3)F(f(4),f(3) (F(4,4)F(f(4),f(4) (0F(4,4)(1F(4,3)(1F(3,4) (0F(3,3) 1(11)(11)1 1111 12.2 一阶语言一阶语言166定理2.1 封闭的公式在任何解释下都变成命题。定义2.8 设A为一公式，若A在任何解释下均为真，则称A为永真式（逻辑有效式）。若A在任何解释下均为假，则称A为矛盾式（永假式）。若至少存在一个解释使A为真，则称A为可满足式。在一阶逻辑里面，由于公式的复杂性和解释的
84、多样性，迄今为止还没有一种能判断任意一个公式是否可满足的算法。2.2 一阶语言一阶语言167定义2.9 设A0是含p1,p2,pn命题变项的命题公式，A1,A2,An是n个谓词公式，用Ai(1 i n)处处代替A0中的pi，所得公式A称为A0的代换实例。定理2.2 重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。2.2 一阶语言一阶语言1682.3 一阶逻辑的等值演算一阶逻辑等值式与置换规则在一阶逻辑中，有些命题可以有不同的符号化形式。如： 没有不能表示为分数的有理数。令H(x): x是有理数。w(x):x能表示成分数。 则： （1）x (H(x) w(x) （2） x(H(x) w(
85、x)均正确。 同命题逻辑一样，我们称（1）、（2）是等值的。169定义2.10设A，B是一阶逻辑中任意两个公式， 若A B为重言式，则称A与B是等值的，记作A B。 称A B是等值式。已经得证的重要等值式：第一组第一组：由等值式给出的代换实例，如：(1) x F(x) x F(x) (2) x y(F(x,y)G(x,y) x y(F(x,y)G(x,y) (3) F(x)G(y) F(x) G(y)(4) x(F(x)G(y)z L(z) x(F(x)G(y)z L(z)2.3 一阶逻辑的等值演算170第二组第二组：1、消去量词等值式设个体域为有限集D=a1，a2， ，an，则(1) x A
86、(x)A(a1)A(a2) A(an)(2) x A(x)A(a1)A(a2) A(an)2、量词否定等值式设A(x)是任意的含自由出现个体变项x的公式，则(1) x A(x) x A(x)(2) x A(x) x A(x)2.3 一阶逻辑的等值演算1713、量词辖域收缩与扩张等值式设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则(1) x(A(x)B) x A(x)B x(A(x)B) x A(x)B x(A(x)B) x A(x) B x(B A(x) B x A(x)2.3 一阶逻辑的等值演算172量词辖域收缩与扩张等值式中的 x(A(x)B) x A(x) B如何证明
87、？左 x( A(x) B) x A(x) B (应用此前1式) x A(x) B x A(x) B 右2.3 一阶逻辑的等值演算1733、量词辖域收缩与扩张等值式设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则(2) x(A(x)B) x A(x)B x(A(x)B) x A(x)B x(A(x)B) x A(x) B x(B A(x) B x A(x)2.3 一阶逻辑的等值演算1744、量词分配等值式 设A(x)、B(x)是任意的含自由出现个体变项x的公式，则(1) x(A(x)B(x) x A(x) x B(x) (2)x(A(x)B(x) x A(x) x B(x) 2
88、.3 一阶逻辑的等值演算175例 证明：(1) x(A(x)B(x) x A(x) x B(x)(2) x(A(x)B(x) x A(x) x B(x)其中，A(x)、B(x)为含x自由出现的公式。证:（1）只需证明x(A(x)B(x)x A(x) x B(x)不是永真式。 设个体域为人集合，A(x):x是男人。 B(x):x是女人。（2）只需证明 x(A(x)B(x) x A(x) x B(x)不是永真式。 设个体域为全总个体域，A(x):x是人。 B(x):x有尾巴。2.3 一阶逻辑的等值演算176例：证明下列各式为等值式。(1) x(F(x)G(x) x(F(x) G(x)(2) x(F
89、(x)G(x) x(F(x) G(x)(3) xy(F(x)G(y)H(x,y) xy (F(x)G(y) H(x,y) (4) xy(F(x)G(y)H(x,y) xy(F(x)G(y) H(x,y) 2.3 一阶逻辑的等值演算177证：(1) x(F(x) G(x) x (F(x)G(x) （量词否定等值式） x ( F(x) G(x) （置换规则） x ( F(x) G(x) （置换规则）(2) x(F(x)G(x) x (F(x) G(x) （量词否定等值式） x ( F(x)G(x) （置换规则） x( F(x) G(x) （置换规则）2.3 一阶逻辑的等值演算178证： (3) x
90、y(F(x)G(y)H(x,y) x（y(F(x)G(y)H(x,y)） xy（F(x)G(y)H(x,y)） xy（F(x)G(y)）H(x,y)） xy（F(x)G(y)） H(x,y)）2.3 一阶逻辑的等值演算179前束范式在命题逻辑中，公式有析取范式和合取范式两种形式；在一阶逻辑中，公式也有范式形式。定义2.11设A 是一个一阶逻辑公式，若A具有如下形式 q1x1q2x2qkxkB 则称A为前束范式，其中qi为或，B为不含量词的公式。2.3 一阶逻辑的等值演算如：如： x y（F(x)G(y)） H(x,y)） x y(F(x,y)G(y,z) xH(x,y,z)说明：1）若A中无量
91、词，则A也看作是前束范式 2）前束范式的特点：所有量词均非否定地出现在公式最前面，且它的辖域一直延伸到公式末。180定理（前束范式存在定理） 一一阶阶逻逻辑辑中中的的 任任何何公公式式都都存存在在与与之之等等价价的的前束范式。前束范式。本定理说明：任何公式的前束范式都是存在的，但一般不是唯一的。求法：利用前面的公式及三条变换规则（置换规则、换名规则、代替规则）即可求出与公式等值的前束范式。2.3 一阶逻辑的等值演算181例例2.112.11：求下列公式的前束范式。：求下列公式的前束范式。（1） x F(x) x G(x)解： (1) x F(x) x G(x) (量词否定等值式) x (F(x
92、) G(x) (量词分配等值式)或 (1) x F(x) y G(y) (换名规则) x F(x) y G(y) (量词否定等值式) x (F(x) y G(y) (量词辖域扩张等值式) x y (F(x) G(y) (量词辖域扩张等值式)2.3 一阶逻辑的等值演算182例例2.112.11：求下列公式的前束范式。：求下列公式的前束范式。（2） x F(x) x G(x)解： （2） x F(x) y G(y) (换名规则) x F(x) y G(y) (量词否定等值式) x (F(x) y G(y) (量词辖域扩张等值式) x y (F(x) G(y) (量词辖域扩张等值式)2.3 一阶逻辑
93、的等值演算183例例2.112.11：求下列公式的前束范式。：求下列公式的前束范式。（3） x F(x,y) y G(x,y)解： （3） t F(t,y) w G(x,w) (换名规则) t w(F(t,y) G(x,w) (量词辖域扩张等值式)或(3) x F(x,t) y G(w,y) (代替规则) x y(F(x,t) G(w,y) (量词辖域扩张等值式)2.3 一阶逻辑的等值演算184例例2.112.11：求下列公式的前束范式。：求下列公式的前束范式。（4）(x F(x,y) y G(y) x H(x,y,z) 解:（4）(x F(x,y) b G(b)c H(c,y,z) (换名规
94、则)x b(F(x,y) G(b)c H(c,y,z) (量词辖域扩张等值式)xbc (F(x,y) G(b)H(c,y,z) (量词辖域扩张等值式)2.3 一阶逻辑的等值演算185练习：求下列公式的前束范式。练习：求下列公式的前束范式。（1） x F(x) x G(x)解： x F(x) y G(y) (换名规则) x y (F(x) G(y) (量词辖域扩张等值式)(2)x F(x) x G(x) x F(x) y G(y) (换名规则) x y (F(x) G(y) (量词辖域扩张等值式)2.3 一阶逻辑的等值演算186练习：求下列公式的前束范式。练习：求下列公式的前束范式。（3） x
95、F(x) y G(x,y) (4) x (F(x,y) y G(x,y,z) )(5) x F(x,y) (F(x) y H(x,y) 2.3 一阶逻辑的等值演算187练习：求下列公式的前束范式。练习：求下列公式的前束范式。（3） x F(x) y G(x,y) 解： a F(a) b G(x,b) (换名规则) a b (F(a) G(x,b) (量词辖域扩张等值式)或 x F(x) y G(z,y) (代替规则) x y (F(x) G(z,y) (量词辖域扩张等值式)2.3 一阶逻辑等值式188练习：求下列公式的前束范式。练习：求下列公式的前束范式。(4) x (F(x,y) y G(x
96、,y,z) 解： a (F(a,y) b G(a,b,z) (换名规则) a b(F(a,y)b G(a,b,z) (量词辖域扩张等值式)或 x (F(x,a) y G(x,y,z) (代替规则) x y (F(x,a) G(x,y,z)(量词辖域扩张等值式)2.3 一阶逻辑的等值演算1892.4 一阶逻辑的推理理论一阶逻辑的推理理论在一阶逻辑中，从前提A1,A2Ak出发推结论B的推理的形式结构，依然采取如下的蕴涵式形式 A1 A2 Ak B若此式为重言式，则称推理正确；否则称推理不正确。本书主要介绍在形式系统中构造证明的证明方法。190在一阶逻辑中称永真式的蕴涵式为推理定律。若某个推理的形式
97、结构正是某条推理定律，则这个推理显然是正确的。推理定律的几组来源：(1) 命题逻辑推理定律的代换实例。例如： x F(x) y G(y)= x F(x) x F(x) = x F(x) y G(y) p212.4 一阶逻辑的推理理论191(2) 由基本等值式生成的推理定律。例如： x F(x) = x F(x) x F(x) = x F(x) x A(x) = x A(x) x A(x) = x A(x) 2.4 一阶逻辑的推理理论192(3) x A(x)x B(x)= x (A(x) B(x) x(A(x) B(x)= x A(x) x B(x) x (A(x)B(x)= x A(x) x
98、 B(x) x(A(x)B(x)= x A(x) x B(x) 2.4 一阶逻辑的推理理论193四条重要推理规则：p40-411、全称量词消去规则（UI规则）2、全称量词引入规则（UG规则）3、存在量词引入规则（EG规则）4、存在量词消去规则（EI规则）注意：只能对前束范式适用上述规则。2.4 一阶逻辑的推理理论1941、全称量词消去规则（ UI 规则） x A(x) 或 x A(x) A(y) A(c)成立的条件：(1) 在第一式 中，取代x的y应为任意的不在A中约束出现的个体变项。(2)在第二式中，c为任意的个体常项。(3)用y或c去取代A(x)中的自由出现的x时，一定要在x自由出现的一切
99、地方进行取代。2.4 一阶逻辑的推理理论1952、全称量词引入规则（ UG 规则） A(y) x A(x)成立的条件：(1)无论A(y)中自由出现的个体变项y取何值，A(y)应均为真。(2)取代自由出现的y的x也不能在A(y)中约束出现。2.4 一阶逻辑的推理理论1963、存在量词引入规则（ EG规则） A(c) x A(x)成立的条件：(1)c是特定的个体常项。(2)取代c的x不能在A(c)中出现过。2.4 一阶逻辑的推理理论1974、存在量词消去规则（ EI规则） x A(x) A(c) 成立的条件：(1)c是使A为真的特定的个体常项。(2)c不在A(x)中出现过。(3)若A(x)中除自由
100、出现的x外，还有其它自由出现的个体变项，此规则不能使用。如: x A(x,y) A(c,y) 2.4 一阶逻辑的推理理论198例：例：在自然推理系统在自然推理系统F F中，构造下列推理的证明。中，构造下列推理的证明。前提： x (A(x)B(x)， x A(x)结论： x B(x)证明： x A(x) 前提引入 A(c) EI 规则 x (A(x)B(x) 前提引入 A(c)B(c) UI 规则 B(c) 假言推理 x B(x) EG规则注意： 引入的顺序不可更改！ 2.4 一阶逻辑的推理理论199练练1 1：在自然推理系统在自然推理系统F F中，构造下列推理的证明。中，构造下列推理的证明。
101、凡是人都是 要死的。 苏格拉底是人。 苏格拉底是要死的。设：M(x):x是人。D(x):x 是要死的。a:苏格拉底。则：前提：x(M(x)D(x)，M(a）.结论： D(a) .证明： x (M(x)D(x) 前提引入 P M(a)D(a) UI规则 T UI M(a) 前提引入 P D(a) 假言推理 T I 2.4 一阶逻辑的推理理论200练练2:2:在自然推理系统在自然推理系统F F中，构造下列推理的证明。中，构造下列推理的证明。前提：x(F(x) G(x)， x G(x).结论： x F(x) .证明： x G(x) 前提引入 P x G(x) 置换规则 T E G(a) UI T U
102、I x(F(x) G(x) 前提引入 P F(a) G(a) UI T UI F(a) 析取三段论 T I x F(x) EG T EG2.4 一阶逻辑的推理理论201练练3:3:在自然推理系统在自然推理系统F F中，构造下列推理的证明。中，构造下列推理的证明。前提：x(F(x)G(x), x( r(x) G(x), x r(x).结论： x F(x) .证明： x F(x) 结论否定引入 x F(x) 置换规则 F(a) EI x(F(x) G(x) 前提引入 F(a) G(a) UI G(a) 析取三段论 x( r(x) G(x) 前提引入 r(a) G(a) UI r(a) 析取三段论
103、x r(x) 前提引入 (11) r(a) UI (12) r(a) r(a) (11) 合取2.4 一阶逻辑的推理理论202练练4:4:指出下面证明中的错误。指出下面证明中的错误。证明： x (F(x)G(x) 前提引入 F(y)G(y) UI x F(x) 前提引入 F(y) EI G(y) 假言推理 x G(x) UG对x F(x)消去量词时，要求用特定的个体常项取代x，而不能用变项y取代x，所以到有错。2.4 一阶逻辑的推理理论203练练5:5:指出下面证明中的错误。指出下面证明中的错误。证明： xy F(x,y) 前提引入 y F(z,y) UI F(z,c) EI x F(x,c)
104、 UG yx F(x,y) EG因为y F(z,y)中存在自由出现的个体变项z，因而不能使用eI规则。所以到有错。2.4 一阶逻辑的推理理论204例：例：在自然推理系统在自然推理系统F F中，构造下列推理的证明中，构造下列推理的证明。前提： x (A(x)B(x)， x (A(x)H(x)结论： x (B(x)H(x)证明： x (A(x)H(x) 前提引入 A(c) H(c) EI 规则 x (A(x)B(x) 前提引入 A(c)B(c) UI 规则 A(c) 化简规则 H(c) 化简规则 B(c) 假言推理 B(c)H(c) 合取 x (B(x)H(x) EG规则2.4 一阶逻辑的推理理论
105、205练练1:1:在自然推理系统在自然推理系统F F中，构造下列推理的证明。中，构造下列推理的证明。前提：x(F(x) (G(a) r(x)， x F(x).结论： x (F(x) r(x).证明： x F(x) 前提引入 F(b) EI x(F(x) (G(a) r(x) 前提引入 F(b) (G(a) r(b) UI G(a) r(b) 假言推理 r(b) 化简 F(b) r(b) 合取 x (F(x) r(x) EG2.4 一阶逻辑的推理理论206练练2:2:在自然推理系统在自然推理系统F F中，构造下列推理的证明。中，构造下列推理的证明。前提： x(F(x) H(x)， x(G(x)
106、H(x) .结论： x(G(x) F(x).证明： x(F(x) H(x) 前提引入 x ( F(x) H(x) 置换规则 x(H(x) F(x) 置换规则 H(y) F(y) UI x(G(x) H(x) 前提引入 G(y) H(y) UI G(y) F(y) 假言三段论 x(G(x) F(x) UG2.4 一阶逻辑的推理理论207例：例：在自然推理系统在自然推理系统F F中，构造下列推理的证明中，构造下列推理的证明。设个体域为实数域。 不存在能表示成分数的无理数。有理数都能表示成分数。因此，有理数都不是无理数。解：设F(x):x是无理数. G(x):x是有理数. H(x):x能表示成分数.
107、前提： x(F(x) H(x)， x(G(x) H(x) .结论： x(G(x) F(x).证明同前。2.4 一阶逻辑的推理理论208练练1 1：在自然推理系统在自然推理系统F F中，构造下列推理的证明中，构造下列推理的证明。学术委员会的每个成员都是博士并且是教授。有些成员是青年人。因而有的成员是青年教授。解： 先将简单命题符号化： A(x):x是学术委员会成员。 B(x):x是博士。 J(x):x是教授。 H(x):x是青年人。前提： x (A(x)B(x)J(x)， x (A(x)H(x)结论： x (A(x) J(x) H(x)2.4 一阶逻辑的推理理论209证明： x (A(x)H(x
108、) 前提引入 A(c) H(c) EI 规则 x (A(x)B(x) J(x) 前提引入 A(c)B(c)J(c) UI 规则 A(c) 化简规则 H(c) 化简规则 B(c) J(c) 假言推理 J(c) 化简规则 A(c) J(c) H(c) 合取 x (A(x) J(x)H(x) EG规则2.4 一阶逻辑的推理理论210练练2 2：在自然推理系统在自然推理系统F F中，构造下列推理的证明中，构造下列推理的证明。有些病人相信所有的医生。但是病人都不相信骗子。所以，医生都不是骗子。解： 先将简单命题符号化： A(x):x是病人。 B(x):x是医生。J(x):x是骗子。 H(x,y):x相信
109、y。前提： x (A(x) y(B(y) H(x,y)， x (A(x) y(J(y) H(x,y).结论： x (B(x) J(x).2.4 一阶逻辑的推理理论211证明： x(A(x)y(B(y)H(x,y) ) 前提引入 A(c) y(B(y)H(c,y) EI 规则 A(c) 化简规则 y(B(y)H(c,y) 化简规则 x (A(x) y(J(y) H(x,y) 前提引入 A(c) y(J(y) H(c,y) EI规则 y(J(y) H(c,y) 假言推理 y(H(c,y) J(y) 置换规则 B(z)H(c,z) UI规则 H(c,z) J(z) UI规则 (11) B(z) J(z) 假言三段论 (12) x (B(x) J(x) (11)UG规则2.4 一阶逻辑的推理理论212第一部分 数理逻辑the end of this part.thanks !213
