¿Por qué no puede Dafny probar que A[i-1] <= A[i] asegura que A[i] <= A[j] para i <= j?
Método fantasma lemma1(A:array
requiere A.Longitud>2
requiere para todo i:: 0 <= i-1 < i < A.Longitud ==> A[i-1] <= A[i]
asegura A[0] <= A[1] <= A[2]
{
}
El código anterior funciona, pero el siguiente no funciona
Método fantasma lemma2(A:array<int>)
requiere A.Longitud>2
requiere para todo i:: 0 <= i-1 < i < A.Longitud ==> A[i-1] <= A[i]
asegura A[0] <= A[2]
{
}
Método fantasma lemma3(A:array
requiere A.Longitud>2
requiere para todo i:: 0 <= i-1 < i < A.Longitud ==> A[i-1] <= A[i]
asegura para todo i,j :: 0 <= i < j < A.Longitud ==> A[i] <= A[j]
{
}
Problema: Una postcondición puede no ser válida en esta ruta de retorno.
¿Qué precondiciones adicionales requiere?
davy.ai
El código anterior se basa en un orden específico de los elementos en el arreglo A. Sin embargo, lemma2 y lemma3 tienen postcondiciones más débiles en comparación con lemma1, lo que significa que tienen garantías menos estrictas sobre el orden de los elementos. Por lo tanto, para preservar la postcondición del código original, lemma2 y lemma3 requieren precondiciones adicionales que aseguren el mismo orden de los elementos que en lemma1.
Para lemma2, una precondición adicional podría ser “A[1] <= A[2]”. Esto aseguraría que A[0] sea menor o igual que A[2] porque A[0] <= A[1] (según lo requerido por el código original), y A[1] <= A[2] (según lo garantizado por la precondición adicional).
Para lemma3, una precondición adicional podría ser “para todo i,j :: 0 <= i < j < A.Length ==>> A[i] <= A[j]”. Esto aseguraría que todos los pares de elementos en A estén ordenados, lo que implica el orden de los primeros tres elementos según lo requerido por el código original.