如何在 dafny 中证明分数加法

Question

我想证明以下分数加法。即j/2+k/2 = (j+k)/2。为此，我有以下内容：

lemma adding_fraction(j: nat, k: nat)
    ensures j / 2 + k / 2 == (j + k) / 2
{
    assert j / 2 + k / 2
        == j * (1 / 2) + k * (1 / 2)
        == (1/2) * (j + k)
        == (j + k) / 2
    assert j/2 + k/2 == (j + k) / 2;
}

我在这个引理的最后一个 like 上收到无效的 AssertStmt 错误。我不完全确定为什么。此外，我不确定为什么达夫尼已经无法证明这一点。有人可以就如何证明这个引理提供一些帮助吗？

我现在确实看到一个错误。即在 dafny 1/2 == 0 是真的。所以所有的除法似乎都是通过 floor 操作完成的。上面的代码中说的是 j%2=0 和 k%2=0 然后 dafny 能够证明它没有问题。我怎样才能强迫达夫尼不使用地板？这是一个问题，因为在现实生活中：1/2 + 5/2 = 6/2 = 3 但在地板上：1/2 + 5/2 = 0 + 2 = 2.

Answer 1

首先，引理不正确。如果 j 和 k 都是奇数，那么 j / 2 + k / 2 将比 (j + k) / 2 少一，因为除法是截断整数除法。例如，我们可以在 Dafny

中证明如下反例

lemma counterexample()
  ensures var j := 1; var k := 3;
    !(j / 2 + k / 2 == (j + k) / 2)
{}

关于你的另一个问题，你在倒数第二行少了一个分号。 Dafny 的错误消息可以在此处改进，但最好记住，Dafny 每次报告“无效”时，都是语法错误，您应该注意错别字。此错误的完整 Dafny 消息是（大致）

tmp.dfy(8,4): Error: invalid AssertStmt
1 parse errors detected in tmp.dfy

你可以看到它至少包含一个行号（对于后缺少分号的断言）和错误消息第二行的短语“parse errors” .

修复此语法错误后，有几个语义错误与无法证明断言有关。这些的根本原因是引理是错误的。

如何在 dafny 中证明分数加法

How to prove fraction addition in dafny

fractions

dafny