离散数学课件第二章(第1讲)

第二章谓词逻辑§1基本概念§2谓词逻辑的翻译§3谓词公式的解释§4谓词演算的等价式与蕴含式§5前束范式§6谓词逻辑演的推理理论§1基本概念

在研究命题逻辑中，原子命题是命题演算中最基本的单位，不再对原子命题进行分解.这样会产生二大缺点：

（1）不能研究命题的结构，成分和内部逻辑的特征；

（2）也不可能表达二个原子命题所具有的共同特征，甚至在命题逻辑中无法处理一些简单又常见的推理过程。

例：苏格拉底论证是正确的，但不能用命题逻辑的推理规则推导出来。

“所有的人总是要死的。P“苏格拉底是人。Q“所以苏格拉底是要死的。”R1.谓词《定义》：用以刻划客体的性质或关系的即是谓词。

我们可把原子命题分解为二部分：主语（名词，代词）和谓语（动词）。例：张华是学生，李明是学生。则可把它表示成：

H:表示“是学生”，j:表示“张华”，m:表示“李明”，则可用下列符号表示上述二个命题：H(j)，H(m)。

H作为“谓词”用大写英文字母表示，j,m称为“客体”或称“个体”。客体一般用小写的英文字母表示。分析：（1）若谓词字母联系着一个客体，则称作一元谓词；若谓词字母联系着二个客体，则称作二元谓词；若谓词字母联系着n个客体，则称作n元谓词。（2）客体的次序必须是有规定的。例：河南省北接河北省。

nLb写成二元谓词为：L(n,b)，但不能写成L(b,n)。

2.命题函数客体在谓词表达式中可以是任意的名词。例：C—“是有颜色的。”

g：水果；y：树叶；f：衣服。则C(g),C(y),C(f)都是命题。在上例中，如果用x表达任意的客体，则x表示客体变元，C(x)表示“x是有颜色的”，则称C(x)为命题函数。《定义》由一个谓词字母和一些非空的客体变元的集合所组成的表达式，称为简单命题函数。

讨论：

（a）当简单命题函数仅有一个客体变元时，称为一元简单命题函数；

（b）若用某一特定客体去取代客体变元之后，则命题函数就变为命题；（c）命题函数中客体变元的取值范围称为个体域（论述域）。（d）个体域（论述域）:用特定的集合表示的客体变元的取值范围。例：P(x)表示x是素数。这是一个命题函数。其值取决于个体域。个体域的给定形式有二种：①具体给定。如：｛j,e,t｝②全总个体域任意域：将各种个体域综合在一起作为论述范围的域称全总个体域。命题函数可以转变为命题，有两种方法：a)将x取定一个值。如：P(4)，P(5)b)将谓词量化。如：xP(x)，xP(x)3.量词（1）全称量词

“

”为全称量词符号，读作“所有的”，“任意的”，“每个”。

例：“这里所有的都是苹果”可写成：

xA(x)或(

x)A(x)全称量词的几种形式的读法：

·

xP(x)：“对所有的x，x是…”；

·

x¬P(x)：“对所有x，x不是…”；

·

¬

xP(x)：“并不是对所有的x，x是…”；

·

¬

x¬P(x)：“并不是所有的x，x不是…”。例：将“对于所有x和所有y，如果x高于y，那么y不高于x”写成命题表达形式。

解：G(x,y)：x高于y

xy(G(x,y)¬G(y,x))

（2）存在量词

“

”为存在量词符号，读作“存在一个”，“有些”，“某些”，“至少存在一个”等等。存在量词的几种形式的读法：

·

xA(x)：存在x,使x是…；

·

x¬A(x)：存在x,使x不是…；

·

¬

xA(x)：不存在x,使x是…；

·

¬

x¬A(x)：不存在x,使x不是…。为什么将谓词量化，命题函数可以转变为命题？设给定个体域：{a1…an},以{a1…an}中的每一个个体代入

则：

xP(x)

P(a1)

…

P(an)

xQ(x)

Q(a1)

…

Q(an)

例如：Q(x)表示:x<5

{-1,0,3}{-3,6,2}{15,30}

xQ(x)TFF

xQ(x)TTF注：个体域不同，则表示同一命题的值不同。4.谓词公式

原子谓词公式：不出现命题联结词和量词的谓词命名式称为原子谓词公式，并用P(x1…xn)来表示。（P称为n元谓词，x1…xn称为客体变元）。

《定义》（谓词公式的归纳法定义）⑴原子谓词公式是谓词公式；⑵若A是谓词公式，则¬A也是谓词公式；⑶若A,B都是谓词公式，则(AB),(AB),(AB),(AB)都是谓词公式；⑷若A是谓词公式，x是任何变元，则

xA,

xA也都是谓词公式；⑸当且仅当有限次地应用⑴-⑷所求得的那些公式才是谓词公式。5.自由变元与约束变元(1)辖域：紧跟在量词后面括号内的谓词公式，叫做相应量词的作用域或辖域。例：

x(P(x)),

x(P(x)Q(x))

P(x)是全称量词的辖域，P(x)Q(x)是存在量词的辖域。若量词后括号内为原子谓词公式，则括号可以省去。例：

x(P(x))

xP(x)

辖域举例①在

xP(x)Q(x)中,x的辖域是P(x);②在

y(C(y)∧x(T(x)uQ(x,u)))中,u的辖域是：Q(x,u);x的辖域是：T(x)uQ(x,u);y的辖域是：

C(y)∧x(T(x)uQ(x,u)).(2)自由变元与约束变元约束变元：位于量词的辖域内，并且与量词下标相同的变元。自由变元：当且仅当不受量词约束的变元。例：

xP(x,y),

xP(x)Q(y)

在谓词公式

xP(x,y)中，x是约束变元，y是自由变元。在谓词公式

xP(x)Q(y)中，x是约束变元，y是自由变元。注：自由变元可以位于量词的辖域内，也可以不在量词的辖域内。(3)区别是命题还是命题函数的方法

（a）若谓词公式中有自由变元，则该公式为命题函数；（b）若谓词公式中的变元都是约束变元，则该公式为命题。或者说若谓词公式中没有自由变元出现，则该公式是一个命题。例：

xP(x,y,z)是二元命题函数

yxP(x,y,z)是一元命题函数

yxP(x,y)是命题(4)约束变元的改名规则

我们认为xP(x,y)和zP(z,y)是等价的谓词公式，所以任何谓词公式对约束变元都可以改名。但是，不能用同一个变元去表示谓词公式中的二个不同变元。例如：xP(x,y)和yP(y,y)是不等价的。约束变元的改名规则：

（a）改名时所用的变元符号在量词辖域内未出现的；（b）在改名时要把公式中所有相同的约束变元全部同时改掉。例：xP(x)yR(x,y)可改写成:xP(x)zR(x,z)但不能改成:xP(x)xR(x,x)因为在谓词公式xR(x,x)中，前面的x原为自由变元，现在变为约束变元了。(5)自由变元的代入规则

对谓词公式中的自由变元的更改叫做代入。

(a)用以代入的变元与原公式中所有变元的名称不能相同。

(b)对公式中出现该自由变元的每一处都进行代入。§2谓词公式的翻译一般来说，将自然语言翻译成谓词公式主要有以下几个步骤：

（1）确定个体域，如无特别说明，一般使用全总个体域；（2）根据个体域，分析命题中的个体、个体性质以及各个个体间的关系，确定谓词；（3）根据表示数量的词确定量词；如果使用全总个体域，则要加入特性谓词。（4）利用联结词将整个命题符号化。例：某个人很聪明。令C(x)：x很聪明。下面给出不同的个体域来讨论命题的翻译：①个体域为：{人类}则可翻译为:

xC(x)；②个体域为任意域（全总个体域），则人必须首先从任意域中分离出来。设M(x)表示：x是人，M(x)为特性谓词。

则可翻译为:

x(M(x)

C(x))特性谓词：用来限制个体变元取值范围的谓词。(2)对于同一个体域，用不同的量词时，特性谓词加入的方法不同。

对于全称量词，其特性谓词以条件联结词的前件的方式加入；

对于存在量词，其特性谓词以合取的形式加入。注:(1)个体域不同，表示同一命题的谓词公式的形式不同。

例：（1）每个学生都要参加考试。令S(x)：x是学生（特性谓词）T(x):x要参加考试

可翻译为:

x(S(x)

T(x))

（2）一些人是聪明的。令M(x):x是人（特性谓词）C(x)：x是聪明的。可翻译为:

x(M(x)∧C(x))

解：设I(x):x是整数；（特性谓词）R1(x)：x是正数；R2(x)：x是负数。此句可翻译为：

x(I(x)(R1(x)

R2(x))。例：任何整数或是正的，或是负的。例：试将苏格拉底论证符号化：“所有的人总是要死的。因为苏格拉底是人，所以苏格拉底是要死的。”

解：设M(x)：x是人；（特性谓词）D(x)：x是要死的；

M(s)：苏格拉底是人；D(s)：苏格拉底是要死的。则翻译为：

x(M(x)

D(x))，M(s)

D(s)例：“没有不犯错的人。”

解：设F(x)为“x犯错误”，M(x)为“x是人”（特性谓词）。则可翻译为：¬(

x(M(x)

¬

F(x)))也可以翻译为：

x(M(x)F(x))解：T(x):x坐头等舱J(x):x坐经济舱F(x):x家境富裕前提：x(T(x)

J(x)),

x(T(x)

F(x))

,

xF(x),

xF(x)

例：每个乘客或坐头等舱或坐经济舱；每个乘客当且仅当其家境富裕时坐头等舱；有些乘客家境富裕；并非所有的乘客都家境富裕。因此，有些乘客坐经济舱。（个体域为全体乘客构成的集合）结论：

xJ(x)则 可翻译为：

(x)(S(x)L(x)H(x)G(x)S(x))由于对个体描述性质的刻划深度不同，可翻译成不同形式的谓词公式。例

：在南京高校学习的学生，未必都是南京籍的学生。设S(x)：x是南京高校学习的学生。F(x)：x是南京籍的学生。则翻译为：

x(S(x)F(x))

本题也可加深刻划：S(x)：x是学生。L(x)：x在学习。