0

我正在尝试使用 Welder 通过双重感应来证明一个属性。定义取自这里。可以在此处找到提供该理论更多细节的相关问题。无论如何，我只需要一些部分来显示我的问题：

基本上，我正在使用整数形式的表达式，POP(i,p)并且POW(i,p,q). 它们有一个正态性，称为 n。我想证明 if n(x) && n(y)then n(x+y)。

我们来看看具体的情况x = POP(i,p)，y = POP(j,q)然后x+y定义如下：

if i = j then pop(i,p+q)
if i > j then pop(j,POP(i-j,p)+q)
if i < j then pop(i,POP(j-i,q)+p)

wherepop是一个模拟POP具有一些细微差异的构造的函数。

我在 Welder 中通过双重归纳进行证明如下：

def property(x: Expr) = {
  forall("y" :: shf){ case (y) => 
    (n(x) && n(y)) ==> n(x+y)
  } 
}
structuralInduction(property _, "x" :: shf) { case (ihs1, goal1) =>
  val xi = ihs1.expression
  xi match{
  ...

我要关注的相关案例如下：

case C(`POP_ID`,i,pshf) =>
  def popproperty(y: Expr) = { 
    n(y) ==> n(xi+y) 
  }
  structuralInduction(popproperty _, "y" :: shf) { case (ihs2, goal2) =>
   val yi = ihs2.expression
   implI(n(yi)){ axioms2 =>
    yi match{
     case C(`constshfID`, fc) => andI(ihs1.hypothesis(pshf),axioms1)
     case C(`POP_ID`,j,qshf) => 
      andI(
       implE(forallE(normpop1Lemma)(i,normadd(pshf,qshf)))( g => 
        andI(implE(forallE(ihs1.hypothesis(pshf))(qshf))( g => 
         andI(axioms1,axioms2)), axioms1, axioms2)),
       implI(i > j){ gt => 
        implE(forallE(normpop1Lemma)(i,normadd(POP(i-j,pshf),qshf)))( g => 
         andI(implE(ihs2.hypothesis(qshf))(g => axioms2),axioms1,axioms2,gt))                            
       },
       implI(i < j){ lt => 
        implE(forallE(normpop1Lemma)(i,normadd(POP(j-i,pshf),qshf)))( g => 
         andI(implE(ihs2.hypothesis(qshf))(g => axioms2),axioms1,axioms2,lt))
                            
    }
   )

这里normpop1Lemma指出，为了拥有n(pop(i,p))你需要i自然和p正常。但是，我发现第二种情况没有得到证明。事实上，我需要将第二个属性概括为

def popproperty(y: Expr) = { 
  forall("x" :: shf){
   n(y) ==> n(x+y) 
  }
}

但那我不是在打破感应吗？我真的可以解决这些案件i > j吗i < j？（在我实验的时候还有更多）

编辑

目前，我可以先在 y 上感应，然后在 x 上感应，对于 POP-POP 案例，我可以显示哪些情况i = j，i > j但i < j不是。我认为它可以通过使用它来工作，POP(j-i,q) + p = p + POP(j-i,q)但事实并非如此。

相反，现在我试图证明两个不同的属性，假设其中一个案例不能成立（要么 thei < j要么 the i > j）。

4

1 回答 1

1

嗯，我希望你的证明看起来更像这样：

structuralInduction((x: Expr) =>
  forall("y" :: shf)(y => (n(x) && n(y)) ==> n(x+y)), "x" :: shf
) { case (ihs1, g1) =>
  structuralInduction((y: Expr) =>
    (n(ihs1.expression) && n(y)) ==> n(ihs1.expression+y), "y" :: shf
  ) { case (ihs2, g2) =>
    implI(n(ihs1.expression) && n(ihs2.expression)) { normalXY =>
      (ihs1.expression, ihs2.expression) match {
        case (C(`POP_ID`,i,pshf), C(`POP_ID`,j,qshf)) => andI(
           ... // case (i == j)
           ... // case (i > j)
           implI(i < j) { iLtJ =>
             andI(
               ... // stuff using normprop1Lemma
               implE(forallE(ihs1.hypothesis(pshf))(normadd(POP(j-i,qshf)) {
                 g => // the reason why n(normadd(POP(j-i,qshf)) and n(pshf)
               },
               ... // invoke some lemma showing x+y == y+x
             )
           }
        )
      }
    }
  }
}

在这里，我们使用来自外部归纳的归纳假设，因为我们正在对 执行归纳p \in x。我想normprop1Lemma是告诉你这normadd(POP(j-i,qshf))是正常的形式。如果是正常形式，您可能需要一些引理说明它p \in x是x正常形式。

希望这可以帮助！

于 2017-05-21T15:53:48.933 回答