第10讲谓词逻辑等值式精选文档.ppt

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

1、第10讲谓词逻辑等值式2022/9/21一阶逻辑1本讲稿第一页，共三十三页2022/9/21一阶逻辑2一阶(first order)逻辑的合式公式n项n原子公式n合式公式本讲稿第二页，共三十三页2022/9/21一阶逻辑3合式公式中的变项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(F(x)y(G(y)H(x,y)n自由出现:既非指导变项又非约束出现.例如:y(G(y)H(x,y)本讲稿第三页，共三十三页2022/9/21一

2、阶逻辑4解释(interpret)n对一个合式公式的解释包括给出n个体域n谓词n函数n个体常项的具体含义本讲稿第四页，共三十三页2022/9/21一阶逻辑5赋值(举例)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/9/21一阶逻辑6一阶逻辑永真式(tautology)n永真式:在各种解释下取值均为真(逻辑有效式)n命题逻辑永真式:在各种解释下取值均为真

3、(重言式)n永假式:在各种解释下取值均为假(矛盾式)n命题逻辑永假式:在各种解释下取值均为假(矛盾式)n可满足式：非永假式本讲稿第六页，共三十三页2022/9/21一阶逻辑7代换实例n在含命题变项p1,p2,pn的命题公式中,每个命题变项代换成一阶逻辑公式所得到的式子,称为原来公式的代换实例.n例：F(x)G(y)xF(x)G(y)本讲稿第七页，共三十三页2022/9/21一阶逻辑8一阶逻辑公式分类n例：xF(x)xF(x)nxF(x)(G(y)xF(x)nxF(x)yG(y)n(xF(x)yG(y)yG(y)本讲稿第八页，共三十三页2022/9/21一阶逻辑9命题符号化(举例)n例:“不存在

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

5、一阶逻辑12代换实例n在命题逻辑等值式中,代入一阶逻辑公式所得到的式子,称为原来公式的代换实例.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/9/21一阶逻辑13有限个体域上消去量词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)(

6、F(c,a)F(c,b)F(c,c)本讲稿第十三页，共三十三页2022/9/21一阶逻辑14量词否定等值式nxA(x)xA(x)nxA(x)xA(x)A A本讲稿第十四页，共三十三页2022/9/21一阶逻辑15量词否定等值式(举例)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/9/21一阶逻辑17量词辖域收缩与扩张()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

7、)x(F(x)yG(y)xF(x)yG(y)本讲稿第十七页，共三十三页2022/9/21一阶逻辑18量词辖域收缩与扩张(、续)nx(A(x)B)nx(BA(x)n证明:x(A(x)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/9/21一阶逻辑19量词辖域收缩与扩张()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(

8、y)n例2:xy(F(x)G(y)x(F(x)yG(y)xF(x)yG(y)本讲稿第十九页，共三十三页2022/9/21一阶逻辑20量词辖域收缩与扩张(、续)n x(A(x)B)xA(x)B 证明:x(A(x)B)x(A(x)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/9/21一阶逻辑21量词分配nx(A(x)B(x)xA(x)xB(x)nx(A(x)B(x)xA(x)xB(x)本讲稿第二十一页，共三十三页2022/9/21一阶逻辑22量词分配(反例)nx(A

9、(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(x):x是奇数;左0,右1 本讲稿第二十二页，共三十三页2022/9/21一阶逻辑23相同量词的交换nxy(x,y)yx(x,y)xy(x,y)yx(x,y)本讲稿第二十三页，共三十三页2022/9/21一阶逻辑24换名(rename)规则n把某个指导变项和其量词辖域中所有同名的约束出现,都换成某个新的个体变项符号.n例如

10、: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/9/21一阶逻辑25代替(substitute)规则n把某个自由变项的所有出现,都换成某个新的个体变项符号.n例如:n A(x)B(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/9/21一阶逻辑26置换(permutation)

11、规则n设(A)是含公式A的一阶谓词公式，(B)是用公式B置换(A)中所有出现的A后得到的公式。若A B,则(A)(B)本讲稿第二十六页，共三十三页2022/9/21一阶逻辑27例5.5本讲稿第二十七页，共三十三页2022/9/21一阶逻辑28举例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/9/21一阶逻辑29前束范式n设为一谓词公式，如果具有如下形式：Q1x1Q2x2.Qnxn其中Qi(1in)为或，为不含量词的公式，则称为前束范式.本讲稿第二十九页

12、，共三十三页2022/9/21一阶逻辑30前束范式存在定理n定理：任意一个谓词公式，都存在着一个等值的前束范式。n(注：利用换名规则或代替规则以及上述所提及的等值式可知，任意公式都有其前束范式(存在性)，但并不唯一.)本讲稿第三十页，共三十三页2022/9/21一阶逻辑31前束合取（析取）范式n设为一谓词公式，如果具有如下形式：Q1x1Q2x2.Qnxn其中Qi(1in)为或，为不含量词的合取（析取）范式公式，则称为前束合取（析取）范式n合取范式形如：(A11 A12 A1n)(A21 A22 A2n）(Am1 Am2 Amn）其中Aij是原子公式或其否定。本讲稿第三十一页，共三十三页2022/9/21一阶逻辑32举例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/9/21一阶逻辑33习题nP78-80 2，6-12本讲稿第三十三页，共三十三页