第10讲谓词逻辑等值式.ppt

《第10讲谓词逻辑等值式.ppt》由会员分享，可在线阅读，更多相关《第10讲谓词逻辑等值式.ppt（33页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、一阶逻辑的字母表n个体常项:a,b,c,a1,b1,c1,n个体变项:x,y,z,x1,y1,z1,n函数符号:f,g,h,f1,g1,h1,n谓词符号:F,G,H,F1,G1,H1,n量词符号:,n联结词符号:,n括号与逗号:(,),，2022/12/211一阶逻辑一阶(first order)逻辑的合式公式n项n原子公式n合式公式2022/12/212一阶逻辑合式公式中的变项n量词辖域:在xA,xA中,A是量词的辖域.例如:x(F(x)y(G(y)H(x,y)n指导变项:紧跟在量词后面的个体变项.例如:x(F(x)y(G(y)H(x,y)n约束出现:在辖域中与指导变项同名的变项.例如:x(

2、F(x)y(G(y)H(x,y)n自由出现:既非指导变项又非约束出现.例如:y(G(y)H(x,y)2022/12/213一阶逻辑解释(interpret)n对一个合式公式的解释包括给出n个体域n谓词n函数n个体常项的具体含义2022/12/214一阶逻辑赋值(举例)nF(f(a,a),b)n赋值1：个体域是全体自然数;a:2;b:4;f(x,y)=x+y;F(x,y):x=y 原公式赋值成:“2+2=4”。n赋值2：个体域是全体实数;a:3;b:5;f(x,y)=x-y;F(x,y):xy 原公式赋值成:“3-35”。2022/12/215一阶逻辑一阶逻辑永真式(tautology)n永真式

3、:在各种解释下取值均为真(逻辑有效式)n命题逻辑永真式:在各种解释下取值均为真(重言式)n永假式:在各种解释下取值均为假(矛盾式)n命题逻辑永假式:在各种解释下取值均为假(矛盾式)n可满足式：非永假式2022/12/216一阶逻辑代换实例n在含命题变项p1,p2,pn的命题公式中,每个命题变项代换成一阶逻辑公式所得到的式子,称为原来公式的代换实例.n例：F(x)G(y)xF(x)G(y)2022/12/217一阶逻辑一阶逻辑公式分类n例：xF(x)xF(x)nxF(x)(G(y)xF(x)nxF(x)yG(y)n(xF(x)yG(y)yG(y)2022/12/218一阶逻辑命题符号化(举例)n

4、例:“不存在最大的自然数”。(论域取全体自然数)解:设:G(x,y):xy;原命题符号化成:xyG(y,x)或:xy G(y,x)2022/12/219一阶逻辑一阶逻辑等值式(定义)n等值：AB n读作：A等值于Bn含义：A与B在各种赋值下取值均相等nAB 当且仅当 AB是永真式n例如：xF(x)xF(x)F F2022/12/2110一阶逻辑一阶逻辑等值式(来源)n命题逻辑等值式的代换实例n与量词有关的n有限个体域量词消去n量词否定n量词辖域收缩与扩张n量词分配n相同量词的交换n与变项命名有关的n换名规则n代替规则2022/12/2111一阶逻辑代换实例n在命题逻辑等值式中,代入一阶逻辑公式

5、所得到的式子,称为原来公式的代换实例.n例1：AA,令A=xF(x),得到xF(x)xF(x)n例2：ABAB,令A=F(x),B=G(y),得到F(x)G(y)F(x)G(y)2022/12/2112一阶逻辑有限个体域上消去量词n设个体域为有限集D=a1,a2,an,则xA(x)A(a1)A(a2)A(an)xA(x)A(a1)A(a2)A(an)n例:个体域D=a,b,c,则 xyF(x,y)x(F(x,a)F(x,b)F(x,c)(F(a,a)F(a,b)F(a,c)(F(b,a)F(b,b)F(b,c)(F(c,a)F(c,b)F(c,c)2022/12/2113一阶逻辑量词否定等值式

6、nxA(x)xA(x)nxA(x)xA(x)A A2022/12/2114一阶逻辑量词否定等值式(举例)n N n (nN|an-a|N|an-a|N|an-a|N|an-a|N|an-a|N|an-a|N|an-a|N|an-a|)2022/12/2116一阶逻辑量词辖域收缩与扩张()nx(A(x)B)xA(x)Bnx(A(x)B)xA(x)Bn说明:B中不含x的出现n例1:x(F(x)G(y)xF(x)G(y)n例2:xy(F(x)G(y)x(F(x)yG(y)xF(x)yG(y)2022/12/2117一阶逻辑量词辖域收缩与扩张(、续)nx(A(x)B)nx(BA(x)n证明:x(A(x

7、)B)x(A(x)B)xA(x)B xA(x)B xA(x)Bn证明:x(BA(x)x(BA(x)BxA(x)BxA(x)BxA(x)xA(x)B BxA(x)2022/12/2118一阶逻辑量词辖域收缩与扩张()nx(A(x)B)xA(x)Bnx(A(x)B)xA(x)Bnx(A(x)B)xA(x)Bnx(BA(x)BxA(x)n说明:B中不含x的出现n例1:x(F(x)G(y)xF(x)G(y)n例2:xy(F(x)G(y)x(F(x)yG(y)xF(x)yG(y)2022/12/2119一阶逻辑量词辖域收缩与扩张(、续)n x(A(x)B)xA(x)B 证明:x(A(x)B)x(A(x)

8、B)xA(x)B xA(x)B xA(x)Bn x(BA(x)BxA(x)证明:x(BA(x)x(BA(x)BxA(x)BxA(x)BxA(x)2022/12/2120一阶逻辑量词分配nx(A(x)B(x)xA(x)xB(x)nx(A(x)B(x)xA(x)xB(x)2022/12/2121一阶逻辑量词分配(反例)nx(A(x)B(x)xA(x)xB(x)nx(A(x)B(x)xA(x)xB(x)个体域为全体自然数;A(x):x是偶数 B(x):x是奇数;左1,右0 nx(A(x)B(x)xA(x)xB(x)nx(A(x)B(x)xA(x)xB(x)个体域为全体自然数;A(x):x是偶数 B(

9、x):x是奇数;左0,右1 2022/12/2122一阶逻辑相同量词的交换nxy(x,y)yx(x,y)xy(x,y)yx(x,y)2022/12/2123一阶逻辑换名(rename)规则n把某个指导变项和其量词辖域中所有同名的约束出现,都换成某个新的个体变项符号.n例如:n x(A(x)B(x)y(A(y)B(y)n xA(x)xB(x)yA(y)zB(z)n H(x,y)xF(x)y(G(y)H(x,y)H(x,y)zF(z)u(G(u)H(x,u)2022/12/2124一阶逻辑代替(substitute)规则n把某个自由变项的所有出现,都换成某个新的个体变项符号.n例如:n A(x)B

10、(x)A(y)B(y)n xA(x)B(x)xA(x)B(y)n H(x,y)xF(x)y(G(y)H(x,y)H(s,t)xF(x)y(G(y)H(s,y)2022/12/2125一阶逻辑置换(permutation)规则n设(A)是含公式A的一阶谓词公式，(B)是用公式B置换(A)中所有出现的A后得到的公式。若A B,则(A)(B)2022/12/2126一阶逻辑例5.52022/12/2127一阶逻辑举例nxA(x)xB(x)x(A(x)B(x)nxA(x)xB(x)yA(y)xB(x)y(A(y)xB(x)yx(A(y)B(x)特点：所有量词都在最前面2022/12/2128一阶逻辑前

11、束范式n设为一谓词公式，如果具有如下形式：Q1x1Q2x2.Qnxn其中Qi(1in)为或，为不含量词的公式，则称为前束范式.2022/12/2129一阶逻辑前束范式存在定理n定理：任意一个谓词公式，都存在着一个等值的前束范式。n(注：利用换名规则或代替规则以及上述所提及的等值式可知，任意公式都有其前束范式(存在性)，但并不唯一.)2022/12/2130一阶逻辑前束合取（析取）范式n设为一谓词公式，如果具有如下形式：Q1x1Q2x2.Qnxn其中Qi(1in)为或，为不含量词的合取（析取）范式公式，则称为前束合取（析取）范式n合取范式形如：(A11 A12 A1n)(A21 A22 A2n）(Am1 Am2 Amn）其中Aij是原子公式或其否定。2022/12/2131一阶逻辑举例nxA(x)xB(x)x(A(x)B(x)nxA(x)xB(x)yA(y)xB(x)y(A(y)xB(x)yx(A(y)B(x)2022/12/2132一阶逻辑习题nP78-80 2，6-122022/12/2133一阶逻辑