第1章数理逻辑-谓词逻辑.ppt

《第1章数理逻辑-谓词逻辑.ppt》由会员分享，可在线阅读，更多相关《第1章数理逻辑-谓词逻辑.ppt（84页珍藏版）》请在三一文库上搜索。

1、第一章 数理逻辑 Mathematics Logic,1.61.8 谓词逻辑 Predicate Logic,问题的提出：(命题逻辑的局限性),例：苏格拉底论断 前提 “所有的人总是要死的” “苏格拉底是人” 结论 “所以苏格拉底是要死的” 命题逻辑中原子命题不可再分,P,Q,R,PQR,不是有效推理,例 1：小张是大学生 2：小李是大学生 Q1 ：2大于3 Q2 ：6大于4 命题逻辑无法反映不同原子命题间的内在共性 解决问题的方法 分析原子命题，分离其主语和谓语 考虑一般和个别，全称和存在,1.6 谓词和量词,1.6.1 谓词 谓词的概念和表示 在原子命题中，用来刻划一个个体的性质或个体之间

2、关系的成分称为谓词，刻划一个个体性质的词称为一元谓词；刻划n个个体之间关系的词称为n元谓词 常用大写英文字母表示 个体 能够独立存在的事物 通常用小写英文字母a、b、c、.表示个体常量 用小写英文字母x、y、z.表示任何个体，则称这些字母为个体变元,例 1 (a) 5 是质数 (b) 张明生于北京 (c) 7=32 F(x)：x是质数 G(x, y)： x生于y ，a：张明，b：北京 H(x, y, z) ：x=yz,F(5),G(a,b),H(7,3,2),变元的次序很重要,谓词常元 一个字母代表一特定谓词, 例如F代表“是质数”, 则称此字母为谓词常元 谓词变元 若字母代表任意谓词, 则称

3、此字母为谓词变元 论域 个体域 谓词命名式中个体变元的取值范围 空集不能作为论域,命题函数,谓词命名式不是命题 若谓词是常元 个体词是常元 谓词命名式才成为一个命题 谓词函数 由一个谓词和若干个个体变元组成的命题形式称为简单命题函数，表示为P(x1,x2,xn)。由一个或若干个简单命题函数以及逻辑联结词组成的命题形式称为复合命题函数 n=0时 命题变元,例 A(x)：x身体好 B(x)：x学习好 C(x)：x工作好 如果x身体不好，则x的学习与工作都不会好复合命题函数 A(x)(B(x)C(x),1.6.2 量词,例 “所有的正整数都是素数” “有些正整数是素数” 假设 只有两个正整数a和b

4、个体域为a,b P(x)：x是素数,P(a) P(b),P(a) P(b),全称量词,记作 表示“每个”、“任何一个”、“一切”、“所有的”、“凡是”、“任意的”等 x读作“任意x”， “所有x”， “对一切x ” 量词后边的个体变元，指明对哪个个体变元量化，称为量词后的指导变元 例 所有人都是要死的 D(x)：x是要死的 个体域：所有人构成的集合 x D(x),存在量词,记作 表示“有些”、“一些”、“某些”、“至少一个”等 x读作“存在x”，“对某些x”或“至少有一x” 指导变元 例 有些有理数是整数 (x)：x是整数 个体域：有理数集合 x(x),全总个体域（全总域）,含有量词的命题的真

5、值与论域有关 含有量词的命题的表达式的形式与论域有关 全总个体域 宇宙间所有的个体聚集在一起所构成的集合 约定 除特殊说明外，均使用全总个体域 对个体变化的真正取值范围，用特性谓词加以限制,例,所有的人都是要死的 有的人活百岁以上 D(x)：x是要死的 G(x) ：x活百岁以上 个体域E为全体人组成的集合 x D(x) x G(x) 全总个体域 引入特性谓词 M(x)：x是人 x(M(x) D(x) x (M(x)G(x),特性谓词添加规则,对全称量词, 特性谓词作为条件式之前件加入 对存在量词, 特性谓词作为合取项而加入 例 (a) 没有不犯错误的人 F(x)：x犯错误 M(x)：x是人 x

6、 (M(x)F(x) (b) 凡是实数, 不是大于零就是等于零或小于零 R(x)：x是实数 L(x, y)：xy E (x, y) ： x = y S(x, y)：x y x(R(x) L(x, 0) E (x, 0) S (x, 0),1.6.3 量化断言和命题的关系,假设论域有限, 不妨设论域D=1, 2, 3 xP(x)？ xP(x) P(1) P(2) P(3) xP(x)？ xP(x) P(1) P(2) P(3) 若论域无限可数，概念可以推广,1.6.4 谓词公式,个体函数（函词） 例 小王比他的父亲高 T(x，y)：x比y高 a：小王 b：小王的父亲 T(a，b) 无法显示个体之

7、间的依赖关系 定义函数 f(x)=x的父亲 T(a， f(a),函词与谓词的区别 函词中的个体变元用个体带入后的结果依然是个体 f(a)=小王的父亲 谓词中的个体变元用确定的个体带入后就变成了命题 M(x)：x是人 M(a)：小王是人 函词是论域到论域的映射 f : DD 谓词是从论域到T,F的映射 M : D T,F,项和原子公式,项(item) 表示个体 定义 个体常量是项 个体变元是项 如果f是一个n(n1)元函词，其t1, t2, tn都是项，则f(t1, t2, tn)是项 例 a, b, c x, y, z f (x), g (a, f (y),原子公式(atom) 定义 若P是一

8、个n元谓词，且t1,t2,tn是项，则P(t1,t2,tn)是原子 命题词也是原子(n=0) 例 P, Q (x), A (x, f (x), B (x, y, a),谓词演算的合式公式(Wff),也叫谓词公式，简称公式 定义 (1)原子公式是合式公式 (2)如果A、B是合式公式，则A、(AB)、(AB)、(AB)、(AB)都是合式公式 (3)如果A是合式公式，x是中的任何个体变元，则x和x也是合式公式 (4)有限次地使用规则(1)至(3)求得的公式是合式公式 例 P，(PQ)，(Q(x)P)，x(A(x)B(x)，xC(x),命题符号化,谓词逻辑中比较复杂 命题的符号表达式与论域有关系 例：

9、每个自然数都是整数 论域D=N I(x)：x是整数 x I (x) 论域为全总个体域 特性谓词N(x)：x是自然数 x(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) 或者x(P(x)G(x) (3)不是所有的自然数都是偶数。 N(x)：x是自然数，E(x)：x是偶数 x(N(x)E(x) 或者x(N(x)E(x),(4)某些人对食物过敏 F(x, y)：x对y过敏，M(x)：x是

10、人， 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),练习：将下列命题符号化,所有教练员都是运动员；(J(x)，L(x) 某些运动员是大学生；(S(x) 某些教练员是年老的，但是健壮的；(O(x)，V(x) 金教练虽不年老，但不健壮；(j) 不是所有运动员都是教练员； 某些大学生运动员是国家选手；(C(x) 没有一个国家选手不是健壮的； 所有老

11、的国家选手都是运动员； 没有一位女同志既是国家选手又是家庭妇女；(W(x)，H(x) 有些女同志既是教练员又是国家选手； 所有运动员都钦佩某些教练员；(A(x, y) 有些大学生不钦佩运动员。,练习参考答案,x(J(x)L(x) x(L(x)S(x) x(J(x)O(x)V(x) J(j)O(j)V(j) x(L(x)J(x) 或者 x(L(x)J(x) x(S(x)L(x)C(x) x(C(x)V(x) 或者 x(C(x)V(x) x(C(x)O(x)L(x) x(W(x)C(x)H(x) x(W(x)J(x)C(x) x(L(x)y(J(y)A(x,y) x(S(x)y(L(y)A(x,y

12、),几个特别的例子,(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) 表示有且仅有一个个体满足P,xy(P(x)P(y)x=y),用符号 !xP(x) 表示顶多有一个个体满足P,(4) 如果人都爱美，则漂亮衣服有销路 M(x)：x是人，L(x)：x爱美， C(x)：x是衣服， B(x)：x是漂亮的，S(x

13、)：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),1.6.5 自由变元与约束变元,量词的作用域(辖域) 定义：在谓词公式中，量词的作用范围称之为量词的作用域，也叫量词的辖域。 例 xA(x) x的辖域为A(x) x(P(x)Q(x)yR(x,y) x的辖域是(P(x)Q(x)yR(x,y) y的辖

14、域为R(x,y) xyz(A(x,y)B(x,y,z)C(t),x的辖域,z的辖域,y的辖域,自由变元,一般地， 如果量词后边只是一个原子谓词公式时，该量词的辖域就是此原子谓词公式。 如果量词后边是括号，则此括号所表示的区域就是该量词的辖域。 如果多个量词紧挨着出现，则后边的量词及其辖域就是前边量词的辖域。,约束变元 如果个体变元x在x或者x的辖域内，则称x在此辖域内约束出现，并称x在此辖域内是约束变元 自由变元 如果个体变元x不在任何量词的辖域内，则称x是自由出现，并称x是自由变元 例 x(F(x,y)yP(y)Q(z) F(x,y)中的x和P(y)中的y是约束变元 而F(x,y)中的y和Q

15、(z)中的z是自由变元,例：指出下列各公式中的量词辖域及自由变元和约束变元,xy(P(x)Q(y)zR(z) x的辖域y(P(x)Q(y) y的辖域P(x)Q(y) z的辖域R(z) x(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是自由变元,对约束变元和自由变元的几点说明,约束变元用什么符号表示无关紧要 xA(x)与yA(y)是一样的 一个谓词公式如果无自由变元，它就表示一个命题 例：A(x)表示x是个大学生 xA(x)或者xA(x)是命

16、题 一个n元谓词P(x1,x2,xn)，若在前边添加k个量词，使其中的 k个个体变元变成约束变元，则变成n-k元谓词函数,P(x,y,z)表示x+yz 假设论域是整数集，xyP(x,y,z)表示？ “任意给定的整数x，都可以找到整数y，使得x+yz” 。 令z=1，则xyP(x,y,1)表示？ “任意给定的整数x，都可以找到整数y，使得x+y1”,。 xyP(x,y,1)表示？,例,不同个体以相同的符号出现容易产生混淆 例 x(F(x,y)yP(y)Q(z) 约束变元的换名规则： 对约束变元可以更改名称，改名的范围是：量词后的指导变元以及该量词的辖域内此个体变元出现的各处同时换名。 改名后用的

17、个体变元名称，不能与该量词的辖域内的其它变元名称相同。,约束变元换名,x(P(x)Q(x,y)(R(x)A(x) x以两种形式出现 对x换名 z(P(z)Q(z,y)(R(x)A(x) x(P(x,y)yQ(x,y,z)S(x,y) 对x和y换名 u(P(u,v)vQ(u,v,z)S(x,y) 错误 u(P(u,y)zQ(u,z,z)S(x,y) 错误 u(P(u,y)vQ(u,v,z)S(x,y) 正确,例,自由变元换名,自由变元也可以换名 此换名叫代入 自由变元的代入规则： 对谓词公式中的自由变元可以作代入。代入时需要对公式中出现该变元的每一处，同时作代入 代入后的变元名称要与公式中的其它

18、变元名称不同,例,x(P(x)Q(x,y)(R(x)A(x) 用z代替自由变元x x(P(x)Q(x,y)(R(z)A(z) x(P(x,y)yQ(x,y,z)S(x,z) 用w和t分别代自由变元x和y x(P(x,t)yQ(x,y,z)S(w,z),1.7 谓词演算的永真公式,谓词公式的解释 指定一个论域D 对A中出现的每一个n元函数，指定一个D上的 n元个体函数常量 对A中出现的每一个n元谓词，指定一个D上的n元谓词常量 对A中出现的每一个个体常量及自由变元，指定D中的一个个体常量 对A中出现的每一个命题变元P，指派一个真值T或F 由此得到一个命题AI，称AI的真值为合适公式A在解释I 下

19、的真值,例,取解释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下的真值分别为?,xyP(x,y),T,T,F,F,T,T,T,yxP(x,y),T,F,F,F,F,F,T,例,取解释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

20、(1),1),P(2)Q(f(2),1),T,T,x(P(x)Q(f(x),a)在解释I下的真值为T,谓词公式的永真式,定义 给定谓词公式A，E是其论域，如果在任何解释下公式A的真值都为真，则称公式A在论域E上是永真式。如果不论对什么论域E，都使得公式A为永真式，则称A为永真式。 例：I(x)：x是整数，论域E为自然数集合 I(x)在E上是永真式 I(x) I(x)是与论域无关的永真式 谓词公式的永假式 谓词公式的可满足式,例：试说明以下公式的类型,xA(x)A(y) xA(x)A(y) A(x) (A(x) ：x+6=5) x( A(x) A(x) x (A(x)B(x) xA(x)xB(x

21、) x (A(x)B(x) xA(x) xB(x),永真式,可满足式,可满足式,永假式,5. 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 T,T,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)的真值为假，该式不是永真式,6. x (A(x)B(x) xA(x)xB(x) 解 取解释I如下: D=1,2,或,x A(x) x B(x),T,x (A(x

22、)B(x),F,所以在 I 下x (A(x)B(x) xA(x)xB(x)的真值为假，该式不是永真式,谓词公式的等价,定义 两个任意谓词公式A和B, E是它们公有的论域, 若在任何解释下，A与B作的真值都相同(或者说AB是永真式)，则称公式A与B在论域E上是等价的。如果不论对什么论域E，都使得公式A与B等价，则称A与B等价，记作AB。 例：I(x)：x是整数，N(x)：x是自然数，论域E是自然数集合 I(x)与N(x)在E上是等价的 N(x)I(x) N(x)I(x),谓词公式的蕴含,定义 两个任意谓词公式A和B，E是它们的论域，若在任何解释下，都使得公式AB为永真式，则称在论域E上公式A永真

23、蕴含B。如果不论对什么论域E， AB是永真式，则称A永真蕴含B，记作AB。 例：G(x)：x大于5，N(x)：表示x是自然数，论域E=-1,-2,6,7,8,9, 在E上公式G(x)N(x)是永真式 (G(x)N(x)N(x)是与论域无关的永真式，所以(G(x)N(x)N(x),1.7.2 谓词演算的基本永真公式,命题演算的永真公式也是谓词演算的永真公式 含有量词的谓词演算的基本永真公式 () xAA xAA () xP(x)P(y) 或 xP(x)P(x) P(y)xP(x) 或 P(x)xP(x) () 量词的否定 xP(x) xP(x) xP(x) xP(x) 量词转换公式,例,xyz(

24、x+z=y) xyz(x+z=y) xyz(x+z=y) xy z(x+z=y) xy z(x+zy),() 量词辖域的扩张和收缩 xA(x)Px(A(x)P) xA(x)Px(A(x)P) xA(x)Px(A(x)P) xA(x)Px(x)P) PxA(x)x(PA(x) PxA(x)x(PA(x) xA(x)Px(A(x)P) 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,(v) 量词的分配形式 x(A(x)B(x)xA(x)xB(x)

25、 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) 证明式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(x)xB(x),注意：公式3和4不是等价公式，而是永真蕴含式 例： 给定如下解释 A(x)： x是奇数 B(x)：x是偶数 则 xA(x)xB(x)为真 x(A(x)B(x) 为假 所以xA(x)xB(x)

26、不蕴含x(A(x)B(x) 或 D=1,2 A(1): T A(2): F B(1): F B(2): T,证明式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)为真，得 xA(x)xB(x)为真 所以 x(A(x)B(x)xA(x)xB(x),证明公式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) 即

27、xA(x)xB(x)x(A(x)B(x) 公式4得证。 特别要注意蕴含式的方向，不要搞错,(vi) 量词对及的处理 x(A(x)B(x)xA(x)xB(x) xA(x)xB(x)x(A(x)B(x) 证明1. xA(x)xB(x) xA(x)xB(x) xA(x)xB(x) x(A(x)B(x) x(A(x)B(x) 证明2. xA(x)xB(x) xA(x)xB(x) xA(x)xB(x) x(A(x)B(x) x(A(x)B(x),(vii) 关于多个量词的永真式 xyA(x,y)yxA(x,y) xyA(x,y)yxA(x,y) yxA(x,y)xyA(x,y) xyA(x,y)xyA(

28、x,y) yxA(x,y)xyA(x,y) xyA(x,y)yxA(x,y) yxA(x,y)xyA(x,y) xyA(x,y)yxA(x,y),1.7.3 几条规则(命题演算的推广),代入规则 设A是命题逻辑中的永真式，则用谓词逻辑的合适公式代替A中的某些命题变元得到的代入实例也是永真式；如果A是永假式，则上述代入实例也是永假式 例 A(x)A(x)B(x) PPQ x(A(x)B(x)x(A(x)B(x) PQPQ (xA(x)xB(x)xA(x)xB(x) 摩根律,替换规则 设A(x1, x2, xn) B(x1, x2, , xn), 而A是公式C中的子公式, 将B替换C中之A不必每一

29、处得D, 则CD。 对偶原理 在公式A B或A B中, A , B仅含运算符 , 和, 将上式中的全称量词与存在量词互换, 与互换, T和F互换, 则 A* B *, B* A*,1.8 谓词演算的推理规则,谓词演算中推理的形式结构 推理的形式结构仍为 H1H2Hn C 若H1H2Hn C是永真式，则称 前提H1，H2，Hn逻辑的推出结论C， 其中H1，H2，Hn和C都是谓词公式 谓词演算中的推理规则 命题演算中的推理规则，可在谓词推理理论中应用 P规则、T规则、CP规则 与量词有关的规则,全称指定规则 US (Universal Specialization),又称全称示例规则 作用：去掉全

30、称量词 两种形式： xA(x)A(y) xA(x)A(c) 使用此规则时要注意： （1）y为任意不在A(x)中约束出现的个体变元； （2）c为任意的个体常元 例：设A(x,y):xy 考查xyA(x,y) 可得到结论yA(z,y) 但不能得出结论yA(y,y),存在指定规则ES(Existential Specification),又称存在示例规则 作用：去掉存在量词 形式：xA(x)A(c) 使用此规则时要注意： （1）c是使A为真的特定个体常元； （2）c不在A(x)中出现 （3）如果A(x)中有其他自由变元出现，且x是随其他自由变元变化的，那么不能使用此规则 例：设A(x,y)：xy，考

31、查如下推理过程是否正确 xyA(x,y) yA(z,y) A(z,c),存在推广规则EG(Existential Generalization),作用：添加存在量词 形式： A(c)xA(x) 使用此规则时注意： (1) c是个体域中某个确定的个体 (2) 代替c的x不能已在A(c)中出现 例：设A(x,y)：xy，对xyA(x,y)考查如下推理过程 A(x,c) xA(x,x) 错误,全称推广规则UG(Universal Generalization),作用：添加全称量词 形式： A(y)xA(x) 使用此规则时注意： (1) y在A(y)中自由出现，且y取任何值时A均为真 (2) x不在A

32、(y)中约束出现 例：设A(x,y)：xy，考查如下推理过程 xA(x,y) x xA(x,x) 错误,量词四规则的使用限制条件,非常重要 ES, US, EG, UG四条规则都只有在量词的作用域是整个公式的情况下才能使用 例：考察如下推理过程 xP(x)yQ(y) xP(x)Q(c) ES 或 P(z)yQ(y) US 错误！,1.8.3 推理举例,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,2.所有自然数都是整数

33、。有些数是自然数。因此有些数是整数。 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 , x(A(x)B(x) P xA(x) P A(c) ES A(c)B(c) US B(c) T I xB(x) EG,3. 不认识错误的人，也不能改正错误。有些诚实的人改正了错误。所以有些诚实的人是认识了错误的人。 设A(x):x是认识错误的人。 B(x):x改正了错误。C(x):x是诚实的人。 符号化为： x(A(x)B(x)， x(C(x)B

34、(x), x(C(x)A(x),x(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 ,观察以下推理过程，指出问题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),满

35、足P的特定个体,c能满足Q？,事实上xP(x)xQ(x) x(P(x)Q(x)不成立,观察以下推理过程，指出问题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),4. 一些病人喜欢所有医生。任何病人都不喜欢庸医。所以没有医生是庸医。 设: P(x):x是病人, D(x):x是医

36、生, 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),x(P(x)y(D(y)L(x,y)，x(P(x)y(Q(y)L(x,y) y(D(y)Q(y) x(P(x)y(D(y)L(x,y) P P(c)y(D(y)L(c,y) ES P(c) T I y(D(y)L(c,y) T I x(P(x)y(Q(y)L(x,y) P P(c)y(Q(y)L(c,y) US y(Q(y)L(c,y) T I D(z)L(c,z) US Q(z)L(c,z) US L(c,z) Q(z) T

37、E D(z)Q(z) T I D(z)Q(z) T E (D(z)Q(z) T E y(D(y)Q(y) UG y(D(y)Q(y) T E,练习,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),5. x(P(x)Q(x) xP(x)xQ(x) xP(x) P(附

38、加前提) 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,用反证法证明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,练习,分别用反证法和附加前提法证明： x(A(x)B(x) xA(x)xB(x) 反证法： (1) (xA(x)xB(x)

39、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) (11) B(c) T(7)(10)I (12) B(c) B(c) T(8)(11)I,附加前提法： (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(

40、4)(5)I (7) xB(x) EG(6) (8) xA(x)xB(x) CP (9) xA(x)xB(x) T(8)E,用推理证明公式：yxA(x,y)xyA(x,y), yxA(x,y) P xA(x,c) ES A(z,c) US yA(a,y) EG xyA(x,y) UG ,推理注意事项：,注意使用ES、US、EG、UG的限制条件 对于同一个个体变元，既有带也有带的前提，去量词时，应先去后去，这样才可以特指同一个个体 c 添加和删去量词时，该量词必须是公式的最左边的量词，且此量词的前边无任何符号，它的辖域作用到公式末尾,(1)xP(x)yQ(y) P (2) xP(x)Q(b) E

41、S (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) (6) P(a)Q(b) ES(4) (7) P(a)Q(b) T(5)E 正确的作法,xP(x) P P(c) US 错误的作法,(1) xP(x) P (2) xP(x) T(1)E (3) P(c) ES (2) 正确的作法,xyP(x,y) P xP(x,c) ES 错误的作法,(1) xyP(x,y) P (2) yP(a,y) US(1) 正确的作法,小结,本章重点掌握内容： 1.各基本概念清楚。 2.会命题符号化。 3.熟练掌握等价公式和永真蕴涵式。 4.熟练掌握谓词逻辑的三种推理方法。,