谓词逻辑 谓词逻辑

《谓词逻辑 谓词逻辑》由会员分享，可在线阅读，更多相关《谓词逻辑 谓词逻辑（87页珍藏版）》请在金锄头文库上搜索。

1、第二章 谓词逻辑v问题的提出：一个原子命题只用一个字母表示 ，而不再对命题中的句子成分细分。v所有的人都是要死的；苏格拉底是人；所以，苏格拉底是要死的。v令P：所有的人都是要死的；Q：苏格拉底是人；R：苏格拉底是要死的。 则原问题符号化为：PQR。2-1 基本概念2-1.1 个体与个体变元v定义：能够独立存在的事物，称之为个体，也 称之为客体。它可以是具体的，也可以是抽象的 事物。通常用小写英文字母a、b、c、.表示。v定义：用小写英文字母x、y、z.表示任何个 体，则称这些字母为个体变元。2-1.2 谓词v定义：用以刻画个体的性质或者个体之间关系的 即是谓词。v例如 S(x):表示x是大学生

2、。 一元谓词G(x, y)：表示 xy。 二元谓词B(x, y, z)：表示x在y与z之间。三元谓词 一般地P(x1,x2,xn) 是n元谓词。2-1.3 命题函数谓词相当于一个函数，称之为命题函数。 定义：n元谓词P(x1,x2,xn)称之为简单命题 函数。 规定：当命题函数P(x1,x2,xn)中 n=0 时， 即0元谓词，表示不含有客体变元的谓词， 它本身就是一个命题变元。复合命题函数定义：将若干个简单命题函数用逻辑联结词联结起来 ，构成的表达式，称之为复合命题函数。简单命题 函数与复合命题函数统称为命题函数。例：给定简单命题函数：A(x)：x身体好，B(x)：x学习好，C(x)：x工作

3、好， 则复合命题函数 A(x)(B(x)C(x) 表示2-1.4 论域(个体域)v设N(x)表示“x是负数”，I(x)表示“x是整数” ，则N(x)I(x)表示v设P(x)表示“x是大学生”。论域(个体域)v定义：在命题函数中命题变元的取值范围，称之 为论域，也称之为个体域。例如 S(x):x是大学生，个体域是:人类。G(x, y)：xy， 个体域是:实数。v定义：由所有论域构成的论域，称之为全总个体 域。v约定:对于一个命题函数，如果没有给定个体域， 则假定该个体域是全总个体域。个体函数v例：张华的父亲是教师。v设P(x)：表示x是教师。a：表示张华的父亲。 则原命题符号化为： 设f(x):

4、表示x的父亲。a：表示张华。 则原命题符号化为： f(x)称为个体函数（或函词）。注意区分个体函数与谓词间的区别 ：v个体函数是论域到论域的映射，g:NN ，如果指定的个体aN，则g(a)N。谓词是从个体域到T,F的映射，即谓词 E(x)可以看成映射E:NT,F，如果指 定个体aN，则E(a)的真值T,F。2-1.5 量词v例如：v有些人是大学生。v 所有事物都是发展变化的。v 任何一个有理数都可以用分数形式表示。 定义：在命题中表示对个体数量化的词，称 之 为量词。存在量词与全称量词(1).存在量词：记作，表示“有些”、“有一个” 、“某些”、“至少一个”等。xF(x):表示存在着客体域中的

5、客体具有性质F。当且仅当论域中至少有一个x0使得F(x0)为T 时， xF(x)为真。(2).全称量词：记作，表示“每个”、“任何一个 ”、“一切”、“所有的”、“凡是”、“任意的 ”等。xF(x):表示客体域里所有的客体都有性质F。当且仅当对论域中所有的x来说，F(x)均为T 时，xF(x)为真。v定义：量词后边要有一个个体变元，指明对哪个个 体变元量化，称此客体变元是量词后的指导变元。2-2 谓词公式及命题符号化原子谓词公式v定义：称n元谓词P(x1,x2,.,xn)为原子 谓词公式。v例如 P、Q(x) 、 A(x,f(x)、B(x,y,a) 都是原子谓词公式。2-2.3 谓词合式公式(

6、WFF)(Well Formed formulas)v定义：谓词合式公式递归定义如下：1.原子谓词公式是合式公式。2.如果A是合式公式，则A也是合式公式。3.如果A、B是合式公式，则(AB)、(AB)、 (AB)、(AB)都是合式公式。4.如果A是合式公式，x是中的任何个体变元 ，则x和x也是合式公式。5.只有有限次地按规则(1)至(4)求得的公式才 是合式公式。v谓词合式公式也叫谓词公式，简称公式。v判断下面哪些符号串是合式公式：P、(PQ)、(Q(x)P)、 x(A(x)B(x)、xC(x)、xyP(x) 、P(x)Q(x)xv为了方便，最外层括号可以省略，但是 若量词后边有括号，则此括号

7、不能省。2-2.4 量词的作用域(辖域)v定义：在谓词公式中，量词的作用范围称之 为量词的作用域，也叫量词的辖域。v例如 xA(x)中x的作用域为A(x).vx(P(x)Q(x)yR(x,y)中 x的作用域是(P(x)Q(x)yR(x,y)y的作用域为R(x,y)。vxyz(A(x,y)B(x,y,z)C(t) x的辖域z的辖域 y的辖域2-2.5 自由变元与约束变元v定义：如果个体变元x在x或者x的作用域内 ，则称x在此作用域内约束出现，并称x在此作 用域内是约束变元。否则x是自由出现，并称x 是自由变元。v x(F(x,y)yP(y)Q(z) 对约束变元和自由变元有如下几点说明： (1).

8、对约束变元用什么符号表示无关紧要。 (2).一个谓词公式如果无自由变元，它就表示一 个命题。 3).一个n元谓词P(x1,x2,xn)，若在前边添加k 个量词，使其中的 k个个体变元变成约束变元 ，则此 n元谓词就变成了n-k元谓词。v约束变元的改名规则： (1).对约束变元可以更改名称，改名 的范围是：量词后的指导变元以及 该量词的作用域内此个体变元出现 的各处同时换名。 (2).改名后用的个体变元名称，不能 与该量词的作用域内的其它变元名 称相同。 例如x(P(x)Q(x,y)(R(x)A(x) 可以对x改名成z(P(z)Q(z,y)(R(x)A(x) 对自由变元也可以换名字，此换名叫代入

9、 。 对自由变元的代入规则： (1).对谓词公式中的自由变元可以作代入 。代入时需要对公式中出现该变元的每 一处，同时作代入。 (2).代入后的变元名称要与公式中的其它 变元名称不同2-2.6 命题的符号化 在谓词演算中，命题的符号表达式与论域有关 系。 1.每个自然数都是整数。 (1).如果论域是自然数集合N，令 I(x)：x是整 数，则命题的表达式为 xI(x)。 (2).如果论域扩大为全总个体域时，上述表达 式xI(x)表示“所有个体都是整数”，显然 这是假的命题，此表达式已经不能表达原命 题了。因此需要添加谓词N(x)：x是自然数， 用于表明x的特性，于是命题的符号表达式为 x(N(x

10、)I(x)2.有些大学生吸烟。(1).如果论域是大学生集合S，令A(x)：x吸烟 ，则命题的表达式为 xA(x) (2).如果论域扩大为全总个体域时，上述表达 式xA(x)表示“有些客体吸烟”，就不是表 示此命题了，故需要添加谓词 S(x)：x是大 学生，用于表明x的特性，于是命题的表达式 为 x(S(x)A(x)v为什么必须这样添加特性谓词？ 1.每个自然数都是整数。 2.有些大学生吸烟。v令N:自然数集合，I:整数集合，S:大学生集合，A:烟民的集合。INSA吸烟大学生I包含N x(N(x)I(x)吸烟大学生是S与A的交集 x(S(x)A(x)3.所有大学生都喜欢一些歌星。令S(x)：x是

11、大学生，X(x)：x是歌星，L(x,y)：x喜欢y。 则命题的表达式为x(S(x)y(X(y)L(x,y) 4.没有不犯错误的人。 令P(x)：x是人，F(x)：x犯错误，此命题的表达式为5.不是所有的自然数都是偶数。令N(x)：x是自然数，E(x)：x是偶数，命题的表达式为:6.如果一个人只是说谎话，那么他所说的每句话没有一句 是可以相信的。令A(x)：x是人，B(x,y)：y是x说的话，C(x):x是谎话，D(x)：x是可以相信的命题的表达式为: x(A(x)(y(B(x,y)C(y)z(B(x,z)D(z) )7.每个人都有一个生母。设 P(x):x是个人。M(x,y):y是x的生母。此

12、命题可以 写成x(P(x)y(P(y)M(x,y) 8. 不管白猫黑猫，抓到老鼠就是好猫。设C（x）：x是猫 B（x）：x是黑的W（x）：x是白的 G（x）：x是好的M（y）：y是老鼠 K（x，y）：x抓住y 命题的表达式为:x(C(x)(W(x)B(x)(y(M(y)K(x,y)G(x)对平面上任意两个不同的点，有且仅有一条直 线通过这两点。vP(x)：x是一个点vL(x)：x是一条直线vR(x, y, z)：z通过x和yvE(x,y)：x=yv(x)(y)(P(x)P(y) E(x,y) (z)(L(z)R(x,y,z)(u)(L(u)R(x,y,u)E(z,u)v取个体域为实数集，函数f

13、在a点连续的定义 是：f在点a连续，当且仅当对每个0，存在 一个0，使得对所有的x，若|x-a|yv则该定义可符号化为：P(f,a)v(Q(,o)(Q(,0)x(Q(,|x-a|)Q(,|f(x)-f(a)|)这只大红书柜摆满了那些古书。vF(x,y):x摆满了y R(x):x是大红书柜vQ(y):y是古书 a:这只 b:那些v则 R(a)Q(b)F(a,b)vA(x):x是书柜 B(x):x是大的 C(x):x是红 的 D(y):y是古老的 E(y):y是图书 v F(x,y):x摆满y a:这只 b:那些v则A(a)B(a)C(a)D(b)E(b)F(a,b)v练习：v金子发光，但发光的不

14、一定都是金子 。v没有大学生不懂外语。v任何金属都可以溶解在某种液体里v如果明天天气好，有些学生将去香山 v在北京工作的人未必都是北京人有限域下公式 (x)P(x)、(x)P(x)的表示法v设论域为a1，a2，an，则有v(x)P(x)= P(a1) P(a2 ) P(an)v(x)P(x) = P(a1)P(a2 ) P(an)在域a1，a2上多次量化公式(x)(y)F(x,y)=(x)(y)F(x,y)=(y)F(a1,y)(y)F(a2,y) =F(a1, a1)F(a1, a2)F(a2, a1)F(a2, a2)=F(a1, a1)F(a2, a1)F(a1, a2)F(a2, a2

15、)=(x)F(x,a1)(x)F(x,a2) = (y)(x)F(x,y)(x)(y)F(x,y)=F(a1, a1)F(a1, a2)F(a2, a1)F(a2, a2) = (y)(x)F(x,y)在域a1，a2上多次量化公式(x)(y)F(x,y)=( x)(y)F(x,y)=(y)F(a1,y) (y)F(a2,y) =(F(a1, a1)F(a1, a2)(F(a2, a1)F(a2, a2)(y)(x) F(x,y)=(y) (x)F(x,y)=(x)F(x, a1) (x)F(x, a2) =(F(a1, a1 )F(a2, a1)(F(a1, a2)F(a2, a2)(x)(y)F(x,y)(y)(x) F(x,y)2-3.1 对谓词公式赋值v对谓词公式G的赋值I包括以下几点： （1）指定一个个体域D； （2）对公式中出现的每个函词，指定D上的个 体函数； （3）对公式中出现的每个谓词，指定D上的谓 词； （4）对公式中出现的每个个体常量和自由变元 ，指定D中的一个个体； （5）对公式中出现的每个命题变