选择排序的程序正确性、不变量和谓词逻辑

Question

我正在尝试证明选择排序的正确性，其中我应该只使用数学谓词逻辑来证明程序的正确性，我发现很难将下面给出的英文语句写成谓词并继续通过遵循推理规则的正确性证明，

void sort(int [] a, int n) {
  for (int i=0; i<n-1; i++) {
    int best = i;
    for (int j=i; j<n; j++) {
      if (a[j] < a[best]) {
        best = j;
      }
    }
    swap a[i] and a[best];
  }
}

我必须在谓词中编写的语句是，

a[0...i-1]排序为
a[i..n-1] 中的所有条目都大于或等于 a[0..i-1] 中的条目。

Answer 1

关于像 a[0...i-1] 这样的子数组的语句实际上是关于该子数组中所有元素的语句，因此您需要使用 universal quantifiers 将其转换为关于单个成员的语句。

要说一个子数组是有序的，我们可以这样说："for any pair of indices j < k in the subarray, the values at those indices are in order."

For all 0 <= j < i-1, for all j < k <= i-1, arr[j] <= arr[k].

第二个属性已经写成关于两个子数组的"all entries"的语句，但让我们更明确一点："for any pair of indices j in the first subarray and k in the second subarray, the value in the first subarray is less than or equal to the value in the second subarray."

For all 0 <= j <= i-1, for all i <= k <= n-1, arr[j] <= arr[k].

选择排序的程序正确性、不变量和谓词逻辑

Program Correctness, Invariants and Predicate Logic for selection sort

predicate

proof-of-correctness

hoare-logic