离散数学_谓词逻辑

第二章

谓词逻辑

在命题逻辑中，命题被当作一个基本的， 在命题逻辑中，命题被当作一个基本的，不可分割的 单位，只研究由原子命题和联接词所组成的复合命题； 单位，只研究由原子命题和联接词所组成的复合命题；因 而无法研究命题的内部结构及命题之间内在的联系。 而无法研究命题的内部结构及命题之间内在的联系。本章 介绍的谓词逻辑，对原子命题的成份、 介绍的谓词逻辑，对原子命题的成份、结构和原子命题间 的共同特性等作了进一步分析。引入了个体词、谓词、 的共同特性等作了进一步分析。引入了个体词、谓词、量 谓词公式等概念， 词、谓词公式等概念，在此基础上研究谓词公式间的等值 关系和蕴含关系， 关系和蕴含关系，并且对命题逻辑中的推理规则进行扩充 和进行谓词演绎。 和进行谓词演绎。 主要内容如下： 主要内容如下： 谓词、 谓词、个体词和量词 谓词演算公式 谓词演算的永真公式 谓词演算的推理理论

谓词、 谓词、个体词和量词 例对下述论断无法判断其正确性。 在命题逻辑中 ，对下述论断无法判断其正确性。 “苏格拉底三段论” : 苏格拉底三段论” 凡人都是要死的， 凡人都是要死的， 苏格拉底是人， 苏格拉底是人， 所以苏格拉底是要死的。 所以苏格拉底是要死的。 还有许多。 类似的例 还有许多。 所有的人都要呼吸 , 李莉是人 , 所以李莉要呼吸。 所以李莉要呼吸。 例如： 例如： 所有的正整数都大于0, 所有的正整数都大于 3是正整数 是正整数, 是正整数 所以3大于 。 所以 大于0。 大于 2

一、个体词和谓词在谓词演算中， 在谓词演算中，可将原子命题分解为谓词与个 体词两部分。 体词两部分。

定义2-1 定义

是指可以独立存在的客体。 个体是指可以独立存在的客体。

个体可以是抽象的，也可是具体的。 注 个体可以是抽象的，也可是具体的。个体通常 在一个命题里表示思维对象。 在一个命题里表示思维对象。

定义2-2 用来刻划个体的性质或个体之间关系的 定义 词称为谓词，刻划一个个体性质的词称为一元谓词； 刻划n个个体之间关系的词称为 元谓词 刻划 个个体之间关系的词称为n元谓词。 例1 (1)李明是学生； (2)张亮比陈华高； )李明是学生； )张亮比陈华高；(3)陈华坐在张亮与李明之间。 )陈华坐在张亮与李明之间。 在这三个命题中，李明、张亮、陈华都是个体； 在这三个命题中，李明、张亮、陈华都是个体； 是学生” “…是学生”是一元谓词， “…比…高”是二元谓 是学生 是一元谓词， 比 高 之间” 词， “…坐…与…之间”是三元谓词。 坐 与

之间 是三元谓词。

通常，我们用大写字母表示谓词， 通常，我们用大写字母表示谓词，小写字母 表示个体。 表示个体。 上述命题可分别表示为 Q(a), P(b,c), ( ( ), R(c,b,a)。 ( )。 一般地，一个由n个个体和 元谓词所组成的 个个体和n元谓词所组成的 一般地，一个由 个个体和 命题可表示为F( 其中F表示 元谓词, 命题可表示为 (a1,a2, … ,an),其中 表示 元谓词 其中 表示n元谓词 a1,a2, … ,an 分别表示n个个体。 分别表示 个个体。 个个体 注意： 的排列次序是重要的。 注意：a1,a2, … ,an的排列次序是重要的。 4

二、个体变元和命题函数 表示具体或特定的个体的个体词称为个体常元。 个体常元 表示具体或特定的个体的个体词称为个体常元。表示抽象的，或泛指的(或者说取值不确定的) 个体变元 表示抽象的，或泛指的(或者说取值不确定的) 个体称为个体变元。 个体称为个体变元。 例2 设 H是表示谓词“…能够到达山顶”,若个体w:王 是表示谓词“ 能够到达山顶” 若个体 王 是表示谓词 能够到达山顶 ),H( ), ),H( ) 红；t:老虎；s:汽车，则H(w), (t), (s)分别表 ：老虎； :汽车， ( ), 示“王红能够到 达山顶。”“老虎能够到达山顶。”“汽车 达山顶。”“老虎能够到达山顶 ”“汽车 老虎能够到达山顶。 能够到达山顶。 这里 、 、 均是个体常元 均是个体常元。 能够到达山顶。”这里w、t、s均是个体常元。 H(x): 能够到达山顶。这里的 是泛指的，不确定的， ( ): 能够到达山顶。这里的x是泛指的 不确定的， ):x能够到达山顶 是泛指的， x可在一定的范围内取值。故x是个体变元。 可在一定的范围内取值。 是个体变元。 可在一定的范围内取值 是个体变元

例3 L(x,y,z)表示“x+y=z”,其中 ( )表示“ 其中x,y,z为个体变元。 为个体变元。 其中 为个体变元L(3,2,5)表示真命题“3+2=5”, ( , , )表示真命题“ , 而L(1,2,4)表示假命题“1+2=4”。 ( , , )表示假命题“ 。

定义2-3 定义

由一个谓词和若干个个体变元组成的命题形式称

表示为P(x 为简单命题函数，表示为 1,x2,…,xn)。由一个或若干个简单 。 命题函数以及逻辑联结词组成的命题形式称为复合命题函数。 均是简单命题函数。 例如 H(x),L(x,y,z)均是简单命题函数。 , 均是简单命题函数 (P(x,y)∨L(x,y,z)) ∨ P(y, x)是一复合命题函数 是一复合命题函数

在命题函数中， 在命题函数中，个体变元的取值范围称为个体域。 表示“ 的个体域为正整数集， 例4 P(x,y)表示“2 x+y=1”,若x,y的个体域为正整数集， 表示 ， 的

个体域为正整数集 则总是假； 则总是假； 的个体域为有理数集， 若x,y的个体域为有理数集，则y=1―2x,对任意的有理数 ， 的个体域为有理数集 ，对任意的有理数k 为真。 在x= k,y =1―2k时，P(k,1―2k)为真。 , 时 为真

三、量词和全总个体域 1.量词 量词使用前面介绍的概念， 使用前面介绍的概念，还不足以表达日常生活中 的各种命题。 的各种命题。

例如：对于命题 “ 所有的正整数都是素数 ”和 “ 有些正整数是素数 ” 仅用个体词和谓词是很难表达的。 仅用个体词和谓词是很难表达的。 在命题里表示数量的词。 量词 在命题里表示数量的词。

(1) 全称量词 )

如“所有人都是要死的。”可表示为 x D(x), 所有人都是要死的。 ( ), x的个体域为全体人的集合。 的个体域为全体人的集合。 的个体域为全体人的集合

“ x”

(2)存在量词 “ x ” ) 有些有理数是整数。 如 “有些有理数是整数。” ):x是整数 令I(x): 是整数； ): 是整数； xI ) 于是命题可表示为 (x) I 其中x的个体域为有理数集合。 其中 的个体域为有理数集合。 的个体域为有理数集合 (3)存在唯一量词 “ x ” ) ! 方程x+1=0存在唯一的整数解。” 存在唯一的整数解。 如 “方程 存在唯一的整数解 ):x是 的整数解。 令P(x): 是x+1=0的整数解。 ( ): 的整数解 !x ( ), 则命题可表示为 P(x), 其中x的个体域为整数集。 其中 的个体域为整数集。 的个体域为整数集 8

2.全总个体域 .含有量词的命题的表达式的形式， 含有量词的命题的表达式的形式，与个体 含有量词的命题的真值与个体域也有关。 含 含有量词的命题的真值与个体域也有关 域有关。 域有关。 有量词的命题的真值与个体域也有关。 因此，为了方便，我们引入全总个体域的概念。 因此，为了方便，我们引入全总个体域的概念。 定义2―5 宇宙间所有的个体聚集在一起所 定义 构成的集合称为全总个体域。 后面的讨论中，除特殊说明外， 后面的讨论中，除特殊说明外，均使用全总 个体域。而对个体变化的真正取值范围， 个体域。而对个体变化的真正取值范围，用特性 谓词加以限制。 谓词加以限制。 一般地，对全称量词， 一般地，对全称量词，此特性谓词作蕴含的 前件；对存在量词，此特性谓词常作合取项。 前件；对存在量词，此特性谓词常 …… 此处隐藏：4821字，全部文档内容请下载后查看。喜欢就下载吧 ……