《离散数学教学课件：lecture 5 一阶逻辑等值式与置换规则》由会员分享，可在线阅读，更多相关《离散数学教学课件：lecture 5 一阶逻辑等值式与置换规则（16页珍藏版）》请在金锄头文库上搜索。
1、定义定义5.1设A，B是一阶逻辑中任意两个公式，若AB是永真式，则称A与B是等值等值的。记做AB，称AB是等值式等值式。一、基本等值式一、基本等值式第一组代换实例由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式，因而第二章的16组等值式给出的代换实例都是一阶逻辑的等值式的模式。例如：xF(x)xF(x)F(x)G(y)F(x)G(y)第二组消去量词等值式设个体域为有限域D=a1,a2,an，则有(1)xA(x)A(a1)A(a2)A(an)(2)xA(x)第三组量词否定等值式设A(x)是任意的含有自由出现个体变项x的公式，则(1)xA(x)xA(x)(2)xA(x)A(a1)A(a2)A
2、(an)(5.1)xA(x)(5.2)第四组量词辖域收缩与扩张等值式设A(x)是任意的含约束出现个体变项x的公式，B中不含x的出现，则(1)x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x)BxA(x)(5.3)(2)x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x)BxA(x)(5.4)第五组量词分配等值式设A(x)，B(x)是任意的含自由出现个体变项x的公式，则(1)x(A(x)B(x)）(2)x(A(x)B(x)）xA(x)xB(x)xA(x)xB(x)(5.5)问：x(A(x)B(x)）xA
3、(x)xB(x)?二、基本规则二、基本规则1置换规则设(A)是含公式A的公式，(B)是用公式B取代(A)中所有的A之后的公式，若AB，则(A)(B).2换名规则设A为一公式，将A中某量词辖域中某约束变项的所有出现及相应的指导变元改成该量词辖域中未曾出现过的某个体变项符号，公式的其余部分不变，设所得公式为A，则AA.3代替规则设A为一公式，将A中某个自由出现的个体变项的所有出现用A中未曾出现过的个体变项符号代替，A中其余部分不变，设所得公式为A，则AA.三、等值演算三、等值演算例例5.1将下面公式化成与之等值的公式，使其没有既是约束出现又是自由出现的个体变项。xF(x,y,z)yG(x,y,z)
4、解解2.xF(x,y,z)yG(x,y,z)xF(x,t,z)yG(x,y,z)(代替规则)解解1.xF(x,y,z)yG(x,y,z)tF(t,y,z)yG(x,y,z)(换名规则)tF(t,y,z)wG(x,w,z)(换名规则)xF(x,t,z)yG(w,y,z)(代替规则)四、一阶逻辑公式的标准形四、一阶逻辑公式的标准形前束范式前束范式定义定义5.2设A为一个一阶逻辑公式，若A具有如下形式Q1x1Q2x2QkxkB则称A为前束范式前束范式，其中Qi(1ik)为或，B为不含量词的公式。定理定理5.1(前束范式存在定理)一阶逻辑中的任何公式都存在与之等值的前束范式。例例5.6求下面公式的前束
5、范式：xF(x)xG(x)解解1.xF(x)xG(x)xF(x)yG(y)(换名规则)或者解解2.xF(x)xG(x)xF(x)xG(x)(5.2)第二式)xF(x)yG(y)(5.2)第二式)x(F(x)yG(y)(5.3)第二式)xy(F(x)G(y)(5.3)第二式)x(F(x)G(x)(5.5)第一式)五、推理定律五、推理定律第一组命题逻辑推理定律的代换实例。例如：xF(x)yG(y)=xF(x)xF(x)=xF(x)yG(y)分别为命题逻辑中化简律和附加律的代换实例。第二组由基本等值式生成的推理定律。上一节给出的两组等值式中的每个等值式可生成两个推理定律。例如：xF(x)=xF(x)
6、xF(x)=xF(x)和xF(x)=xF(x)xF(x)=xF(x)分别由双重否定律和量词否定等值式生成。第三组还有下面各重要推理定律。例如：(1)xA(x)xB(x)=(2)x(A(x)B(x)=(3)x(A(x)B(x)=(4)x(A(x)B(x)=x(A(x)B(x)xA(x)xB(x)xA(x)xB(x)xA(x)xB(x)问：x(A(x)B(x)）=xA(x)xB(x)?六、推理规则六、推理规则1全称量词消去规则(简记为UI规则或UI)两式成立的条件是：（1）在第一式中，取代x的y应为任意的不在A(x)中约束出现的个体变项。（2）在第二式中，c为任意个体变项。（3）用y或c去取代A(
7、x)中自由出现的x时，一定要在x自由出现的一切地方进行取代。2全称量词引入规则(简记为UG规则或UG)该式成立的条件是：（1）无论A(y)中自由出现的个体变项y取何值，A(y)应该均为真。（2）取代自由出现的y的x也不能在A(y)中约束出现。3存在量词引入规则(简称EG规则或EG)该式成立的条件是：（1）c是特定的个体常项。（2）取代c的x不能在A(c)中出现过。4存在量词消去规则(简记为EI规则或EI)该式成立的条件是：（1）c是使A为真的特定的个体常项。（2）c不在A(x)中出现。（3）若A(x)中除自由出现的x外，还有其它自由出现的个体变项，此规则不能使用。注意:UI、UG、EI和EG规
8、则只能对前束范式使用七、一阶逻辑自然推理系统七、一阶逻辑自然推理系统F定义定义5.3自然推理系统自然推理系统F定义如下：1字母表。同一阶语言的字母表。2合式公式。同合式公式的定义。3推理规则：（1）前提引入规则。（2）结论引入规则。（3）置换规则。（4）假言推理规则。（5）附加规则。（6）化简规则。（7）拒取式规则。（8）假言三段论规则。（9）析取三段论规则。（10）构造性二难推理规则。（11）合取引入规则。（12）UI规则。（13）UG规则。（14）EI规则。（15）EG规则。F中的推理过程类似命题演算自然推理系统P。例例5.9在自然推理系统F中，构造下面推理的证明：任何自然数都是整数；存在着自然数。所以存在着整数。个体域为实数集合R。解解先将原子命题符号化。设F(x):x为自然数，G(x):x为整数。前提：x(F(x)G(x),xF(x)结论：xG(x)证明：xF(x)前提引入F(c)EI规则x(F(x)G(x)前提引入F(c)G(c)UI规则G(c)假言推理xG(x)EG规则
