第五章谓词逻辑
?在命题逻辑中,命题被当作一个基本的,不可分割的单位,只研究由原子命题和联接词所组成的复合命题;因而无法研究命题的内部结构及命题之间内在的联系。
·词项逻辑虽然能处理命题内部主谓项之间的推理关系,但其推理形式都局限于一些特定的形式。面对很多明显有效且司空见惯的推理,词项逻辑也无能为力。
传统逻辑的不足
——谓词逻辑的必要性
例1:有人喜欢所有的展品;(1)
所以,所以展品都有人喜欢。(2)
由(1)显然可以推出(2),但传统逻辑对此推理无法
处理。
例2:所有犯罪或者是故意犯罪,或者是过失犯罪;(3)
有些犯罪不是故意犯罪;(4)
所以,有些犯罪是过失犯罪。(5)
由(3)、(4)推出(5),显然也是有效的。但此推
理既不是三段论,又不是命题推理,当然也不是关系推理,
说明传统逻辑对此推理也是心有余而力不足。
主要内容
?本章介绍的谓词逻辑,对原子命题的成份、结构和原子命题间的共同特性等作了进一步分析。引入了个体词、谓词、量词、谓词公式等概念,在此基础上研究谓词公式间推导关系,对命题逻辑中的推理规则进行扩充,从而可以使我们可以进行量化自然推理。
第一节命题的内部结构
一、个体词和谓词
在谓词演算中,可将原子命题分解为谓词与个体词两部分。
定义5-1 个体是指可以独立存在的客体,个体词是指表示个体的词项。
注个体通常在一个命题里表示思维对象。因此个体词代表命题中的主项。
个体词有个体变项和个体常项之分。个体变项表示某个不确定的个体,而个体常项表示某个确定的个体。
定义5-2 用来刻划个体的性质或个体之间关系的词称为谓词。刻划个体性质的词称为一元谓词;刻划n个个体之间关系的词称为n元谓词。
例3
(1)李明是学生;
(2)李明比陈华高;
(3)x坐在陈华和李明之间。
在这三个命题中,李明、陈华都是个体常项,x是个体变项;“…是学生”是一元谓词,“…比…高”是二元谓词,“…坐…与…之间”是三元谓词。通常,我们用大写字母F、G、H 等表示谓词,小写字母a、b、c等表示个体常项,小写字母x、y、z等表示个体变项。
上述命题可分别表示为F(a), G(a,b),
H(x,b,a)。
一般地,一个由n个个体词和一个n元谓词所组成的命题可表示为F(a1,a2, … ,an),其中F表示n元谓词, a1,a2, … ,an 分别表示n个个体。
注意:a1,a2, … ,an的排列次序是重要的。
二、个体函项和个体域
在上例3中,主词是个体常项或者变项。但在有些句子中,主词既不是常项也不是变项,而是个体函项。
例4 张三的父亲病了。
主词“张三的父亲”不是以个体的名字,而是由另一个体张三确定或者说生成的。换句话说,“…的父亲”是以个体为自变量的函数。我们把这种以个体域为定义域,以个体为值域的函数称为个体函数。由于这种个体函数在原子命题中也可以作为主项,因而我们也把个体函数称为个体函项。
一般情况下,我们用f(x)表示个体函项。
例5 令F(x)表示“x病了”,f(x)表示“x的父亲”,a表示“张三”,则张三病了可以表示为F(a),而张三的父亲病了可以表示为F(f(a))。
在命题函数中,个体变元的取值范围称为个体域。
例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”
如“所有人都是要死的。”可表示为x D(x),
x的个体域为全体人的集合。
(2)存在量词“x ”
如“有些有理数是整数。”
令I(x):x是整数;
于是命题可表示为xI(x)
其中x的个体域为有理数集合。
(3)存在唯一量词“!x ”
如“方程x+1=0存在唯一的整数解。”
令P(x):x是x+1=0的整数解。
则命题可表示为!x P(x),
其中x的个体域为整数集。
2.全总个体域
含有量词的命题的表达式的形式,与个体域有关。
因此,为了方便,我们引入全总个体域的概念。
定义5―3 宇宙间所有的个体聚集在一起所构成的集合称为全总个体域。
后面的讨论中,除特殊说明外,均使用全总个体域。而对个体变化的真正取值范围,用特性谓词加以限制。
一般地,对全称量词,此特性谓词作蕴含的前件;对存在量词,此特性谓词常作合取项。例5 (1) “所有的人都是要死的。”
(2) “有的人活百岁以上。”
当x的个体域E为全体人组成的集合时,符号化上述命题。
令D(x):x是要死的。则(1)可表示为x D(x)。
令G(x):x活百岁以上。则(2)可表示为x G(x)。
当取x的个体域为全总个体域时,必须引入一个特性谓词将人从全宇宙的一切事物中分离出来。
(1)对所有个体而言,如果它是人,则它是要死的。
( 2)存在着个体,它是人并且它活百岁以上。
于是令M(x):x是人。
(1)x(M(x)D(x))
(2)x(M(x)∧G(x))
六个基本的谓词表达式
?x Fx 表示“任一对象都具有F这种性质”。
? x Fx 表示“存在对象具有F这种性质”。
?x?y Gxy 表示“任一对象x与任一对象y,都具有G这种关系”。
?x?y Gxy 表示“对于任一对象x, 存在对象y,x与y具有G这种关”。
?x?y Gxy 表示“存在对象x, 对任一对象y,x与y具有G这种关系”。
?x?y Gxy 表示“存在对象x和y,x与y具有G这种关系”。
几个重要概念
个体域:个体变项取值的范围,也称论域。
辖域:量词约束的范围。
约束个体变项:被量词约束的个体变项。
自由个体变项:不被量词约束的个体变项。
第二节自然语言的谓词表达式
一、直言命题的符号化
例6 将下列命题符号化(使用全总个体域)。
(1) 发光的不都是金子
解: 令P(x):x发光;G(x):x是金子。
则该命题可表示为:
?x(P(x) ∧?G(x))
或??x(P(x) →G(x))
(2)所有运动员都钦佩某些教练。
解:令P(x):x是运动员;T(x):x是教练;Q(x,y):x钦佩y。
则该命题可表示为:?x(P(x) →?y(T(y) ∧Q(x, y)))
(3)凡是实数均能比较大小。
解令R(x):x是实数;G(x,y):x与y可比较大小.
则该命题可表示为
例7 将下列命题符号化
(1)会叫的狗未必咬人。
解令D(x):x是狗;P(x):x会叫;Q(x):x咬人。则可表示为(课件上了)y))
G(x,
R(y)
y((R(x)
x→
∧
?
?
(2)没有不散的筵席。
解B(x):x是筵席;D(x):x是要散的;
则句(2)可表示为:(课件上)
(3)蛇是冷血的爬行动物。
解:Sx: x是蛇;Cx: x是冷血动物;Rx:x爬行动物。。
可表示为(课件上)
总结:直言命题的谓词表达式
全称肯定:所有S都是P
?x (Sx →Px)
全称否定:所有S都不是P
?x (Sx →?Px)
特称肯定:有的S是P
?x (Sx ∧Px)
特称否定:有的S不是P
?x (Sx ∧?Px)
例1 苏格拉底三段论可用谓词公式表示。
令M(x):x是人;D(x):x是要死的;
a:苏格拉底
则三段论可表示为
( x(M(x)D(x))∧M(a)) D(a)
例2 给出“x+y≥3”的谓词公式的表示形式。
解令P(x,y,z):x+y≥z
则上述表达式可用谓词公式表示为P(x,y,3)。
二、约束变元和自由变元
个体变元有自由变元和约束变元之分.
例3 “x是整数”可以表示为Q(x),
它是一个命题函数,而不是命题。
例4“ x 例5“凡是有理数都可以表示成分数。” 令Q(x):x是有理数;F(x):x可以表示为分数 符号化表示为(课件上) 这是一个真值确定的命题。 例6 “某些人对某些药物过敏” 令H(x):x是人;M(y):y是药;S(x,y):x对y过敏。 符号化表示为(课件上)也是一个真值确定的命题。 在谓词公式中,形如。。。或。。。的那一部分称为公式的x约束部分。而A(x)称为量词 x或x的辖域。x在公式的x约束部分的任一出现都称为x的约束出现。 公式中约束出现的变元是约束变元 当x的出现不是约束出现时,称x的出现是自由出现。自由出现的变元是自由变元。例7 指出下列各公式中的量词辖域及自由变元和约束变元。 (课件上)。。。 解。。。是的辖域。 是的辖域. R(z)是z的辖域。 x,y,z在公式中的所有出现均是约束出现,故它们均是约束变元。 (课件上) 解P(x,y)-> yQ(x,y,z)是x的辖域,在这一部分中,x是约束出现,故x是约束变元,在P(x,y)中的y是自由出现,故y为自由变元。但Q(x,y ,z)是y的辖域,因而在Q(x,y ,z)中y却是约束出现,故此时y是约束变元,z是自由变元。在S(x,z)中x,z是自由变元。 例8对公式。。。进行换名,使各变元只呈一种形式出现。 解需对x,y换名 。。。 2. 代入规则 对于公式中自由变元的更改叫做代入。 (1)对于谓词公式中的自由变元可以代入,代入时须对该自由变元的所有自由出现同时进行代入; (2)代入时所选用的变元符号与原公式中所有变元的符号不相同。 例如对例8中公式。。。的x,y的自由出现分别用w,t代入得 。。。 8.3 谓词公式的等值和蕴含 一、公式的类型 一个谓词公式一般含有个体变元、命题变元和谓词,只有当公式中的自由变元用某个体域中确定的个体代入,命题变元用确定的命题代入后,原公式才变成为一个命题。 指派一组代入到谓词公式中,并使得谓词公式成为命题的确定的个体和命题称为公式的一组指派。 定义8-7 给定谓词公式A,其个体域为E,如果对于任一组指派,公式A的值总是为真,则称A在E上式永真的。如果对于公式A的任一组指派,公式A的值总是为假,则称A在E上是永假的。如果至少存在着一组指派,使公式A的值为真,则称A在E上是可满足的。 例1 试说明下列各公式的类型(个体域取为全总个体域) (1) (2) (3)F(x) (其中F(x): x+6=5) (4) 解(1) 永真公式 (2) 可满足公式 (3) 可满足公式 (4) 永假公式 例2 试说明下列各公式的类型。 (1) (2) (3) (4)P (x ,y ) 其中x ,y 的个体域为R ;谓词P (x ,y ):x=y ; Q 是命题变元. 解 (1) 可满足公式。 (2) 永假公式。 (3) 永真公式。 (4) 可满足公式。 二、公式的等值与蕴含 定义8-8 设A 、B 是两个公式,它们有共同的个体域E ,若对于A 和B 的任意一组指派,两公式都具有相同的真值,则称公式A 和B 在E 上等值,记作A 。。。 B 。 定义8-9 对于公式A 和B ,若A B 1,则称公式A 蕴含公式B ,记作A B 。 谓词演算中的等值式和蕴涵式 1.命题公式的推广 在命题演算中,任一等值式或蕴涵式,其中同一命题变元,当用同一命题公式取代时,其结果仍是等值式或蕴涵式。 将此情况推广到谓词公式中,用谓词公式去取代命题演算中等值式或蕴涵式的命题变元时,便得到谓词演算的等值式或蕴涵式。 。。。 2. 全称量词和存在量词间转化的等值式 其中A (x )是任意的公式 对个体域是有限时,给出其证明。 证明 设个体域 ,则 3.量词辖域扩展与收缩的等值式 ) ()()()(x A x x xA x A x x xA ?????????? (2)① ② ③ ④ 4. 量词分配等值式与蕴涵式 (1)① ② 证明(1)① “个体域中每一个体x,使得A(x)与B(x)均为真”与“个体域中每一个体x,使得A(x)为真且每一个体x使得B(x)为真”具有相同的含义. (2)① ② 证明(2)② 由(2)①得 5.量词与联结词的关系 证明 证明设为假, 则为真,为假。 因此在个体域中必存在某个体a使B(a)为假,但A(a)为真。 于是为假,因此为假。由此永真。 故 8.4 谓词演算的推理理论 在谓词演算中,推理的形式结构仍为 。。。 若是永真式, 则称由前提逻辑的推出结论C, 在此, C均为谓词公式。 一、推理规则 命题演算中的推理规则,可在谓词推理理论中应用。 与量词有关的推理规则 1. US(全称消去规则) 。。。 使用此规则时要注意: (1)x是A(x)中的自由变元; (2)y为任意不在A(x)中约束出现的个体变元; (3)c为任意的个体常元。 关于(2)的反例: 设则, x,y的个体域为R,是一真命题. 若应用US得,则是错误的。 正确的做法是换成 2. ES(存在消去规则) 。。。 使用此规则时应注意: (1)c 是使A为真的特定个体常元;(2)如果A(x)中有其他自由变元出现,且x是随其他自由变元变化的,那么不能使用此规则。 3. UG(全称添加规则) 。。。 使用此规则时注意: (1) y在A(y)中自由出现,且y取任何值时A均为真。 (2) x不在A(y)中约束出现 4、EG(存在添加规则) 。。。 使用此规则时注意: (1) C是个体域中某个确定的个体。 (2) 代替C的x不能已在A(c)中出现。 二、推理规则的应用 例1 证明苏格拉底的三段论。 解令M(x):x是人; D(x):x是要死的; c:苏格拉底。 于是苏格拉底三段论可表示为:。。。 证明(1)M(c) 前提 (2)前提 (3)(1);US (4)D(c) (1),(3); 例2 证明 。。。 证明(1)前提(2)前提 (3)C(a) ∧Q(a) (2);ES (4)(1);US (5)C(a) (3);I1 (6)W(a) ∧R(a) (4),(5);I11 (7)Q(a) (3);I2 (8)R(a) (6);I2 (9)Q(a) ∧R(a) (7),(8);I9 (10)(9);EG 例3 证明。。 证明(1)附加前提 (2)(1);E (3)(2);ES (4)前提 ( 5 ) (4);US (6)Q(c) (3),(5);I10 (7)(6);EG 例4 证明。。。 例5 指出下面推理的错. 证明 (1)前提 (2)(1);I1 (3)(1);I2 (4)(2);ES (5)(3);ES (6)(4)(5);I9 (7)(6);EG 因此。。。 例6 指出下面推理的错误. 设D(x,y)表示“x可被y 整除” ,个体域为{ 5,7 ,10 ,11 }. 因为D(5,5)和D(10,5)为真,所以xD(x,5)为真. 因为D(7,5)和D(11,5)为假,所以xD(x,5)为假. 但有下面的推理过程: (1) xD(x,5) 前提 (2) D(z,5) (1);ES (3) xD(x,5) (2);UG 因此,xD(x,5) xD(x,5). 例7 对多个量词的使用情况,观察下列推理过程. 证明(1)前提 (2)(1);US (3)(2);ES (4)(3);UG (5)(4);EG 推出错误结论:与可交换. 习题 1 将下列命题符号化. (1)在上海高校学习的学生,未必都是上海籍的学生。 解令H(x):x是在上海高校学习的学生 S(y):y是上海籍的学生 或者 (2)没有一位女同志既是国家选手又是家庭妇女。 解令W(x):x是一位女同志; C(x):x是国家选手; H(x):x是家庭妇女 x(W(x)∧C(x)∧H(x)) (3)对于每一个实数x,存在一个更大的实数y。 解令R(x):x是实数;G(x,y):x比y大。 x(R(x) y(R(y)∧G(y,x)) (4)某些汽车比所有的火车都慢,但至少有一列火车比每辆汽车快。 解令C(x):x是汔车;H(x):x是火车; S(x,y): x比y慢。 。。。 2 对下列谓词公式中的约束变元进行改名. 。。。 解对x(P(x) (R(x)∨Q(x)))中的x换为y. xR(x)中的x换名为t得 。。。 3.将下面谓词公式中的自由变元进行代换. 。。。 解对y(P(x,y)中的自由变元x和Q(x,z)中的自由变元x代换为t , 对x(R(x,y) 中的自由变元y代换为s得 。。。 4. 用构造推理过程的方法证明 。。。 5.符号化下述命题,并推证其结论。 “所有有理数是实数,某些有理数是整数,因此某些实数是整数。” 解先将命题符号化 令Q(x):x是有理数;R(x):x是实数;I(x);x是整数. 。。。 证明