《第10讲谓词逻辑等值式优秀课件.ppt》由会员分享,可在线阅读,更多相关《第10讲谓词逻辑等值式优秀课件.ppt(33页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第10讲谓词逻辑等值式2022/10/24一阶逻辑1第1页,本讲稿共33页2022/10/24一阶逻辑2一阶(first order)逻辑的合式公式n项n原子公式n合式公式第2页,本讲稿共33页2022/10/24一阶逻辑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)第3页,本讲稿共33页2022/10/24
2、一阶逻辑4解释(interpret)n对一个合式公式的解释包括给出n个体域n谓词n函数n个体常项的具体含义第4页,本讲稿共33页2022/10/24一阶逻辑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”。第5页,本讲稿共33页2022/10/24一阶逻辑6一阶逻辑永真式(tautology)n永真式:在各种解释下取值均为真(逻辑有效式)n命题逻辑永真式:在各种解释下取值均为
3、真(重言式)n永假式:在各种解释下取值均为假(矛盾式)n命题逻辑永假式:在各种解释下取值均为假(矛盾式)n可满足式:非永假式第6页,本讲稿共33页2022/10/24一阶逻辑7代换实例n在含命题变项p1,p2,pn的命题公式中,每个命题变项代换成一阶逻辑公式所得到的式子,称为原来公式的代换实例.n例:F(x)G(y)xF(x)G(y)第7页,本讲稿共33页2022/10/24一阶逻辑8一阶逻辑公式分类n例:xF(x)xF(x)nxF(x)(G(y)xF(x)nxF(x)yG(y)n(xF(x)yG(y)yG(y)第8页,本讲稿共33页2022/10/24一阶逻辑9命题符号化(举例)n例:“不存
4、在最大的自然数”。(论域取全体自然数)解:设:G(x,y):xy;原命题符号化成:xyG(y,x)或:xy G(y,x)第9页,本讲稿共33页2022/10/24一阶逻辑10一阶逻辑等值式(定义)n等值:AB n读作:A等值于Bn含义:A与B在各种赋值下取值均相等nAB 当且仅当 AB是永真式n例如:xF(x)xF(x)F F第10页,本讲稿共33页2022/10/24一阶逻辑11一阶逻辑等值式(来源)n命题逻辑等值式的代换实例n与量词有关的n有限个体域量词消去n量词否定n量词辖域收缩与扩张n量词分配n相同量词的交换n与变项命名有关的n换名规则n代替规则第11页,本讲稿共33页2022/10/
5、24一阶逻辑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)第12页,本讲稿共33页2022/10/24一阶逻辑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)第13页,本讲稿共33页2022/10/24一阶逻辑14量词否定等值式nxA(x)xA(x)nxA(x)xA(x)A A第14页,本讲稿共33页2022/10/24一阶逻辑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|)第16页,本讲稿共33页2022/10/24一阶逻辑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
7、(y)x(F(x)yG(y)xF(x)yG(y)第17页,本讲稿共33页2022/10/24一阶逻辑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)第18页,本讲稿共33页2022/10/24一阶逻辑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)
8、G(y)n例2:xy(F(x)G(y)x(F(x)yG(y)xF(x)yG(y)第19页,本讲稿共33页2022/10/24一阶逻辑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)第20页,本讲稿共33页2022/10/24一阶逻辑21量词分配nx(A(x)B(x)xA(x)xB(x)nx(A(x)B(x)xA(x)xB(x)第21页,本讲稿共33页2022/10/24一阶逻辑22量词分配(反例)nx(
9、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(x):x是奇数;左0,右1 第22页,本讲稿共33页2022/10/24一阶逻辑23相同量词的交换nxy(x,y)yx(x,y)xy(x,y)yx(x,y)第23页,本讲稿共33页2022/10/24一阶逻辑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)第24页,本讲稿共33页2022/10/24一阶逻辑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)第25页,本讲稿共33页2022/10/24一阶逻辑26置换(permutation)规则n
11、设(A)是含公式A的一阶谓词公式,(B)是用公式B置换(A)中所有出现的A后得到的公式。若A B,则(A)(B)第26页,本讲稿共33页2022/10/24一阶逻辑27例5.5第27页,本讲稿共33页2022/10/24一阶逻辑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)特点:所有量词都在最前面第28页,本讲稿共33页2022/10/24一阶逻辑29前束范式n设为一谓词公式,如果具有如下形式:Q1x1Q2x2.Qnxn其中Qi(1in)为或,为不含量词的公式,则称为前束范式.第29页,本讲稿共33页20
12、22/10/24一阶逻辑30前束范式存在定理n定理:任意一个谓词公式,都存在着一个等值的前束范式。n(注:利用换名规则或代替规则以及上述所提及的等值式可知,任意公式都有其前束范式(存在性),但并不唯一.)第30页,本讲稿共33页2022/10/24一阶逻辑31前束合取(析取)范式n设为一谓词公式,如果具有如下形式:Q1x1Q2x2.Qnxn其中Qi(1in)为或,为不含量词的合取(析取)范式公式,则称为前束合取(析取)范式n合取范式形如:(A11 A12 A1n)(A21 A22 A2n)(Am1 Am2 Amn)其中Aij是原子公式或其否定。第31页,本讲稿共33页2022/10/24一阶逻辑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)第32页,本讲稿共33页2022/10/24一阶逻辑33习题nP78-80 2,6-12第33页,本讲稿共33页