Presentation is loading. Please wait.

Presentation is loading. Please wait.

第二章 谓词逻辑.

Similar presentations


Presentation on theme: "第二章 谓词逻辑."— Presentation transcript:

1 第二章 谓词逻辑

2 问题的提出: 即命题逻辑的局限性 在第一章, 一个原子命题只用一个字母表示, 而不再对命题中的句子成分细分。这样有一些逻
辑问题无法解决。请看下面的例子。 例1.令P:小张是大学生。 Q:小李是大学生。 从符号P、Q中不能归纳出他们都是大学生的共 性。我们希望从所使用的符号那里带给我们更多 的信息,比如可以看出他们的共性。这种想法在 第一章是无法实现的。

3 例2.令 A:所有自然数都是整数。 B:8是自然数。 C:8是整数。 这是著名的三段论推理,A是大前提,B是小前 提,C是结论。显然,由A和B可以推出结论C。 这个推理是有效的,但是这个推理在第一章也是无 法实现的。 分析:命题P与Q中的谓语是相同的(是大学生), 只是主语不同。命题A、B、C之间在主语谓语 方面也是有联系的,靠这种联系才能由A、B推 出C。而从这三个符号上看不出此种联系。 所以就要考虑表示命题的另一个方法。

4 解决这个问题的方法: 在表示命题时,既表示出主语(主词),也表示出谓语(谓 词),就可以解决上述问题。这就提出了谓词的概念。
令S(x)表示x是大学生,a:小张,b:小李 命题P表示成S(a):小张是大学生。 命题Q表示成S(b):小李是大学生。 从符号S(a)、S(b)可看出小张和小李都是大学生的共性。 令N(x):x是自然数。I(x):x是整数。 表示所有的。 A: x(N(x)→I(x)) B :N(8) C :I(8) 推理如此实现: N(8)→I(8) N(8)  I(8) 符号 S(x)、N(x)、I(x)就是所谓的谓词。

5 2-1 基本概念 2-1.1 客体与客体变元 Object 定义:能够独立存在的事物,称之为客体,也称
之为个体。它可以是具体的,也可以是抽象的 事物。通常用小写英文字母a、b、c、...表示。 例如,小张、小李、8、a、沈阳、社会主义等 等都是客体。 定义:用小写英文字母x、y、z...表示任何客 体,则称这些字母为客体变元。 注意:客体变元本身不是客体。

6 2-1.2 谓词 Predicate 定义:一个大写英文字母后边有括号,括号内是 若干个客体变元,用以表示客体的属性或者客体 之间的关系,称之为谓词。如果括号内有n个客 体变元,称该谓词为n元谓词。 例如 S(x):表示x是大学生。 一元谓词 G(x,y):表示 x>y。 二元谓词 B(x,y,z):表示x在y与z之间。三元谓词 一般地 P(x1,x2,…,xn) n元谓词。

7 2-1.3 命题函数 谓词本身并不是命题,只有谓词的括号内填入足 够的客体,才变成命题。 例如, a表示小张,b表示小李,则 S(a):小张是大学生。 S(b):小李是大学生。 G(7,3)表示:7>3。 如果c表示锦州,d表示沈阳,e表示山海关,则 B(c,d,e)表示:锦州在沈阳与山海关之间。 这时S(a)、S(b)、G(7,3)、B(c,d,e)才是命题。

8 令谓词S(x):x是大学生,括号内填入不同的人名,
之为命题函数。 定义:n元谓词P(x1,x2,…,xn)称之为简单命题函数。 规定:当命题函数P(x1,x2,…,xn)中 n=0 时,即0元 谓词,表示不含有客体变元的谓词,它本身就是一个 命题变元。 定义:将若干个简单命题函数用逻辑联结词联结起 来,构成的表达式,称之为复合命题函数。简单命 题函数与复合命题函数统称为命题函数。

9 例如,给定简单命题函数: A(x):x身体好, B(x):x学习好, C(x):x工作好, 复合命题函数 A(x)→(B(x)∧C(x)) 表示:如果x身体不好,则x的学习与工作 都不会好。

10 2-1.4 论域(个体域) Universe of discourse
定义:在命题函数中客体变元的取值范围,称之 为论域,也称之为个体域。 例如 S(x):x是大学生,论域是:人类。 G(x,y):x>y, 论域是:实数。 论域是一个集合。 定义:由所有客体构成的论域,称之为全总个体 域。它是个“最大”的论域。 约定:对于一个命题函数,如果没有给定论 域,则假定该论域是全总个体域。

11 2-1.5 量词 Quantifier 例如:有些人是大学生。 所有事物都是发展变化的。 其中“有些”、“所有的”就是对客体量化的词。 定义:在命题中表示对客体数量化的词,称之为 量词。 定义了两种量词: (1).存在量词:记作,表示“有些”、“一些”、 “某些”、“至少一个”等。 (2).全称量词:记作,表示“每个”、“任何 一个”、“一切”、“所有的”、“凡是”、“任意 的”等。

12 量词后的指导变元:量词后边要有一个客体变元,
用以指明对哪个客体变元量化,称此客体变元是量 词后的指导变元。 例如 x(读作“任意x”),x(读作“存在x”),其 中的x就是量词后的指导变元。 例题1.所有的自然数都是整数。 设 N(x):x是自然数。I(x):x是整数。此命题 可以写成 x(N(x)→I(x)) 例题2.有些自然数是偶数。 设 E(x):x是偶数。 此命题可以写成 x(N(x)∧E(x))

13 例题3. 每个人都有一个生母。 设 P(x):x是个人。M(x,y):y是x的生母。 此命题可以写成 x(P(x)→y(P(y)∧M(x,y)))

14 2-2 谓词公式及命题符号化 命题逻辑中有命题公式,类似地,在谓词逻辑 中,要研究谓词公式。 2-2.1 客体函数
有些命题中,可能有若干个客体,其中有些客 体之间有函数关系,例如 例题1. 如果x是奇数,则2x是偶数。 其中客体x与客体2x之间就有函数关系,可以设 客体函数 g(x)=2x, 设谓词: O(x):x是奇数, E(x):x是偶数, 则此命题可以表示为: x(O(x)→E(g(x)))

15 例题2 小王的父亲是个医生。 设函数f(x)=x的父亲,谓词D(x):x是个医 生,a:小王,此命题可以表示为D(f(a)). 例题3 如果x和y都是奇数,则x+y是偶数。 设 h(x,y)=x+y ,此命题可以表示为: xy((O(x)∧O(y))→E(h(x,y)) 像上述的g(x)、f(x)、h(x,y)就是客体函 数,一般地用小写的英文字母f,g,h….表示 客体之间的函数关系,称之为客体函数。 注意:客体函数与谓词是不同的,不可混淆。

16 客体函数与谓词间的区别: 客体函数中的客体变元用客体带入后的结果依 然是个客体 设例题1的论域是自然数集合N。 (3∈N,g(3)=6,所以g(3)∈N)。 谓词中的客体变元用确定的客体带入后就变成 了命题,其真值为T或者为F。 (3∈N, O(3)是个命题,真值为T)。 从“映射”角度看 客体函数是论域到论域的映射。 g:N→N,客体a∈N,则g(a)∈N。 而谓词是从论域到{T,F}的映射。 谓词E(x)看成映射E:N→{T,F},客体a∈N,则 E(a)∈{T,F}。

17 2-2.2 原子谓词公式 定义:称n元谓词P(x1,x2,...,xn)为原子谓 词公式。 例如 P、Q(x) 、 A(x,f(x))、B(x,y,a) 都是原子谓词公式。

18 2-2.3 谓词合式公式 (WFF) (Well Formed Formulas) 定义:谓词合式公式递归定义如下: 1.原子谓词公式是合式公式。 2.如果A是合式公式,则A也是合式公式。 3.如果A、B是合式公式,则(A∧B)、(A∨B)、 (A→B)、(AB)都是合式公式。 4.如果A是合式公式,x是A中的任何客体变元, 则xA和xA也是合式公式。 5.只有有限次地按规则(1)至(4)求得的公式才是 合式公式。 谓词合式公式也叫谓词公式,简称公式。

19 下面都是合式公式: P、(P→Q)、(Q(x)∧P)、x(A(x)→B(x))、xC(x) 而下面都不是合式公式: xyP(x) 、P(x)∧Q(x)x 为了方便,最外层括号可以省略,但是若量词 后边有括号,则此括号不能省。 注意:公式x(A(x)→B(x))中x后边的括号不 是最外层括号,所以不可以省略。

20 2-2.4 量词的作用域(辖域) Scope of Quantifier 定义:在谓词公式中,量词的作用范围称之为
量词的作用域,也叫量词的辖域。 例如 xA(x)中x的辖域为A(x). x((P(x)∧Q(x))→yR(x,y))中 x的辖域是((P(x)∧Q(x))→yR(x,y)) y的辖域为R(x,y)。 xyz(A(x,y)→B(x,y,z))∧C(t) z的辖域 y的辖域 x的辖域

21 一般地, 如果量词后边只是一个原子谓词公式时, 该量词的辖域就是此原子谓词公式。 如果量词后边是括号,则此括号所表示 的区域就是该量词的辖域。 如果多个量词紧挨着出现,则后边的量 词及其辖域就是前边量词的辖域。

22 2-2.5 自由变元与约束变元 在谓词公式中的客体变元可以分成两种, 一种是受到量词约束的,一种是不受量词 约束的。请看下面公式: x(F(x,y)→yP(y))∧Q(z)∧xA(x) F(x,y)中的x在x的辖域内,受到x的 约束,而其中的y不受x的约束。 P(y)中的y在y的辖域内,受y的约束。 A(x)中的x在x的辖域内,受x的约束。 Q(z)中的z不受量词约束。

23 定义:如果客体变元x在x或者x的辖域内,则x
上例中 x(F(x,y)→yP(y))∧Q(z)∧xA(x) F(x,y)中的x和P(y)中的y以及A(x)中x是 约束变元。 注意:F(x,y)中的x和A(x)中x是受不同量词约 束的约束变元。 而F(x,y)中的y和Q(z)中的z是自由变元。

24 对约束变元和自由变元几点说明: (1).对约束变元用什么符号表示无关紧要。 就是说xA(x)与yA(y)是一样的。这类似于计 算积分与积分变元无关,即积分∫f(x)dx 与 ∫f(y)dy 相同。 (2).一个谓词公式如果无自由变元,它就表示 一个命题。 例如 A(x)表示x是个大学生。xA(x)或者 xA(x)就是个命题了,因为它们分别表示命题 “有些人是大学生”和“所有人都是大学生”。

25 (3).一个n元谓词P(x1,x2,…,xn),若在前边添加
k个量词,使其中的 k个客体变元变成约束变元, 则此 n元谓词就变成了n-k元谓词。 例如P(x,y,z)表示x+y=z,假设论域是整数集。 xyP(x,y,z)表示“任意给定的整数x,都可以 找到整数y,使得x+y=z” 。 如果令 z=1,则xyP(x,y,1)就变成了命题 “任意给定的整数x,都可以找到整数y,使得 x+y=1”,…。 可见每当给z指定个整数a后,xyP(x,y,a) 就变成了一个命题。所以谓词公式xyP(x,y,z) 就相当于只含有客体变元 z的一元谓词了。

26 在一个谓词公式中,如果某个客体变元既以约
束变元形式出现,又以自由变元形式出现,或者 同一个客体变元受多个量词的约束,就容易产生 混淆。为了避免此现象发生,可以对客体变元更 改名称。 如 x(F(x,y)→yP(y))∧Q(z)∧xA(x) 约束变元的改名规则: (1).对约束变元可以更改名称,改名的范围是: 量词后的指导变元以及该量词的辖域内此客体变 元出现的各处同时换名。 (2).改名后用的客体变元名称,不能与该公式中 其它客体变元名称相同。

27 例如x(P(x)→Q(x,y))∨(R(x)∧xA(x)∧B(x))
z(P(z)→Q(z,y))∨(R(x)∧uA(u)∧B(x)) 对自由变元也可以换名字,此换名叫代入。 自由变元的代入规则: (1).对谓词公式中的自由变元可以作代入。代入 时需要对公式中出现该变元的每一处,同时作代 入。 (2).代入后的变元名称要与公式中的其它变元名 称不同。 上例也可以对自由变元x作代入,改成 x(P(x)→Q(x,y))∨(R(z)∧uA(u)∧B(z))

28 2-2.6 命题的符号化 在谓词演算中,命题的符号化比较复杂,命题的符 号表达式与论域有关系。例如 1.每个自然数都是整数。 (1).如果论域是自然数集合N,令 I(x):x是整 数,则命题的表达式为 xI(x) (2).如果论域扩大为全总个体域时,上述表达式 xI(x)表示“所有客体都是整数”,显然这是假的 命题,此表达式已经不能表达原命题了。因此需 要添加谓词N(x):x是自然数,用于表明x的特性, 于是命题的符号表达式为: x(N(x)→I(x))

29 2.有些大学生吸烟。 (1).如果论域是大学生集合S,令A(x):x 吸烟,则命题的表达式为 xA(x) (2).如果论域扩大为全总个体域时,上述 表达式xA(x)表示“有些客体吸烟”,就不 是表示此命题了,故需要添加谓词 S(x): x是大学生,用于表明x的特性,于是命题 的表达式为 x(S(x)∧A(x))

30 可见命题的符号表达式与论域有关。当论域扩
大时,需要添加用来表示客体特性的谓词,称此 谓词为特性谓词。 特性谓词往往就是给定命题中量词后边的那个 名词。如上面两个例子中的“所有自然数”、“有 些大学生”。 如何添加特性谓词,这是个十分重要的问题, 这与前边的量词有关。 如果前边是全称量词,特性谓词后边是蕴含联 结词“→”; 如果前边是存在量词,特性谓词后边是合取联 结词“∧”。

31 I包含N 为什么必须这样添加特性谓词? 分析一下特性谓词和原谓词所表示的概念之间的关系, 得出下面的图,从此图可以得出如此添加特性谓词的正
确性。 令N:自然数集合,I:整数集合, S:大学生集合,A:烟民的集合。 S A I N 吸烟大学生 I包含N x(N(x)→I(x)) 吸烟大学生是S与A的交集 x(S(x)∧A(x)) 再从两个重要的公式看特性谓词的添加方法。

32 先介绍两个公式: 令论域为{1,2,3,4,5},谓词A(x)表示x是整数。B(x)表 示x是奇数。 xA(x)=A(1)∧A(2)∧A(3)∧A(4)∧A(5) xB(x)=B(1)∨B(2)∨B(3)∨B(4)∨B(5) 一般地,设论域为{a1,a2,....,an},则 (1). xA(x)A(a1)∧A(a2)∧......∧A(an) (2). xB(x)B(a1)∨B(a2)∨......∨B(an) 1.每个自然数都是整数。该命题的真值是真的。 表达式x(N(x)→I(x))在全总个体域的真值是真的,因x(N(x)→I(x))(N(a1)→I(a1))∧ (N(a2)→I(a2))∧ … ∧(N(an)→I(an)) 式中的x不论用自然数客体代入,还是用非自然数客体 代入均为真。例如(N(0.1)→I(0.1))也为真。

33 而x(N(x)∧I(x))在全总个体域却不是永真式。
x(N(x)∧I(x))(N(a1)∧I(a1))∧(N(a2)∧I(a2)) ∧…∧(N(an)∧I(an)) 比如x用0.2代入(N(0.2)∧I(0.2))就为假。 所以此表达式不能表示这个命题。 2.有些大学生吸烟。 此命题的真值也是真的。 x(S(x)∧A(x))(S(a1)∧A(a1))∨(S(a2)∧A(a2)) ∨ … ∨(S(an)∧A(an)) 上式中x只有用吸烟的大学生代入才为真。假如a2不是 大学生或者不会吸烟的客体,则(S(a2)∧A(a2))为假。 所以用x(S(x)∧A(x))表示此命题是对的。 而x(S(x)→A(x))中的x用非大学生的客体代入时也为 真,例如(S(a2)→A(a2))为真。所以表达式 x(S(x)→A(x))不能表示这个命题。

34 3.所有大学生都喜欢一些歌星。 令S(x):x是大学生,X(x):x是歌星, L(x,y):x喜欢y。 则命题的表达式为: x(S(x)→y(X(y)∧L(x,y))) 4.没有不犯错误的人。 此话就是“没有人不犯错误”,“没有”就是“不存在”之 意。令P(x):x是人,F(x):x犯错误, 此命题的表达式为: x(P(x)∧F(x)) 或者 x(P(x)→F(x)) 5.不是所有的自然数都是偶数。 令N(x):x是自然数,E(x):x是偶数, 命题的表达式为: x(N(x)→E(x)) 或者 x(N(x)∧E(x))

35 6.如果一个人只是说谎话,那么他所说的每句话没有一 句是可以相信的。 令A(x):x是人,B(x,y):y是x说的话,
C(x):x是谎话,D(x):x是可以相信的 命题的表达式为: x(A(x)→(y(B(x,y)→C(y))→z(B(x,z)∧D(z))) 7.每个自然数都有唯一的后继数。 令N(x):x是自然数,A(x,y):y是x的后继数, E(x,y):x=y 则命题的表达式为 x(N(x)→y(N(y)∧A(x,y)∧z((N(z)∧A(x,z))→E(y,z)))) 有一个后继数 后继数的唯一性 下面请同学们自己做练习第60页(2)

36 练习P60(2) 答案 : a) x(J(x)→L(x)) b) x(L(x)∧S(x)) c) x(J(x)∧O(x)∧V(x))
d) J(j)∧O(j)∧V(j) e) x(L(x)→J(x)) 或者 x(L(x)∧J(x)) f) x(S(x)∧L(x)∧C(x)) g) x(C(x)∧V(x)) 或者 x(C(x)→V(x)) h) x((C(x)∧O(x))→L(x)) i) x(W(x)∧C(x)∧H(x)) j) x(W(x)∧J(x)∧C(x)) k) x(L(x)→y(J(y)∧A(x,y))) l) x(S(x)∧y(L(y)→A(x,y)))

37 小结 1.命题的符号表达式形式与论域有关系。 论域扩大需要用特性谓词对客体进行说明.注意如何添 加特性谓词(即要注意特性谓词后边是什么联结词)。 2.如果量词前有否定符号,如“没有...”“不是所有 的...”等,可以按照字面直译。如“x…” “x...” 3.命题的符号表达式中所有客体变元必须都是约束变元, 才表示命题。有时给定命题中有些量词没有明确给出, 要仔细分析并写出这隐含的量词。 例如 a) 金子闪光,但闪光的不一定都是金子。G(x),F(x) x(G(x)→F(x))∧x(F(x) →G(x)) b) 没有大学生不懂外语。S(x),K(x,y),F(x) x(S(x)∧y(F(y)→K(x,y)))

38 作业 60页 (2) 62页 (2), (3) b), c), (5) b) (6) 65页 (4) b) (5) a)

39 2-3谓词演算的等价式与蕴涵式 在命题逻辑中,我们是通过对公式的命题变元 赋值来讨论永真式、永真蕴含式及等价公式的。
在谓词演算中,也要讨论一些重要的谓词公式。 但是由于谓词公式中可能有命题变元、客体变元。 对命题变元赋值比较容易,因为只有两个值可赋。 而对客体变元作指派却不那么简单,因为论域中 的客体可能有无限个。另外谓词公式的真值还与 论域有关。

40 2-3.1 对谓词公式赋值 定义:若将给定的谓词公式中的命题变元, 用确定的命题代替,对公式中的客体变元用 论域中的客体代替,这个过程就称之为对谓 词公式作指派,或称之为对谓词公式赋值。 例如公式 P→N(x),N(x):x是自然数, 论域为实数集合R, 令P:2>1,x=4 时,此公式变成P→N(4),它的真值就是“真”。

41 2-3.2 谓词公式的永真式定义 定义:给定谓词公式A,E是其论域,如 果不论对公式A作任何赋值,都使得A的真 值为真,则称公式A在论域E上是永真式。 如果不论对什么论域E,都使得公式A为永 真式,则称A为永真式。 例如,I(x):x是整数,论域E为自然数 集合,公式I(x)在E上就是永真式。 而公式 I(x)∨I(x)就是与论域无关的 永真式。

42 定义:给定谓词公式A、B,E是它们的论域,
2-3.3 谓词公式的等价公式定义 定义:给定谓词公式A、B,E是它们的论域, 如果不论对公式A、B作任何赋值,都使得A与B的 真值相同(或者说AB是永真式),则称公式A与B 在论域E上是等价的。如果不论对什么论域E,都 使得公式A与B等价,则称A与B等价,记作AB。 例如,I(x):表示x是整数,N(x):表示x是自 然数,假设论域E是自然数集合,公式I(x)与N(x) 在E上是等价的。 而公式N(x)→I(x) 与N(x)∨I(x)就是与论域 无关的等价的公式,即 N(x)→I(x)N(x)∨I(x)。

43 定义:给定谓词公式A、B,E是它们的论域,
2-3.4 谓词公式的永真蕴含式定义 定义:给定谓词公式A、B,E是它们的论域, 如果不论对公式A、B作任何赋值,都使得A→B为 永真式,则称在论域E上公式A永真蕴含B。如果 不论对什么论域E,都使得公式A→B为永真式, 则称A永真蕴含B,记作AB。 例如,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)。

44 2-3.5. 重要公式 下面讨论重要的谓词等价公式和永真蕴含式。 一.由命题公式推广出的公式
不含自由变元的谓词公式本身(如xA(x)、xB(x))就 是命题。 含有n个自由变元的谓词公式,赋予论域中的n个指定 客体后就变成命题(如S(a)、G(3,1)),于是可把此谓词公 式看成一个命题变元。 因此用谓词公式代替43页公式中的命题变元,就可以将 命题演算中的等价公式和永真蕴含式推广到谓词演算中使 用。例如 A(x)A(x)∨B(x) PP∨Q x(A(x)→B(x))x(A(x)∨B(x)) P→QP∨Q (xA(x)∧xB(x))xA(x)∨xB(x) 摩根定律

45 二.带量词的公式在论域内的展开式 先看一个例子,令A(x):表示x是整数,B(x): 表示x是奇数,设论域是{1,2,3,4,5},谓词公式
xA(x)表示论域内所有的客体都是整数,显然公 式xA(x)的真值为真,因为A(1)、A(2)、A(3)、 A(4)、A(5)都为真,于是有 xA(x)A(1)∧A(2)∧A(3)∧A(4)∧A(5) 类似地,谓词公式xB(x)表示论域内有些客体是奇数, 显然公式xB(x)的真值也为真,因为B(1)、B(3)、B(5) 的真值为真,于是有 xB(x)B(1)∨B(2)∨B(3)∨B(4)∨B(5) 一般地,设论域为{a1,a2,....,an},则 1. xA(x)A(a1)∧A(a2)∧......∧A(an) 2. xB(x)B(a1)∨B(a2)∨......∨B(an)

46 y(P(1,y) P(f(1),f(y))) y(P(2,y) P(f(2),f(y)))
练习:设论域D={1,2} a=1 b=2 f(1)=2 f(2)=1 P(1,1)=T P(1,2)=T P(2 ,1)=F P(2,2)=F 求谓词公式xy(P(x,y)P(f(x),f(y)))的真值。 解: xy(P(x,y)P(f(x),f(y))) y(P(1,y) P(f(1),f(y))) y(P(2,y) P(f(2),f(y))) ((P(1,1) P(f(1),f(1))) (P(1,2) P(f(1),f(2)))) ((P(2,1) P(f(2),f(1)))(P(2,2) P(f(2),f(2)))) ((P(1,1) P(2,2))(P(1,2) P(2,1))) ((P(2,1) P(1,2))(P(2,2) P(1,1))) ((TF ) (TF))((FT)  (FT)) (F F)(T  T) FT F

47 三.量词否定公式 我们还是先用一个例子说明这个问题。令 A(x)表示x是优等生,论域是某班级的学生集合。
xA(x)表示:不是所有人都是优等生。 xA(x)表示:有些人不是优等生。 xA(x)表示:没有人是优等生。 xA(x)表示:所有人都不是优等生。 从这个例子可以看出 “不是所有人都是优等生。”与“有些人不是优等 生。”是等价的。 “没有人是优等生。”与“所有人都不是优等生。” 是等价的。于是有:

48 1. xA(x)xA(x) 2. xA(x)xA(x) 对这两个公式可以证明如下: 证明:设论域为{a1,a2,....,an},则 xA(x)(A(a1)∧A(a2)∧...∧A(an)) A(a1)∨A(a2)∨...∨A(an)xA(x) 类似可以证明另一个公式。 从这两个公式,可以总结出如下规律:将量词前 的“”移到量词的后边,或者将量词后的“”移到 量词的前边时,量词也随着改变,如果原来是全 称量词改成存在量词,如果原来是存在量词改成 全称量词。所以我们也把这两个公式称为量词转 换公式。

49 四.量词辖域的扩充公式 如果B是个不含客体变元x的谓词公式,且不 在x和x的辖域内,可以将B放入x和x的辖 域内。即得如下公式:
1. xA(x)∨Bx(A(x)∨B) 2. xA(x)∧Bx(A(x)∧B) 3. xA(x)∨Bx(A(x)∨B) 4. xA(x)∧Bx(A(x)∧B) 5. B→xA(x)x(B→A(x)) 6. B→xA(x)x(B→A(x)) 7. xA(x)→Bx(A(x)→B) 8. xA(x)→Bx(A(x)→B)

50 证明:设论域为{a1,a2,....,an}, 上述公式我们只证明三个。
xA(x)∨B(A(a1)∧A(a2)∧...∧A(an))∨B (A(a1)∨B)∧(A(a2)∨B)∧...∧(A(an)∨B) x(A(x)∨B) B→xA(x)B∨xA(x)x(B∨A(x)) x(B→A(x)) xA(x)→BxA(x)∨BxA(x)∨B x(A(x)∨B)x(A(x)→B) 在使用公式7.、8.时,要特别注意,量词的辖 域扩充后,量词发生了变化。

51 五.量词分配公式 证明:设论域为{a1,a2,....,an}, 1. x(A(x)∨B(x))xA(x)∨xB(x)
4. xA(x)∨xB(x)x(A(x)∨B(x)) 证明:设论域为{a1,a2,....,an}, x(A(x)∨B(x)) (A(a1)∨B(a1))∨(A(a2)∨B(a2))∨… ∨(A(an)∨B(an)) (A(a1)∨A(a2)∨...∨A(an))∨ (B(a1)∨B(a2)∨...∨B(an)) xA(x)∨xB(x)

52 注意公式3.和4.不是等价公式,而是永 真蕴含式。 例如公式3.由xA(x)∧xB(x)不能推出x(A(x)∧B(x)), 我们可以举一个反例,设A(x)和B(x)分别 表示“x是奇数”和“x是偶数”,显然命题 xA(x)∧xB(x)为真。而x(A(x)∧B(x)) 是表示命题“存在一些数既是奇数,也是偶 数”,显然不为真。 所以说由xA(x)∧xB(x)不能推出 x(A(x)∧B(x)).

53 证明公式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)为真。于是有

54 下面利用公式3.证明公式4.。 证明:因为公式3.中的A(x)和B(x)是任意的谓词 公式,不妨用A(x)和B(x)分别代替公式3.中
x(A(x)∧B(x))xA(x)∧xB(x) x(A(x)∨B(x))xA(x)∧xB(x) x(A(x)∨B(x))(xA(x)∨xB(x)) 应用公式 P→QQ→P 得 xA(x)∨xB(x)x(A(x)∨B(x)) 公式4.得证。 在使用公式4.的时候,特别要注意蕴含 式的方向,不要搞错。

55 1. x(A(x)→B(x))xA(x)→xB(x)
六.其它公式 1. x(A(x)→B(x))xA(x)→xB(x) 2. xA(x)→xB(x)x(A(x)→B(x)) 证明1. xA(x)→xB(x) xA(x)∨xB(x) xA(x)∨xB(x) x(A(x)∨B(x)) x(A(x)→B(x)) 证明2. xA(x)→xB(x) xA(x)∨xB(x) xA(x)∨xB(x) x(A(x)∨B(x)) x(A(x)→B(x))

56 七.两个量词的公式 在A(x,y)前有两个量词,如果两个量词是相同 的,它们的次序是无关紧要,但是如果是不同的,
它们的次序就不可以随便交换。例如设 A(x,y)表示“x+y=0”,论域为:实数集合, xyA(x,y)表示“对于任意给定的一个实数x,可 以找到一个y,使得x+y=0”,这是一个为“真”的命题。 而交换量词后 yxA(x,y) 表示“存在一个实数y,与任意给定 的一个实数x之和都等于0”,这是一个为“假”的命 题。

57 有如下一些公式: 1. xyA(x,y)yxA(x,y) 2. xyA(x,y)yxA(x,y)
4. xyA(x,y)xyA(x,y) 5. yxA(x,y)xyA(x,y) 6. xyA(x,y)yxA(x,y) 7. yxA(x,y)xyA(x,y) 8. xyA(x,y)yxA(x,y) 注意:下面式子不成立 xyA(x,y)yxA(x,y)

58 xyA(x,y) yxA(x,y) yxA(x,y) xyA(x,y) xyA(x,y) yxA(x,y)
为了便于记忆,用下面图形表示上面八个公式。 xyA(x,y) yxA(x,y) yxA(x,y) xyA(x,y) xyA(x,y) yxA(x,y) yxA(x,y) xyA(x,y)

59 (A(a1,a1)∧A(a1,a2)∧…∧A(a1,an))∧
实际上,根据具有传递性,还可以派生出一些公式。 下面我们只证明一个等价公式。用谓词逻辑推理方法很容 易证明上面那些永真蕴涵式,在此就不证明了。下面证明 公式1.。 证明:设论域为{a1,a2,....,an},则 xyA(x,y)yA(a1,y)∧yA(a2,y)∧…∧yA(an,y) (A(a1,a1)∧A(a1,a2)∧…∧A(a1,an))∧ (A(a2,a1)∧A(a2,a2)∧…∧A(a2,an))∧…∧ (A(an,a1)∧A(an,a2)∧…∧A(an,an)) (A(a1,a1)∧A(a2,a1)∧…∧A(an,a1))∧ (A(a1,a2)∧A(a2,a2)∧…∧A(an,a2))∧…∧ (A(a1,an)∧(A(a2,an)∧…∧A(an,an)) xA(x,a1)∧xA(x,a2)∧…∧xA(x,an) yxA(x,y)

60 xyA(x,y)的真值。 下面同学动手作课堂练习练习: 令A(x,y)表示x+y=xy, 论域是{1,2,3}, 求谓词公式
解: xyA(x,y)xyA(x,y) yA(1,y)∨yA(2,y)∨yA(3,y) (A(1,1)∧A(1,2)∧A(1,3))∨ (A(2,1)∧A(2,2)∧A(2,3))∨ (A(3,1)∧A(3,2)∧A(3,3)) (T∧T∧T)∨(T∧F∧T)∨(T∧T∧T) T∨F∨TT

61 本节小结: 熟练掌握谓词等价公式和永真蕴涵式的证明方法及应用。 作业题: P66 (3) b) P71 (2) d), (6)

62 2-4 前束范式 与命题公式的范式类似,谓词公式也有规范形 式。这里主要介绍前束范式--所有量词都在公式 前边约束变元。 1.前束范式定义:
2-4 前束范式 与命题公式的范式类似,谓词公式也有规范形 式。这里主要介绍前束范式--所有量词都在公式 前边约束变元。 1.前束范式定义: 一个谓词公式符合下面条件,就是前束范式: 所有量词前面都没有联接词; 所有量词都在公式的左面; 所有量词的辖域都延伸到公式的末尾。 例如 yxz(A(x)→(B(x,y)∨C(x,y,z))) 就是前束范式, 而 xA(x)∧yB(y) xA(x)→B(x) 就不是前束范式。

63 2.前束范式的写法 给定一个带有量词的谓词公式, 1)消去公式中的联接词→和(为了便于量词辖域的扩充); 2)如果量词前有“”,则用量词否定公式将 “”后移。再用摩根定律或求公式的否定公 式,将“”后移到原子谓词公式之前。 3)用约束变元的改名规则或自由变元的代入 规则对变元换名(为量词辖域扩充作准备) 4)用量词辖域扩充公式提取量词,使之成为 前束范式形式。

64 例1. xA(x)→xB(x) xA(x)∨xB(x) xA(x)∨xB(x) xA(x)∨yB(y) (换元) x(A(x)∨yB(y)) (量词辖域扩充) xy(A(x)∨B(y)) 另一个方法:xA(x)→xB(x) x(A(x)∨B(x)) (量词分配公式)

65 例2.x(P(x)∧R(x))→(xP(x)∧Q(x))
x(P(x)∨R(x))∨(yP(y)∧Q(z)) (换变元) x(P(x)∨R(x))∨y(P(y)∧Q(z)) (扩量词辖域) xy((P(x)∨R(x))∨(P(y)∧Q(z)))(扩量词辖域) 3.前束析取范式与前束合取范式: 前束析取范式:前束范式中量词后的括号内是析取范式形式。 前束合取范式:前束范式中量词后的括号内是合取范式形式。 上例的前束析取范式为: xy(P(x)∨R(x)∨(P(y)∧Q(z))) 上例的前束合取范式为: xy((P(x)∨R(x)∨P(y))∧(P(x)∨R(x)∨Q(z)))

66 下面同学动手做练习。 写出第75页(2)d) 中谓词公式的前束范式。 x(P(x)→Q(x,y))→(yP(y)∧zQ(y,z)) x(P(x)∨Q(x,y))∨(yP(y)∧zQ(y,z)) (去→) x(P(x)∨Q(x,y))∨(yP(y)∧zQ(y,z))(换量词) x(P(x)∧Q(x,y))∨(yP(y)∧zQ(y,z)) (后移) x(P(x)∧Q(x,y))∨(uP(u)∧zQ(y,z)) (换变元) xuz((P(x)∧Q(x,y))∨(P(u)∧Q(y,z))) (扩量词辖域) 此式是前束析取范式。

67 本节掌握前束范式的写法。 作业 P75 (1)b) (2)c)

68 2-5 谓词演算的推理理论 推理方法: 直接推理、条件论证、反证法 所用公式:43页和70页的I1~I19,E1~E33
推理规则:P、T、CP、US、ES、EG、UG 后四个规则,是处理量词的,因为推理时要使 用不含量词的命题公式,所以要去掉量词,如果 结论有量词,还要添加量词。 下面介绍四个新规则:

69 一.全称特指规则 US (Universal Specialization) 形式: xA(x)A(c) (其中c是论域内指定客体) 含义:如果xA(x)为真,则在论域内任 何指定客体c,都使得A(c)为真。 作用:去掉全称量词。 要求:c不是A(x)中的符号。

70 二.存在特指规则ES (Existential Specialization)
形式: xA(x)A(c) (其中c是论域内指定客体) 含义:如果xA(x)为真,则在论域内指定客体c, 都使得A(c)为真。 作用:去掉存在量词。 要求:⑴ c不是A(x)中的符号。 ⑵ 用ES指定的客体c不应该是在此之前用 US规则或者用ES规则所指定的客体c(即本次用ES 特指客体c,不应该是以前特指的客体)。  请看下面两个例子: 

71 例1. 令A(x)表示x是自然数,B(x)表示x是整数。
⑴ x(A(x)→B(x)) P ⑵ A(c)→B(c) US 如c=0.1 ⑶ xA(x) P ⑷ A(c) × ES A(0.1)为F ⑴ xB(x) P ⑵ B(c) ES 如c=-1 ⑶ xA(x) P ⑷ A(c) × ES A(-1)为F

72 分析一下,下面作法是否正确? ⑴ xA(x) P ⑵ A(c) ES ⑶x(A(x)→B(x)) P ⑷ A(c)→B(c) US ⑸ B(c) T ⑵⑷ I11 好比 A、B两个人约会, A—对沈阳对不十分熟悉 B-是老沈阳人 应由谁先提出约会地点?(先局部后全体)

73 三.存在推广规则 EG (Existential Generalization) 形式: A(c)xA(x) (其中c是论域内指定客体) 含义:如果在论域内指定客体c使得 A(c)为真,则xA(x)为真。 作用:添加存在量词。 要求:x不是A(c)中的符号。

74 四.全称推广规则 UG (Universal Generalization) 形式: A(c)xA(x) (其中c是论域内任何指定客体) 含义:如果在论域内任何指定客体c都使 得A(c)为真,则xA(x)为真。 作用:添加全称量词。 要求:x不是A(c)中的符号。 c一定是任意的客体,否则不可全 称推广。

75 例1 所有金属都导电。铜是金属。 故铜导电。 令 M(x):x是金属。C(x):x导电。a:铜。 符号化为: x(M(x)→C(x)),M(a) C(a) ⑴ x(M(x)→C(x)) P  ⑵ M(a)→C(a) US ⑴ ⑶ M(a) P ⑷ C(a) T ⑵⑶ I11

76 例2. 所有自然数都是整数。有些数是自然 数。因此有些数是整数。 令A(x)表示x是自然数,B(x)表示x是整数。 x(A(x)→B(x)), xA(x)  xB(x) ⑴ xA(x) P ⑵ A(c) ES ⑴ ⑶ x(A(x)→B(x)) P ⑷ A(c)→B(c) US ⑶ ⑸ B(c) T ⑵⑷ I11 ⑹ xB(x) EG ⑸

77 例2中,如果按下面方法推理,是否正确? x(A(x)→B(x)), xA(x)  xB(x) ⑴ x(A(x)→B(x)) P ⑵ A(c)→B(c) US ⑴ ⑶ xA(x) P ⑷ A(c) ES ⑶ ⑸ B(c) T ⑵⑷ I11 ⑹ xB(x) EG ⑸ 如果有问题,问题在哪里?

78 例3 不认识错误的人,也不能改正错误。 有些诚实的人改正了错误。所以有些诚实 的人是认识了错误的人。 设A(x):x是认识错误的人。 B(x):x改正了错误。C(x):x是诚实的人。 符号化为: x(A(x)→B(x)),x(C(x)∧B(x)),  x(C(x)∧A(x))

79 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 ⑵I1 ⑷ B(c) T ⑵I2 ⑸ x(A(x)→B(x))P ⑹ A(c)→B(c) US ⑸ ⑺ A(c) T ⑷⑹ I12 ⑻ A(c) T ⑺ E1 ⑼ C(c)∧A(c) T ⑶⑻ I9 ⑽ x(C(x)∧A(x)) EG ⑼

80 课堂练习:证明下面推理的有效性: “鸟都会飞。猴子都不会飞。所以,猴子都不是鸟。” 设 B(x):x是鸟;F(x):x会飞;M(x):x是猴子。 x(B(x)→F(x)),x(M(x)→F(x))x(M(x)→B(x)) 证明: ⑴ x(B(x)→F(x)) P ⑵ B(a)→F(a) US ⑴ ⑶ x(M(x)→F(x)) P ⑷ M(a)→F(a) US ⑶ ⑸ F(a)→B(a) T ⑵ E18 ⑹ M(a)→B(a) T ⑷ ⑸ I13 ⑺ x(M(x)→B(x)) UG ⑹

81 课堂练习P79(1)d)改成: x(A(x)∨B(x)),x(B(x)→C(x)),xC(x) xA(x) (1) x(A(x)∨B(x)) P (2) A(a)∨B(a) ES (1) (3) x(B(x)→C(x)) P (4) B(a)→C(a)) US (3) (5) xC(x) P (6) C(a) US (5) (7 ) B(a) T (4)(6) I12 (8) A(a) T (2)(7) I10 (9) xA(x) EG (8)

82 例4 一些病人喜欢所有医生。任何病人都不喜欢
庸医。所以没有医生是庸医。 设: 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))

83 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(a)∧y(D(y)→L(a,y)) ES ⑴ ⑶ P(a) T ⑵ I1 ⑷ y(D(y)→L(a,y)) T ⑵ I2 ⑸ x(P(x)→y(Q(y)→L(x,y))) P ⑹ P(a)→y(Q(y)→L(a,y)) US ⑸ ⑺ y(Q(y)→L(a,y)) T ⑶ ⑹ I11 ⑻ D(b)→L(a,b) US ⑷ ⑼ Q(b)→L(a,b) US ⑺ ⑽ L(a,b) →Q(b) T ⑼ E18 ⑾ D(b)→Q(b) T ⑻⑽ I13 ⑿ D(b)∨Q(b) T ⑾ E16 ⒀ (D(b)∧Q(b)) T ⑿ E8 ⒁ y(D(y)∧Q(y)) UG ⒀ ⒂ y(D(y)∧Q(y)) T ⒁ E25

84 例5 x(P(x)→Q(x))  xP(x)→xQ(x)
用条件论证证明: ⑴ xP(x) P(附加前提) ⑵ x(P(x)→Q(x)) P ⑶ P(a)→Q(a) ES ⑵ ⑷ P(a) US ⑴ ⑸ Q(a) T ⑶⑷ I11 ⑹ xQ(x) EG ⑸ ⑺ xP(x)→xQ(x) CP

85 下面请同学作课堂练习 用反证法证明例5: x(P(x)→Q(x)) xP(x)→xQ(x)
⑴ (xP(x)→xQ(x)) P(假设前提) ⑵ (xP(x)∨xQ(x)) T ⑴ E16 ⑶ xP(x)∧xQ(x) T⑵ E9 ⑷ xP(x) T⑶ I1 ⑸ xQ(x) T⑶ I2 ⑹ x(P(x)→Q(x)) P ⑺ P(a)→Q(a) ES ⑹ ⑻ P(a) US ⑷ ⑼ Q(a) T ⑺⑻ I11 ⑽ xQ(x) EG ⑼ ⑾ xQ(x)∧xQ(x) T⑸⑽ I9 下面请同学作课堂练习

86 给定谓词如下:S(x):x是学生;L(x):x是校领导; G(x):x
是好的;T(x):x是老师;P(x): x受过处分; C(x,y):y表扬x 用上述谓词表达下面各个命题,并且用谓词逻辑推理方 法证明下面推理的有效性。 “没有受过处分的学生,都受到过校领导的表扬;有些 好学生,仅仅受到老师的表扬;所有好学生,都没有受 过处分。所以,有的老师是校领导。” 先请同学将上述各个命题符号化,然后推理。 x((S(x)P(x))y(L(y)C(x,y))), x((S(x)G(x))y(C(x,y)T(y))) , x((S(x) G(x)) P(x)) y(T(y)L(y))

87 x((S(x)P(x))y(L(y)C(x,y))),x((S(x)G(x))y(C(x,y)T(y)))
x((S(x) G(x)) P(x)) y(T(y)L(y)) ⑴ x((S(x)G(x))y(C(x,y)T(y))) P ⑵ (S(a)G(a))y(C(a,y)T(y)) ES ⑴ ⑶ S(a)G(a) T ⑵ I1 ⑷ x((S(x) G(x)) P(x)) P ⑸ (S(a) G(a)) P(a) US ⑷ ⑹ P(a) T ⑶ ⑸ I11 ⑺ S(a) T ⑶ I1 ⑻ S(a)  P(a) T ⑹⑺I9 ⑼ x((S(x)P(x))y(L(y)C(x,y))) P ⑽ (S(a)P(a))y(L(y)C(a,y)) US ⑼ ⑾ y(L(y)C(a,y)) T ⑻⑽ I11 ⑿ y(C(a,y)T(y)) T ⑵ I2 ⒀ L(b) C(a,b) ES ⑾ ⒁ C(a,b)T(b) US ⑿ ⒂ L(b) T ⒀ I1 ⒃ C(a,b) T ⒀ I ⒄ T(b) T⒁ ⒃ I11 ⒅T(b)L(b) T ⒂ ⒄I ⒆ y(T(y)L(y)) EG ⒅

88 用推理证明公式: yxA(x,y)xyA(x,y) ⑴ yxA(x,y) P ⑵ xA(x,b) ES ⑴ ⑶ A(a,b) US ⑵ ⑷ yA(a,y) EG ⑶ ⑸ xyA(x,y) UG ⑷ 例如A(x,y)表示:xy=0 论域:实数集合 ⑵中特指 b=0

89 判断下面的推理是否正确? ⑴ xy A(x,y) P ⑵ yA(a,y) US ⑴ ⑶ A(a,b) ES ⑵ ⑷ xA(x,b) UG ⑶ ⑸ yxA(x,y) EG ⑷ 似乎是有:xyA(x,y)yxA(x,y) 此式是错误的! 比如:令A(x,y):y是x的生母。论域:人类 xyA(x,y):每个人都有一个生母。 yxA(x,y):有一个人是大家的生母。 下面总结推理时的注意事项:

90 推理时注意事项: 1. 注意使用ES、US、EG、UG的限制条件。 2. 去量词: (1)对于同一个客体变元,既有带也有带的
前提,应先去,后去,这样才可以特指同一个 客体 c 。(称先局部,后全体) (2)被去的量词必须是公式的最左边的量词,且 此量词的前边无任何符号,它的辖域作用到公式 末尾。

91 ⑷ xy(P(x)∨Q(y)) T ⑶ E ⑸ y(P(a)∨Q(y)) ES ⑷ ⑹ P(a)∨Q(b)) ES ⑸
下面的作法是错误的: ⑴ xP(x)→yQ(y) P ⑵ xP(x)→Q(b) × ES ⑴ ⑶ P(a)→Q(b) × US ⑵ 正确作法是: ⑴ xP(x)→yQ(y) P ⑵ xP(x)∨yQ(y) T ⑴ E ⑶ xP(x)∨yQ(y) T ⑵ E ⑷ xy(P(x)∨Q(y)) T ⑶ E ⑸ y(P(a)∨Q(y)) ES ⑷ ⑹ P(a)∨Q(b)) ES ⑸ ⑺ P(a)→Q(b) T ⑹E 实际上,x的辖域扩充后量词改成为x

92 令P(x,y):y是x的生母,显然⑵是个假命题。
错误作法: ⑴ xP(x) P ⑵ P(c) US⑴ 待去量词前有 正确作法是:⑴ xP(x) P ⑵ xP(x) T⑴ E ⑶ P(c) ES ⑵ 实际上⑴中不是x而是x。 错误作法: ⑴ xyP(x,y) P ⑵ xP(x,c) ES⑴ 待去量词前有符号 正确作法是:⑴ xyP(x,y) P ⑵ yP(a,y) US ⑴ 令P(x,y):y是x的生母,显然⑵是个假命题。

93 从理论上来讲: 转换定律:X是公式A的子公式,且XY,如果用Y 替换A中X而得到B,则有AB。 但是:如果X是公式A的子公式,且XY,如果用Y 替换A中X而得到B,那么不一定有AB。 即不可以对一个子公式用永真蕴涵式右侧替换! 例如:P∧QP,而(P∧Q)P 是不成立的。 而US、ES、UG、和EG规则都是蕴涵式,所以不可 对一个子公式用这些规则。 xA(x)A(c) xA(x)A(c) A(c)xA(x) A(c)xA(x)

94 3.添加量词时: 量词也要加在公式的最左边, (即新加的量词前也无任何符号!!)且其辖域作 用到公式的末尾。 下面是错误的作法: ⑷ P(a)→Q(b) ⑸ xP(x)→Q(b) UG ⑴ × ⑹xP(x)→yQ(y) EG ⑵ × 正确作法: ⑸ x(P(x)→Q(b)) UG ⑴ ⑹ yx(P(x)→Q(y)) EG ⑵ 如果结论需要将量词放到里边,可通过量词辖域 缩小(扩充)公式实现。

95 本节要求: 熟练掌握谓词逻辑推理方法。 注意推理时的注意事项。 作业:79页 ⑴c)d) ⑵、⑶

96 第二章 小结 本章重点掌握内容: 1.各基本概念清楚。 2.会命题符号化。 3.熟练掌握等价公式和永真蕴涵式。 4.会写前束范式。 5.熟练掌握谓词逻辑的三种推理方法。

97 下面上第二章的习题课

98 第二章 习题课 一. 命题符号化 60页(2) a) 所有教练员是运动员。(J(x) L(x) ) x(J(x)→L(x))
一. 命题符号化 60页(2) a) 所有教练员是运动员。(J(x) L(x) ) x(J(x)→L(x)) b) 某些运动员是大学生。 (S(x) ) x(L(x)∧S(x)) c) 某些教练是年老的,但是健壮的。( O(x) V(x) ) x(J(x)∧O(x)∧V(x)) d) 金教练既不老,但也不是健壮的。( j ) J(j)∧O(j)∧V(j) e) 不是所有运动员都是教练。 x(L(x)→J(x)) 或者 x(L(x)∧J(x))

99 f) 某些大学生运动员是国家选手。(C(x) )
x(S(x)∧L(x)∧C(x)) g) 没有一个国家选手不是健壮的。 x(C(x)∧V(x)) 或者 x(C(x)→V(x)) h) 所有老的国家选手都是运动员。 x((O(x)∧C(x))→L(x)) i) 没有一位女同志既是国家选手又是家庭妇女。 (W(x) H(x) ) x(W(x)∧C(x)∧H(x))

100 j) 有些女同志既是教练又是国家选手。 x(W(x)∧J(x)∧C(x)) k) 所有运动员都钦佩某些教练。A(x,y) x(L(x)→y(J(y)∧A(x,y))) l) 有些大学生不钦佩运动员。 x(S(x)∧y(L(y)→A(x,y)))

101 62页(2)令P(x), L(x), R(x,y,z), E(x,y)分别
表示“x是一个点”,“x是一条直线”,“z通过x和 y”,“x=y”。符号化下面句子。 对于两个不同的点有且只有一条直线通过该两 点。 xy((P(x)∧P(y)∧E(x,y)) →z(L(z)∧R(x,y,z)∧t((L(t)∧R(x,y,t))→E(t,z)))) (3)b)对于每一个实数x,存在一个更大的实数y。 设R(x):x是实数,G(x,y):x>y x(R(x)→y(R(y)∧G(y,x)))

102 c) 存在实数x、y和z,使得x与y之和大于x与z之
积。 设R(x):x是实数,G(x,y):x>y f(x,y)=x+y g(x,y)=xy xyz(R(x)∧R(y)∧R(z)∧G(f(x,y),g(x,z))) 或者 xyz(R(x)∧R(y)∧R(z)∧G(x+y,xz)) (5)b) 没有一个数使数1是它的后继数。 设N(x):x是数,A(x,y):y是x的后继数 x(N(x)∧A(x,1))

103 (6)那位戴眼镜的用功的大学生在看那本大而厚的
巨著。 设A(x):x是戴眼镜的,B(x):x是用功的, C(x):x是大学生, D(x):x是大的, E(x):x是厚的, F(x):x是巨著, A(x,y):x在看y, a:那位, b:这本 A(a)∧B(a)∧C(a)∧D(b)∧E(b)∧F(b)∧ A(a,b)

104 P:2>1,Q(x):x≤3, R(x):x>5,a:5,{-2,3,6}
66页(3)b)求谓词公式的真值。 P:2>1,Q(x):x≤3, R(x):x>5,a:5,{-2,3,6} x(P→Q(x))∨R(a)(P→xQ(x))∨R(a) (P→(Q(-2)∧Q(3)∧Q(6)))∨R(5) (T→(T ∧T ∧F ))∨F (T→F)∨FF∨F F (4)b) 对约束变元换名 x(P(x)→(R(x)∨Q(x)))∧ xR(x)→zS(x,z) y(P(y)→(R(y)∨Q(y)))∧ tR(t)→uS(x,u) (5)a)对自由变元代入 (yA(x,y)→xB(x,z))∧ xzC(x,y,z) (yA(u,y)→xB(x,v))∧ xzC(x,w,z)

105 72页(2)d)用对谓词公式赋值后求真值。 论域为{1,2} P(1) P(2) Q(1,1) Q(1,2) Q(2,1) Q(2,2) F T T T F F xy(P(x)∧Q(x,y)) y(P(1)∧Q(1,y))∧y(P(2)∧Q(2,y)) ((P(1)∧Q(1,1))∨(P(1)∧Q(1,2)))∧ ((P(2)∧Q(2,1))∨(P(2)∧Q(2,2))) ((F∧T)∨(F∧T))∧((T∧F)∨(T∧F)) (F∨F)∧(F∨F)F

106 (6)判断下面推证是否正确。 x(A(x)→B(x)) ① x(A(x)∨B(x)) ② x(A(x)∧B(x) ③ x(A(x)∧B(x)) ④ (xA(x)∧xB(x)) ⑤ xA(x)∨xB(x) ⑥ xA(x)∨xB(x) ⑦ xA(x)→xB(x) 第④步错,由⑶到⑷用的是公式: x(A(x)∧B(x))(xA(x)∧xB(x)) 无此公式,而是 x(A(x)∧B(x)) xA(x)∧xB(x),应将⑷中的换成 即:

107 x(A(x)→B(x)) ① x(A(x)∨B(x)) ② x(A(x)∧B(x) ③ x(A(x)∧B(x)) ④ (xA(x)∧xB(x)) ⑤ xA(x)∨xB(x) ⑥ xA(x)∨xB(x) ⑦ xA(x)→xB(x) 因为由公式E18 P→QQ→P x(A(x)∧B(x)) xA(x)∧xB(x) , P Q 得 (xA(x)∧xB(x))x(A(x)∧B(x))

108 75页(1)b)把下面谓词公式化为前束范式 x(yP(x,y)→(zQ(z)→R(x))) x(yP(x,y)∨(zQ(z)∨R(x))) x(yP(x,y)∨(zQ(z)∨R(x))) x(yP(x,y)∨ z(Q(z)∨R(x))) xyz(P(x,y)∨ (Q(z)∨R(x)))

109 (2)c)把下面公式化成前束析取范式和前束合取
范式。 xP(x)→x(zQ(x,z)∨zR(x,y,z)) xP(x)∨x(zQ(x,z)∨zR(x,y,z)) xP(x)∨x(zQ(x,z)∨zR(x,y,z)) xP(x)∨u(zQ(u,z)∨tR(u,y,t)) xuzt(P(x)∨(Q(u,z)∨R(u,y,t))) xuzt(P(x)∨Q(u,z)∨R(u,y,t)) 此式既是前束析取范式,也是前束合取范式。

110 79页(2)a)用CP规则证明 x(P(x)∨Q(x) xP(x)∨x Q(x) 因为xP(x)∨x Q(x)xP(x)→x Q(x) ⑴ xP(x) P(附加前提) ⑵ xP(x) T ⑴ E ⑶ P(a) ES ⑵ ⑷ x(P(x)∨Q(x) P ⑸ P(a)∨Q(a) US ⑷ ⑹ Q(a) T ⑶⑸I ⑺ x Q(x) EG ⑹ ⑻ xP(x)→x Q(x) CP

111 (3)a)所有有理数是实数,某些有理数是整数,
因此某些实数是整数。 设Q(x):x是有理数 R(x):x是实数 I(x):x是整数 x(Q(x)→R(x)), x(Q(x)∧I(x))  x(R(x)∧I(x)) ⑴ x(Q(x)∧I(x)) P ⑵ Q(a)∧I(a) ES⑴ ⑶ Q(a) T ⑵ I ⑷ I(a) T ⑵ I ⑸ x(Q(x)→R(x)) P ⑹ Q(a)→R(a) US ⑸ ⑺ R(a) T ⑶⑹ I ⑻ R(a)∧I(a) T ⑷⑺ I ⑼ x(R(x)∧I(x)) EG⑻

112 b)任何人如果他喜欢步行,他就不喜欢乘汽车;每个人或者喜欢乘汽车或者喜欢骑自行车。有的人不爱骑自行车,因此有的人不爱步行。
设 A(x):x是人, B(x):x是喜欢步行, C(x):x喜欢乘汽车,D(x):x喜欢骑自行车 x(A(x)→(B(x)→C(x))), x(A(x)→(C(x)∨D(x))), x(A(x)∧D(x))  x(A(x)∧B(x))

113 ⑴ x(A(x)∧D(x)) P ⑵ A(a)∧D(a) ES ⑴ ⑶ A(a) T ⑵ I ⑷ D(a) T ⑵ I ⑸ x(A(x)→(B(x)→C(x))) P ⑹ A(a)→(B(a)→C(a)) US ⑸ ⑺ B(a)→C(a) T ⑶⑹ I ⑻ x(A(x)→(C(x)∨D(x))) P ⑼ A(a)→(C(a)∨D(a)) US⑻ ⑽ C(a)∨D(a) T ⑶⑼ I ⑾ C(a) T ⑷⑽ I ⑿ B(a) T ⑺⑾ I ⒀ A(a)∧B(a) T ⑶⑿ I ⒁ x(A(x)∧B(x)) EG ⒀

114 c)每个大学生不是文科生就是理工科生,有的大学生是优等生,小张不是理工科生,但他是优等生,因此如果小张是大学生,他就是文科生。
设 A(x):x是大学生, B(x):x是文科生, C(x):x是理工科生,D(x):x是优等生, a:小张 x(A(x)→(B(x)→C(x))), x(A(x)∧D(x)) C(a)∧D(a)  A(a)→B(a)

115 ⑵ x(A(x)→(B(x)→C(x))) P ⑶ A(a)→(B(a)→C(a)) US ⑵ ⑷ B(a)→C(a) T ⑴⑶I
x(A(x)→(B(x)→C(x))),x(A(x)∧D(x)) C(a)∧D(a)  A(a)→B(a) ⑴ A(a) P(附加前提) ⑵ x(A(x)→(B(x)→C(x))) P ⑶ A(a)→(B(a)→C(a)) US ⑵ ⑷ B(a)→C(a) T ⑴⑶I ⑸ C(a)∧D(a) P ⑹ C(a) T ⑸I ⑺ B(a) T ⑷⑹ I ⑻ B(a) T ⑺ E ⑼ A(a)→B(a) CP

116 补充题:小杨、小刘和小林为高山俱乐部成员,该俱乐
部的每个成员是个滑雪者或登山者。没有一个登山者喜 欢雨。而所有滑雪者都喜欢雪。凡是小杨喜欢的,小刘 就不喜欢。小杨喜欢雨和雪。试证明该俱乐部是否有个 是登山者而不是滑雪者的成员。如果有,他是谁? 设:M(x):x是高山俱乐部成员。H(x):x是滑雪者。 D(x):x是登山者。L(x,y):x喜欢y。 a:小杨;b:小刘;c:小林;d:雨;e:雪。 命题符号化为: M(a), M(b), M(c), x(M(x)→( H(x)∨D(x))), x(D(x)∧L(x,d)), x(H(x)→L(x,e)) y(L(a,y)→L(b,y)), L(a,d)∧L(a,e)

117 ⑴ L(a,d)∧L(a,e) P ⑵ L(a,e) T ⑴ ⑶ y(L(a,y)→L(b,y)) P ⑷ L(a,e)→L(b,e)) US ⑶ ⑸ L(b,e)) T ⑵ ⑷ I11 ⑹x(H(x)→L(x,e)) P ⑺ H(b)→L(b,e)) US ⑹ ⑻ H(b) T ⑸ ⑺ I12 ⑼ x(M(x)→(H(x)∨D(x))) P ⑽ M(b)→(H(b)∨D(b)) US ⑼ ⑾ M(b) P ⑿ H(b)∨D(b) T ⑽ ⑾ I11 ⒀ D(b) T ⑻ ⑿ I10 ⒁ D(b)∧H(b) T ⑻ ⒀

118 第二章 谓词逻辑 到此结束


Download ppt "第二章 谓词逻辑."

Similar presentations


Ads by Google