离散数学谓词逻辑.ppt

离散数学谓词逻辑
谓词、个体词和量词
例 在命题逻辑中 ，对下述论断无法判断其正确性。
“苏格拉底三段论” ：
凡人都是要死的，
苏格拉底是人，
所以苏格拉底是要死的。
类似的例 还有许多。 例如：
所有的人都要呼吸 , 所有的正整数都大于0,
李莉是人 , 3是正整数,
所以李莉要呼吸。 所以3大于0。
一、个体词和谓词
在谓词演算中，可将原子命题分解为谓词与个体词两部分。
定义2-1 个体是指可以独立存在的客体。
注　个体可以是抽象的，也可是具体的。个体通常在一个命题里表示思维对象。
定义2-2 用来刻划个体的性质或个体之间关系的词称为谓词，刻划一个个体性质的词称为一元谓词；刻划n个个体之间关系的词称为n元谓词。
例1 （1）李明是学生； （2）张亮比陈华高；
（3）陈华坐在张亮与李明之间。
在这三个命题中，李明、张亮、陈华都是个体；“…是学生”是一元谓词， “…比…高”是二元谓词， “…坐…与…之间”是三元谓词。
通常，我们用大写字母表示谓词，小写字母表示个体。
上述命题可分别表示为 Q（a）, P（b,c），R（c,b,a）。
一般地，一个由n个个体和n元谓词所组成的命题可表示为F（a1,a2, … ,an）,其中F表示n元谓词, a1,a2, … ,an 分别表示n个个体。
注意：a1,a2, … ,an的排列次序是重要的。
二、个体变元和命题函数
个体常元 表示具体或特定的个体的个体词称为个体常元。
个体变元 表示抽象的，或泛指的（或者说取值不确定的）个体称为个体变元。
例2 设 H是表示谓词“…能够到达山顶”，若个体w:王红；t：老虎；s：汽车，则H（w），H（t），H（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(x1,x2,…,xn)。由一个或若干个简单命题函数以及逻辑联结词组成的命题形式称为复合命题函数。
例如 H(x)，L(x,y,z)均是简单命题函数。
在命题函数中，个体变元的取值范围称为个体域。
例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)为真。
(P(x,y)∨L(x,y,z)) P(y, x)是一复合命题函数
三、量词和全总个体域
量词　 在命题里表示数量的词。

使用前面介绍的概念，还不足以表达日常生活中的各种命题。
例如：对于命题 “ 所有的正整数都是素数 ” 和
“ 有些正整数是素数 ”
仅用个体词和谓词是很难表达的。
（1） 全称量词 　“ x”
　　如“所有人都是要死的。”可表示为 x D（x），
x的个体域为全体人的集合。
（2）存在量词 “　x ”
（3）存在唯一量词 “ !x ”
如 “有些有理数是整数。”
令Ｉ(x）：x是整数；
于是命题可表示为 xＩ(x）
其中x的个体域为有理数集合。
如 “方程x+1=0存在唯一的整数解。”
令P（x）：x是x+1=0的整数解。
则命题可表示为 !x P（x），
其中x的个体域为整数集。
2．全总个体域
含有量词的命题的表达式的形式，与个体域有关。
含有量词的命题的真值与个体域也有关。因此，为了方便，我们引入全总个体域的概念。
定义2―5 宇宙间所有的个体聚集在一起所构成的集合称为