You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

Dafny递归触发器调试:整数抽象幂定义的验证困境

递归触发器导致Dafny验证无限循环的调试方法求助

我正在为所有整数扩展抽象幂(apow)的定义,尽管已经设置了触发器,但仍陷入递归触发器引发的无限验证循环。目前只能通过任务管理器观察Z3是否占用大量内存,希望能找到更高效的递归触发器调试方法,避免盲目试错。

相关代码如下:

function apow<A>(g: Group, elem: A, n: int): A
    decreases n*n
    ensures n == 0 ==> apow(g,elem,n) == g.identity
{
    if n == 0 then g.identity else if n > 0 then g.compose(elem, apow(g, elem, n-1)) else if n < 0 then g.compose(g.inverse(elem), apow(g, elem, n+1)) else g.identity
}

lemma apowClosed<A>(g: Group, elem: A, n: int)
    requires elem in g.elements
    requires g.identity in g.elements
    requires isIdentity(g)
    requires closedComposition(g)
    requires closedInverse(g)
    requires isInverse(g)
    decreases n*n
    ensures apow(g, elem, n) in g.elements
{}

lemma allApowClosed<A>(g: Group, elem: A) 
    requires ValidGroup(g)
    requires elem in g.elements
    ensures forall x: int :: apow(g, elem, x) in g.elements
{
    reveal apow();
    forall x: int {
        apowClosed(g, elem, x);
    }
}

lemma {:verify true} apowAdditionInt<A>(g: Group<A>, elem: A, n: int, k: int)
    requires elem in g.elements
    // requires ValidGroup(g)
    requires closedComposition(g)
    requires closedInverse(g)
    requires g.identity in g.elements
    requires isIdentity(g);
    requires associativeComposition(g)
    ensures g.compose(apow(g, elem, n), apow(g, elem, k)) == apow(g, elem, n+k)
{
    allApowClosed(g, elem);
    if k == 0 {
        assert apow(g, elem, k) == g.identity;
        assert g.compose(apow(g, elem, n), g.identity) == apow(g, elem, n+k);
    }else if n == 0 {
        assert apow(g, elem, n) == g.identity;
        assert g.compose(g.identity, apow(g, elem, k)) == apow(g, elem, n+k);
    }else if n > 0 && n+k > k {
        apowPos(g, elem, n);
        apowPos(g, elem, n+k);
        assert apow(g, elem, n-1) in g.elements;
        assert apow(g, elem, k) in g.elements;
        assert apow(g, elem, n+k) in g.elements;
        // assume g.compose(elem, g.compose(apow(g, elem, n-1), apow(g, elem, k))) == g.compose(elem, apow(g, elem, n-1+k));
        calc {
            g.compose(apow(g, elem, n), apow(g, elem, k));
            g.compose(g.compose(elem, apow(g, elem, n-1)), apow(g, elem, k));
            g.compose(elem, g.compose(apow(g, elem, n-1), apow(g, elem, k)));
            == {apowAdditionInt(g,elem, n-1,k);}
            g.compose(elem, apow(g, elem, n-1+k));
            // apow(g, elem, n+k);
        }
    }else{

    }
}
datatype Group<!A> = Group(elements: set<A>, identity: A, compose: (A,A) -> A, inverse: (A) -> A)

predicate isIdentity<A>(g: Group<A>) {
    forall a :: a in g.elements ==> g.compose(a,g.identity) == a && g.compose(g.identity, a) == a
}

predicate closedComposition<A>(g: Group<A>) {
    forall x,y :: x in g.elements && y in g.elements ==> g.compose(x,y) in g.elements
}

predicate associativeComposition<A>(g: Group<A>) {
    forall a,b,c :: a in g.elements && b in g.elements && c in g.elements ==> g.compose(g.compose(a,b),c) == g.compose(a, g.compose(b,c))
}
predicate closedInverse<A>(g: Group<A>) {
forall x {:trigger g.inverse(x)} :: x in g.elements ==> g.inverse(x) in g.elements
}

predicate isInverse<A>(g: Group<A>) {
forall x {:trigger g.inverse(x)} :: x in g.elements ==> g.compose(x,g.inverse(x)) == g.identity && g.compose(g.inverse(x),x) == g.identity
}

内容的提问来源于stack exchange,提问作者Hath995

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.08.03 10:15:34