资源预览内容
第1页 / 共37页
第2页 / 共37页
第3页 / 共37页
第4页 / 共37页
第5页 / 共37页
第6页 / 共37页
第7页 / 共37页
第8页 / 共37页
第9页 / 共37页
第10页 / 共37页
亲,该文档总共37页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
离散数学,一阶逻辑推理理论,内容回顾,一阶逻辑合式公式及解释 一阶逻辑等值式及前束范式,例:给定解释I如下: 1.DI=2,3 2.DI中特定元素a=2 3.DI上的函数f(x)为f(2)=3,f(3)=2; 4.DI上的谓词F(x)为 F(2)=0,F(3)=1;G(x,y)为 G(i,j)= 1 (i,j=2,3);L(x,y)为 L(2,2)= L(3,3)=1;L(2,3)= L(3,2)=0;求在解释I下,下列各式的真值: x(F(x) G(x,a) x(F(f(x) G(x,f(x) xyL(x,y),回顾: 当个体域为有限集时,如D=a1,a2,am,对于任意的谓词A(x),都有:xA(x) A(a1)A(a2)A(am)xA(x) A(a1)A(a2)A(am),3. xyL(x,y) yL(2,y) yL(3,y) (L(2,2) L(2,3) (L(3,2) L(3,3) 1 1 1,练习:求下列公式的前束范式(xF(x,y) yG(x,y) xF(x,y) y G(x,y) x F(x,y) y G(x,y) x F(x,t) y G(s,y) x( F(x,t) y G(s,y) xy( F(x,t) G(s,y),今日内容,一阶逻辑推理理论 推理形式的定义 量词引入和消去规则 一阶逻辑下的推理证明,一阶逻辑推理理论,在一阶逻辑中,推理的形式结构仍为A1A2AkB若该式是永真式,则称推理正确,称B是A1,A2,Ak的逻辑结论此时将该式记为 A1A2Ak B 命题逻辑中的推理规则及在一阶逻辑中的代换实例,在一阶逻辑中仍然成立,回顾 量词辖域收缩与扩张等值式: 对于含变项x约束出现的任意公式A(x)和不含x的任意公式B 1.(1) x(A(x)B) xA(x) B(2) x(A(x)B) xA(x) B(3) x(A(x)B) xA(x) B(4) x(B A(x) BxA(x) 2.(1) x(A(x)B) xA(x) B(2) x(A(x)B) xA(x) B(3) x(A(x)B) xA(x) B(4) x(B A(x) BxA(x),量词分配等值式: 对于任意的公式A(x)和B(x),x(A(x)B(x) (xA(x)xB(x) 对的分配x(A(x)B(x) (xA(x)xB(x) 对的分配 注意: 对不满足分配律对不满足分配律,(1) xA(x)xB(x) x(A(x)B(x)(2) x(A(x)B(x) xA(x)xB(x) (3) x(A(x)B(x) xA(x)xB(x)(4) x(A(x)B(x) xA(x)xB(x),一些常用的重要推理定律,一阶逻辑中新增加4条推理规则消去和引入规则: 全称量词消去(指定)规则 全称量词引入(推广)规则 存在量词引入( 推广)规则 存在量词消去(指定)规则,U: universal E: existential G: generalization I: instantiation,全称量词消去规则(简称UI规则) 这条规则含以下两种形式: xA(x) A(y) xA(x) A(c) ,两式成立的条件是 1.x是A(x)中自由出现的个体变项; 2.在式中,y为任意的不在A(x)中约束出现的个体变项; 3.在式中,c为个体域中任意的个体常项。只有在满足上述条件时,推理规则才成立! 在推理过程中 ,两种形式可根据需要选用。,例:设定义域为实数,取F(x,y)为xy,A(x)=yF(x,y),xA(x) xyF(x,y) 公式xA(x)是真命题。考虑如下推理是否正确 : xyF(x,y) 前提引入yF(y,y) UI规则 yF(y,y)是假命题,推理不正确出错的原因是违背了条件:xA(x) A(y)中, y应为任意的不在A(x)中约束出现的个体变项。,全称量词引入规则(简称UG规则)A(y) xA(x) 公式成立的条件是1.y在A(y)中自由出现,且y取任何值时A均为真 2.取代y的x不在A(y)中约束出现。,例:设定义域为实数,取F(x,y)为xy,A(y)=xF(x,y)=x(xy),A对任意给定的y都是真的。 如下推理是否正确 : xF(x,y) 前提引入xxF(x,x) UG xx(xx)是假命题,推理出错。出错的原因是违背了条件2:取代y的x不在A(y)中约束出现zxF(x,z) UG ,存在量词引入规则(简称EG规则)A(c) xA(x) 公式成立的条件是1.c是特定的个体常项 ; 2.取代c的x不能已在A(c)中出现过 。 例1:设定义域为实数,取F(x,y)为xy, A(2)=xF(x,2)= x(x2),(真命题) 如下推理是否正确 : xF(x,2) 前提引入xxF(x,x) EG 假命题,推理出错。出错的原因是违背了条件2,x已在A(2)中出现过。,存在量词引入规则(简称EG规则)A(c) xA(x) 公式成立的条件是1.c是特定的个体常项 ; 2.取代c的x不能已在A(c)中出现过 。 例1:设定义域为实数,取F(x,y)为xy, A(2)=xF(x,2)= x(x2),(真命题) 如下推理是否正确 : xF(x,2) 前提引入yxF(x,y) EG, ,存在量词消去规则(简称EI规则)xA(x) A(c) 公式成立的条件是1.c是使A为真的特定的个体常项;2.c不曾在A(x)中出现过;3.A(x)中除x外没有其他自由出现的个体变项。,例: 在自然数集中,设F(x)为x是奇数,G(x)是x是偶数,则xF(x)xG(x)是真命题.以下推论是否正确: (1) xF(x)xG(x) 前提引入 (2) xF(x) (1)化简规则 (3) xG(x) (1)化简规则 (4) F(a) (2)EI规则 (5) G(a) (3)EI规则 (6) F(a)G(a) (4)(5)合取规则 (7) x(F(x)G(x) (6)EG规则,例: 在自然数集中,设F(x)为x是奇数,G(x)是x是偶数,则xF(x)xG(x)是真命题.以下推论是否正确: (1) xF(x)xG(x) 前提引入 (2) xF(x) (1)化简规则 (3) xG(x) (1)化简规则 (4) F(a) (2)EI规则 (5) G(a) (3)EI规则 (6) F(a)G(a) (4)(5)合取规则 (7) x(F(x)G(x) (6)EG规则 出错的原因是存在量词消去规则 xA(x) A(c) 时违背了条件:c是使A为真的特定的个体常项,例: 在自然数集中,设F(x)为x是奇数,G(x)是x是偶数,则xF(x)xG(x)是真命题. 以下推理是否正确: (1) xF(x)xG(x) 前提引入 (2) xF(x) (1)化简规则 (3) xG(x) (1)化简规则 (4) F(a) (2)EI (5) G(b) (3)EI (6) F(a)G(b) (4)(5)合取规则 (7) x(F(x)G(x) (6)EG,例: 在自然数集中,设F(x)为x是奇数,G(x)是x是偶数,则xF(x)xG(x)是真命题. 以下推理是否正确: (1) xF(x)xG(x) 前提引入 (2) xF(x) (1)化简规则 (3) xG(x) (1)化简规则 (4) F(a) (2)EI (5) G(b) (3)EI (6) F(a)G(b) (4)(5)合取规则 (7) x(F(x)G(x) (6)EG (7)x(F(x)G(b) (6)EG (8)xy(F(x)G(y) (7)EG 在应用以上4条量词规则时,要特别注意!,一阶逻辑推理实例,命题逻辑中的推理规则及在一阶逻辑中的代换实例,在一阶逻辑推理中仍然使用 量词消去和引入规则,例: 证明苏格拉底三段论“凡人都是要死的。苏格拉底是人.所以苏格拉底是要死的。” 命题符号化:F(x):x是人(特性谓词);G(x):x是要死的;a:苏格拉底 前提:x(F(x)G(x)),F(a) 结论:G(a) 证明: (1)x(F(x)G(x)) 前提引入 (2)F(a)G(a) UI(2) (3)F(a) 前提引入 (4)G(a) (2)(3)假言推理,例1:所有的有理数都是实数,有的有理数是整数。所以,有的实数是整数。 请在一阶逻辑中证明上述推理的正确性。证明: 命题符号化: 令F(x) :x为有理数; G(x) :x为实数; H(x) :x为整数前提: x ( F(x) G(x) , x ( F(x) H(x) )结论: x ( G(x) H(x) ),例1:所有的有理数都是实数,有的有理数是整数。所以,有的实数是整数。请在一阶逻辑中证明上述推理的正确性。证明:命题符号化:F(x) :x为有理数; G(x) :x为实数; H(x) :x为整数,前提:“ x ( F(x) G(x) ,$x ( F(x) H(x) )结论: $ x ( G(x) H(x) ),前提:“ x ( F(x) G(x) ,$x ( F(x) H(x) )结论: $ x ( G(x) H(x) ),证明: $x ( F(x) H(x) ) 前提引入 F(c) H(c) EI “ x ( F(x) G (x) ) 前提引入 F(c) G(c) UI F(c) 化简 G(c) 假言推理 H(c) 化简 G(c) H(c) 合取 $ x ( G(x) H(x) ) EG,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号