Dafny GCD 引理证明
Dafny GCD lemma Proof
我想用 dafny 来证明以下关于 GCD 的引理:对于所有 k 个自然数,如果 k|a 和 k|b,则 k|gcd(a,b)。到目前为止我有以下代码:
// Euclid's algorithm for computing the greatest common divisor
function gcd(a: nat, b: nat): nat
requires a > 0 && b > 0
{
if a == b then a else
if b > a then gcd(a, b - a) else
gcd(a - b, b)
}
predicate divides(a: nat, b:nat)
requires a > 0
{
exists k: nat :: b == k * a
}
lemma dividesLemma(a: nat, b: nat)
//k|a && k|b ==> k|gcd(a,b)
requires a > 0 && b > 0
ensures gcd(a,b) > 0
ensures forall k: nat :: divides(a,k) && divides(b,k) ==> divides(gcd(a,b),k)
{
if(a == b) {
assert a * 1 == gcd(a,b);
assert b * 1 == gcd(a,b);
} else if b > a {
if(divides(a, b)) {
assert divides(a,a);
assert divides(a,b);
assert divides(a, gcd(a,b));
} else {
dividesLemma(a, b - a);
}
} else {
if(divides(b, a)) {
assert divides(b,b);
assert divides(b,a);
assert divides(b, gcd(a,b));
} else {
dividesLemma(a, a - b);
}
}
}
我知道如何手工证明这一点。我会考虑 a 和 b 的素数分解,并说 gcd(a,b) 是组合素数分解,这样我们就可以从每个素数分解中得到最少数量的素数。例如,如果 a = 9 和 b = 15,则 9 = 3x3 的素数分解和 15 = 3x5 的素数分解,因此 gcd(9,5) = 3 因为这是它们素数分解的最小组合。使用这个事实应该清楚,如果 k|b 和 k|a,k 必须包含那些最小素数。我怎样才能用dafny表达这个?目前,我正在考虑 if a=b 和 if a|b 或 b|a 的基本情况,但不确定如何将 a 和 b 可能在其素数分解中不共享公共素数这一事实结合起来。
任何帮助将不胜感激!
divides
的调用方式有问题。我认为
在 ensures 子句中你的意思是 divides(k, a)
而不是 divides(a, k)
divides(b, k)
和 divides(gcd(a, b), k)
.
同样如此
在递归调用 dividesLemma(a, b - a)
之后解决这个问题的一种方法是
使用方法的后置条件。这里我们知道对于所有 k
这样 k
除 a
和 k
除 b - a
意味着 k
除 gcd(a, b-a)
。使用此信息,我们尝试证明所需的后置条件(代码或证明很容易遵循)
dividesLemma(a, b - a);
assert gcd(a, b) == gcd(a, b-a);
assert forall k : nat :: k > 0 && divides(k, a) && divides(k, b-a) ==> divides(k, gcd(a, b));
forall k : nat | k > 0 && divides(k, a) && divides(k, b) ensures divides(k, gcd(a, b)) {
var m :| a == m * k;
var n :| b == n * k;
assert (b - a) == (n - m) * k;
assume n >= m;
assert divides(k, a);
assert divides(k, b-a);
// Implied from last assert forall
assert divides(k, gcd(a, b));
}
这里我假设n >= m
因为divides
需要n-m
是nat
,这可以单独证明。
另外第二个递归调用应该是dividesLemma(a - b, b)
.
function gcd(a: nat, b: nat): nat
requires a > 0 && b > 0
{
if a == b
then a
else if a < b
then gcd(a, b-a)
else gcd(a-b, b)
}
predicate divides(a: nat, b: nat)
requires a > 0 && b > 0
{
exists k: nat :: b == k * a
}
lemma helper(a: nat, b: nat, k : nat)
requires a > 0 && b > 0 && k > 0
requires divides(k, a) && divides(k, b)
requires b >= a
ensures exists m, n :: a == m * k && b == n * k && m <= n;
{ }
lemma dividesLemma(a: nat, b: nat)
decreases a + b
requires a > 0 && b > 0
ensures gcd(a, b) > 0
ensures forall k: nat :: k > 0 && divides(k, a) && divides(k, b) ==> divides(k, gcd(a, b))
{
if (a == b){
}
else if (b > a){
dividesLemma(a, b - a);
assert gcd(a, b) == gcd(a, b-a);
assert forall k : nat :: k > 0 && divides(k, a) && divides(k, b-a) ==> divides(k, gcd(a, b));
forall k : nat | k > 0 && divides(k, a) && divides(k, b) ensures divides(k, gcd(a, b)) {
helper(a, b, k);
var m, n :| a == m * k && b == n * k && m <= n;
assert b - a == (n - m) * k;
assert divides(k, b-a);
}
}
else {
dividesLemma(a - b, b);
assert gcd(a, b) == gcd(a - b, b);
assert forall k : nat :: k > 0 && divides(k, a-b) && divides(k, b) ==> divides(k, gcd(a, b));
forall k : nat | k > 0 && divides(k, a) && divides(k, b) ensures divides(k, gcd(a, b)) {
helper(b, a, k);
var m, n :| b == m * k && a == n * k && m <= n;
assert a - b == (n - m) * k;
assert divides(k, a-b);
}
}
}
我想用 dafny 来证明以下关于 GCD 的引理:对于所有 k 个自然数,如果 k|a 和 k|b,则 k|gcd(a,b)。到目前为止我有以下代码:
// Euclid's algorithm for computing the greatest common divisor
function gcd(a: nat, b: nat): nat
requires a > 0 && b > 0
{
if a == b then a else
if b > a then gcd(a, b - a) else
gcd(a - b, b)
}
predicate divides(a: nat, b:nat)
requires a > 0
{
exists k: nat :: b == k * a
}
lemma dividesLemma(a: nat, b: nat)
//k|a && k|b ==> k|gcd(a,b)
requires a > 0 && b > 0
ensures gcd(a,b) > 0
ensures forall k: nat :: divides(a,k) && divides(b,k) ==> divides(gcd(a,b),k)
{
if(a == b) {
assert a * 1 == gcd(a,b);
assert b * 1 == gcd(a,b);
} else if b > a {
if(divides(a, b)) {
assert divides(a,a);
assert divides(a,b);
assert divides(a, gcd(a,b));
} else {
dividesLemma(a, b - a);
}
} else {
if(divides(b, a)) {
assert divides(b,b);
assert divides(b,a);
assert divides(b, gcd(a,b));
} else {
dividesLemma(a, a - b);
}
}
}
我知道如何手工证明这一点。我会考虑 a 和 b 的素数分解,并说 gcd(a,b) 是组合素数分解,这样我们就可以从每个素数分解中得到最少数量的素数。例如,如果 a = 9 和 b = 15,则 9 = 3x3 的素数分解和 15 = 3x5 的素数分解,因此 gcd(9,5) = 3 因为这是它们素数分解的最小组合。使用这个事实应该清楚,如果 k|b 和 k|a,k 必须包含那些最小素数。我怎样才能用dafny表达这个?目前,我正在考虑 if a=b 和 if a|b 或 b|a 的基本情况,但不确定如何将 a 和 b 可能在其素数分解中不共享公共素数这一事实结合起来。
任何帮助将不胜感激!
divides
的调用方式有问题。我认为
在 ensures 子句中你的意思是 divides(k, a)
而不是 divides(a, k)
divides(b, k)
和 divides(gcd(a, b), k)
.
在递归调用 dividesLemma(a, b - a)
之后解决这个问题的一种方法是
使用方法的后置条件。这里我们知道对于所有 k
这样 k
除 a
和 k
除 b - a
意味着 k
除 gcd(a, b-a)
。使用此信息,我们尝试证明所需的后置条件(代码或证明很容易遵循)
dividesLemma(a, b - a);
assert gcd(a, b) == gcd(a, b-a);
assert forall k : nat :: k > 0 && divides(k, a) && divides(k, b-a) ==> divides(k, gcd(a, b));
forall k : nat | k > 0 && divides(k, a) && divides(k, b) ensures divides(k, gcd(a, b)) {
var m :| a == m * k;
var n :| b == n * k;
assert (b - a) == (n - m) * k;
assume n >= m;
assert divides(k, a);
assert divides(k, b-a);
// Implied from last assert forall
assert divides(k, gcd(a, b));
}
这里我假设n >= m
因为divides
需要n-m
是nat
,这可以单独证明。
另外第二个递归调用应该是dividesLemma(a - b, b)
.
function gcd(a: nat, b: nat): nat
requires a > 0 && b > 0
{
if a == b
then a
else if a < b
then gcd(a, b-a)
else gcd(a-b, b)
}
predicate divides(a: nat, b: nat)
requires a > 0 && b > 0
{
exists k: nat :: b == k * a
}
lemma helper(a: nat, b: nat, k : nat)
requires a > 0 && b > 0 && k > 0
requires divides(k, a) && divides(k, b)
requires b >= a
ensures exists m, n :: a == m * k && b == n * k && m <= n;
{ }
lemma dividesLemma(a: nat, b: nat)
decreases a + b
requires a > 0 && b > 0
ensures gcd(a, b) > 0
ensures forall k: nat :: k > 0 && divides(k, a) && divides(k, b) ==> divides(k, gcd(a, b))
{
if (a == b){
}
else if (b > a){
dividesLemma(a, b - a);
assert gcd(a, b) == gcd(a, b-a);
assert forall k : nat :: k > 0 && divides(k, a) && divides(k, b-a) ==> divides(k, gcd(a, b));
forall k : nat | k > 0 && divides(k, a) && divides(k, b) ensures divides(k, gcd(a, b)) {
helper(a, b, k);
var m, n :| a == m * k && b == n * k && m <= n;
assert b - a == (n - m) * k;
assert divides(k, b-a);
}
}
else {
dividesLemma(a - b, b);
assert gcd(a, b) == gcd(a - b, b);
assert forall k : nat :: k > 0 && divides(k, a-b) && divides(k, b) ==> divides(k, gcd(a, b));
forall k : nat | k > 0 && divides(k, a) && divides(k, b) ensures divides(k, gcd(a, b)) {
helper(b, a, k);
var m, n :| b == m * k && a == n * k && m <= n;
assert a - b == (n - m) * k;
assert divides(k, a-b);
}
}
}