离散数学第五章.doc

一阶逻辑等值式与置换规则
  设A,B是一阶逻辑中任意两个公式,若AB是永真式,则称A与B是等值的。记做AB,称AB是等值式。
    谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式类似。下面主要讨论关于量词的等值式。
一、基本等值式
   第一组代换实例
   由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式,因而第二章的16组等值式给出的代换实例都是一阶逻辑的等值式的模式。例如:
        xF(x)┐┐xF(x)
        xy(F(x,y)→G(x,y))┐┐xy(F(x,y)→G(x,y))
等都是()式的代换实例。又如:
        F(x)→G(y)┐F(x)∨G(y)
        x(F(x)→G(y))→zH(z)┐x(F(x)→G(y))∨zH(z))
等都是()式的代换实例。
    第二组消去量词等值式
   设个体域为有限域D={a1,a2,…,an},则有
    (1)xA(x)A(a1)∧A(a2)∧…∧A(an)
    (2)xA(x)A(a1)∨A(a2)∨…∨A(an)     ()
   第三组量词否定等值式
   设A(x)是任意的含有自由出现个体变项x的公式,则
    (1)┐xA(x)x┐A(x)
    (2)┐xA(x)x┐A(x)                ()
    ()式的直观解释是容易的。对于(1)式,“并不是所有的x都有性质A”与“存在x没有性质A”是一回事。对于(2)式,“不存在有性质A的x”与“所有x都没有性质A”是一回事。
   第四组量词辖域收缩与扩张等值式
   设A(x)是任意的含自由出现个体变项x的公式,B中不含x的出现,则
    (1)x(A(x)∨B)xA(x)∨B
       x(A(x)∧B)xA(x)∧B
       x(A(x)→B)xA(x)→B
       x(B→A(x))B→xA(x)            ()
    (2)x(A(x)∨B)xA(x)∨B
       x(A(x)∧B)xA(x)∧B
       x(A(x)→B)xA(x)→B
       x(B→A(x))B→xA(x)            ()
    注意:这些等值式的条件。
    第五组量词分配等值式
   设A(x),B(x)是任意的含自由出现个体变项x的公式,则
    (1)x(A(x)∧B(x))xA(x)∧xB(x)
    (2)x(A(x)∨B(x))xA(x)∨xB(x)   ()
二、基本规则
    
    设Φ(A)是含公式A的公式,Φ(B)是用公式B取代Φ(A)中所有的A之后的公式,若AB,则Φ(A)Φ(B).
    一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同,只是在这里A,B是一阶逻辑公式。
    
    设A为一公式,将A中某量词辖域中某约束变项的所有出现及相应的指导变元改成该量词辖域中未曾出现过的某个体变项符号,公式的其余部分不变,设所得公式为A',则A'A.
    
    设A为一公式,将A中某个自由出现的个体变项的所有出现用A中未曾出现过的个体变项符号代替,A中其余部分不变,设所得公式为A',则A'A.
三、等值演算
  将下面公式化成与之等值的公式,使其没有既是约束出现又是自由出现的个体变项。
    (1)xF(x,y,z)→yG(x,y,z)
    (2)x(F(x,y)→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)    (换名规则)
原公式中,x,y都是既约束出现又有自由出现的个体变项,只有z仅自由出现。而在最后得到的公式中,x,y,z,t,w中再无既是约束出现又有自由出现个体变项了。还可以如下演算,也可以达到要求。
         
xF(x,y,z)→yG(x,y,z)
      xF(x,t,z)→yG(x,y,z)     (代替规则)
      xF(x,t,z)→yG(w,y,z)     (代替规则)
    (2)x(F(x,y)→yG(x,y,z))
    x(F(x,t)→yG(x,y,z))       (代替规则)
或者
        x(F(x,y)→yG(x,