离散数学-一阶谓词逻辑

1、1离散数学离散数学课程学时：课程学时：4848讲讲 授：杨绍禹授：杨绍禹一阶逻辑n例：苏格拉底论断q前提n“所有的人都是要死的”n“苏格拉底是人”q结论n“所以苏格拉底是要死的”n命题逻辑限定原子命题是不能细分的整体q命题逻辑的局限性PQRPQR不是命题演算不是命题演算的有效推理的有效推理问题的提出：( (为什么要对原子命题进一步细分为什么要对原子命题进一步细分? ?) )？n例q1：小张是大学生q2：小李是大学生qQ1：2大于3qQ2：6大于4n不同原子命题之间是有内在联系的，但命题逻辑无法研究这种内在联系n解决问题的方法q分析原子命题，分离其主语和谓语q考虑一般和个别，全称和存在刻划个体的

2、性质刻划两个个体的关系原子命题不能细分吗？(能否能否对原子命题进一步细分对原子命题进一步细分? ?) )谓词和量词n4.1 谓词谓词q谓词的概念和表示(如何如何对原子命题进一步细分对原子命题进一步细分? ?) )n在原子命题中，用来刻划一个个体的性质或几个个体之间关系的成分称为谓词谓词。n刻划一个个体性质的词称为一元谓词一元谓词；刻划n个个体之间关系的词称为n元谓词。元谓词。谓词常用大写英文字母表示。n谓词与个体词一起才能表示命题。用A(a)表示“a具有性质A”(或“a属于A类”)，用B(a1,a2,an)表示“a1,a2,an关系满足B”。q个体n能够独立存在的事物，思维的对象n通常用小写英

3、文字母a、b、c、.表示个体常量个体常量n用小写英文字母x、y、z.表示任何个体，则称这些字母为个体个体变元变元三个要件以命题逻辑为基础谓词命名式(谓词填式)(a) 5是质数 (b) 张明生于北京(c) 7=32P(x)：x是质数G(x, y)： x生于y ，a：张明，b：北京H(x, y, z) ：x=yzP(5)G(a,b)H(7,3,2)谓词 个体词谓词命名式(谓词填式)N元谓词填式中变元谓词填式中变元的次序很重要元的次序很重要例例思考：xyz该怎么表示？练习练习1.小张不是工人2.张三和李四是表兄弟3.小莉是非常聪明和美丽的4.实数x大于实数y5.大灰狼偷吃了小羊羔 W(a)W(x):

4、x是工人a: 小张 P(a,b)P(a)Q(a)R(x):x是实数G(x,y): xy G(R(x),R(y)?R(x)R(y)G(x,y)否定命题P(x)Q(y)E(x,y)P1(x)P2(x)P3(x) Q1(y)Q2 (y)E(x,y)问题：R(x,y):x和y是实数？分解到词n谓词常元q一个字母代表一特定谓词, 则称此字母为谓词常元(量)。例如P(x)表示“x是质数”这种模式的判断,P就是谓词常元。n谓词变元q若字母代表任意谓词, 则称此字母为谓词变元n论域q谓词命名式中个体变元的取值范围q个体域与全总域q空集不能作为论域谓词谓词命题函数n谓词命名式不是不是命题q若谓词是常元q个体词是

5、常元q谓词命名式才成为一个命题n命题函数q由一个谓词和若干个个体变元组成的命题形式称为简单命题函数简单命题函数，表示为P(x1,x2,xn)。由一个或若干个简单命题函数以及逻辑联结词组成的命题形式称为复合命题函数复合命题函数qn=0时n命题变元命题变元n例q A(x)：x身体好 B(x)：x学习好 C(x)：x工作好q表示“如果x身体不好，则x的学习与工作都不会好”的复合命题函数qA(x)(B(x)C(x)n命题函数不是命题，没有确定真值，但其中谓词是谓词常量时，可通过个体指派使其成为命题。如：若简单命题函数P(X)表示“x是质数”，则P(1)为F，P(2)为T。n除个体指派外，还常用“量”作

6、出判断，如：“所有的人都是要死的”、“有的数是质数”。这种表述在数理逻辑目标语言中需要引入量词，当然量化与个体指派之间是有联系的，数理逻辑中常用量词有两个全称量词和存在量词。4.2 量词n例q “所有的正整数都是素数” q “有些正整数是素数”n假设q只有两个正整数a和bq个体域为a,bqP(x)：x是素数P(a) P(b)P(a) P(b)全称量词n记作n表示“每个”、“任何一个”、“一切”、“所有的”、“凡是”、“任意的”等nx读作“任意x”， “所有x”， “对一切x ”n量词后边的个体变元，指明对哪个个体变元量化，称为量词后的指导变元指导变元n例q所有人都是要死的qD(x)：x是要死的

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

8、组成的集合1)x D(x)2)x G(x)n全总个体域q引入特性谓词qM(x)：x是人1)x(M(x) D(x)2)x (M(x)G(x)特性谓词添加规则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) 4.3 量化断言和命题的关系n假设论域有限,不妨设论域D=1,2,3q

9、xP(x)？nxP(x) P(1) P(2) P(3)qxP(x)？nxP(x) P(1) P(2) P(3)n若论域无限可数，概念可以推广n两个量词共轭qxP(x) xP(x)qxP(x) xP(x)xA(x) xA(x)a1a2anx取遍论域中的所有值T关于x的命题函数A(x)取值皆为T全称命题xA(x)的真值为TTTTxA(x) xA(x)a1a2anFFFF关于x的命题函数A(x)取值皆为F存在命题xA(x)的真值为F量化断言和个体指派的关系x取遍论域中的所有值总之：总之： 1.1.全称命题全称命题 xAxA(x)(x)为真，当且仅当为真，当且仅当 a aDD，A A(a)(a)皆为皆

10、为真真 2.2.全称命题全称命题 xAxA(x)(x)为假，当且仅当为假，当且仅当 a aDD，A A(a)(a)为假。为假。 3.3.存在命题存在命题 xAxA(x)(x)为真，当且仅当为真，当且仅当 a aDD，A A(a)(a)为真。为真。 4.4.存在命题存在命题 xAxA(x)(x)为假，当且仅当为假，当且仅当 a aDD，A A(a)(a)皆为假。皆为假。4.4 谓词公式n个体函数（函词）q例n小王比他的父亲高 H(x，y)：x比y高a：小王b：小王的父亲H(a，b)无法显示个体之间的依赖关系q定义函数nf(x)=x的父亲nH(a， f(a)n函词与谓词的区别q函词中的个体变元用个

11、体代入后的结果依然是个体nf(a)=小王的父亲q谓词中的个体变元用确定的个体带入后就变成了命题nM(x)：x是人nM(a)：小王是人q函词是论域到论域的映射nf : DDq谓词是从论域到T,F的映射nM : D T,F项和原子公式n项(item)q表示个体q定义(1)个体常量是项(2)个体变元是项(3)如果f是一个n(n1)元函词，其t1, t2, tn都是项，则f(t1, t2, tn)是项p例na, b, cnx, y, znf (x), g (a, f (y) n原子公式(atom)q定义n若P是一个n元谓词，且t1,t2,tn是项，则P(t1,t2,tn)是 原子公式q命题词也是原子(

12、n=0)q例nP, Q (x), A (x, f (x), B (x, y, a)谓词演算的合式公式(Wff)n也叫谓词公式，简称公式n定义(1)原子公式是合式公式(2)如果A、B是合式公式，则(A)、(AB)、(AB)、(AB)、(AB)都是合式公式(3)如果A是合式公式，x是个体变元，则x和x也是合式公式(4)有限次地使用规则(1)至(3)求得的公式是合式公式（谓词公式）n括号省略规则n例qP，(Q(x)P)，x(A(x)B(x)，xC(x)， xZ(y)命题符号化n谓词逻辑中比较复杂n命题的符号表达式与论域有关系q例：每个自然数都是整数q论域D=NnI(x)：x是整数nx I (x)q论

13、域为全总个体域n特性谓词N(x)：x是自然数nx(N(x)I(x)例：将下列命题符号化(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) (3)某些人对食物过敏F(x, y)：x对y过敏，M(x)：x是人， G(x)：x是食物 x (M(x)y(G(y)F(x,y)(4)每个人都有些缺点 H(x, y)：x有y，M(x)：x是人， S(x)：x是缺点 x(M(x) y(S(y)H(x,y)(5)尽管有人聪明, 但未必人人聪明 M

14、(x)：x是人， S(x)：x聪明 x(M(x)S(x)x(M(x)S(x)(6)所有老虎都能吃人(7)不管白猫黑猫，凡能逮住耗子的就是好猫(8)无论是步行的、骑马的、乘车的，凡口渴的皆要喝水练习：将下列命题符号化(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(

15、x)(10)有些女同志既是教练员又是国家选手；(11)所有运动员都钦佩某些教练员；(A(x, y)(12)有些大学生不钦佩运动员。练习参考答案(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)(6)x(S(x)L(x)C(x) (7)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)(1)所有教练员都是运动员；(J(x)，L(x)(

16、2)某些运动员是大学生；(S(x)(3)某些教练员是年老的，但是健壮的； (O(x)，V(x)(4)金教练虽不年老，但不健壮；(j)(5)不是所有运动员都是教练员；(6)某些大学生运动员是国家选手；(C(x)(7)没有一个国家选手不是健壮的；(8)所有老的国家选手都是运动员；(9)没有一位女同志既是国家选手又是家庭妇女 (W(x)，H(x)(10)有些女同志既是教练员又是国家选手；(11)所有运动员都钦佩某些教练员；(A(x, y)(12)有些大学生不钦佩运动员。几个特别的例子(1) 如果明天下雨下雨，则某些人将被淋湿 不是个体不是个体定义命题词P：明天下雨， M(x)：x是人，W(x)：x将

17、被淋湿P x(M(x) W(x)(2) 有且仅有有且仅有一个偶素数A(x)：x是偶素数 x(A(x) y(A(y)x=y)或者 x(A(x)y(xyA(y)(3) 顶多只有一台顶多只有一台机器是好的 A(x)：x是好机器用符号 !xA(x) 表示有且仅有一个个体满足Axy(A(x)A(y)x=y)用符号 !xA(x) 表示顶多有一个个体满足A思考：用E(x)表示“x是偶数”， P(x)表示“x是素数”，公式会是怎么样？ (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(

18、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)4.5 自由变元与约束变元n量词的作用域作用域(辖域辖域)q定义定义：在谓词公式中，量词的作用范围称之为量词的作用域，也叫量词的辖域。q例nxA(x)qx的辖域为A(x)nx(P(x)Q(x)yR(x,y)qx的辖域是(P(x)Q(x)yR(x,y)qy的辖域为R(x,y)nxyz(A(x,y)B(x,

19、y,z)C(t) x x的辖域的辖域 z z的辖域的辖域 y y的辖域的辖域自由变元自由变元一般地，n如果量词后边只是一个原子谓词公式时，该量词的辖域就是此原子谓词公式。n如果量词后边是括号，则此括号所表示的区域就是该量词的辖域。n如果多个量词紧挨着出现，则后边的量词及其辖域就是前边量词的辖域。n约束变元q如果个体变元x在x或者x的辖域内，则称x在此辖域内约束出现，并称x在此辖域内是约束变元n自由变元q如果个体变元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是

20、自由变元例：指出下列各公式中的量词辖域及自由变元和约束变元nxy(P(x)Q(y)zR(z)qx的辖域y(P(x)Q(y)qy的辖域P(x)Q(y)qz的辖域R(z)nx(P(x,y)yQ(x,y,z)S(x,z)qx的辖域P(x,y)yQ(x,y,z)其中x是约束变元y是自由变元qy的辖域Q(x,y,z)其中y是约束变元x, z是自由变元qS(x，z)中x，z是自由变元对约束变元和自由变元的几点说明n约束变元用什么符号表示无关紧要qxA(x)与yA(y)是一样的 n一个谓词公式如果无自由变元，它就表示一个命题q例：A(x)表示x是个大学生qxA(x)或者xA(x)是命题nP(x,y,z)表示

21、x+yzq假设论域是整数集，xyP(x,y,z)表示？n“任意给定的整数x，都可以找到整数y，使得x+yz” 。q令z=1，则xyP(x,y,1)表示？n“任意给定的整数x，都可以找到整数y，使得x+y1”,qxyP(x,y,1)表示？例36封闭的公式定义定义4.6 若公式若公式A中不含自由出现的个体变项，则称中不含自由出现的个体变项，则称A为为封闭封闭的公式的公式，简称，简称闭式闭式.例如，例如， x y(F(x) G(y)H(x,y) 为闭式，为闭式，而而 x(F(x) G(x,y) 不是闭式不是闭式 37公式的解释FafF定义定义4.7 设设L 是是L生成的一阶语言生成的一阶语言, L

22、的的解释解释I由由4部分组成：部分组成： (a) 非空个体域非空个体域 DI . (b) 对每一个个体常项符号对每一个个体常项符号a L, 有一个有一个 DI, 称称 为为a在在I 中的解释中的解释. (c) 对每一个对每一个n元函数符号元函数符号f L, 有一个有一个DI上的上的n元函数元函数 , 称称 为为f在在I中的解释中的解释. (d) 对每一个对每一个n元谓词符号元谓词符号F L, 有一个有一个DI上的上的n元谓词常项元谓词常项 , 称称 为为F在在I中的解释中的解释.aInIDDf:afF 设公式设公式A, 取个体域取个体域DI , 把把A中的个体常项符号中的个体常项符号a、函数符

23、、函数符号号f、谓词符号、谓词符号F分别替换成它们在分别替换成它们在I中的解释中的解释 、 、 , 称称所得到的公式所得到的公式A 为为A在在I下的下的解释解释, 或或A在在I下下被解释成被解释成A .实例yxyxF :),(0 ayxyxgyxyxf ),(,),(例例6 给定解释给定解释 I 如下：如下： (a) 个体域个体域 D=R (b) (c) (d) 写出下列公式在写出下列公式在I下的解释下的解释, 并指出它的真值并指出它的真值. (1) xF(f(x,a),g(x,a) x(x+0=x 0) 真真(2) x y(F(f(x,y),g(x,y)F(x,y) x y(x+y=x yx

24、=y) 假假(3) xF(g(x,y),a) x(x y=0) 真值不定真值不定, 不是命题不是命题39公式的类型n定理4.1 闭式在任何解释下都是命题注意: 不是闭式的公式在解释下可能是命题, 也可能不是命题. n定义4.8 若公式A在任何解释下均为真, 则称A为永真式(逻辑有效式). 若A在任何解释下均为假, 则称A为矛盾式(永假式). 若至少有一个解释使A为真, 则称A为可满足式.n几点说明： 永真式为可满足式，但反之不真 判断公式是否是可满足的(永真式, 矛盾式)是不可判定的40代换实例n定义4.9 设A0是含命题变项 p1, p2, , pn的命题公式，A1, A2, , An是n个

25、谓词公式，用Ai (1in) 处处代替A0中的pi，所得公式A称为A0的代换实例.n例如， F(x)G(x), xF(x)yG(y)等都是pq的代换实例.n定理4.2 重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式. 41实例n例7 判断下列公式中，哪些是永真式，哪些是矛盾式？ (1) xF(x)(xyG(x,y)xF(x)重言式重言式 p(qp) 的代换实例，故为永真式的代换实例，故为永真式. (2) ( xF(x)yG(y)yG(y)矛盾式矛盾式 (pq) q 的代换实例，故为永假式的代换实例，故为永假式. (3) x(F(x)G(x)解释解释I1: 个体域个体域N, F(x):x

26、5, G(x): x4, 公式为真公式为真 解释解释I2: 个体域个体域N, F(x):x5, G(x):xy), 真真; 而而B被解释为被解释为 y(yy), 假假 原因原因: 在在A中中x自由出现自由出现在在 y的辖域的辖域F(x,y)内内反例反例2. 前提前提: P(x)Q(x), P(x) 结论结论: xQ(x) 取解释取解释I: 个体域为个体域为Z, 在在I下前提为下前提为真真, 结论为假结论为假, 从而推理不正确从而推理不正确整除整除被被是偶数是偶数2:)(,:)(xxQxxP69反例2(续)n“证明”: P(x)Q(x) 前提引入 P(x) 前提引入 Q(x) 假言推理 xQ(x

27、) +n错误原因: 在使用+规则, 而x在前提的公式中自由出现.70第五章 一阶逻辑等值演算与推理n主要内容q一阶逻辑等值式 基本等值式，置换规则、换名规则、代替规则q前束范式q推理的形式结构q自然推理系统NL 推理定律、推理规则71基本要求n深刻理解并牢记一阶逻辑中的重要等值式, 并能准确而熟练地应用它们n熟练正确地使用置换规则、换名规则、代替规则n熟练地求出给定公式的前束范式n深刻理解自然推理系统NL 的定义，牢记NL 中的各条推理规则，特别是注意使用、+、+、 4条推理规则的条件n能正确地给出有效推理的证明 72练习12 a1. 给定解释给定解释I如下如下:(1) 个体域个体域D=2,3

28、(2) (3)(4)求下述在求下述在I下的解释及其真值下的解释及其真值: x y(F(f(x) G(y,f(a)2)3(, 3)2(:)( ffxf0)3 , 3(, 1)2 , 3()3 , 2()2 , 2(:),(1)3(, 0)2(:)( GGGGyxGFFxF解解 xF(f(x)yG(y,f(a) F(f(2) F(f(3) (G(2,f(2) G(3,f(2) 1 0 (1 0)073练习2n2.求下述公式的前束范式: xF(x)y(G(x,y)H(x,y)解解 使用换名规则使用换名规则, xF(x)y(G(x,y) H(x,y) zF(z)y(G(x,y) H(x,y) 换名规则换名规则 z(F(z)y(G(x,y) H(x,y) 辖域扩张辖域扩张 z y(F(z)(G(x,y) H(x,y) 辖域扩张辖域扩张 使用代替规则使用代替规则 xF(x)y(G(x,y) H(x,y) xF(x)y(G(z,y) H(z,y) 代替规则代替规则 x(F(x)y(G(z,y) H(z,y) 辖域扩张辖域扩张 x y(F(x)(G(z,y) H(z,y) 辖域扩张辖域扩张74练习3n3.构造下面推理的证明:(1) 前提：x(F(x)G