null第二章 谓词逻辑第二章 谓词逻辑§2.1 谓词的概念与表示法
§2.2 命题函数与量词
§2.3 谓词公式与翻译
§2.4 变元的约束
§2.5 谓词演算的等价式与蕴含式
§2.6 前束范式
§2.7 谓词演算的推理理论第二章 谓词逻辑第二章 谓词逻辑教学目的及要求:
深刻理解和掌握谓词逻辑的基本概念和基本推理方法。
教学内容:
谓词的概念与表示、命题函数与量词、谓词公式与翻译、变量的约束、谓词演算的等价式与蕴涵式、前束范式、谓词演算的推理理论。
教学重点:
谓词逻辑中的基本概念和基本推理方法。
教学难点:谓词演算的推理理论。§2.1 谓词的概念与表示法
§2.1 谓词的概念与表示法
在研究命题逻辑中,原子命题是命题演算中最基本的单位,不再对原子命题进行分解,这样会产生二大缺点:
(1)不能研究命题的结构,成分和内部逻辑的特征
(2)也不可能表达二个原子命题所具有的共同特征,甚至在命题逻辑中无法处理一些简单又常见的推理过程。
例:苏格拉底论证是正确的,但不能用命题逻辑的推理规则推导出来。 “所有的人总是要死的。 A
“苏格拉底是人。 B
“所以苏格拉底是要死的。” C§2.1 谓词的概念与表示法§2.1 谓词的概念与表示法1.谓词:
[定义]用以刻划客体的性质或关系的即是谓词。 我们可把陈述句分解为二部分:
主语(名词,代词)和谓语(动词)。
例:张华是学生,李明是学生。则可把它表示成:
H:表示“是学生”,j:表示“张华”,m:表示“李明”,则可用下列符号表示上述二个命题:H(j),H(m)。 H作为“谓词”(或者谓词字母)用大写英文字母表示,j,m为主语,称为“客体”或称“个体”。 §2.1 谓词的概念与表示法§2.1 谓词的概念与表示法(1)谓词填式:谓词字母后填以客体所得的式子。
例:H(a, b)
(2)若谓词字母联系着一个客体,则称作一元谓词;若谓词字母联系着二个客体,则称作二元谓词;若谓词字母联系着n个客体,则称作n元谓词。
(3)客体的次序必须是有规定的。 例:河南省北接河北省。
n L b 写成二元谓词为:L(n,b),但不能写成L(b,n) 。 §2.2 命题函数与量词§2.2 命题函数与量词1. 命题函数
客体在谓词表达式中可以是任意的名词。 例:C—“总是要死的。”
j:张三;t:老虎;e:桌子。
则C(j), C(t), C(e)均表达了命题。
在上面的例子中,C:表示“总是要死的”;x:表示变元(客体变元),则C(x)表示“x总是要死的”,则称C(x)为命题函数。
定义:由一个谓词字母和一个非空的客体变元的集合
所组成的表达式,称为简单命题函数。 §2.2 命题函数与量词§2.2 命题函数与量词讨论定义: (a)当简单命题函数仅有一个客体变元时,称为一元简单命题函数; (b)若用任何客体去取代客体变元之后,则命题函数就变为命题; (c)命题函数中客体变元的取值范围称为个体域(论述域)。
例:P(x)表示x是质数。这是一个命题函数。其值取决于个体域。
可以将命题函数命题,有两种方法:
§2.2 命题函数与量词§2.2 命题函数与量词 a)将x取定一个值。如:P(4),P(5)
b)将谓词量化。如:(x)P(x),(x)P(x)
个体域的给定形式有二种:
①具体给定。
如:{j, e, t}
②全总个体域任意域:所有的个体从该域中取得。§2.2 命题函数与量词§2.2 命题函数与量词2.量词
(1)全称量词 “”为全称量词符号,读作“对于所有的”,“对任一个”,“对一切”。 例:“这里所有的都是苹果”
可写成: (x)A(x)或(x)A(x)
几种形式的读法: · (x)P(x): “对所有的x,x是…”; · (x)¬P(x) : “对所有x,x不是…”; · ¬(x)P(x) : “并不是对所有的x,x是…”; · ¬(x)¬P(x) : “并不是所有的x,x不是…”。§2.2 命题函数与量词§2.2 命题函数与量词例:将“对于所有的x和任何的y,如果x高于y,那么y不高于x”写成命题表达形式。 解:( x)( y)(G(x,y) ¬ G(y,x)) G(x,y):x高于y
(2)存在量词 “”为存在量词符号,读作“存在一个”,“对于一些”,“对于某些”,“至少存在一个”,“这里存在着这样的”
“”表达式的读法: · ( x) A(x) :存在一个x,使x是…; · ( x)¬A(x) :存在一个x, 使x不是…; · ¬( x) A(x) :不存在一个x, 使x是…; · ¬( x)¬A(x) :不存在一个x, 使x不是…。§2.2 命题函数与量词§2.2 命题函数与量词例:(a)存在一个人;
(b)某个人很聪明; (c)某些实数是有理数
将(a),(b),(c)写成命题。
解:规定:M(x):x是人;C(x):x是很聪明; R1(x):x是实数(特性谓词)
R2(x):x是有理数。
则 (a)( x) M(x) ; (b) ( x )(M(x) C(x));
(c)( x) (R1(x) R2(x)) 。
(3)量化命题的真值:决定于给定的个体域
给定个体域:{a1…an}以{a1…an}中的每一个代入
(x)P(x)P(a1)… P(an) (x)Q(x)Q(a1)… Q(an) §2.3 谓词公式与翻译§2.3 谓词公式与翻译1.谓词公式 原子谓词公式:不出现命题联结词和量词的谓词命名式称为原子谓词公式,并用P(x1…xn)来表示。(P称为n元谓词, x1…xn称为客体变元),当n=0时称为零元谓词公式。
[定义](谓词公式的归纳法定义)
⑴原子谓词公式是谓词公式;
⑵若A是谓词公式,则¬A也是谓词公式;
⑶若A, B都是谓词公式,则(AB),(AB),(AB),(AB)都是谓词公式;
⑷若A是谓词公式,x是任何变元,则(x)A,( x)A也都是谓词公式; §2.3 谓词公式与翻译§2.3 谓词公式与翻译⑸只有按⑴-⑷所求得的那些公式才是谓词公式(谓词公式又简称“公式”)。
例1:任何整数或是正的,或是负的。 解:设:I(x): x是整数; R1(x):x是正数;R2(x):x是负数。
此句可写成:(x)(I(x)(R1(x) R2(x) )。
例2:试将苏格拉底论证符号化:“所有的人总是要死的。因为苏格拉底是人,所以苏格拉底是要死的。” 解:设M(x):x是人;D(x):x是要死的; M(s):苏格拉底是人;D(s):苏格拉底是要死。§2.3 谓词公式与翻译§2.3 谓词公式与翻译写成符号形式:
( x)(M(x) D(x)), M(s) D(s)
2.由于对个体描述性质的刻划深度不同,可翻译成不同形式的谓词公式。§2.4 变元的约束§2.4 变元的约束
1.辖域:紧接在量词后面括号内的谓词公式。
例: (x)P(x) , (x)(P(x) Q(x)) 。 若量词后括号内为原子谓词公式,则括号可以省去。
2.自由变元与约束变元 约束变元:在量词的辖域内,且与量词下标相同的变元。
自由变元:当且仅当不受量词的约束。
例: (x)P(x,y) ,( x)(P(x) y(P(x,y)) 。 §2.4 变元的约束§2.4 变元的约束3.约束变元的改名规则 任何谓词公式对约束变元可以改名。
我们认为(x)P(x,y)和(z)P(z,y)是一等价的谓词公式,但是需注意,不能用同一变元去表示同一谓词公式中的二个变元。例如:( y)P(y,y)是不正确的。
下面介绍约束变元的改名规则: (a)在改名中要把公式中所有相同的约束变元全部同时改掉; (b)改名时所用的变元符号在量词辖域内未出现的。 §2.4 变元的约束§2.4 变元的约束例: (x)P(x) (y)R(x,y)可改写成(x)P(x) (z)R(x,z) ,但不能改成(x)P(x) ( x)R(x,x) , (x)R(x,x)中前面的x原为自由变元,现在变为约束变元了。
4.区别是命题还是命题函数的方法 (a)若在谓词公式中出现有自由变元,则该公式为命题函数; (b)若在谓词公式中的变元均为约束出现,则该公式为命题。
例: (x)P(x,y,z)是二元谓词,
(y)(x)P(x,y,z)是一元谓词,
而谓词公式中如果没有自由变元出现,则该公式是一个命题。 §2.4 变元的约束§2.4 变元的约束举例:
例1:“没有不犯错的人。” 解:设F(x)为“x犯错误”,M(x)为“x是人”(特性谓词)。
可把此命题写成:¬(x)(M(x) F(x)))(x)(M(x)F(x))
例2:“x是y的外祖父” “x是z的父亲且z是y的母亲” 设P(z):z是人;F(x,z):x是z的父亲;M(z,y):z是y的母亲。 则谓词公式可写成:(z)(P(z) F(x,z) M(z,y)) 。
5.代入规则:对公式中的自由变元的更改叫做代入。
(a)对公式中出现该自由变元的每一处进行代入,
(b)用以代入的变元与原公式中所有变元的名称不能相同。§2.4 变元的约束§2.4 变元的约束6.个体域(论述域,客体域):用特定的集合表示的被约束变元的取值范围。
(1)个体域不同,则表示同一命题的谓词公式的形式不同。 例:“所有的人必死。”令D(x),x是要死的。
下面给出不同的个体域来讨论:
(ⅰ)个体域为:{人类},
则可写成(x)D(x);
(ⅱ)个体域为任意域(全总个体域),则人必须首先从任意域中分离出来,
设M(x),x是人,称M(x)为特性谓词。 命题可写成 ( x)(M(x) D(x))§2.4 变元的约束§2.4 变元的约束(2)个体域不同,则表示同一命题的值不同。Q(x): x<5 (3)对于同一个体域,用不同的量词时,特性谓词加入的方法不同。 对于全称量词,其特性谓词以前件的方式加入; 对于存在量词,其特性谓词以与的形式加入。§2.4 变元的约束§2.4 变元的约束例:设个体域为:{白虎(白猫),黄咪(黄猫),,},
同时令C(x):x是猫(特性谓词);B(x):x是黑色的;A(x):x是动物。
(ⅰ)描述命题:“所有的猫都是动物”。
即: (x)(C(x) A(x))(T)(真命题)
写成(x)(C(x) A(x)) (F)则为假命题了。
∵ (x)(C(x) A(x))TT T TT
(x)(C(x) A(x)) TT F FF
(ⅱ)描述命题:“一些猫是黑色的” 。
(x)(C(x) B(x)) FF F F F
而 (x)(C(x) B(x))F F T TT§2.4 变元的约束§2.4 变元的约束7.量词对变元的约束,往往与量词的次序有关。
例:
(y)(x)(x
说明
关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书
:
若个体域是有限的,则可省掉量词。
若个体域是无限的,则可将上述概念推广从而省去量词,不过要注意这是由无限项组成的命题。 §2.5 谓词演算的等价式与蕴含式§2.5 谓词演算的等价式与蕴含式例:设个体域为:N={0,1,2…},
P(x)表示:x>3 ,则可写出:
(x)P(x)P(0) P(1) … P(i) …
(x)P(x) P(0)P(1) … P(i) …
下面分类介绍在谓词公式中含有量词的等价式和永真蕴含式。 (1)量词转换律: E25(Q3) ¬(x)P(x) (x)¬P(x)
E26(Q4) ¬(x)P(x) (x)¬P(x)
下面
证明
住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问
:设个体域为: S={a1,a2,…an} §2.5 谓词演算的等价式与蕴含式§2.5 谓词演算的等价式与蕴含式 ¬(x)P(x) ¬(P(a1) P(a2) … P(an))
¬P(a1) ¬P(a2) … ¬P(an)(x)¬P(x)
下面举例说明量化命题和非量化命题的差别:否定形式不同 例: 否定下列命题:
(a)上海是一个小城镇 A(s)
(b)每一个自然数都是偶数 (x)(N(x)E(x))
上述二命题的否定为: (a)上海不是一个小城镇 ¬A(s)
(b)有一些自然数不是偶数
¬(x)(N(x)E(x))(x)¬(N(x)E(x))
(x)¬(N(x)E(x)) (x) (N(x) ¬E(x))§2.5 谓词演算的等价式与蕴含式§2.5 谓词演算的等价式与蕴含式结论:对于非量化命题的否定只需将动词否定,而对于量化命题的否定不但对动词进行否定而且对量词同时进行否定,其方法是: x的否定变为x , x的否定变为x 。
(2) 量词辖域的扩张及其收缩律
E27(Q6) ( x)A(x) P (x)(A(x) P)
(Q7) ( x)A(x) P (x)(A(x) P)
E28(Q9) (x)A(x) P (x)(A(x) P)
(Q8) ( x)A(x) P (x)(A(x) P)
P为不含有变元X的任何谓词公式§2.5 谓词演算的等价式与蕴含式§2.5 谓词演算的等价式与蕴含式证明E27(Q6),设个体域为: S={a1,a2,…an}
(x)A(x) P(A(a1) A(a2) … A(an)) P (A(a1)P)(A(a2)P)… (A(an) P )
(x)(A(x) P)
E30 (Q14) (x)A(x)B (x)(A(x)B)
E31 (Q15)( x)A(x)B (x)(A(x)B)
E32(Q16) A(x)B(x) (x)(AB (x))
E33 (Q17) A (x) B(x) (x)(AB (x))
证明E30 (Q14) ,设个体域为: S={a1,a2,…an}
(x)(A(x)B) (A(a1)B) … (A(an)B)
(¬A(a1) B) … (¬A(an) B) §2.5 谓词演算的等价式与蕴含式§2.5 谓词演算的等价式与蕴含式 (¬A(a1) … ¬A(an)) B
(x )¬A(x) B ¬(x)(A(x) B)
( x)A(x)B
(3)量词分配律
E24(Q10) (x)(A(x)B(x)) (x)A(x)( x)B(x)
E23 (Q11) (x) (A(x) B(x)) (x)A(x) ( x)B(x)
I18(Q12) (x) (A(x) B(x)) (x)A(x) ( x)B(x)
I17(Q13) (x)A(x) (x)B(x) ( x)
(A(x) B(x))
E29(Q18) (x) (A(x) B(x)) (x)A(x) (x)B(x)
I19(Q19) (x)A(x) (x)B(x) (x)(A(x) B(x))§2.5 谓词演算的等价式与蕴含式§2.5 谓词演算的等价式与蕴含式证明E24(Q10)和I19(Q19) ,设个体域为: S={a1,a2,…an}
E24(Q10) (x)(A(x)B(x))
(A(a1)B(a1)) …. (A(an)B(an))
(A(a1)… A(an)) (B(a1)… B(an))
(x)A(x)( x) B(x)
I19(Q19) (x)A(x) (x)B(x)
¬(x)A(x) (x)B(x) (x)¬A(x) (x)B(x)
(¬A(a1)… ¬A(an)) (B(a1)… B(an))
(¬A(a1) B(a1)) … (¬A(a1) B(an))
…(¬A(an) B(a1)) … (¬A(an) B(an))§2.5 谓词演算的等价式与蕴含式§2.5 谓词演算的等价式与蕴含式 (¬A(a1) B(a1)) … (¬A(an) B(an))
(x)(¬A(x) B(x))
(x)(A(x) B(x))
(4)量词的添加和除去的永真蕴含式 Q1 (x)P(x) P(y)
Q2 P(y) (x)P(x)
Q5 (x)P(x) (x)P(x)
(x)P P (x)P P (P为不含x变元)Y是x个体域中任一元素§2.5 谓词演算的等价式与蕴含式§2.5 谓词演算的等价式与蕴含式(5)含有多个量词的永真式: (ⅰ)量词出现的次序直接关系到命题的含义: “(x)(y)”表示:“无论选定一个什么样的x值总能找到一个y能使x和y…”
“(y)(x)”表示:“只选取一个y值,以致无论怎样选定一个x,能够使y和x…”
下面列出对应的表达式可以看出其不同处: 设x的个体域为: {a1,a2,…an} ,
y的个体域为: {b1,b2,…bn} , 则: (x)(y)P(x,y) (y)P(a1,y) … ( y)P(an,y) §2.5 谓词演算的等价式与蕴含式§2.5 谓词演算的等价式与蕴含式 (P(a1, b1) … P(a1, bn)) …
(P(an, b1) … P(an, bn))
(y)(x)P(x,y)
(x)P(x, b1) … (x)P(x, bn)
(P(a1, b1) … P(an, b1)) …
(P(a1, bn) … P(an, bn))
例:x,y的个体域{鞋子},P(x,y):X和Y配成一双鞋子。 (x)(y)P(x,y) T
(y)(x)P(x,y) F
§2.5 谓词演算的等价式与蕴含式§2.5 谓词演算的等价式与蕴含式(ⅱ)在含有多个量词的谓词公式中,
(x)(y),( x)(y)的位置是可以改变的,且不影响命题的真值。 例:x,y的个体域为N={0,1,2…},则
(x)(y)P(x,y)
(y)P(0,y) … ( y)P(i,y) …
(P(0,0) P(0,1) … P(0,j) …)…
(P(i,0) P(i,1) … P(i,j) …) …
(P(0,0) P(1,0) … P(i,0) …)
(P(0,1) P(1,1) … P(i,1) …)…
(x)P(x,0) ( x)P(x,1) …xP(x,j) …
( y)(x)P(x,y) §2.5 谓词演算的等价式与蕴含式§2.5 谓词演算的等价式与蕴含式同样: (x)(y)P(x,y) (y)(x)P(x,y)
(ⅲ)量词转换律的推广应用:把¬深入到谓词公式前面去的方法。
¬(x)(y)(z)P(x,y,z) (x)¬ (y)(z)P(x,y,z)
(x)(y)¬(z)P(x,y,z)
(x)(y)(z)¬P(x,y,z)
(ⅳ)两个量词, 所组成的谓词公式的等价式和永真蕴含式(8个) (x)(y)P(x,y) (y)(x)P(x,y)
(x)(y)P(x,y) (y)(x)P(x,y)
( y)(x)P(x,y) (x)(y)P(x,y)
(y)(x)P(x,y) (x)(y)P(x,y) §2.5 谓词演算的等价式与蕴含式§2.5 谓词演算的等价式与蕴含式 (x)(y)P(x,y) (y)(x)P(x,y)
(x)(y)P(x,y) (y)(x)P(x,y)
( y)(x)P(x,y) (x)(y)P(x,y)
(x)(y)P(x,y) (y)(x)P(x,y)
(6)谓词公式的对偶式
[定义] 在一个谓词公式A中(其中不出现,词)把公式A中 , , F, T, , , 变为公式A*中 , , T, F, , , 则称A*是A的对偶式。
[定理] 若谓词公式A B,则A* B* ;若谓词公式A B ,则B* A* ( 这里A,B有同样的个体域)。§2.5 谓词演算的等价式与蕴含式§2.5 谓词演算的等价式与蕴含式例:
I17(Q13)( x)A(x)( x)B(x) (x)(A(x)B(x))
I18(Q12) (x)A(x) ( x)B(x) (x)(A(x) B(x))
§2.6 前束范式§2.6 前束范式[定义]一个公式,如果量词均非否定地在全式的开头,它们的作用域延伸到整个公式的末尾,则称此公式叫前束范式。
例: (x)(y)(z)(¬ Q(x,y) R(z)) (前束范式)
[定理] 任何一个谓词公式均和一个前束范式等价。 证明:①利用量词转换把¬深入到原子谓词公式前, ②利用约束变元的改名规则,
③利用量词辖域的扩张收缩律,把量词移到全式的最前面,这样一定可得到等价的前束范式。§2.6 前束范式§2.6 前束范式例:
(x)P(x) R(x) (y)P(y) R(x)
( y)(P(y) R(x))
例:把(x)P(x)( x)Q(x) 变成前束范式。 (x)P(x) (x)Q(x) ¬(x)P(x)(x)Q(x)
(x)¬P(x) (x)Q(x)
(x)(¬P(x) Q(x))
§2.7 谓词演算的推理理论§2.7 谓词演算的推理理论1.含有量词的特殊永真式
[定义] 设A(x)是一个谓词公式,x是其中的自由变元,若把y代入到A(x)里而不会产生变元的新的约束出现,则称A(x)对于y是自由的。
例:下面A(x)对于y是自由的: ① A(x) ( z)P(z) Q(x,z),这里x为自由变元,若用y去取代A(x)中的x,
A(y) (z)P(z) Q(y,z),这里y也仍为自由变元;§2.7 谓词演算的推理理论§2.7 谓词演算的推理理论②下面A(x)对于y不是自由的:
A(x) (y)(S(x) S(y)), x为自由变元,
若用y代入A(x)的x中去得:
A(y) (y)(S(y) S(y)) ,y变为约束变元了,产生了新的约束出现。
如有必要代入y,则应先将式中的约束变元y改名。
(z)(S(x)S(z))然后代入y
(z)(S(y)S(z))y仍为自由变元。
归结: 判定A(x)对于y是自由的,只要看公式A(x)中y, y的辖域内有没有x的自由出现就行:若有x的自由出现则A(x)对于y不是自由的,若无的x自由出现则一定可以肯定A(x)对于y是自由的。§2.7 谓词演算的推理理论§2.7 谓词演算的推理理论下面分别介绍四个推理规则
(1)全称指定规则(US规则)。 如果对个体域中所有客体x, A(x)成立,则对个体域中某个任意客体c, A(c) 成立。该规则表示成:
(x)A(x) A(c) (x,c个体域)
(2)全称推广规则(UG规则)
如果能够证明对个体域中每一个客体c,命题A(c) 都成立,则可得到结论(x)A(x) 成立。该规则表示成: A(x) (x)A(x)
§2.7 谓词演算的推理理论§2.7 谓词演算的推理理论(3)存在指定规则(ES规则) 如果对于个体域中某些客体A(x)成立,则必有某个特定的客体c,使A(c)成立。该规则表示成:
( x)A(x) A(c)
例:x的个体域为I={整数},P(x):x是偶数,Q(x): x是奇数。
(x)P(x) (x)Q(x) T 但
P(c) Q(c) F
§2.7 谓词演算的推理理论§2.7 谓词演算的推理理论(4)存在推广规则(EG规则)
如果对个体域中某个特定客体c,有A(c) 成立,则在个体域中,必存在x,使A(x)成立。该规则表示成:
A(c) (x)A(x)
2 推论规则及使用说明
命题逻辑中的P,T,CP规则和简接证明法,都可以引用到谓词逻辑的推论规则中来,不过要注意对量词做适当处理,
其方法是:用US,ES在推导中去掉量词,用UG,EG使结论量化。
§2.7 谓词演算的推理理论§2.7 谓词演算的推理理论规则使用说明: (1)在使用ES,US时一定要是前束范式 (2)推导中连续使用US规则可用相同变元 ( x)P(x) P(y),( x)Q(x) Q(y),
(3)推导中既ES用,又用US, 则必须先用ES ,后用US方可取相同变元,反之不行。
(x)P(x) P(y) (x)Q(x) Q(y)
(4)推导中连续使用ES规则时,使用一次更改一个变元。 §2.7 谓词演算的推理理论§2.7 谓词演算的推理理论例:证明苏格拉底论证 (x)(M(x)D(x))M(s) D(s)
(1) M(s) P
(2)( x)(M(x)D(x)) P
(3) M(s)D(s) US
(4) D(s) T
例:证: (x)(H(x)M(x)) , (x)H(x) (x)M(x)
§2.7 谓词演算的推理理论§2.7 谓词演算的推理理论(1) (x)H(x) P
(2) H(c) ES
(3) (x)(H(x)M(x)) P
(4) H(c) M(c) US
(5) M(c) T
(6) (x)M(x) EG
例:证: (x) (P(x)Q(x)) (x) P(x) (x)Q(x)
(1)( x) P(x) 引入前件
(2) (x) (P(x)Q(x)) P
(3)P(c) Q(c) ES §2.7 谓词演算的推理理论§2.7 谓词演算的推理理论 (4) P(c) US
(5) Q(c) T
(6) (x)Q(x) EG
(7) (x )P(x)(x)Q(x) CP
例:证明:
¬(x)(P(x)Q(x)), (x)P(x) ¬( x)Q(x)
(1) ¬¬ (x)Q(x) 假设前提
(2) (x)Q(x) T
(3) Q(c) US
(4) (x)P(x) P §2.7 谓词演算的推理理论§2.7 谓词演算的推理理论 (5) P(c) US
(6) P(c)Q(c) T
(7) (x)(P(x)Q(x)) UG
(8) ¬(x)(P(x)Q(x)) P
(9) (x)(P(x)Q(x)) ¬(x)(P(x)Q(x)) T
(10) F
例:下列结论能否从前提中推出:
(x )(P(x)Q(x)) , ¬Q(a) (x) ¬ P(x)
a为x个体域中一个元素
(1) ¬Q(a) P
(2)( x) (P(x)Q(x)) P§2.7 谓词演算的推理理论§2.7 谓词演算的推理理论(3) P(a)Q(a) US
(4) ¬P(a) T
(5) (x) ¬ P(x) UG
在使用US,ES,UG,EG这四条规则时,要注意严格按照它们的规定去使用。
§2.7 谓词演算的推理理论§2.7 谓词演算的推理理论
书
关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf
中例4证明:
(1)(x)(y)(S(x,y)M(y))(z)(P(z)R(x,z)) P
(2)(y)(S(b,y) M(y))(z)(P(z)R(b,z)) US(1)
(3)(z)P(z) 附加前提
(4)(z)(P(z)) T(3)
(5)P(a) US(4)
(6)P(a)R(b,a) T(5)
(7)(P(a)R(b,a)) T(6)
(8)(z)(P(z)R(b,z)) UG(7)
(9)(z)(P(z)R(b,z)) T(8)§2.7 谓词演算的推理理论§2.7 谓词演算的推理理论(10)(y)(S(b,y) M(y)) T(2)(9)
(11)(y)(S(b,y) M(y)) T(10)
(12)(S(b,c) M(c)) US(11)
(13)S(b,c) M(c) T(12)
(14) S(b,c) M(c) T(13)
(15)(y)(S(b,y) M(y)) UG(14)
(16)(x)(y)(S(x,y) M(y)) UG(15)
(17) (z)P(z) (x)(y)(S(x,y) M(y)) CP(3)(16) §2.7 谓词演算的推理理论§2.7 谓词演算的推理理论例: 二个量词的推理比较复杂:
( x)P(x)(x)(P(x)Q(x) R(x)) , (x)P(x), (x)Q(x)
(x)( y)(R(x) R(y))
(1) ( x)P(x) P
(2) P(w) ES
(3) P(w) Q(w) T
(4) (x)P(x) (x)(P(x)Q(x) R(x)) P
(5)( x)(P(x)Q(x) R(x)) T
§2.7 谓词演算的推理理论§2.7 谓词演算的推理理论(6) P(w)Q(w) R(w) US
(7) R(w) T
(8) (x)R(x) EG
(9) (x)Q(x) P
(10) Q(z) ES
(11) P(z) Q(z) T
(12) P(z)Q(z) R(z) US
§2.7 谓词演算的推理理论§2.7 谓词演算的推理理论(13) R(z) T
(14) (y)R(y) EG
(15) (x)R(x) ( y)R(y) T
(16) (x)( y)(R(x) R(y)) T
三个量词的推理过程更为复杂
第二章小结第二章小结学习第二章要注意以下几点:
(1)同一个命题在不同个体域内可能有不同的符号化形式,同时也可能有不同的真值,因而在将一个命题符号化之前,必须弄清个体域。
(2)在将命题符号化时,要特别注意量词与联结词的搭配。经常的情况是全称量词与蕴含词搭配,存在量词与合取词搭配。因此有下面两种形式的公式:
(x)(A(x) B(x)) ①
(x)(A(x) B(x)) ②
而 (x)(A(x) B(x)) ③
(x)(A(x) B(x)) ④第二章小结第二章小结③与①,④与②的含义完全不同。
(3)记住主要的等价式。会用约束变元和自由变元换名规则进行等价演算,求出给定公式的前束范式。
(4)在谓词演算的推理证明中,要特别注意US,UG,ES,EG规则成立的条件。 习题选讲习题选讲例1.符号化下列命题:
(1)没有不犯错误的人;
(2)发光的不都是金子;
(3)在南京高校学习的学生,未必都是南京籍的学生。
解:(1)设M(x):x是人。 Q(x):x犯错误。
本题符号化为:(x)(M(x)Q(x))
或者: (x)(M(x)Q(x))
(2)设L(x):x是发光的东西。G(x):x是金子。
(x)(L(x)G(x)) 或 (x)(L(x)G(x))习题选讲习题选讲(3)设S(x):x是南京高校学习的学生。
F(x):x是南京籍的学生。
则 (x)(S(x)F(x))
本题也可加深刻划:
S(x):x是学生。L(x):x在学习。
H(x):x在南京高校。
G(x):x是南京籍的人。
则(x)(S(x)L(x)H(x)G(x) S(x))习题选讲习题选讲例2.写出(x)(F(x)G(x))(xF(x) (x)G(x))的前束范式。
解:
原式 (x)(F(x)G(x))((x)F(x) (x)G(x))
(x)(F(x)G(x)) ((x)F(x) (x)G(x))
(x)((F(x) G(x)) G(x)) (x) F(x)
(x)((F(x) G(x)) (x) F(x)
(x)((F(x) G(x)) (y) F(y)
(x) (y) (F(x) G(x) F(y))