第一章 数理逻辑谓词逻辑PPT讲稿.ppt

《第一章 数理逻辑谓词逻辑PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第一章 数理逻辑谓词逻辑PPT讲稿.ppt（100页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第一章 数理逻辑谓词逻辑第1页，共100页，编辑于2022年，星期一2谓词逻辑Predicate Logic第2页，共100页，编辑于2022年，星期一3问题的提出：(命题逻辑的局限性)n例：苏格拉底论断前提n“所有的人总是要死的”n“苏格拉底是人”结论n“所以苏格拉底是要死的”n命题逻辑中原子命题不可再分PQRPQR不是有效推理不是有效推理第3页，共100页，编辑于2022年，星期一4n例1：小张是大学生2：小李是大学生Q1：2大于3Q2：6大于4n命题逻辑无法反映不同原子命题间的内在共性n解决问题的方法分析原子命题，分离其主语和谓语考虑一般和个别，全称和存在第4页，共100页，编辑于202

2、2年，星期一53.1谓词的概念与表示谓词的概念与表示n定义定义3.1.1在原子命题中，用来刻划一个个体的性质或个体之间关系的成分称为谓词谓词，刻划一个个体性质的词称为一元谓词一元谓词；刻划n个个体之间关系的词称为n元谓词元谓词n常用大写英文字母表示个体n能够独立存在的事物n通常用小写英文字母a、b、c、.表示个体常量n用小写英文字母x、y、z.表示任何个体，则称这些字母为个体变元个体变元第5页，共100页，编辑于2022年，星期一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

3、)H(7,3,2)谓词 个体词谓词命名式(谓词填式)变元的次序很重要变元的次序很重要第6页，共100页，编辑于2022年，星期一7n谓词常量（谓词常元）一个字母代表一特定谓词,例如F代表“是质数”,则称此字母为谓词常量n谓词变元若字母代表任意谓词,则称此字母为谓词变元n论域个体域谓词命名式中个体变元的取值范围空集不能作为论域第7页，共100页，编辑于2022年，星期一83.2 命题函数与量词n谓词命名式不是不是命题若谓词是常元个体词是常元谓词命名式才成为一个命题n定义定义3.2.1由一个谓词常量，一些个体变元组成的表达式称为简单命题简单命题函数函数，表示为P(x1,x2,xn)。由一个或若干个

4、简单命题函数以及逻辑联结词组成的命题形式称为复合命题函数复合命题函数，简单命题函数和复合命题函数统称为命题函数命题函数 n=0时n命题变元命题变元第8页，共100页，编辑于2022年，星期一9n例 A(x)：x身体好 B(x)：x学习好 C(x)：x工作好如果x身体不好，则x的学习与工作都不会好 复合命题函数A(x)(B(x)C(x)第9页，共100页，编辑于2022年，星期一10量词n例“所有的正整数都是素数”“有些正整数是素数”n假设只有两个正整数a和b个体域为a,bP(x)：x是素数P(a)P(b)P(a)P(b)第10页，共100页，编辑于2022年，星期一11量词n定义定义3.2.2

5、 设为论域上的一个一元谓词，则 命题x(x)的真值为，iff 对上的每一个个体a，命题(a)的真值为；命题x(x)的真值为，iff 在上存在个体a，使得命题(a)的真值为。第11页，共100页，编辑于2022年，星期一12全称量词n记作n表示“每个”、“任何一个”、“一切”、“所有的”、“凡是”、“任意的”等nx读作“任意x”，“所有x”，“对一切x”n量词后边的个体变元，指明对哪个个体变元量化，称为量词后的指导变元指导变元n例所有人都是要死的D(x)：x是要死的个体域：所有人构成的集合x D(x)第12页，共100页，编辑于2022年，星期一13存在量词n记作 n表示“有些”、“一些”、“某

6、些”、“至少一个”等n x读作“存在x”，“对某些x”或“至少有一x”n指导变元指导变元n例有些有理数是整数(x)：x是整数个体域：有理数集合x(x)第13页，共100页，编辑于2022年，星期一14全总个体域（全总域）n含有量词的命题的真值与论域有关n含有量词的命题的表达式的形式与论域有关n全总个体域全总个体域宇宙间所有的个体聚集在一起所构成的集合约定约定n除特殊说明外，均使用全总个体域n对个体变化的真正取值范围，用特性谓词特性谓词加以限制第14页，共100页，编辑于2022年，星期一15例1)所有的人都是要死的2)有的人活百岁以上D(x)：x是要死的G(x)：x活百岁以上n个体域E为全体人

7、组成的集合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页，编辑于2022年，星期一16特性谓词添加规则n对全称量词,特性谓词作为条件式之前件加入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页，编辑于2022年，星期一173.3 谓词演算的合式

8、公式谓词演算的合式公式n个体函数（函词）例n小王比他的父亲高 T(x，y)：x比y高a：小王b：小王的父亲T(a，b)无法显示个体之间的依赖关系定义函词nf(x)=x的父亲nT(a，f(a)第17页，共100页，编辑于2022年，星期一18n函词与谓词的区别函词中的个体变元用个体带入后的结果依然是个体nf(a)=小王的父亲谓词中的个体变元用确定的个体带入后就变成了命题nM(x)：x是人nM(a)：小王是人函词是论域到论域的映射nf:DD谓词是从论域到T,F的映射nM:D T,F第18页，共100页，编辑于2022年，星期一19项和原子公式n定义定义3.3.1 项(item)表示个体定义(1)个

9、体常量是项(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页，编辑于2022年，星期一20n定义定义3.3.2 原子公式(atom)定义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页，编辑于2022年，星期一21谓词演算的合式公式(Wff)n也叫谓词公式，简称公式n定义定义3.3.3(1)原子公式是合式公式(2)如果A、B是合式公式，则A

10、、(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页，编辑于2022年，星期一22命题符号化n谓词逻辑中比较复杂n命题的符号表达式与论域有关系例：每个自然数都是整数论域D=NnI(x)：x是整数nx I(x)论域为全总个体域n特性谓词N(x)：x是自然数nx(N(x)I(x)第22页，共100页，编辑于2022年，星期一23例：将下列命题符号化(1)所有大学生都喜欢一些歌星。S(x)：x是

11、大学生，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)第23页，共100页，编辑于2022年，星期一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)(

12、6)尽管有人聪明,但未必人人聪明 M(x)：x是人，S(x)：x聪明 x(M(x)S(x)x(M(x)S(x)第24页，共100页，编辑于2022年，星期一25练习：将下列命题符号化(1)所有教练员都是运动员；(J(x)，L(x)(2)某些运动员是大学生；(S(x)(3)某些教练员是年老的，但是健壮的；(O(x)，V(x)(4)金教练虽不年老，但不健壮；(j)(5)不是所有运动员都是教练员；(6)某些大学生运动员是国家选手；(C(x)(7)没有一个国家选手不是健壮的；(8)所有老的国家选手都是运动员；(9)没有一位女同志既是国家选手又是家庭妇女；(W(x)，H(x)(10)有些女同志既是教练员

13、又是国家选手；(11)所有运动员都钦佩某些教练员；(A(x,y)(12)有些大学生不钦佩运动员。第25页，共100页，编辑于2022年，星期一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)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,

14、y)第26页，共100页，编辑于2022年，星期一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)顶多只有一台顶多只有一台机器是好的 P(x)：x是好机器用符号 !xP(x)表示有且仅有一个个体满足Pxy(P(x)P(y)x=y)用符号 !xP(x)表示顶多有一个个体满足P第27页，共100页，编辑于2022年，星期一28 (4)如果人都爱美，则漂亮衣服有销路

15、 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)L(x)y(C(y)B(y)S(y)第28页，共100页，编辑于2022年，星期一293.4 变元的约束变元的约束n量词的作用域作用域(辖域辖域)定义定义：在谓词公式中，量词的作用范围称之为量词的作用域，也叫量词的辖域。例

16、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页，编辑于2022年，星期一30一般地，n如果量词后边只是一个原子谓词公式时，该量词的辖域就是此原子谓词公式。n如果量词后边是括号，则此括号所表示的区域就是该量词的辖域。n如果多个量词紧挨着出现，则后边的量词及其辖域就是前边量词的辖域。第30页，共100页，编辑于2022年，星期一31n约束变元如果个体变元x在x或者x的辖域内，则

17、称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页，编辑于2022年，星期一32例：指出下列各公式中的量词辖域及自由变元和约束变元nxy(P(x)Q(y)zR(z)x的辖域y(P(x)Q(y)y的辖域P(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)

18、其中y是约束变元x,z是自由变元S(x，z)中x，z是自由变元第32页，共100页，编辑于2022年，星期一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页，共100页，编辑于2022年，星期一34nP(x,y,z)表示x+yz假设论域是整数集，xyP(x,y,z)表示？n“任意给定的整数x，都可以找到整数y，使得x+

19、yz”。令z=1，则xyP(x,y,1)表示？n“任意给定的整数x，都可以找到整数y，使得x+y1”,。例第34页，共100页，编辑于2022年，星期一35n不同个体以相同的符号出现容易产生混淆n例x(F(x,y)yP(y)Q(z)n约束变元的换名规则：1.对约束变元可以更改名称，改名的范围是：量词后的指导变元以及该量词的辖域内此个体变元出现的各处同时换名。2.改名后用的个体变元名称，不能与该量词的辖域内的其它变元名称相同。约束变元换名第35页，共100页，编辑于2022年，星期一36nx(P(x)Q(x,y)(R(x)A(x)x以两种形式出现对x换名 z(P(z)Q(z,y)(R(x)A(x

20、)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页，编辑于2022年，星期一37自由变元换名n自由变元也可以换名n此换名叫代入n自由变元的代入规则：1.对谓词公式中的自由变元可以作代入。代入时需要对公式中出现该变元的每一处，同时作代入2.代入后的变元名称要与公式中的其它变元名称不同第37页，共100页，编辑于2022年，星期一38例nx(P(x)Q(x,y)(R(x)A(x)用z代替自由变元xx(P(x)Q

21、(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页，编辑于2022年，星期一393.5 谓词公式的解释谓词公式的解释n定义定义3.5.1 对谓词公式的解释包括以下几点：1.指定一个论域D2.对A中出现的每一个n元函数，指定一个D上的 n元个体函数常量3.对A中出现的每一个n元谓词，指定一个D上的n元谓词常量4.对A中出现的每一个个体常量及自由变元，指定D中的一个个体常量5.对A中出现的每一个命题变元P，指派一个真值T或F 由此得到一个命题AI，称AI的真值为合

22、适公式A在解释I 下的真值第39页，共100页，编辑于2022年，星期一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页，编辑于2022年，星期一41xyP(x,y)TTFFTTT212211xyP(x,y)yP(x,y)P(x,y)yx第41页，共100页，编辑于2022年，星期一42yxP(x,y)TFFFFFT212211yx P(x,y)xP(x,y)P(x,y)xy第42页，共100页，编辑于2022年，星期一43例n取解

23、释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页，编辑于2022年，星期一443.6 谓词公式的永真式n定义定义 给定谓词公式A，E是其论域，如果在任何解释下公式A的真值都为真，则称公式A在论域E上是永真式。如果不论对什么论域E，都使得公式A为永真式，则称A为永真式。例：I(x)：x是

24、整数，论域E为自然数集合nI(x)在E上是永真式nI(x)I(x)是与论域无关的永真式n谓词公式的永假式n谓词公式的可满足式第44页，共100页，编辑于2022年，星期一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页，编辑于2022年，星期一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

25、 F TT A(2)B(2)T 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页，编辑于2022年，星期一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页，编辑于2022年

26、，星期一48命题演算的推广 n定理定理3.6.1(代入定理)设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页，编辑于2022年，星期一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

27、)为真。另一方面，若x(x)为真，则中的每一个个体a皆使(a)为真，即(a)为假，所以x(x)为假，即x(x)为真。利用的结论，我们有：x(x)x(x)x(x)x(x)第49页，共100页，编辑于2022年，星期一50例 xyz(x+z=y)xyz(x+z=y)xyz(x+z=y)xy z(x+z=y)xy z(x+zy)第50页，共100页，编辑于2022年，星期一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(

28、A(x)P)8.xA(x)Px(A(x)P)P是不含个体变元x的谓词公式证明式1：(逻辑推证)一方面，当P为F时，xA(x)Px(A(x)P)xA(x)另一方面，当P为T时，xA(x)Px(A(x)P)T量词辖域的扩张和收缩第51页，共100页，编辑于2022年，星期一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

29、(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)量词与和等联词的关系 第52页，共100页，编辑于2022年，星期一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页，编辑于2022年，星期一54证明式3 x(A(x)B(x)xA(x)xB(x)证明：假设前件

30、x(A(x)B(x)为真，则论域中至少有一个个体a，使得 A(a)B(a)为真，即A(a)和B(a)都为真，所以有xA(x)以及xB(x)为真，得xA(x)xB(x)为真 所以 x(A(x)B(x)xA(x)xB(x)第54页，共100页，编辑于2022年，星期一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页，编辑于2022年，星期一561.xy

31、A(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)6.xyA(x,y)yxA(x,y)7.yxA(x,y)xyA(x,y)8.xyA(x,y)yxA(x,y)多个量词的量化次序 第56页，共100页，编辑于2022年，星期一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*

32、A*第57页，共100页，编辑于2022年，星期一583.7 谓词演算的推理理论n谓词演算中推理的形式结构推理的形式结构仍为H1H2Hn C 若H1H2Hn C是永真式，则称前提H1，H2，Hn逻辑的推出结论C，其中H1，H2，Hn和C都是谓词公式n谓词演算中的推理规则命题演算中的推理规则，可在谓词推理理论中应用nP规则、T规则、CP规则n与量词有关的规则第58页，共100页，编辑于2022年，星期一59全称示例规则 US(Universal Specialization)n又称全称指定规则n作用：去掉全称量词n两种形式：xA(x)A(y)xA(x)A(c)n使用此规则时要注意：（1）y为任意

33、不在A(x)中约束出现的个体变元；（2）c为任意的个体常元n例：设A(x,y):xy 考查xyA(x,y)可得到结论yA(z,y)但不能得出结论yA(y,y)第59页，共100页，编辑于2022年，星期一60存在示例规则ES(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

34、,c)第60页，共100页，编辑于2022年，星期一61存在推广规则EG(Existential Generalization)n作用：添加存在量词n形式：A(c)xA(x)n使用此规则时注意：(1)c是个体域中某个确定的个体(2)代替c的x不能已在A(c)中出现n例：设A(x,y)：xy，对xyA(x,y)考查如下推理过程A(x,c)xA(x,x)错误第61页，共100页，编辑于2022年，星期一62全称推广规则UG(Universal Generalization)n作用：添加全称量词n形式：A(y)xA(x)n使用此规则时注意：(1)y在A(y)中自由出现，且y取任何值时A均为真(2)x

35、不在A(y)中约束出现n例：设A(x,y)：xy，考查如下推理过程 xA(x,y)x xA(x,x)错误第62页，共100页，编辑于2022年，星期一63量词四规则的使用限制条件n非常重要ES,US,EG,UG四条规则都只有在量词的作用四条规则都只有在量词的作用域是域是整个公式整个公式的情况下才能使用的情况下才能使用例：考察如下推理过程xP(x)yQ(y)xP(x)Q(c)ES或 P(z)yQ(y)US 错误错误！第63页，共100页，编辑于2022年，星期一64推理举例推理举例1.证明苏格拉底的三段论。令 M(x):x是人。D(x):x是要死的。a:苏格拉底。符号化为：x(M(x)D(x),

36、M(a)D(a)x(M(x)D(x)P M(a)D(a)US M(a)P D(a)T I 第64页，共100页，编辑于2022年，星期一652.所有自然数都是整数。有些数是自然数。因此有些数是整数。A(x)：x是自然数，B(x)：x是整数。x(A(x)B(x)，xA(x)xB(x)x(A(x)B(x)P xA(x)P A(c)B(c)US A(c)ES B(c)T I xB(x)EG 一般先做存一般先做存在指定再做在指定再做全称指定全称指定第65页，共100页，编辑于2022年，星期一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

37、第66页，共100页，编辑于2022年，星期一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页，共100页，编辑于2022年，星期一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)

38、A(x)EG 第68页，共100页，编辑于2022年，星期一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(x)x(P(x)Q(x)不成立不成立 第69页，共100页，编辑于2022年，星期一70观察以下推理过程，指出问题2：设D(x,y)表示“x可被y 整除”,个体域 为 5,7,10,11。因为D(5，5)和D(10,5)为真，所以xD(x,5)为

39、真.因为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页，编辑于2022年，星期一714.一些病人喜欢所有医生。任何病人都不喜欢庸医。所以没有医生是庸医。设:P(x):x是病人,D(x):x是医生,Q(x):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页，编辑于2022年，星期一72 x(P(x)x(P(x)y y

40、(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(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)

41、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(y)T ED(y)Q(y)T E第72页，共100页，编辑于2022年，星期一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)

42、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页，编辑于2022年，星期一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(x)CP第74页，共100页，编辑于2022年，星期一75用反证法证明5：x(P(x)Q(x)xP(x)xQ(x)(xP(x)xQ(x)P(假设前提)(xP(x)xQ(x)T

43、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页，编辑于2022年，星期一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(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)

44、(11)B(c)T(7)(10)I(12)B(c)B(c)T(8)(11)I第76页，共100页，编辑于2022年，星期一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页，编辑于2022年，星期一78用推理证明公式：yxA(x,y)xyA(x,y)y)yxA(x,y)P xA(x,c)ES A(z,c)US yA(a,y)y)EG xyA(x,y)U

45、G 第78页，共100页，编辑于2022年，星期一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)xP(x)yQ(y)T(2)E(4)xy(P(x)Q(y)T(3)E(5)y(P(a)Q(y)ES(4)(

46、6)P(a)Q(b)ES(4)(7)P(a)Q(b)T(5)E正确的作法正确的作法第79页，共100页，编辑于2022年，星期一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页，编辑于2022年，星期一813.8 自动定理证明自动定理证明*n n数理逻辑为自动推理证明奠定了基础数理逻辑为自动推理证明奠定了基础n数理逻辑的创始人亚里士多德三段论大前提、小前提和

47、 结论三个部分的论证 亚里士多德例：凡人都会死（大前提）苏格拉底是人（小前提）所以：苏格拉底会死（结论）第81页，共100页，编辑于2022年，星期一82自动证明的提出笛卡尔莱布尼茨n笛卡尔、莱布尼茨（17世纪）萌发了用机械系统实现定理证明的想法把一类数学问题当作一个整体，建立统一的证明过程，按照规定的程序步骤机械地进行下去，在有限步骤之后判断出定理的正确性 第82页，共100页，编辑于2022年，星期一83自动证明的发展n由于传统的兴趣和应用的价值，初等几何问题的自动求解成为数学机械化的研究焦点。希尔伯特n希尔伯特20世纪初，在他的名著几何基础中给出了一条可以对一类几何命题进行判定的定理。希

48、尔伯特对命题的要求太高，当时仅能解决很少的一类几何定理的机器证明，却是历史上第一个关于某类几何命题的机械化检验方法的定理第83页，共100页，编辑于2022年，星期一84自动证明的发展塔斯基n塔斯基（波兰）1950年，证明了：“一切初等几何和初等代数范围的命题都可以用机械方法判定”为几何定理的机器证明开拓了一条利用代数方法的途径方法太复杂，即使用高速计算机也证明不了稍难的几何定理第84页，共100页，编辑于2022年，星期一85自动证明的发展艾伦.纽厄尔n纽厄尔,西蒙和肖1956年,发表了论文逻辑理论机(LTM)认为LTM不仅是计算机智力的有力证明，也是人类认知本质的证明1957年开发了最早的

49、AI程序设计语言IPL语言1960年，成功地合作开发了“通用问题求解系统”GPS(General Problem Solver)赫伯特.西蒙第85页，共100页，编辑于2022年，星期一86自动证明的发展王浩n美籍华裔王浩第一次明确提出“走向数学的机械化走向数学的机械化”1959年，采用“王浩算法”用计算机证明了罗素、怀海德的巨著数学原理中的几百条有关命题逻辑的定理，仅用了 9 分钟宣告了用计算机进行定理证明的可能性在1984年首届自动定理证明大会上获最高奖“里程碑”奖。第86页，共100页，编辑于2022年，星期一87自动证明的发展n1977年，美国年轻的数学家阿佩尔等在高速电子计算机上耗费

50、 1200 小时的计算时间，证明了著名的“四色定理”，人类百年悬而未决的疑问最终被圆满解决了。这一成就轰动一时，成为机器定理证明的一个典范。第87页，共100页，编辑于2022年，星期一88属于中国的自动证明方法吴方法n吴文俊1977年，发表论文初等几何判定问题与机械化证明1984 年，学术专著几何定理机器证明的基本原理1985 年，论文关于代数方程组的零点发表吴文俊消元法吴文俊消元法 利用中国古典数学的成就，提出具有中国特色的自动证明方法 2001年荣获首届国家科学技术最高奖吴文俊第88页，共100页，编辑于2022年，星期一89推理是如何进行的？n推理过程多种多样n例1：如果今天不下雨，我