Начальный вопрос относительно логики очень простого доказательства правильности

Question

Я пытаюсь ознакомиться с доказательствами правильности и нуждается в некоторой помощи.В Доказательство для Sampleflect (P.25), почему мы предполагаем, что мы как $ a '[i] и $ 1 \ leqя \ leq k $ ?Я не совсем уверен, почему мы делаем это, так как текст говорится, что «из того, что значит для алгоритма для удовлетворения его спецификации, любые доказательства правильности начнутся с предположения о предположении о состоянии».Однако не является предварительным условием здесь просто предварительное предварительное условие Simplelect, как указано здесь (стр. 6)?

Answer 1

Оба предположения, которые вы упоминаете, являются «местными» в том смысле, что они являются субклавом в доказательстве и не являются частью условий теоремы. Вы также можете увидеть их как определение локальной переменной $ i $ , эквивалентная формулировка двух предположений будет

1. Пусть $ i $ Будьте таким, что $ A '[I] и $ 1 \ leq i \ leq n $ .

2. Пусть $ i $ Будьте таким, что $ 1 \ leq i \ leq k $ .

Доказательство подсчитывает количество значений $ i $ , для которых эти операторы выполняются, что показывает, что постусловие выполняется.

---

Я думаю, что часть вашей путаницы следует из некоторого неявного языка в этих параграфах, поэтому я перепишу один из них в полном объеме быть более явными. Первый абзац из книги читает:

Предположим, $ a '[i] для некоторых $ i $ , $ 1 \ leq i \ leq n $ . Затем $ i , для Если $ k , $ a '[k]> a' [i] $ нарушает отсюда своего рода. Следовательно, есть меньше, чем $ k $ Элементы $ a '$ и, следовательно,
= «Математический контейнер»> $ a $ , со значением меньше, чем $ a '[k] $ .

Более явная фразы выглядит следующим образом:

Пусть $ i $ Будьте так, чтобы $ a '[i] И $ 1 \ leq i \ leq n $ . Если $ k , то $ A '[I] противоречит С постусловием сортировки, поэтому $ i \ leq k $ . Если $ i= k $ , то $ a '[i]= a' [k] $ , Что противоречит нашему определению $ i $ .

Итак, мы показали, что если $ a '[i] и $ 1 \ leq i \ leq n $ , затем $ i . Это означает, что количество элементов $ a '$ со значением строго меньше, чем $ a' [k] $ строго меньше, чем $ K $ . Поскольку $ A $ - это перестановка $ a '$ , есть меньше, чем $ k $ Элементы $ a $ строго меньше, чем $ a '[k] $ . Поскольку $ a '[k] $ - это возвращаемое значение алгоритма, первая часть поступления выбора удовлетворена.

Общая структура второго абзаца аналогична, поэтому вы сможете понять его, если вы сможете понять первую.