离散数学第二章.ppt

第二章谓词逻辑§1谓词的概念与表示§2命题函数与量词§3谓词公式与翻译§4变元的约束§5谓词演算的等价式与蕴含式§6前束范式§7谓词演算的推理理论§1谓词的概念与表示

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

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

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

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

“所有的人总是要死的。A“苏格拉底是人。B“所以苏格拉底是要死的。”C§1谓词的概念与表示1.谓词：《定义》：用以刻划客体的性质或关系的即是谓词。

我们可把原子命题分解为二部分：主语（名词，代词）和谓语（动词）。例：张华是学生，李明是学生。则可把它表示成：H:表示“是学生”，j:表示“张华”，m:表示“李明”，则可用下列符号表示上述二个命题：H(j)，H(m)。

§1谓词的概念与表示（1）若谓词字母联系着一个客体，则称作一元谓词；若谓词字母联系着二个客体，则称作二元谓词；若谓词字母联系着n个客体，则称作n元谓词。（2）客体的次序必须是有规定的。

例：河南省北接河北省。nLb

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

§2命题函数与量词1.命题函数客体在谓词表达式中可以是任意的名词。

例：C—“总是要死的。”j：张三；t：老虎；e：桌子。则C(j),C(t),C(e)均表达了命题。

在上面的例子中，C：表示“总是要死的”；x：表示变元（客体变元），则C(x)表示“x总是要死的”，则称C(x)为命题函数。《定义》由一个谓词字母和一些非空的客体变元的集合所组成的表达式，称为简单命题函数。

§2命题函数与量词讨论定义：

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

（b）若用任何客体去取代客体变元之后，则命题函数就变为命题；

（c）命题函数中客体变元的取值范围称为个体域（论述域）。例：P(x)表示x是质数。这是一个命题函数。其值取决于个体域。个体域（论述域，客体域）:用特定的集合表示的客体变元的取值范围。§2命题函数与量词个体域的给定形式有二种：①具体给定。如：｛j,e,t｝②全总个体域?任意域：将各种个体域综合在一起作为论述范围的域称全总个体域。§2命题函数与量词2.量词（1）全称量词

“?”为全称量词符号，读作“对于所有的”，“对任一个”，“对一切”。

例：“这里所有的都是苹果”可写成：?xA(x)或(?x)A(x)几种形式的读法：

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

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

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

·??x?P(x)：“并不是所有的x，x不是…”。§2命题函数与量词例：将“对于所有的x和任何的y，如果x高于y，那么y不高于x”写成命题表达形式。

解：?x?y(G(x,y)??G(y,x))

G(x,y)：x高于y（2）存在量词

“?”为存在量词符号，读作“存在一个”，“对于一些”，“对于某些”，“至少存在一个”，“这里存在着这样的”等等。“?”表达式的读法：

·?xA(x)：存在一个x,使x是…；

·?x?A(x)：存在一个x,使x不是…；

·??xA(x)：不存在一个x,使x是…；

·??x?A(x)：不存在一个x,使x不是…。§2命题函数与量词例：（a）存在一个人；（b）某个人很聪明；（c）某些实数是有理数将（a）,（b）,（c）写成命题。解：规定：M(x)：x是人；C(x)：x是很聪明；

R(x)：x是实数(特性谓词)Q(x)：x是有理数。则（a）?xM(x)；（b）?x(M(x)?C(x))；（c）?x(R(x)?Q(x))。（3）量化命题的真值：决定于给定的个体域给定个体域：{a1…an}以{a1…an}中的每一个代入

?xP(x)?P(a1)?…?P(an)