Свойства основных конструкций структурного программирования

Свойства простых операторов.

Для пустого оператора справедлива теорема

Теорема 9.1. Пусть P - предикат над информационной средой. Тогда имеет место свойство {P}{P}.

Доказательство этой теоремы очевидно: пустой оператор не изменяет состояние информационной среды (в соответствии со своей семантикой), поэтому его предусловие сохраняет истинность и после его выполнения.

Для оператора присваивания справедлива теорема

Теорема 9.2. Пусть информационная среда IS состоит из переменной X и остальной части информационной среды RIS:

IS = (X, RIS).

Тогда имеет место свойство

{Q(F(X, RIS), RIS)} X:= F(X, RIS) {Q(X, RIS)},

где F(X, RIS) - некоторая однозначная функция, Q - предикат.

Доказательство. Пусть (X0, RIS0) - некоторое произвольное состояние информационной среды IS, и пусть перед выполнением оператора присваивания предикат Q(F(X0, RIS0), RIS0) является истинным. Тогда после выполнения оператора присваивания будет истинен предикат Q(X, RIS), так как X получит значение F(X0, RIS0), а состояние RIS не изменяется данным оператором присваивания, и, следовательно, после выполнения этого оператора присваивания в этом случае

Q(X, RIS)=Q(F(X0, RIS0), RIS0).

В силу произвольности выбора состояния информационной среды теорема доказана.

Примером свойства оператора присваивания может служить пример 9.1.

Рассмотрим теперь свойства основных конструкций структурного программирования: следования, разветвления и повторения.

Свойство следования выражает следующая

Теорема 9.3. Пусть P, Q и R - предикаты над нформационной средой, а S1 и S2 - обобщенные операторы, обладающие соответственно свойствами

{P}S{Q}

и

{Q}S2{R}.

Тогда для составного оператора

S1; S2

имеет место свойство {P} S1; S2 {R}.

Доказательство. Пусть для некоторого состояния информационной среды перед выполнением оператора S1 истинен предикат P. Тогда в силу свойства оператора S1 после его выполнения будет истинен предикат Q. Так как по семантике составного оператора после выполнения оператора S1 будет выполняться оператор S2, то предикат Q будет истинен и перед выполнением оператора S2. Следовательно, после выполнения оператора S2 в силу его свойства будет истинен предикат R, а так как оператор S2 завершает выполнение составного оператора (в соответствии с его семантикой), то предикат R будет истинен и после выполнения данного составного оператора, что и требовалось доказать.

Например, если имеют место свойства (9.2) и (9.3), то имеет место и свойство

{n<m} n:= n + k; n:= 3*n {n<3*(m + k)}.

Свойство разветвления выражает следующая

Теорема 9.4. Пусть P, Q и R - предикаты над информационной средой, а S1 и S2 - обобщенные операторы, обладающие соответственно свойствами

{P,Q} S1{R} и {ØP,Q} S2 {R}.

Тогда для условного оператора

ЕСЛИ P ТО S1ИНАЧЕ S2 ВСЕ ЕСЛИ

имеет место свойство

{Q} ЕСЛИ P ТО S1ИНАЧЕ S2 ВСЕ ЕСЛИ {R}.

Доказательство. Пусть для некоторого состояния информационной среды перед выполнением условного оператора истинен предикат Q. Если при этом будет истинен также и предикат P, то выполнение условного оператора в соответствии с его семантикой сводится к выполнению оператора S1. В силу же свойства оператора S1 после его выполнения (а в этом случае - и после выполнения условного оператора) будет истинен предикат R. Если же перед выполнением условного оператора предикат P будет ложен (а Q, по-прежнему, истинен), то выполнение условного оператора в соответствии с его семантикой сводится к выполнению оператора S2. В силу же свойства оператора S2 после его выполнения (а в этом случае - и после выполнения условного оператора) будет истинен предикат R. Тем самым теорема полностью доказана.

Прежде чем переходить к свойству конструкции повторения следует отметить полезную для дальнейшего

Теорему 9.5. Пусть P, Q, P1 и Q1 - предикаты над информационной средой, для которых справедливы импликации

P1Þ P и QÞ Q1,

и пусть для оператора S имеет место свойство {P}S{Q}.Тогда имеет место свойство {P1}S{Q1}.

Эту теорему называют еще теоремой об ослаблении свойств.

Доказательство. Пусть для некоторого состояния информационной среды перед выполнением оператора S истинен предикат P1. Тогда будет истинен и предикат P (в силу импликации P1Þ P). Следовательно, в силу свойства оператора S после его выполнения будет истинен предикат Q, а значит и предикат Q1 (в силу импликации QÞ Q1). Тем самым теорема доказана.

Свойство повторения выражает следующая

Теорема 9.6. Пусть I, P, Q и R - предикаты над информационной средой, для которых справедливы импликации

PÞ I и (I,ØQ) Þ R,

и пусть S - обобщенный оператор, обладающий свойством {I}S{I}.

Тогда для оператора цикла

ПОКА Q ДЕЛАТЬ S ВСЕ ПОКА

имеет место свойство

{P} ПОКА Q ДЕЛАТЬ S ВСЕ ПОКА {R}.

Предикат I называют инвариантом оператора цикла.

Доказательство. Для доказательства этой теоремы достаточно доказать свойство

{I} ПОКА Q ДЕЛАТЬ S ВСЕ ПОКА {I,ØQ}

(по теореме 9.5 на основании имеющихся в условиях данной теоремы импликаций). Пусть для некоторого состояния информационной среды перед выполнением оператора цикла истинен предикат I. Если при этом предикат Q будет ложен, то оператор цикла будет эквивалентен пустому оператору (в соответствии с его семантикой) и в силу теоремы 9.1 после выполнения оператора цикла будет справедливо утверждение (I,ØQ). Если же перед выполнением оператора цикла предикат Q будет истинен, то оператор цикла в соответствии со своей семантикой может быть представлен в виде составного оператора

S; ПОКА Q ДЕЛАТЬ S ВСЕ ПОКА

В силу свойства оператора S после его выполнения будет истинен предикат I, и возникает исходная ситуация для доказательства свойства оператора цикла: предикат I истинен перед выполнением оператора цикла, но уже для другого (измененного) состояния информационной среды (для которого предикат Q может быть либо истинен либо ложен). Если выполнение оператора цикла завершается, то, применяя метод математической индукции, мы за конечное число шагов придем к ситуации, когда перед его выполнением будет справедливо утверждение (I,ØQ). А в этом случае, как было доказано выше, это утверждение будет справедливо и после выполнения оператора цикла. Теорема доказана.

Например, для оператора цикла из примера (9.4) имеет место свойство

{n>0, p=1, m=1} ПОКА m <> n ДЕЛАТЬ

m:=m+1; p:= p*m

ВСЕ ПОКА {p= n!}.

Это следует из теоремы 9.6, так как инвариантом этого оператора цикла является предикат p= m! и справедливы импликации

(n>0, p=1, m=1) Þ p= m! и (p= m!, m= n) Þ p= n!

Дата добавления: 2014-01-11