- •Формальные методы доказательства правильности программ и их спецификаицй
- •Общие положения
- •Предусловия и постусловия в доказательствах правильности
- •Правила вывода (доказательства)
- •Правило усиления предусловия и ослабления постусловия
- •Правило получения предусловия оператора присваивания
- •Правило проверки предусловия оператора присваивания
- •Правило проверки предусловия условного оператора if
- •Правило получения предусловия условного оператора if
- •Правило условного оператора if №1
- •Правило условного оператора if №2
- •Правило последовательности операторов
- •Правило цикла с условием продолжения без инициализации
- •Правило цикла с условием продолжения с инициализацией
- •Правило «разделяй и властвуй» №1
- •Правило «разделяй и властвуй» №2-4
- •Правило подпрограммы или сегмента программы №1
- •Правило подпрограммы или сегмента программы №2
- •Правило подпрограммы или сегмента программы №3
- •Применение правил вывода
- •Пример доказательства правильности программы для алгоритма дискретного экспоненцирования
- •Вводные замечания
- •Представление чисел
- •Алгоритм a*b modulo n - алгоритм выполнения операции модулярного умножения
Правило условного оператора if №1
Правило вывода IFЗ – «Условный оператор if»
If
{V1} OP1 {P} and
{V2} OP2 {Р}
then
{V1 and V2} if В then OP1 else OP2 endif {P}
Правило вывода IF3представляет собой слабую теорему, которая следует из правил выводаIF1иP1. Благодаря простой форме образующих ее выражений, на практике иногда она оказывается удобной для применения.
Правило условного оператора if №2
Правило вывода IF4 –«Условный оператор if»
If
{V1 and B} OP1 {P} and
{V2 and not B} OP2 {Р}
then
(V1 and V2} if В then OP1 else OP2 endif {Р}
Правило вывода IF4также следует из правил выводаIF1и P1. Подобно правилу выводаIF3оно обладает определенной практической полезностью вследствие простоты формы предусловия (V1 andV2).
Правило последовательности операторов
Правило вывода S1 - «Последовательность операторов»
If
{V} OP1 {P1} and
{P1} OP2 (Р}
then
{V} (OP1;OP2) {Р}
Правило вывода S1очевидным образом обобщается на последовательность операторов произвольной длины. Таким образом, для того чтобы отыскать предусловие для заданного постусловия по отношению к последовательности операторов, сначала отыщем предусловие дляРпо отношению к последнему оператору последовательности. Затем воспользуемся им в качестве постусловия по отношению к предыдущему, предпоследнему оператору и так далее, то есть будем продвигаться от оператора к оператору по последовательности в обратном направлении. Полученное таким образом предусловие по отношению к первому оператору последовательности является также предусловием дляР по отношению ко всей последовательности.
Правило цикла с условием продолжения без инициализации
Правило вывода W1 - «Цикл с условием продолжения без инициализации»
If
{I and B} OP {I}
then
{I} while В do S endwhile (I and not B}
Если условие Iистинно непосредственно перед началом выполнения цикла с условием продолжения, то иI, иВбудут истинными до первого выполнения тела цикла OP. Поскольку (IandВ) является предусловием дляIпо отношению к OP, тоIбудет истинным после первого выполнения OP. Поэтому иI, иВбудут истинными до второго выполнения тела циклаOPи так далее. УсловиеIбудет истинным после каждого выполнения OP. Если когда-то наступит такой момент, что выполнение цикла закончится, то условиеIбудет истинным, а условиеВложным. То есть условие (Iand notВ) будет истинным при завершении цикла (если завершится его выполнение).
Значение условия Iистинное, то есть константа, до и после каждого выполнения тела цикла OP. Поэтому условие Iназываютинвариантом цикла. Инвариант цикла является ключевым понятием в разработке и понимании существа цикла.
При применении правила вывода W1требуется, чтобы инвариант циклаIбыл истинным до выполнения цикла. Обычно инвариант Iизначально истинен тривиальным образом. Другими словами, начальное состояние представляет особый случай инварианта цикла. При завершении выполнения цикла условие (Iand notВ) истинно. То есть конечное состояние также представляет особый случай инвариантаI. Рассматривая инвариант цикла Iс общих позиций, его можно считать результатом обобщения начального и конечного состояний. Из последнего вытекает следующее правило.
Эмпирическое правило определения инварианта цикла. Следует обобщить (ослабить) начальное и конечное состояния (предусловие и постусловие) для того, чтобы найти подходящий инвариант цикла.
Почти любому циклу предшествует его «инициализация» выполнение сегмента программы, единственным назначением которого является установка исходной истинности инварианта цикла.
Весьма часто желательно доказать корректность цикла совместно с его инициализацией. Для этого мы располагаем правилом вывода W2.