《数学部分 一阶逻辑0》由会员分享，可在线阅读，更多相关《数学部分 一阶逻辑0（37页珍藏版）》请在金锄头文库上搜索。
1、离散数学,一阶逻辑推理理论,内容回顾,一阶逻辑合式公式及解释 一阶逻辑等值式及前束范式,例:给定解释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），都有
2、: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),今日内容,一阶逻辑推理理论 推理形式的定义 量词引入和消去规则 一阶逻辑下的推理证明,一阶逻辑推理理论,在一阶逻辑中，推理的形式结构仍为A1A2
3、AkB若该式是永真式，则称推理正确，称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),量词分配
4、等值式: 对于任意的公式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
5、: 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
6、,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)中约束
7、出现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
8、(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规则
9、 (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为真的特定的个体常项,例: 在自然数集中，
10、设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
11、) (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
12、（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,
