离散数学 谓词逻辑.ppt

第二章谓词逻辑
1
在命题逻辑中,原子命题是进行演算的基本单位,不研究命题的内部结构以及命题之间的内在联系,因而,命题逻辑中的推理有很大的局限性。例如,著名的苏格拉底三段论:
所有的人都是要死的,
苏格拉底是人,
所以苏格拉底是要死的。
符号化:
分别用P、Q、R表示以上三个命题,则P∧Q→R表示这一推理过程。
蕴含式P∧Q→R不是重言式,虽然凭我们的直觉这个论断正确,在内部逻辑中却无法证明。
谓词逻辑的任务就是对原子命题作进一步的分析,研究其内部的逻辑结构,并在此基础上更深入地刻画推理。
2
谓词逻辑:原子命题=客体词+谓词
命题所陈述的对象称为客体词。它可以是一个具体的事物,也可以是一个抽象的概念。例如,李明、自然数、思想等都可以作为客体词。
定义用来刻画客体词的性质或客体词之间的关系的词称为谓词。
例如:
π是无理数。
小李是计算机系的学生。
李明比王宏高2厘米。
“π”、“小李”、“李明”、“王宏”都是客体词;
“……是无理数”“……是计算机系的学生”“……高2厘米”都是谓词。前两个谓词表示客体词的性质,而后一个谓词描述客体词之间的关系。

3
谓词的表示
客体词有两种:客体常元和客体变元。客体常元表示具体的或特定的客体,一般用小写字母a、b、c等表示;表示抽象的或泛指的客体的词称为客体变元,常用小写字母x、y、z等表示。
谓词,通常用大写的字母A、B、C等表示。
谓词填式:单独一个谓词不是完整的命题,把谓词字母后填以客体所得的式子。
4
例子
[例2-] 张明是位大学生。
解:设S(x):x是大学生,c:张明,
则原句的谓词形式为S(c)。
[例2-]我坐在张三和李四中间。
解:设S(x,y,z):x坐在y和z之间,i:我,z:张三,l:李四,
则原句的谓词形式为S(i,z,l)。
一元谓词:表示客体性质
多元谓词:表示客体间关系
5
一般来说,谓词P(x1 ,…,xn)不是命题,真值无法确定,只有当n 个客体常元代替 x1,x2 ,…, xn 这n个客体变元之后,才有了确定的真值,因而也就成了命题。
例如,L(x,y) 是表示x小于y的二元谓词,它的真值不能确定,当以2(用a 表示)、3(用b表示)替换x和y之后,L(a,b)成为真命题。
6

例子:
假设谓词H表示“能够到达山顶”,客体p表示李四,q表示老虎,r表示汽车。
那么 H(p), H(q), H(r)表示三个不同的命题
相同点:H(x)
定义由一个谓词,一些客体变元组成的表达式称为简单命题函数。由一个或者n个简单命题函数以及逻辑联结词组合而成的表达式称为复合命题函数。
7
客体变元的取值范围称为个体域(或论述域)。个体域可以是有限客体的集合,如:{a、b、c}、{计算机系的学生};也可以是无限客体的集合,如实数几何、自然数集合等。
特别是,当没有特别声明时,可以将宇宙间的一切事物和概念构成的集合作为个体域,称为全总个体域。
8
量词
。
。
这两个命题中的客体词和谓语均相同,区别在于“所有的”和“有些”这两个表示数量的词。表示数量的词在谓词逻辑中称为量词,量词包括全称量词和存在量词两种。

全称量词对应日常语言中的“一切”、“所有的”、“任意的”等词,表示对个体域的所有客体,用符号“∀”表示。

存在量词对应对应日常语言中的“存在着”、“至少有一个”、“有些”等词,表示存在着个体域的客体,用符号“∃”表示.
9
例如:
∀ xF(x)表示个体域中的所有客体都有性质F;
∃ xF(x)表示存在着个体域中的客体具有性质F。
当个体域有限时,设个体域为{a1,a2,…,an },则
∀x F(x)⇔F(a1)∧F(a2)∧…∧ F(an )
∃x F(x)⇔F(a1) ∨ F(a2)∨…∨F(an)
10