第二章 谓词逻辑

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

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

解决这个问题的方法： 在表示命题时，既表示出主语(主词)，也表示出谓语(谓 词)，就可以解决上述问题。这就提出了谓词的概念。 令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)就是所谓的谓词。

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

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元谓词。

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

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

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

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

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

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

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

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)))

例题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….表示 客体之间的函数关系，称之为客体函数。 注意:客体函数与谓词是不同的,不可混淆。

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

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

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是Ａ中的任何客体变元， 则xＡ和xＡ也是合式公式。 5.只有有限次地按规则(1)至(4)求得的公式才是 合式公式。 谓词合式公式也叫谓词公式，简称公式。

下面都是合式公式： 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后边的括号不 是最外层括号，所以不可以省略。

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的辖域

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

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

定义：如果客体变元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是自由变元。

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

(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的一元谓词了。

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

例如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))

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

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

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

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

先介绍两个公式： 令论域为{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))也为真。

而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))不能表示这个命题。

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))

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)

练习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)))

小结 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)))

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

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

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

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

定义：给定谓词公式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)。

定义：给定谓词公式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)。

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) 摩根定律

二.带量词的公式在论域内的展开式 先看一个例子，令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)

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

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

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) 类似可以证明另一个公式。 从这两个公式，可以总结出如下规律：将量词前 的“”移到量词的后边，或者将量词后的“”移到 量词的前边时，量词也随着改变，如果原来是全 称量词改成存在量词，如果原来是存在量词改成 全称量词。所以我们也把这两个公式称为量词转 换公式。

四.量词辖域的扩充公式 如果Ｂ是个不含客体变元x的谓词公式，且不 在x和x的辖域内，可以将Ｂ放入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(Ａ(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)

证明：设论域为{a1,a2,....,an}， 上述公式我们只证明三个。 xA(x)∨B(A(a1)∧A(a2)∧...∧A(an))∨B (A(a1)∨B)∧(A(a2)∨B)∧...∧(A(an)∨B) x(Ａ(x)∨Ｂ) 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.时，要特别注意，量词的辖 域扩充后，量词发生了变化。

五.量词分配公式 证明：设论域为{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)

注意公式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)).

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

下面利用公式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.的时候，特别要注意蕴含 式的方向，不要搞错。

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))

七．两个量词的公式 在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”,这是一个为“假”的命 题。

有如下一些公式： 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)

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)

(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)

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

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

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) 就不是前束范式。

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

例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)) (量词分配公式)

例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)))

下面同学动手做练习。 写出第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))) (扩量词辖域) 此式是前束析取范式。

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

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

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

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

例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

分析一下，下面作法是否正确？ ⑴ 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－是老沈阳人 应由谁先提出约会地点？(先局部后全体)

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

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

例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

例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 ⑸

例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 ⑸ 如果有问题，问题在哪里？

例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))

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 ⑼

课堂练习：证明下面推理的有效性： “鸟都会飞。猴子都不会飞。所以，猴子都不是鸟。” 设 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 ⑹

课堂练习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)

例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))

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

例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

下面请同学作课堂练习 用反证法证明例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 下面请同学作课堂练习

给定谓词如下：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))

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 ⒀ I2 ⒄ T(b) T⒁ ⒃ I11 ⒅T(b)L(b) T ⒂ ⒄I9 ⒆ y(T(y)L(y)) EG ⒅

用推理证明公式： 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

判断下面的推理是否正确？ ⑴ 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)：有一个人是大家的生母。 下面总结推理时的注意事项：

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

⑷ 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

令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的生母，显然⑵是个假命题。

从理论上来讲： 转换定律：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)

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 ⑵ 如果结论需要将量词放到里边,可通过量词辖域 缩小(扩充)公式实现。

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

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

下面上第二章的习题课

第二章 习题课 一. 命题符号化 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))

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))

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)))

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)))

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))

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

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)

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

(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)，应将⑷中的换成 即：

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))

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)))

(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)) 此式既是前束析取范式，也是前束合取范式。

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

(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⑻

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))

⑴ 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 ⒀

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)

⑵ 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

补充题：小杨、小刘和小林为高山俱乐部成员，该俱乐 部的每个成员是个滑雪者或登山者。没有一个登山者喜 欢雨。而所有滑雪者都喜欢雪。凡是小杨喜欢的，小刘 就不喜欢。小杨喜欢雨和雪。试证明该俱乐部是否有个 是登山者而不是滑雪者的成员。如果有，他是谁？ 设：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)

⑴ 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 ⑻ ⒀

第二章 谓词逻辑 到此结束