离散数学的谓词逻辑详解.ppt

《离散数学的谓词逻辑详解.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2021/7/251谓词逻辑2021/7/252命题逻辑的局限性苏格拉底三段论：P：所有的人都是要死的。Q：苏格拉底是人。R：所以苏格拉底要死。凭直觉知道这个结论是真的，推理是有效的。但是，借助命题演算的推理理论，却不能推导出这个结论（无法证明它的正确性）。Why?2021/7/253此三段论的论断显然正确。但是，在命题逻辑中无法得到正确性的反应:P∧QR不是重言式！命题逻辑不能正确反映此三段论的推理过程。这是命题逻辑的局限性!2021/7/254原因在命题逻辑中无法将简单命题之间的内在联系反映出来。命题逻辑中描述的上述三段论，即

2、P∧Q→R，使R与命题P、Q无关的独立命题。但是，实际上R与命题P、Q是有关系的，只是这种关系在命题逻辑中得不到反映。要反映这种内在联系，需对简单命题作进一步分解，分解出其中的成份，包括：个体词，谓词，量词，函词等，研究它们的形式结构及逻辑关系，总结出正确的推理形式和规则，这就是一阶逻辑所研究的内容.一阶逻辑也称谓词逻辑。谓词逻辑是一种表达能力更强的逻辑。2021/7/255谓词逻辑我们将介绍谓词逻辑的基本概念和符号。关于命题、命题的真值、命题词、命题常量和命题变元以及逻辑五个联结词其含意和在命题逻辑中的基本相同，本章中只介绍谓词逻

3、辑中新出现的基本概念和符号，其中主要的是个体词，谓词，量词以及函词。2021/7/2561.谓词与个体词将简单命题分解成个体与谓词这样两个组成部分。谓词，通常是用来描述个体的性质或特征，或者个体之间的关系。谓词逻辑，是命题逻辑的扩充与发展。例1：下面两个命题1.张华是学生2.李明是学生a:张华b:李明H：是学生，则H（x）:x是学生1，2可分别表示成H(a)，H(b).这样表示就揭示了两命题间有相同的谓语这一特征。2021/7/257例2：张华比李明高令a:张华b:李明L(x，y):x高于y该命题可表示为：L(a，b)例1和例2中的

4、H、L称为谓词，其中H是一元谓词，表示个体的性质（是什么），L是二元谓词，表示个体之间的关系。注：（1）常用大写拉丁字母表示谓词.（2）谓词是用来刻划个体的性质或者个体之间的关系的。2021/7/258命题函数与命题例:令P(x)表示x为质数，则P(x)为一元谓词。令H(x，y)表示“x高于y”,则H(x，y)为二元谓词。则：H(张三，李四)表示“张三高于李四”，是命题。注意：P(x.y),H(x，y)为命题函数.P(2)与H(张三，李四)才是命题。谓词中如果有n个变元则称为n元谓词.n元谓词反映了个体之间的n元关系.2021/7/

5、2592.个体词个体是可以独立存在的实体，它可以是一个具体的事物---个体常元，常用小写拉丁字母a，b，c等表示。也可以是一个抽象的概念（即没指定哪一个个体）----个体变元，常用小写拉丁字母：x，y，z等表示．2021/7/2510函词例：张华的哥哥比李明高a:张华b:李明L(x，y):x高于yf(x):x的哥哥则上述符号化为：L(f(a)，b)f称为函词定义：一个n元函词即是一个论域Ｄ上的一个n元函数．2021/7/2511变元在谓词中的次序直接影响了谓词的取值。如:设谓词P(x，y)为“x比y高”，设张三为170cm，李四为1

6、80cm.则:P(李四，张三)为真命题。P(张三，李四)为假命题.概念的讨论2021/7/2512命题的符号化例1:武汉位于重庆与上海之间.解:用个体词a，b，c分别表示武汉，重庆和上海，谓词P(x，y，z)表示x位于y与z之间，则该命题表示为:P(a，b，c).例2：如果王英坐在李红的后面，则王英比李红高.解：令a:王英;b:李红;P(x，y):x坐在y的后面;G(x，y):x比y高.则该命题表示为：P(a，b)G(a，b).2021/7/25133.量词使用前面介绍的概念，还不足以表达日常生活中的各种命题。例如：“所有的正整数

7、都是素数”“有些正整数是素数”两种量词:全称量词和存在量词.2021/7/2514全称量词:1.全称量词：（任意，所有）x:“对一切x”，“对所有的x”，“对任一x”如：xP(x)“对一切x，P(x)是真”┐xP(x)“并非对一切x，P(x)是真”x┐P(x)“对一切x，┐P(x)是真”如:“所有人都是要死的”设x的个体域为全体人的集合，则可表示为xD(x)2021/7/2515存在量词:2.存在量词：（存在）x:“存在x“、”某些x“、”至少有一x”如：xP(x)“存在x，P(x)是真”┐xP(x)“存在x

8、，P(x)是真，并非这样”x┐P(x)“存在x，┐P(x)是真”如:“有些有理数是整数。”令Ｉ(x）：x是整数，设x的个体域为有理数集合，则命题可表示为：xI(x）2021/7/25164.论域含有量词的命题的表达式的形式，与论域