《第一章 数理逻辑谓词逻辑优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第一章 数理逻辑谓词逻辑优秀PPT.ppt（100页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章 数理逻辑谓词逻辑现在学习的是第1页，共100页2谓词逻辑Predicate Logic现在学习的是第2页，共100页3问题的提出：(命题逻辑的局限性)n例：苏格拉底论断前提n“所有的人总是要死的”n“苏格拉底是人”结论n“所以苏格拉底是要死的”n命题逻辑中原子命题不可再分PQRPQR不是有效推理不是有效推理现在学习的是第3页，共100页4n例1：小张是大学生2：小李是大学生Q1：2大于3Q2：6大于4n命题逻辑无法反映不同原子命题间的内在共性n解决问题的方法分析原子命题，分离其主语和谓语考虑一般和个别，全称和存在现在学习的是第4页，共100页53.1谓词的概念与表示谓词的概念与表示n定
2、义定义3.1.1在原子命题中，用来刻划一个个体的性质或个体之间关系的成分称为谓词谓词，刻划一个个体性质的词称为一元谓词一元谓词；刻划n个个体之间关系的词称为n元谓词元谓词n常用大写英文字母表示个体n能够独立存在的事物n通常用小写英文字母a、b、c、.表示个体常量n用小写英文字母x、y、z.表示任何个体，则称这些字母为个体变元个体变元现在学习的是第5页，共100页6n例例 1(a)5 是质数 (b)张明生于北京(c)7=32F(x)：x是质数G(x,y)：x生于y，a：张明，b：北京H(x,y,z)：x=yzF(5)G(a,b)H(7,3,2)谓词 个体词谓词命名式(谓词填式)变元的次序很重要变
3、元的次序很重要现在学习的是第6页，共100页7n谓词常量（谓词常元）一个字母代表一特定谓词,例如F代表“是质数”,则称此字母为谓词常量n谓词变元若字母代表任意谓词,则称此字母为谓词变元n论域个体域谓词命名式中个体变元的取值范围空集不能作为论域现在学习的是第7页，共100页83.2 命题函数与量词n谓词命名式不是不是命题若谓词是常元个体词是常元谓词命名式才成为一个命题n定义定义3.2.1由一个谓词常量，一些个体变元组成的表达式称为简单命题函简单命题函数数，表示为P(x1,x2,xn)。由一个或若干个简单命题函数以及逻辑联结词组成的命题形式称为复合命题函数复合命题函数，简单命题函数和复合命题函数统
4、称为命题函数命题函数 n=0时n命题变元命题变元现在学习的是第8页，共100页9n例 A(x)：x身体好 B(x)：x学习好 C(x)：x工作好如果x身体不好，则x的学习与工作都不会好 复合命题函数A(x)(B(x)C(x)现在学习的是第9页，共100页10量词n例“所有的正整数都是素数”“有些正整数是素数”n假设只有两个正整数a和b个体域为a,bP(x)：x是素数P(a)P(b)P(a)P(b)现在学习的是第10页，共100页11量词n定义定义3.2.2 设为论域上的一个一元谓词，则 命题x(x)的真值为，iff 对上的每一个个体a，命题(a)的真值为；命题x(x)的真值为，iff 在上存在
5、个体a，使得命题(a)的真值为。现在学习的是第11页，共100页12全称量词n记作n表示“每个”、“任何一个”、“一切”、“所有的”、“凡是”、“任意的”等nx读作“任意x”，“所有x”，“对一切x”n量词后边的个体变元，指明对哪个个体变元量化，称为量词后的指导变元指导变元n例所有人都是要死的D(x)：x是要死的个体域：所有人构成的集合x D(x)现在学习的是第12页，共100页13存在量词n记作 n表示“有些”、“一些”、“某些”、“至少一个”等n x读作“存在x”，“对某些x”或“至少有一x”n指导变元指导变元n例有些有理数是整数(x)：x是整数个体域：有理数集合x(x)现在学习的是第13
6、页，共100页14全总个体域（全总域）n含有量词的命题的真值与论域有关n含有量词的命题的表达式的形式与论域有关n全总个体域全总个体域宇宙间所有的个体聚集在一起所构成的集合约定约定n除特殊说明外，均使用全总个体域n对个体变化的真正取值范围，用特性谓词特性谓词加以限制现在学习的是第14页，共100页15例1)所有的人都是要死的2)有的人活百岁以上D(x)：x是要死的G(x)：x活百岁以上n个体域E为全体人组成的集合1)x D(x)2)x G(x)n全总个体域引入特性谓词M(x)：x是人1)x(M(x)D(x)2)x(M(x)G(x)现在学习的是第15页，共100页16特性谓词添加规则n对全称量词,
7、特性谓词作为条件式之前件加入n对存在量词,特性谓词作为合取项而加入n例(a)没有不犯错误的人F(x)：x犯错误 M(x)：x是人 x(M(x)F(x)(b)凡是实数,不是大于零就是等于零或小于零R(x)：x是实数L(x,y)：xyE(x,y)：x=yS(x,y)：x yx(R(x)L(x,0)E(x,0)S(x,0)现在学习的是第16页，共100页173.3 谓词演算的合式公式谓词演算的合式公式n个体函数（函词）例n小王比他的父亲高 T(x，y)：x比y高a：小王b：小王的父亲T(a，b)无法显示个体之间的依赖关系定义函词nf(x)=x的父亲nT(a，f(a)现在学习的是第17页，共100页1
8、8n函词与谓词的区别函词中的个体变元用个体带入后的结果依然是个体nf(a)=小王的父亲谓词中的个体变元用确定的个体带入后就变成了命题nM(x)：x是人nM(a)：小王是人函词是论域到论域的映射nf:DD谓词是从论域到T,F的映射nM:D T,F现在学习的是第18页，共100页19项和原子公式n定义定义3.3.1 项(item)表示个体定义(1)个体常量是项(2)个体变元是项(3)如果f是一个n(n1)元函词，其t1,t2,tn都是项，则f(t1,t2,tn)是项p例na,b,cnx,y,znf(x),g(a,f(y)现在学习的是第19页，共100页20n定义定义3.3.2 原子公式(atom)
9、定义n若P是一个n元谓词，且t1,t2,tn是项，则P(t1,t2,tn)是原子命题词也是原子(n=0)例nP,Q(x),A(x,f(x),B(x,y,a)现在学习的是第20页，共100页21谓词演算的合式公式(Wff)n也叫谓词公式，简称公式n定义定义3.3.3(1)原子公式是合式公式(2)如果A、B是合式公式，则A、(AB)、(AB)、(AB)、(AB)都是合式公式(3)如果A是合式公式，x是中的任何个体变元，则x和x也是合式公式(4)有限次地使用规则(1)至(3)求得的公式是合式公式n例P，(PQ)，(Q(x)P)，x(A(x)B(x)，xC(x)现在学习的是第21页，共100页22命题
10、符号化n谓词逻辑中比较复杂n命题的符号表达式与论域有关系例：每个自然数都是整数论域D=NnI(x)：x是整数nx I(x)论域为全总个体域n特性谓词N(x)：x是自然数nx(N(x)I(x)现在学习的是第22页，共100页23例：将下列命题符号化(1)所有大学生都喜欢一些歌星。S(x)：x是大学生，X(x)：x是歌星，L(x,y)：x喜欢y x(S(x)y(X(y)L(x,y)(2)发光的不都是金子。P(x)：x发光，G(x)：x是金子x(P(x)G(x)或者x(P(x)G(x)(3)不是所有的自然数都是偶数。N(x)：x是自然数，E(x)：x是偶数x(N(x)E(x)或者x(N(x)E(x)
11、现在学习的是第23页，共100页24(4)某些人对食物过敏F(x,y)：x对y过敏，M(x)：x是人，G(x)：x是食物 xy(M(x)G(y)F(x,y)(5)每个人都有些缺点 H(x,y)：x有y，M(x)：x是人，S(x)：x是缺点 x(M(x)y(S(y)H(x,y)(6)尽管有人聪明,但未必人人聪明 M(x)：x是人，S(x)：x聪明 x(M(x)S(x)x(M(x)S(x)现在学习的是第24页，共100页25练习：将下列命题符号化(1)所有教练员都是运动员；(J(x)，L(x)(2)某些运动员是大学生；(S(x)(3)某些教练员是年老的，但是健壮的；(O(x)，V(x)(4)金教练
12、虽不年老，但不健壮；(j)(5)不是所有运动员都是教练员；(6)某些大学生运动员是国家选手；(C(x)(7)没有一个国家选手不是健壮的；(8)所有老的国家选手都是运动员；(9)没有一位女同志既是国家选手又是家庭妇女；(W(x)，H(x)(10)有些女同志既是教练员又是国家选手；(11)所有运动员都钦佩某些教练员；(A(x,y)(12)有些大学生不钦佩运动员。现在学习的是第25页，共100页26练习参考答案(1)x(J(x)L(x)(2)x(L(x)S(x)(3)x(J(x)O(x)V(x)(4)J(j)O(j)V(j)(5)x(L(x)J(x)或者 x(L(x)J(x)(6)x(S(x)L(x
13、)C(x)(7)x(C(x)V(x)或者 x(C(x)V(x)(8)x(C(x)O(x)L(x)(9)x(W(x)C(x)H(x)(10)x(W(x)J(x)C(x)(11)x(L(x)y(J(y)A(x,y)(12)x(S(x)y(L(y)A(x,y)现在学习的是第26页，共100页27几个特别的例子(1)如果明天下雨下雨，则某些人将被淋湿 不是个体不是个体定义命题词P：明天下雨，M(x)：x是人，W(x)：x将被淋湿P x(M(x)W(x)(2)有且仅有有且仅有一个偶素数P(x)：x是偶素数 x(P(x)y(P(y)x=y)或者x(P(x)y(xyP(y)(3)顶多只有一台顶多只有一台机器
14、是好的 P(x)：x是好机器用符号 !xP(x)表示有且仅有一个个体满足Pxy(P(x)P(y)x=y)用符号 !xP(x)表示顶多有一个个体满足P现在学习的是第27页，共100页28 (4)如果人都爱美，则漂亮衣服有销路 M(x)：x是人，L(x)：x爱美，C(x)：x是衣服，B(x)：x是漂亮的，S(x)：x有销路x(M(x)L(x)x(C(x)B(x)S(x)问题一：前后两个x是否指同一个个体？答：前后两个x不是不是同一个个体问题二：若写成如下形式是否正确？x(M(x)L(x)y(C(y)B(y)S(y)答：是正确的正确的，显然x(M(x)L(x)x(C(x)B(x)S(x)x(M(x)
15、L(x)y(C(y)B(y)S(y)现在学习的是第28页，共100页293.4 变元的约束变元的约束n量词的作用域作用域(辖域辖域)定义定义：在谓词公式中，量词的作用范围称之为量词的作用域，也叫量词的辖域。例nxA(x)x的辖域为A(x)nx(P(x)Q(x)yR(x,y)x的辖域是(P(x)Q(x)yR(x,y)y的辖域为R(x,y)nxyz(A(x,y)B(x,y,z)C(t)x x的辖域的辖域 z z的辖域的辖域 y y的辖域的辖域自由变元自由变元现在学习的是第29页，共100页30一般地，n如果量词后边只是一个原子谓词公式时，该量词的辖域就是此原子谓词公式。n如果量词后边是括号，则此括
16、号所表示的区域就是该量词的辖域。n如果多个量词紧挨着出现，则后边的量词及其辖域就是前边量词的辖域。现在学习的是第30页，共100页31n约束变元如果个体变元x在x或者x的辖域内，则称x在此辖域内约束出现，并称x在此辖域内是约束变元n自由变元如果个体变元x不在任何量词的辖域内，则称x是自由出现，并称x是自由变元n例 x(F(x,y)yP(y)Q(z)F(x,y)中的x和P(y)中的y是约束变元而F(x,y)中的y和Q(z)中的z是自由变元现在学习的是第31页，共100页32例：指出下列各公式中的量词辖域及自由变元和约束变元nxy(P(x)Q(y)zR(z)x的辖域y(P(x)Q(y)y的辖域P(
17、x)Q(y)z的辖域R(z)nx(P(x,y)yQ(x,y,z)S(x,z)x的辖域P(x,y)yQ(x,y,z)其中x是约束变元y是自由变元y的辖域Q(x,y,z)其中y是约束变元x,z是自由变元S(x，z)中x，z是自由变元现在学习的是第32页，共100页33对约束变元和自由变元的几点说明n约束变元用什么符号表示无关紧要xA(x)与yA(y)是一样的 n一个谓词公式如果无自由变元，它就表示一个命题例：A(x)表示x是个大学生xA(x)或者xA(x)是命题n一个n元谓词P(x1,x2,xn)，若在前边添加k个量词，使其中的 k个个体变元变成约束变元，则变成n-k元谓词函数现在学习的是第33页
18、，共100页34nP(x,y,z)表示x+yz假设论域是整数集，xyP(x,y,z)表示？n“任意给定的整数x，都可以找到整数y，使得x+yz”。令z=1，则xyP(x,y,1)表示？n“任意给定的整数x，都可以找到整数y，使得x+y1”,。例现在学习的是第34页，共100页35n不同个体以相同的符号出现容易产生混淆n例x(F(x,y)yP(y)Q(z)n约束变元的换名规则：1.对约束变元可以更改名称，改名的范围是：量词后的指导变元以及该量词的辖域内此个体变元出现的各处同时换名。2.改名后用的个体变元名称，不能与该量词的辖域内的其它变元名称相同。约束变元换名现在学习的是第35页，共100页36
19、nx(P(x)Q(x,y)(R(x)A(x)x以两种形式出现对x换名 z(P(z)Q(z,y)(R(x)A(x)nx(P(x,y)yQ(x,y,z)S(x,y)对x和y换名u(P(u,v)vQ(u,v,z)S(x,y)n错误u(P(u,y)zQ(u,z,z)S(x,y)n错误u(P(u,y)vQ(u,v,z)S(x,y)n正确例现在学习的是第36页，共100页37自由变元换名n自由变元也可以换名n此换名叫代入n自由变元的代入规则：1.对谓词公式中的自由变元可以作代入。代入时需要对公式中出现该变元的每一处，同时作代入2.代入后的变元名称要与公式中的其它变元名称不同现在学习的是第37页，共100页
20、38例nx(P(x)Q(x,y)(R(x)A(x)用z代替自由变元xx(P(x)Q(x,y)(R(z z)A(z z)nx(P(x,y)yQ(x,y,z)S(x,z)用w和t分别代自由变元x和yx(P(x,t t)yQ(x,y,z)S(w w,z)现在学习的是第38页，共100页393.5 谓词公式的解释谓词公式的解释n定义定义3.5.1 对谓词公式的解释包括以下几点：1.指定一个论域D2.对A中出现的每一个n元函数，指定一个D上的 n元个体函数常量3.对A中出现的每一个n元谓词，指定一个D上的n元谓词常量4.对A中出现的每一个个体常量及自由变元，指定D中的一个个体常量5.对A中出现的每一个命
21、题变元P，指派一个真值T或F 由此得到一个命题AI，称AI的真值为合适公式A在解释I 下的真值现在学习的是第39页，共100页40例n取解释I如下：D=1,2,定义D上的二元谓词P真值为P(1,1):T；P(1,2):F；P(2,1):F；P(2,2):T 则xyP(x,y)和yxP(x,y)在解释I下的真值分别为?现在学习的是第40页，共100页41xyP(x,y)TTFFTTT212211xyP(x,y)yP(x,y)P(x,y)yx现在学习的是第41页，共100页42yxP(x,y)TFFFFFT212211yx P(x,y)xP(x,y)P(x,y)xy现在学习的是第42页，共100页
22、43例n取解释I如下：D=1,2,令 a:1,f(1)=2,f(2)=1定义D上的谓词P和Q为P(1):F；P(2):T；Q(1,1):T；Q(1,2):T；Q(2,1):F；Q(2,2):F求谓词公式x(P(x)Q(f(x),a)在解释I下的真值P(1)Q(f(1),1)P(2)Q(f(2),1)TTx(P(x)Q(f(x),a)在解释I下的真值为T现在学习的是第43页，共100页443.6 谓词公式的永真式n定义定义 给定谓词公式A，E是其论域，如果在任何解释下公式A的真值都为真，则称公式A在论域E上是永真式。如果不论对什么论域E，都使得公式A为永真式，则称A为永真式。例：I(x)：x是整
23、数，论域E为自然数集合nI(x)在E上是永真式nI(x)I(x)是与论域无关的永真式n谓词公式的永假式n谓词公式的可满足式现在学习的是第44页，共100页45例：试说明以下公式的类型1.xA(x)A(y)2.xA(x)A(y)3.A(x)(A(x)：x+6=5)4.x(A(x)A(x)5.x(A(x)B(x)xA(x)xB(x)6.x(A(x)B(x)xA(x)xB(x)永真式 可满足式 可满足式永假式现在学习的是第45页，共100页465.x(A(x)B(x)xA(x)xB(x)解 取解释I如下:D=1,2 A(1)B(1)A(1)A(2)B(1)B(2)T F F TT A(2)B(2)T
24、 x(A(x)B(x)T x A(x)F x B(x)F则在 I 下 x A(x)x B(x)F所以在 I 下x(A(x)B(x)xA(x)xB(x)的真值为假，该式不是不是永真式现在学习的是第46页，共100页476.x(A(x)B(x)xA(x)xB(x)解 取解释I如下:D=1,2A(1)A(2)B(1)B(2)F T T F或A(1)A(2)B(1)B(2)T F F T x A(x)x B(x)T x(A(x)B(x)F所以在 I 下x(A(x)B(x)xA(x)xB(x)的真值为假，该式不是不是永真式现在学习的是第47页，共100页48命题演算的推广 n定理定理3.6.1(代入定理
25、)设A是命题逻辑中的永真式，则用谓词逻辑的合式公式代替A中的某些命题变元得到的代入实例也是永真式；如果A是永假式，则上述代入实例也是永假式例nA(x)A(x)B(x)PPQnx(A(x)B(x)x(A(x)B(x)PQPQn(xA(x)xB(x)xA(x)xB(x)摩根律现在学习的是第48页，共100页49量词与联词的关系 n 定理定理3.6.2 x(x)x(x)；x(x)x(x)。证明 给定公式x(x)x(x)在论域上的解释。若x(x)在下为真，即x(x)为假，那么中的每一个个体a皆使(a)为假，即(a)为真，所以x(x)为真。另一方面，若x(x)为真，则中的每一个个体a皆使(a)为真，即(
26、a)为假，所以x(x)为假，即x(x)为真。利用的结论，我们有：x(x)x(x)x(x)x(x)现在学习的是第49页，共100页50例 xyz(x+z=y)xyz(x+z=y)xyz(x+z=y)xy z(x+z=y)xy z(x+zy)现在学习的是第50页，共100页51n定理定理3.6.3 1.xA(x)Px(A(x)P)2.xA(x)Px(A(x)P)3.xA(x)Px(A(x)P)4.xA(x)Px(x)P)5.PxA(x)x(PA(x)6.PxA(x)x(PA(x)7.xA(x)Px(A(x)P)8.xA(x)Px(A(x)P)P是不含个体变元x的谓词公式证明式1：(逻辑推证)一方面
27、，当P为F时，xA(x)Px(A(x)P)xA(x)另一方面，当P为T时，xA(x)Px(A(x)P)T量词辖域的扩张和收缩现在学习的是第51页，共100页52n定理定理3.6.41.x(A(x)B(x)xA(x)xB(x)2.x(A(x)B(x)xA(x)xB(x)3.x(A(x)B(x)xA(x)xB(x)4.xA(x)xB(x)x(A(x)B(x)证明式1：个体域中每一个体x，使得 A(x)B(x)为真,等价于对一切x,A(x)是真并且对一切x,B(x)是真证明式2：由1得x(A(x)B(x)xA(x)xB(x)即 x(A(x)B(x)(xA(x)xB(x)故 x(A(x)B(x)xA(
28、x)xB(x)量词与和等联词的关系 现在学习的是第52页，共100页53n注意注意：公式3和4不是等价公式，而是永真蕴含式n例：给定如下解释nA(x)：x是奇数B(x)：x是偶数则 xA(x)xB(x)为真 x(A(x)B(x)为假所以xA(x)xB(x)不蕴含不蕴含x(A(x)B(x)或nD=1,2nA(1):T A(2):F B(1):F B(2):T现在学习的是第53页，共100页54证明式3 x(A(x)B(x)xA(x)xB(x)证明：假设前件x(A(x)B(x)为真，则论域中至少有一个个体a，使得 A(a)B(a)为真，即A(a)和B(a)都为真，所以有xA(x)以及xB(x)为真
29、，得xA(x)xB(x)为真 所以 x(A(x)B(x)xA(x)xB(x)现在学习的是第54页，共100页55证明公式4 xA(x)xB(x)x(A(x)B(x)证明：由3得 x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)(xA(x)xB(x)即xA(x)xB(x)x(A(x)B(x)公式4得证。特别要注意蕴含式的方向，不要搞错现在学习的是第55页，共100页561.xyA(x,y)yxA(x,y)2.xyA(x,y)yxA(x,y)3.yxA(x,y)xyA(x,y)4.xyA(x,y)xyA(x,y)5.yxA(x,y)xyA(x,y
30、)6.xyA(x,y)yxA(x,y)7.yxA(x,y)xyA(x,y)8.xyA(x,y)yxA(x,y)多个量词的量化次序 现在学习的是第56页，共100页57n置换定理设A(x1,x2,xn)B(x1,x2,xn),而A是公式C中的子公式,将B替换C中之A不必每一处得D,则CD。n对偶原理在公式A B或A B中,A,B仅含运算符,和,将上式中的全称量词与存在量词互换,与互换,T和F互换,则 A*B*,B*A*现在学习的是第57页，共100页583.7 谓词演算的推理理论n谓词演算中推理的形式结构推理的形式结构仍为H1H2Hn C 若H1H2Hn C是永真式，则称前提H1，H2，Hn逻辑
31、的推出结论C，其中H1，H2，Hn和C都是谓词公式n谓词演算中的推理规则命题演算中的推理规则，可在谓词推理理论中应用nP规则、T规则、CP规则n与量词有关的规则现在学习的是第58页，共100页59全称示例规则 US(Universal Specialization)n又称全称指定规则n作用：去掉全称量词n两种形式：xA(x)A(y)xA(x)A(c)n使用此规则时要注意：（1）y为任意不在A(x)中约束出现的个体变元；（2）c为任意的个体常元n例：设A(x,y):xy 考查xyA(x,y)可得到结论yA(z,y)但不能得出结论yA(y,y)现在学习的是第59页，共100页60存在示例规则ES(
32、Existential Specification)n又称存在指定规则n作用：去掉存在量词n形式：xA(x)A(c)n使用此规则时要注意：（1）c是使A为真的特定个体常元；（2）c不在A(x)中出现 （3）如果A(x)中有其他自由变元出现，且x是随其他自由变元变化的，那么不能使用此规则n例：设A(x,y)：xy，考查如下推理过程是否正确xyA(x,y)yA(z,y)A(z,c)现在学习的是第60页，共100页61存在推广规则EG(Existential Generalization)n作用：添加存在量词n形式：A(c)xA(x)n使用此规则时注意：(1)c是个体域中某个确定的个体(2)代替c的
33、x不能已在A(c)中出现n例：设A(x,y)：xy，对xyA(x,y)考查如下推理过程A(x,c)xA(x,x)错误现在学习的是第61页，共100页62全称推广规则UG(Universal Generalization)n作用：添加全称量词n形式：A(y)xA(x)n使用此规则时注意：(1)y在A(y)中自由出现，且y取任何值时A均为真(2)x不在A(y)中约束出现n例：设A(x,y)：xy，考查如下推理过程 xA(x,y)x xA(x,x)错误现在学习的是第62页，共100页63量词四规则的使用限制条件n非常重要ES,US,EG,UG四条规则都只有在量词的作用四条规则都只有在量词的作用域是域
34、是整个公式整个公式的情况下才能使用的情况下才能使用例：考察如下推理过程xP(x)yQ(y)xP(x)Q(c)ES或 P(z)yQ(y)US 错误错误！现在学习的是第63页，共100页64推理举例推理举例1.证明苏格拉底的三段论。令 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)US M(a)P D(a)T I 现在学习的是第64页，共100页652.所有自然数都是整数。有些数是自然数。因此有些数是整数。A(x)：x是自然数，B(x)：x是整数。x(A(x)B(x)，xA(x)xB(x)x(A(x)B
35、(x)P xA(x)P A(c)B(c)US A(c)ES B(c)T I xB(x)EG 一般先做存一般先做存在指定再做在指定再做全称指定全称指定现在学习的是第65页，共100页66 x(A(x)B(x)P xA(x)P A(c)ES A(c)B(c)US B(c)T I xB(x)EG现在学习的是第66页，共100页673.不认识错误的人，也不能改正错误。有些诚实的人改正了错误。所以有些诚实的人是认识了错误的人。设A(x):x是认识错误的人。B(x):x改正了错误。C(x):x是诚实的人。符号化为：x(A(x)B(x)，x(C(x)B(x),x(C(x)A(x)现在学习的是第67页，共10
36、0页68x(A(x)B(x),x(C(x)B(x)x(C(x)A(x)x(C(x)B(x)P C(c)B(c)ES C(c)T I B(c)T I x(A(x)B(x)P A(c)B(c)US A(c)T I A(c)T E C(c)A(c)T I x(C(x)A(x)EG 现在学习的是第68页，共100页69观察以下推理过程，指出问题1：(1)xP(x)xQ(x)P (2)xP(x)T(1)I (3)xQ(x)T(1)I (4)P(c)ES(2)(5)Q(c)ES(3)(6)P(c)Q(c)T(4)(5)I (7)x(P(x)Q(x)EG(6)满足P的特定个体c能满足Q？事实上xP(x)xQ
37、(x)x(P(x)Q(x)不成立不成立 现在学习的是第69页，共100页70观察以下推理过程，指出问题2：设D(x,y)表示“x可被y 整除”,个体域 为 5,7,10,11。因为D(5，5)和D(10,5)为真，所以xD(x,5)为真.因为D(7，5)和D(11,5)为假，所以xD(x,5)为假.有以下推理过程(1)xD(x,5)P (2)D(z,5)T(1);ES (3)xD(x,5)T(2);UG 因此，xD(x,5)xD(x,5)现在学习的是第70页，共100页714.一些病人喜欢所有医生。任何病人都不喜欢庸医。所以没有医生是庸医。设:P(x):x是病人,D(x):x是医生,Q(x):
38、x是庸医,L(x,y):x喜欢y.符号化为：x(P(x)y(D(y)L(x,y)，x(P(x)y(Q(y)L(x,y)y(D(y)Q(y)现在学习的是第71页，共100页72 x(P(x)x(P(x)y y(D(y)L(x,y)(D(y)L(x,y)，x(P(x)x(P(x)y(y(Q(y)Q(y)L(x,y)L(x,y)y(D(y)Q(y)y(D(y)Q(y)x(P(x)x(P(x)y y(D(y)L(x,y)P(D(y)L(x,y)P P(c)P(c)y y(D(y)L(c,y)ES(D(y)L(c,y)ES P(c)T I P(c)T I y y(D(y)L(c,y)T I(D(y)L(
39、c,y)T I x(P(x)x(P(x)y(y(Q(y)Q(y)L(x,y)PL(x,y)P P(c)P(c)y(y(Q(y)Q(y)L(c,y)US L(c,y)US y(y(Q(y)Q(y)L(c,y)T IL(c,y)T I D(z)L(c,z)US D(z)L(c,z)US Q(z)Q(z)L(c,z)US L(c,z)US L(c,z)L(c,z)Q(z)T EQ(z)T E D(z)D(z)Q(z)T IQ(z)T I D(z)D(z)Q(z)T EQ(z)T E (D(z)Q(z)T ED(z)Q(z)T E y y(D(y)Q(y)UG D(y)Q(y)UG y y(D(y)Q
40、(y)T ED(y)Q(y)T E现在学习的是第72页，共100页73练习练习x(A(x)B(x),x(B(x)C(x),xC(x)xA(x)(1)x(A(x)B(x)P(2)A(c)B(c)ES(1)(3)x(B(x)C(x)P(4)B(c)C(c)US(3)(5)xC(x)P(6)C(c)US(5)(7)B(c)T(4)(6)I(8)A(c)T(2)(7)I(9)xA(x)EG(8)现在学习的是第73页，共100页745.x(P(x)Q(x)xP(x)xQ(x)xP(x)P(附加前提)x(P(x)Q(x)P P(c)Q(c)ES P(c)US Q(c)T I xQ(x)EG xP(x)xQ
41、(x)CP现在学习的是第74页，共100页75用反证法证明5：x(P(x)Q(x)xP(x)xQ(x)(xP(x)xQ(x)P(假设前提)(xP(x)xQ(x)T E xP(x)xQ(x)T E xP(x)T I xQ(x)T I x(P(x)Q(x)P P(c)Q(c)ES P(c)US Q(c)T I xQ(x)EG xQ(x)xQ(x)T I现在学习的是第75页，共100页76练习分别用反证法和附加前提法证明：x(A(x)B(x)xA(x)xB(x)n反证法：(1)(xA(x)xB(x)P(假设前提)(2)xA(x)xB(x)T E(3)xA(x)T I(4)xB(x)T I(5)xA(
42、x)T(3)E(6)xB(x)T(4)E(7)A(c)ES(5)(8)B(c)US(6)(9)x(A(x)B(x)P(10)A(c)B(c)US(9)(11)B(c)T(7)(10)I(12)B(c)B(c)T(8)(11)I现在学习的是第76页，共100页77n附加前提法：(1)xA(x)P(附加)(2)x(A(x)B(x)P(3)xA(x)T(1)E(4)A(c)ES(3)(5)A(c)B(c)US(2)(6)B(c)T(4)(5)I(7)xB(x)EG(6)(8)xA(x)xB(x)CP(9)xA(x)xB(x)T(8)E现在学习的是第77页，共100页78用推理证明公式：yxA(x,y
43、)xyA(x,y)y)yxA(x,y)P xA(x,c)ES A(z,c)US yA(a,y)y)EG xyA(x,y)UG 现在学习的是第78页，共100页79推理注意事项：推理注意事项：n注意使用ES、US、EG、UG的限制条件n对于同一个个体变元，既有带也有带的前提，去量词时，应先去后去，这样才可以特指同一个个体 cn添加和删去量词时，该量词必须是公式的最左边的量词，且此量词的前边无任何符号，它的辖域作用到公式末尾(1)xP(x)yQ(y)P(2)xP(x)Q(b)ES(3)P(a)Q(b)US(2)错误的作法错误的作法(1)xP(x)yQ(y)P(2)xP(x)yQ(y)T(1)E(3
44、)xP(x)yQ(y)T(2)E(4)xy(P(x)Q(y)T(3)E(5)y(P(a)Q(y)ES(4)(6)P(a)Q(b)ES(4)(7)P(a)Q(b)T(5)E正确的作法正确的作法现在学习的是第79页，共100页80 xP(x)PP(c)US错误的作法错误的作法(1)xP(x)P(2)xP(x)T(1)E(3)P(c)ES(2)正确的作法正确的作法xyP(x,y)PxP(x,c)ES错误的作法错误的作法(1)xyP(x,y)P(2)yP(a,y)US(1)正确的作法正确的作法现在学习的是第80页，共100页813.8 自动定理证明自动定理证明*n n数理逻辑为自动推理证明奠定了基础数
45、理逻辑为自动推理证明奠定了基础n数理逻辑的创始人亚里士多德三段论大前提、小前提和 结论三个部分的论证 亚里士多德例：凡人都会死（大前提）苏格拉底是人（小前提）所以：苏格拉底会死（结论）现在学习的是第81页，共100页82自动证明的提出笛卡尔莱布尼茨n笛卡尔、莱布尼茨（17世纪）萌发了用机械系统实现定理证明的想法把一类数学问题当作一个整体，建立统一的证明过程，按照规定的程序步骤机械地进行下去，在有限步骤之后判断出定理的正确性 现在学习的是第82页，共100页83自动证明的发展n由于传统的兴趣和应用的价值，初等几何问题的自动求解成为数学机械化的研究焦点。希尔伯特n希尔伯特20世纪初，在他的名著几何
46、基础中给出了一条可以对一类几何命题进行判定的定理。希尔伯特对命题的要求太高，当时仅能解决很少的一类几何定理的机器证明，却是历史上第一个关于某类几何命题的机械化检验方法的定理现在学习的是第83页，共100页84自动证明的发展塔斯基n塔斯基（波兰）1950年，证明了：“一切初等几何和初等代数范围的命题都可以用机械方法判定”为几何定理的机器证明开拓了一条利用代数方法的途径方法太复杂，即使用高速计算机也证明不了稍难的几何定理现在学习的是第84页，共100页85自动证明的发展艾伦.纽厄尔n纽厄尔,西蒙和肖1956年,发表了论文逻辑理论机(LTM)认为LTM不仅是计算机智力的有力证明，也是人类认知本质的证
47、明1957年开发了最早的AI程序设计语言IPL语言1960年，成功地合作开发了“通用问题求解系统”GPS(General Problem Solver)赫伯特.西蒙现在学习的是第85页，共100页86自动证明的发展王浩n美籍华裔王浩第一次明确提出“走向数学的机械化走向数学的机械化”1959年，采用“王浩算法”用计算机证明了罗素、怀海德的巨著数学原理中的几百条有关命题逻辑的定理，仅用了 9 分钟宣告了用计算机进行定理证明的可能性在1984年首届自动定理证明大会上获最高奖“里程碑”奖。现在学习的是第86页，共100页87自动证明的发展n1977年，美国年轻的数学家阿佩尔等在高速电子计算机上耗费 1
48、200 小时的计算时间，证明了著名的“四色定理”，人类百年悬而未决的疑问最终被圆满解决了。这一成就轰动一时，成为机器定理证明的一个典范。现在学习的是第87页，共100页88属于中国的自动证明方法吴方法n吴文俊1977年，发表论文初等几何判定问题与机械化证明1984 年，学术专著几何定理机器证明的基本原理1985 年，论文关于代数方程组的零点发表吴文俊消元法吴文俊消元法 利用中国古典数学的成就，提出具有中国特色的自动证明方法 2001年荣获首届国家科学技术最高奖吴文俊现在学习的是第88页，共100页89推理是如何进行的？n推理过程多种多样n例1：如果今天不下雨，我就去你家今天没有下雨n例2：小王
49、说他下午或者去图书馆或者在家休息小王没去图书馆n计算机如何选择？现在学习的是第89页，共100页90消解原理（归结原理）鲁滨逊n美国数学家鲁滨逊提出消解原理（1965年）基本的出发点：要证明一个命题为真都可以通过证明其否命题为假来得到将多样的推理规则简化为一个消解消解（归结）现在学习的是第90页，共100页91什么叫消解P QP RQ R消解式消解式亲本子句亲本子句消解式是亲本子句的消解式是亲本子句的逻辑结论逻辑结论n消解只能在仅含否定和析取联接词的公式(子句)间进行n必须先把公式化成规范的形式范式析取联接词，类似析取联接词，类似“或或”现在学习的是第91页，共100页92消解原理n定义定义3
50、.8.1 原子公式及其否定统称为文字，任何文字的析取式称为子句。例例 RS，P(x)Q(x)，A(x,f(x)Q(x,g(x)n定义定义3.8.2 不包含任何文字的子句称为空子句。n由于空子句不含有文字，它不能被任何解释满足，所以空子句是永假的空子句是永假的，不可满足的。n由子句构成的集合称为子句集。在谓词逻辑中，任何一个谓词公式都可以通过应用等价关系及推理规则化成相应的子句集(主合取范式)。现在学习的是第92页，共100页93谓词演算公式化为子句式步骤：1.消去蕴涵符号 用AB代换AB 2.把非号移入内层 Px)(=x)P(Px)(=x)P(QP Q)(PQP Q)(P=现在学习的是第93页