Hoare Logic while while while '<='

Question

나는 Hoare 논리를 연구 중이고 접근 방법이 올바른지 궁금해하고 있습니다.

I 다음 프로그램 P 가지고

s = 0 
i = 1 
while (i <= n) { 
    s = s + i 
    i = i + 1 
} 

는 그것은 호어 트리플 {N> = 0} P를 만족한다 {S = N에 *을 (N + 1)/2} (그래서 단지 걸리는 합집합). 자, 처음에 나는 | s = i * (i-1)/2 | 내 invariant로 잘 작동합니다. 그러나, 나는 나의 원하는 사후 조건에 루프의 끝으로가는 것에 문제가 있었다. impliciation에 대한

|s = i*(i-1)/2 & i > n| 
=> 
| s = n * (n+1)/2 | 

이 개최하기 때문에, 난 내가 N + 1을 증명해야하고, 다만 어떤 n보다 내가 더 큰. 그래서 내가 생각하는 것은되도록, 불변에 (내가 < = N + 1)을 추가하는 것입니다

|s = i * (i-1)/2 & i <= n+1| 

은 그 때 나는 그래서 그것을 올바른해야한다고 생각 프로그램을 증명할 수 있습니다.

그럼에도 불구하고, 나는 불변량이 조금 "불변 적으로 적다"는 것을 알게됩니다. :). 지금까지의 과정이나 연습에서 보았던 것과 흡사해서 더 우아한 해결책이 있는지 궁금합니다.

그럼에도 불구하고

|s = i * (i-1)/2 & i <= n+1| 

, 내가 할 불변을 찾을 :

Answer 1

그래서 제가 생각하는 것은되도록, 불변에 (내가 < = N + 1)를 추가하는 것입니다 조금, 덜 불변하게 :). 지금까지의 과정이나 연습에서 보았던 것과 흡사해서 더 우아한 해결책이 있는지 궁금합니다.

아니요, 코드 작성 방법이 주어진다면 정확히 그 방법입니다. (두 개의 다른 과목에서 여러 학기 동안 Hoare 논리를 가르쳐 왔기 때문에 경험에서 알 수 있습니다. 대학원 연구의 일부이기 때문에)

i <= n을 사용하는 것은 프로그래밍 할 때 좋은 방법으로 간주됩니다. 그러나 특정 프로그램에서, 당신은 단지뿐만 아니라 당신이 분명히 보유

| s=i*(i-1)/2 & i=n+1 | 
=> 
| s=n*(n+1)/2 | 

를 얻을 수 있기 때문에이 경우 첫 번째 불변을 (실제로 청소기 보이는)에 충분할 것 대신 i != n+1을 쓸 수 있었다.