Логика Хоара

редактировать

Логика Хоара (также известная как логика Флойда – Хора или правила Хора ) - это формальная система с набором логических правил для строгого рассуждения о правильности компьютерных программ. Он был предложен в 1969 году британским ученым-компьютерщиком и логиком Тони Хоаром и впоследствии усовершенствован Хоаром и другими исследователями. Оригинальные идеи были заложены в работе Роберта В. Флойда, который опубликовал аналогичную систему для блок-схем.

Содержание

  • 1 тройка Хоара
  • 2 Частичная и полная правильность
  • 3 правила
    • 3.1 Схема аксиомы пустого оператора
    • 3.2 Схема аксиомы присваивания
    • 3.3 Правило композиции
    • 3.4 Условное правило
    • 3.5 Правило следствия
    • 3.6 Правило Пока
    • 3.7 Правило Пока для полной правильности
  • 4 См. также
  • 5 Примечания
  • 6 Ссылки
  • 7 Дополнительная литература
  • 8 Внешние ссылки

тройка Хора

Центральная особенность Хоара логика - это тройка Хоара . Тройка описывает, как выполнение фрагмента кода меняет состояние вычисления. Тройка Хоара имеет вид

{P} C {Q} {\ displaystyle \ {P \} C \ {Q \}}{\ displaystyle \ {P \} C \ {Q \} }

где P {\ displaystyle P}P и Q {\ displaystyle Q}Q - это утверждения, а C {\ displaystyle C}C - это команда. P { \ displaystyle P}P называется предусловием, а Q {\ displaystyle Q}Q постусловием : когда выполняется предварительное условие, выполнение команды устанавливает постусловие. Утверждения - это формулы в логике предикатов.

Логика Хоара предоставляет аксиомы и правила вывода для всех конструкций простого императивного языка программирования. В дополнение к правилам для простого языка в оригинальной статье Хора, с тех пор Хоаром и многими другими исследователями были разработаны правила для других языковых конструкций. Существуют правила для параллелизма, процедур, переходов и указателей.

частичной и полной корректности

с использованием стандартной логики Хоара., может быть доказана только частичная правильность, а завершение нужно доказывать отдельно. Таким образом, интуитивное прочтение тройки Хоара выглядит так: всякий раз, когда P {\ displaystyle P}P сохраняет состояние до выполнения C {\ displaystyle C}C , тогда Q {\ displaystyle Q}Q будет удерживаться впоследствии, или C {\ displaystyle C}C не завершится. В последнем случае «после» нет, поэтому Q {\ displaystyle Q}Q может быть любым оператором. Действительно, можно выбрать Q {\ displaystyle Q}Q как ложное, чтобы выразить, что C {\ displaystyle C}C не завершается.

Полная корректность также может быть доказана с помощью расширенной версии правила While.

В своей статье 1969 года Хоар использовал более узкое понятие завершения, которое также влекло за собой отсутствие каких-либо ошибок времени выполнения: «Отказ завершить может быть из-за бесконечного цикла; или это может быть из-за нарушения ограничения, определенного реализацией, например диапазона числовых операндов, размера хранилища или ограничения времени операционной системы.»

Правила

Схема аксиомы пустого оператора

Правило пустого оператора утверждает, что skip {\ displaystyle {\ textbf {skip}}}{\ displaystyle {\ textbf {skip}}} не изменяет состояние программы, поэтому все, что выполняется до skip {\ displaystyle {\ textbf {skip}}}{\ displaystyle {\ textbf {skip}}} , остается верным и после этого.

{ P} skip {P} {\ displaystyle {\ dfrac {} {\ {P \} {\ textbf {skip}} \ {P \}}}}{\ displaystyle {\ dfrac {} {\ {P \} {\ textbf {skip}} \ {P \}}}}

Схема аксиомы присваивания

Аксиома присваивания утверждает, что после присваивания любой предикат, который ранее был истинным для правого si de присвоения теперь сохраняется для переменной. Формально пусть P {\ displaystyle P}P будет утверждением, в котором переменная x {\ displaystyle x}x свободна. Затем:

{P [E / x]} x: = E {P} {\ displaystyle {\ dfrac {} {\ {P [E / x] \} x: = E \ {P \}}} }{\ displaystyle {\ dfrac {} { \ {P [E / x] \} x: = E \ {P \}}}}

где P [E / x] {\ displaystyle P [E / x]}{\ displaystyle P [E / x]} обозначает утверждение P {\ displaystyle P}P , в котором каждое свободное вхождение из x {\ displaystyle x}x было заменено выражением E {\ displaystyle E}E .

Схема аксиомы присваивания означает, что истинность P [E / x] {\ displaystyle P [E / x]}{\ displaystyle P [E / x]} эквивалентна истине после присваивания P {\ displaystyle P }P . Таким образом, было P [E / x] {\ displaystyle P [E / x]}{\ displaystyle P [E / x]} истинным до присвоения по аксиоме присваивания, тогда P {\ displaystyle P}P будет истинным, после чего. И наоборот, были P [E / x] {\ displaystyle P [E / x]}{\ displaystyle P [E / x]} false (т.е. ¬ P [E / x] {\ displaystyle \ neg P [E / x]}{\ displaystyle \ neg P [E / x]} true) до оператора присваивания, P {\ displaystyle P}P после этого должно быть false.

Примеры допустимых троек:

  • {x + 1 = 43} y: = x + 1 {y = 43} {\ displaystyle \ {x + 1 = 43 \} y: = x + 1 \ {y = 43 \}}{\ displaystyle \ {x + 1 = 43 \} y: = x + 1 \ {y = 43 \}}
  • {x + 1 ≤ N} x: = x + 1 {x ≤ N} {\ displaystyle \ {x + 1 \ leq N \} x: = x + 1 \ {x \ leq N \}}{\ displaystyle \ {x + 1 \ leq N \} x: = x + 1 \ {x \ leq N \}}

Все предусловия, которые не изменяются выражением, могут быть перенесены в постусловие. В первом примере присвоение y: = x + 1 {\ displaystyle y: = x + 1}{\ displaystyle y: = x + 1 } не меняет того факта, что x + 1 = 43 {\ displaystyle x + 1 = 43}{\ displaystyle x + 1 = 43} , поэтому оба оператора могут появиться в постусловии. Формально этот результат получается путем применения схемы аксиомы с P {\ displaystyle P}P равным (y = 43 {\ displaystyle y = 43}{\ displaystyle y = 43} и x + 1 = 43 {\ displaystyle x + 1 = 43}{\ displaystyle x + 1 = 43} ), что дает P [(x + 1) / y] {\ displaystyle P [(x + 1) / y]}{\ displaystyle P [(x + 1) / y]} быть (x + 1 = 43 {\ displaystyle x + 1 = 43}{\ displaystyle x + 1 = 43} и x + 1 = 43 {\ displaystyle x + 1 = 43}{\ displaystyle x + 1 = 43} ), которое, в свою очередь, может быть упрощено до данного предусловия x + 1 = 43 {\ displaystyle x + 1 = 43}{\ displaystyle x + 1 = 43} .

Схема аксиомы присваивания эквивалентна утверждению, что для найдите предусловие, сначала возьмите постусловие и замените все вхождения левой части присваивания правой частью присваивания. Будьте осторожны и не пытайтесь сделать это в обратном порядке, следуя неправильному образу мышления: {P} x: = E {P [E / x]} {\ displaystyle \ {P \} x: = E \ {P [E / x] \}}{\ displaystyle \ {P \} x: = E \ {P [E / x] \}} ; это правило приводит к бессмысленным примерам, например:

{x = 5} x: = 3 {3 = 5} {\ displaystyle \ {x = 5 \} x: = 3 \ {3 = 5 \}}{\ displaystyle \ { х = 5 \} х: = 3 \ {3 = 5 \}}

Еще одно неправильное правило, которое на первый взгляд кажется заманчивым, - это {P} x: = E {P ∧ x = E} {\ displaystyle \ {P \} x: = E \ {P \ wedge x = E \}}{\ displaystyle \ {P \} x: = E \ {P \ клин x = E \}} ; это приводит к бессмысленным примерам вроде:

{x = 5} x: = x + 1 {x = 5 ∧ x = x + 1} {\ displaystyle \ {x = 5 \} x: = x + 1 \ { x = 5 \ wedge x = x + 1 \}}{\ displaystyle \ {x = 5 \} x: = x + 1 \ {х = 5 \ клин х = х + 1 \}}

Хотя данное постусловие P {\ displaystyle P}P однозначно определяет предусловие P [E / x] {\ displaystyle P [E / x]}{\ displaystyle P [E / x]} , обратное неверно. Например:

  • {0 ≤ y ⋅ y ∧ y ⋅ y ≤ 9} x: = y ⋅ y {0 ≤ x ∧ x ≤ 9} {\ displaystyle \ {0 \ leq y \ cdot y \ wedge y \ cdot y \ leq 9 \} x: = y \ cdot y \ {0 \ leq x \ wedge x \ leq 9 \}}{\ displaystyle \ {0 \ leq y \ cdot y \ wedge y \ cdot y \ leq 9 \} x: = y \ cdot y \ {0 \ leq x \ клин x \ leq 9 \}} ,
  • {0 ≤ y ⋅ y ∧ y ⋅ y ≤ 9} x: = y ⋅ Y {0 ≤ Икс ∧ Y ⋅ Y ≤ 9} {\ Displaystyle \ {0 \ Leq Y \ CDOT Y \ Wedge Y \ CDOT Y \ Leq 9 \} X: = Y \ CDOT Y \ {0 \ Leq X \ Wedge y \ cdot y \ leq 9 \}}{\ Displaystyle \ {0 \ Leq Y \ CDOT Y \ клин у \ CDOT Y \ Leq 9 \} x: = Y \ CDOT Y \ {0 \ Leq x \ клин у \ CDOT Y \ Leq 9 \}} ,
  • {0 ≤ y ⋅ y ∧ y ⋅ y ≤ 9} x: = y ⋅ y {0 ≤ y ⋅ y ∧ x ≤ 9} {\ displaystyle \ {0 \ leq y \ cdot y \ wedge y \ cdot y \ leq 9 \} x: = y \ cdot y \ {0 \ leq y \ cdot y \ wedge x \ leq 9 \}}{\ Displaystyle \ {0 \ Leq Y \ CDOT Y \ клин у \ CDOT Y \ Leq 9 \} х: = Y \ CDOT Y \ {0 \ Leq Y \ CDOT Y \ клин х \ Leq 9 \}} и
  • {0 ≤ y ⋅ y ∧ y ⋅ y ≤ 9} x: = y ⋅ y {0 ≤ y ⋅ y ∧ y ⋅ y ≤ 9} {\ displaystyle \ {0 \ leq y \ cdot y \ wedge y \ cdot y \ leq 9 \} x: = y \ cdot y \ {0 \ leq y \ cdot y \ wedge y \ cdot y \ leq 9 \}}{\ displaystyle \ {0 \ leq y \ cdot y \ wedge y \ cdot y \ leq 9 \ } x: = y \ cdot y \ {0 \ leq y \ cdot y \ wedge y \ cdot y \ leq 9 \}}

являются допустимыми экземплярами схемы аксиомы присваивания.

Аксиома присваивания, предложенная Хоаром, неприменима, когда более одного имени могут ссылаться на одно и то же сохраненное значение. Например,

{y = 3} x: = 2 {y = 3} {\ displaystyle \ {y = 3 \} x: = 2 \ {y = 3 \}}{\ displaystyle \ {y = 3 \} x: = 2 \ {y = 3 \}}

неверно, если x {\ displaystyle x}x и y {\ displaystyle y}y относятся к одной и той же переменной (aliasing ), хотя это правильный экземпляр схемы аксиомы присваивания (с обоими {P} {\ displaystyle \ {P \}}{\ displaystyle \ {P \}} и {P [2 / x]} {\ displaystyle \ {P [2 / x] \}}{\ displaystyle \ {P [2 / x] \}} является {y = 3} {\ displaystyle \ {y = 3 \}}{\ displaystyle \ {y = 3 \}} ).

Правило композиции

Проверка своп-кода. без вспомогательных переменных
Три утверждения ниже (строки 2, 4, 6) обмениваются значениями переменных a {\ displaystyle a}a и b {\ displaystyle b}b , без необходимости во вспомогательной переменной. В проверочном доказательстве начальное значение a {\ displaystyle a}a и b {\ displaystyle b}b обозначается константой A { \ displaystyle A}A и B {\ displaystyle B}B соответственно. Доказательство лучше читать задом наперед, начиная со строки 7; например, строка 5 получается из строки 7 заменой a {\ displaystyle a}a (целевое выражение в строке 6) на a - b {\ displaystyle ab}ab (исходное выражение в строке 6). Некоторые арифметические упрощения используются неявно, а именно. a - (a - b) = b {\ displaystyle a- (ab) = b}{\ displaystyle a- (ab) = b} (строка 5 → 3) и a + b - b = a {\ displaystyle a + bb = a}{\ displaystyle a + bb = a} (строка 3 → 1).
NrКодУтверждения
1:{a = A ∧ b = B} {\ displaystyle \ {a = A \ wedge b = B \}}{ \ displaystyle \ {a = A \ wedge b = B \}}
2:a: = a + b; {\ displaystyle a: = a + b;}{\ displaystyle a : = a + b;}
3:{a - b = A ∧ b = B} {\ displaystyle \ {ab = A \ wedge b = B \}}{ \ Displaystyle \ {ab = A \ клин b = B \}}
4:b: = a - b ; {\ displaystyle b: = ab;}{\ displaystyle b: = ab;}
5:{b = A ∧ a - b = B} {\ displaystyle \ {b = A \ wedge ab = B \}}{\ displaystyle \ {b = A \ wedge ab = B \}}
6:a: = a - b {\ displaystyle a: = ab}{\ displaystyle a: = ab}
7:{b = A ∧ a = B} {\ displaystyle \ {b = A \ wedge a = B \}}{\ displaystyle \ {b = A \ клин а = В \}}

Правило композиции Хоара применяется к последовательно выполняемым программам S {\ displaystyle S}S и T {\ displaystyle T}T , где S {\ displaystyle S}S выполняется до T {\ displaystyle T}T и пишется S; T {\ displaystyle S; T}{\ displaystyle S; T} (Q {\ displaystyle Q}Q называется средним условием):

{P} S {Q}, {Q} T {R} {P} S; T {R} {\ Displaystyle {\ dfrac {\ {P \} S \ {Q \} \ quad, \ quad \ {Q \} T \ {R \}} {\ {P \} S; T \ { R \}}}}{\ displaystyle {\ dfrac {\ {P \} S \ {Q \} \ quad, \ quad \ {Q \} T \ {R \}} {\ {P \} S; T \ {R \}}}}

Например, рассмотрим следующие два случая аксиомы присваивания:

{x + 1 = 43} y: = x + 1 {y = 43} {\ displaystyle \ {x + 1 = 43 \} y: = x + 1 \ {y = 43 \}}{\ displaystyle \ {x + 1 = 43 \} y: = x + 1 \ {y = 43 \}}

и

{y = 43} z: = y {z = 43} {\ displaystyle \ {y = 43 \} z: = y \ {z = 43 \}}{\ displaystyle \ {y = 43 \} z : = Y \ {z = 43 \}}

По правилу упорядочивания можно сделать вывод:

{x + 1 = 43} y: = x + 1; z: = y {z = 43} {\ displaystyle \ {x + 1 = 43 \} y: = x + 1; z: = y \ {z = 43 \}}{\ displaystyle \ {x + 1 = 43 \} y: = x + 1; z: = y \ {z = 43 \}}

Другой пример показан справа коробка.

Условное правило

{B ∧ P} S {Q}, {¬ B ∧ P} T {Q} {P}, если B, то S else T endif {Q} {\ displaystyle {\ dfrac {\ {B \ wedge P \} S \ {Q \} \ quad, \ quad \ {\ neg B \ wedge P \} T \ {Q \}} {\ {P \} {\ textbf {if}} \ B \ {\ textbf {then}} \ S \ {\ textbf {else}} \ T \ {\ textbf {endif}} \ {Q \}}}}{\ displaystyle {\ dfrac {\ {B \ wedge P \} S \ {Q \} \ quad, \ quad \ {\ neg B \ wedge P \} T \ {Q \}} {\ {P \} {\ textbf {if}} \ B \ {\ textbf {then}} \ S \ {\ textbf {else}} \ T \ {\ textbf {endif}} \ {Q \}}}}

Условное правило гласит, что постусловие Q {\ displaystyle Q}Q общий для , затем {\ displaystyle {\ textbf {then}}}{\ displaystyle {\ textbf {then}}} и else {\ displaystyle {\ textbf {else} }}{\ displaystyle {\ textbf {else}}} часть также является постусловием всего оператора if ⋯ endif {\ displaystyle {\ textbf {if}} \ cdots {\ textbf {endif}}}{\ displaystyle {\ textbf {if}} \ cdots {\ textbf {endif}}} . В части , затем {\ displaystyle {\ textbf {then}}}{\ displaystyle {\ textbf {then}}} и else {\ displaystyle {\ textbf {else}}}{\ displaystyle {\ textbf {else}}} незащищенные и отрицательное условие B {\ displaystyle B}B может быть добавлено к предусловию P {\ displaystyle P}P соответственно. Условие B {\ displaystyle B}B не должно иметь побочных эффектов. Пример приведен в следующем разделе.

Это правило не содержалось в исходной публикации Хоара. Однако, поскольку оператор

if B then S else T endif {\ displaystyle {\ textbf {if}} \ B \ {\ textbf {then}} \ S \ {\ textbf {else}} \ T \ {\ textbf {endif}}}{\ displaystyle {\ textbf {if}} \ B \ {\ textbf {then}} \ S \ {\ textbf {else}} \ T \ {\ textbf {endif}}}

имеет тот же эффект, что и конструкция одноразового цикла

bool b: = true; пока B ∧ b do S; b: = false сделано; b: = верно; пока ¬ B ∧ b do T; б: = ложь сделано {\ displaystyle {\ textbf {bool}} \ b: = {\ textbf {true}}; {\ textbf {while}} \ B \ wedge b \ {\ textbf {do}} \ S; b: = {\ textbf {false}} \ {\ textbf {done}}; b: = {\ textbf {true}}; {\ textbf {while}} \ \ neg B \ wedge b \ {\ textbf {do }} \ T; b: = {\ textbf {false}} \ {\ textbf {done}}}{\ displaystyle {\ textbf {bool}} \ b: = {\ textbf {true}}; {\ textbf {while}} \ B \ wedge b \ {\ textbf {do}} \ S ; b: = {\ textbf {false}} \ {\ textbf {done}}; b: = {\ textbf {true}}; {\ textbf {while}} \ \ neg B \ wedge b \ {\ textbf { do}} \ T; b: = {\ textbf {false}} \ {\ textbf {done}}}

условное правило может быть получено из других правил Хоара. Аналогичным образом правила для других производных программных конструкций, таких как for {\ displaystyle {\ textbf {for}}}{\ displaystyle {\ textbf {for}}} loop, do ⋯ до {\ displaystyle {\ textbf {do }} \ cdots {\ textbf {until}}}{\ displaystyle {\ textbf {do}} \ cdots {\ textbf {до}}} цикл, switch {\ displaystyle {\ textbf {switch}}}{\ displaystyle {\ textbf {switch}}} , break {\ displaystyle {\ textbf {break}}}{\ displaystyle {\ textbf {break}}} , continue {\ displaystyle {\ textbf {continue}}}{\ displaystyle {\ textbf {continue}}} может быть сокращено с помощью программного преобразования к правилам из оригинальной статьи Хоара.

Правило следствия

P 1 → P 2, {P 2} S {Q 2}, Q 2 → Q 1 {P 1} S {Q 1} {\ displaystyle {\ dfrac {P_ { 1} \ rightarrow P_ {2} \ quad, \ quad \ {P_ {2} \} S \ {Q_ {2} \} \ quad, \ quad Q_ {2} \ rightarrow Q_ {1}} {\ {P_ {1} \} S \ {Q_ {1} \}}}}{\ displaystyle {\ dfrac {P_ {1} \ rightarrow P_ {2} \ quad, \ quad \ {P_ {2} \} S \ {Q_ {2} \} \ quad, \ quad Q_ { 2} \ rightarrow Q_ {1}} {\ {P_ {1} \} S \ {Q_ {1} \}}}}

Это правило позволяет усилить предусловие P 2 {\ displaystyle P_ {2}}P_ {2} и / или ослабить постусловие Q 2 {\ displaystyle Q_ {2}}Q_ {2} . Он используется, например, для достижения буквально идентичных постусловий для then {\ displaystyle {\ textbf {then}}}{\ displaystyle {\ textbf {then}}} и else {\ displaystyle {\ textbf {else}}}{\ displaystyle {\ textbf {else}}} часть.

Например, доказательство

{0 ≤ x ≤ 15}, если x < 15 then x := x + 1 else x := 0 endif { 0 ≤ x ≤ 15 } {\displaystyle \{0\leq x\leq 15\}{\textbf {if}}\ x<15\ {\textbf {then}}\ x:=x+1\ {\textbf {else}}\ x:=0\ {\textbf {endif}}\{0\leq x\leq 15\}}{\ displaystyle \ {0 \ leq x \ leq 15 \} {\ textbf {if}} \ x <15 \ {\ textbf {then}} \ x: = x + 1 \ {\ textbf {else}} \ x: = 0 \ {\ textbf {endif}} \ {0 \ leq x \ leq 15 \}}

требует применения условного правила, которое, в свою очередь, требует доказательства

{0 ≤ x ≤ 15 ∧ x < 15 } x := x + 1 { 0 ≤ x ≤ 15 } {\displaystyle \{0\leq x\leq 15\wedge x<15\}x:=x+1\{0\leq x\leq 15\}}{\ displaystyle \ {0 \ leq x \ leq 15 \ wedge x <15 \} x: = x + 1 \ {0 \ leq x \ leq 15 \}} или упрощенный
{0 ≤ x < 15 } x := x + 1 { 0 ≤ x ≤ 15 } {\displaystyle \{0\leq x<15\}x:=x+1\{0\leq x\leq 15\}}{\ displaystyle \ {0 \ leq x <15 \} x: знак равно Икс + 1 \ {0 \ Leq Икс \ Leq 15 \}}

для части , затем {\ displaystyle {\ textbf {then}}}{\ displaystyle {\ textbf {then}}} и

{ 0 ≤ Икс ≤ 15 ∧ Икс ≥ 15} Икс: знак равно 0 {0 ≤ Икс ≤ 15} {\ Displaystyle \ {0 \ Leq х \ Leq 15 \ клин х \ GEQ 15 \} х: = 0 \ {0 \ Leq x \ leq 15 \}}{\ displaystyle \ {0 \ leq x \ leq 15 \ wedge x \ geq 15 \} x: = 0 \ {0 \ leq x \ leq 15 \}} , или упрощенно
{x = 15} x: = 0 {0 ≤ x ≤ 15} {\ displaystyle \ {x = 15 \} x: = 0 \ {0 \ leq x \ leq 15 \}}{\ displaystyle \ {x = 15 \} x: = 0 \ {0 \ leq x \ leq 15 \}}

для части else {\ displaystyle {\ textbf {else}}}{\ displaystyle {\ textbf {else}}} .

Однако правило назначения для части then {\ displaystyle {\ textbf {then}}}{\ displaystyle {\ textbf {then}}} требует выбора P {\ displaystyle P}P как 0 ≤ x ≤ 15 {\ displaystyle 0 \ leq x \ leq 15}{\ displaystyle 0 \ leq x \ leq 15} ; применение правила, следовательно, дает

{0 ≤ x + 1 ≤ 15} x: = x + 1 {0 ≤ x ≤ 15} {\ displaystyle \ {0 \ leq x + 1 \ leq 15 \} x: = x + 1 \ {0 \ leq x \ leq 15 \}}{\ Displaystyle \ {0 \ Leq х + 1 \ Leq 15 \} х: = х + 1 \ {0 \ Leq х \ leq 15 \}} , что логически эквивалентно
{- 1 ≤ x < 15 } x := x + 1 { 0 ≤ x ≤ 15 } {\displaystyle \{-1\leq x<15\}x:=x+1\{0\leq x\leq 15\}}{\ displaystyle \ {- 1 \ leq x <15 \} x: = x + 1 \ {0 \ leq x \ leq 15 \}} .

Правило следствия необходимо для усиления предусловия {- 1 ≤ x < 15 } {\displaystyle \{-1\leq x<15\}}{\ displaystyle \ {- 1 \ leq x <15 \}} , полученное из правила присвоения, в {0 ≤ x < 15 } {\displaystyle \{0\leq x<15\}}{\ displaystyle \ {0 \ leq x <15 \}} , необходимое для условного правила.

Аналогично, для части else {\ displaystyle {\ textbf {else}}}{\ displaystyle {\ textbf {else}}} правило присваивания дает

{0 ≤ 0 ≤ 15} x: = 0 {0 ≤ x ≤ 15} {\ displaystyle \ {0 \ leq 0 \ leq 15 \} x: = 0 \ {0 \ leq x \ leq 15 \}}{\ displaystyle \ {0 \ leq 0 \ leq 15 \} x: = 0 \ {0 \ leq x \ leq 15 \}} или эквивалентно
{true} x: = 0 {0 ≤ x ≤ 15} {\ displaystyle \ {{\ textbf {true}} \} x: = 0 \ {0 \ leq x \ leq 15 \}}{\ displaystyle \ {{\ textbf {true}} \} x: = 0 \ {0 \ leq x \ leq 15 \}} ,

отсюда следствие правило должно применяться с P 1 {\ displaystyle P_ {1}}P_ {1} и P 2 {\ displaystyle P_ {2}}P_ {2} равным { х = 15} {\ displaystyle \ {x = 15 \}}{\ displaystyle \ {x = 15 \}} и {true} {\ displaystyle \ {{\ textbf {true}} \}}{\ displaystyle \ {{\ textbf {true}} \}} , соответственно, чтобы снова усилить предусловие. Неформально, эффект правила последствий состоит в том, чтобы «забыть», что {x = 15} {\ displaystyle \ {x = 15 \}}{\ displaystyle \ {x = 15 \}} известен на входе else {\ displaystyle {\ textbf {else}}}{\ displaystyle {\ textbf {else}}} часть, поскольку правило присваивания, используемое для части else {\ displaystyle {\ textbf {else}}}{\ displaystyle {\ textbf {else}}} , не выполняет ' Мне нужна эта информация.

В то время как правило

{P ∧ B} S {P} {P}, пока B выполняет S, выполнено {¬ B ∧ P} {\ displaystyle {\ dfrac {\ {P \ wedge B \} S \ {P \}} {\ {P \} {\ textbf {while}} \ B \ {\ textbf {do}} \ S \ {\ textbf {done}} \ {\ neg B \ wedge P \}} }}{\ displaystyle {\ dfrac {\ {P \ wedge B \} S \ {P \}} {\ {P \} {\ textbf {while}} \ B \ {\ textbf {do}} \ S \ {\ textbf {done}} \ {\ neg B \ wedge P \}}}}

Здесь P {\ displaystyle P}P - это инвариант цикла, который должен сохраняться в теле цикла S {\ displaystyle S}S . После завершения цикла этот инвариант P {\ displaystyle P}P все еще сохраняется, и, более того, ¬ B {\ displaystyle \ neg B}\ neg B должно быть вызвало петля до конца. Как и в условном правиле, B {\ displaystyle B}B не должен иметь побочных эффектов.

Например, доказательство

{x ≤ 10} в то время как x < 10 do x := x + 1 done { ¬ x < 10 ∧ x ≤ 10 } {\displaystyle \{x\leq 10\}{\textbf {while}}\ x<10\ {\textbf {do}}\ x:=x+1\ {\textbf {done}}\{\neg x<10\wedge x\leq 10\}}{\ displaystyle \ {x \ leq 10 \} {\ textbf {while}} \ x <10 \ {\ textbf {do}} \ x: = x + 1 \ {\ textbf {done}} \ {\ neg x <10 \ клин x \ leq 10 \}}

правилом while требует доказательства

{x ≤ 10 ∧ x < 10 } x := x + 1 { x ≤ 10 } {\displaystyle \{x\leq 10\wedge x<10\}x:=x+1\{x\leq 10\}}{\ displaystyle \ {x \ leq 10 \ wedge x <10 \} x: = x + 1 \ {x \ leq 10 \ }} , или упрощенно
{x < 10 } x := x + 1 { x ≤ 10 } {\displaystyle \{x<10\}x:=x+1\{x\leq 10\}}{\ displaystyle \ {x <10 \} x: = x + 1 \ {x \ leq 10 \}} ,

, который легко получить с помощью правила присваивания. Наконец, постусловие {¬ x < 10 ∧ x ≤ 10 } {\displaystyle \{\neg x<10\wedge x\leq 10\}}{\ displaystyle \ { \ neg x <10 \ клин x \ leq 10 \}} можно упростить до {x = 10} {\ displaystyle \ {x = 10 \}}{\ displaystyle \ {x = 10 \}} .

В другом примере правило while может использоваться для формальной проверки следующей странной программы для вычисления точного квадратного корня x {\ displaystyle x}x из произвольного числа a {\ displaystyle a}a - даже если x {\ displaystyle x}x - целочисленная переменная, а a {\ displaystyle a}a - не квадратное число:

{true} в то время как Икс ⋅ Икс ≠ а пропустить готово {x ⋅ x = a ∧ true} {\ displaystyle \ {{\ textbf {true}} \} {\ textbf {while}} \ x \ cdot x \ neq a \ {\ textbf {do}} \ {\ textbf {skip}} \ {\ textbf {done}} \ {x \ cdot x = a \ wedge {\ textbf {true}} \}}{\ displaystyle \ {{\ textbf {true}} \} {\ textbf {while}} \ x \ cdot x \ neq a \ {\ textbf {do}} \ {\ textbf {skip}} \ {\ textbf {done}} \ {x \ cdot x = a \ wedge {\ textbf {true}} \}}

После применения правила while с P {\ displaystyle P}P будучи истинным {\ displaystyle {\ textbf {true}}}{\ displaystyle {\ textbf {true}}} , остается доказать

{true ∧ x ⋅ x ≠ a} пропустить {true} {\ displaystyle \ {{\ textbf {true}} \ wedge x \ cdot x \ neq a \} {\ textbf {skip}} \ {{\ textbf {true}} \}}{ \ displaystyle \ {{\ textbf {true}} \ wedge x \ cdot x \ neq a \} {\ textbf {skip}} \ {{\ textbf {true}} \}} ,

который следует из правила пропуска и правила следствия.

На самом деле странная программа частично верна: если она завершилась, несомненно, что x {\ displaystyle x}x должно было содержать (случайно) значение из квадратного корня a {\ displaystyle a}a . Во всех остальных случаях он не прекращается; поэтому это не совсем правильно.

В то время как правило полной правильности

Если выше обычного в то время как правило заменяется следующим, исчисление Хоара также может использоваться для доказательства полной правильности, то есть прекращение, а также частичная правильность. Обычно здесь вместо фигурных скобок используются квадратные скобки для обозначения различных представлений о правильности программы.

< is a well-founded ordering on the set D, [ P ∧ B ∧ t ∈ D ∧ t = z ] S [ P ∧ t ∈ D ∧ t < z ] [ P ∧ t ∈ D ] while B do S done [ ¬ B ∧ P ∧ t ∈ D ] {\displaystyle {\dfrac {<\ {\text{is a well-founded ordering on the set}}\ D\quad,\quad [P\wedge B\wedge t\in D\wedge t=z]S[P\wedge t\in D\wedge t{\ displaystyle {\ dfrac {<\ {\ text {- это хорошо обоснованный порядок на множестве}} \ D \ quad, \ quad [P \ wedge B \ wedge t \ in D \ wedge t = z ] S [П \ клин t \ in D \ клин t <z]} {[P \ клин t \ in D] {\ textbf {while}} \ B \ {\ textbf {do}} \ S \ {\ textbf {готово}} [\ отр B \ клин P \ клин t \ in D]}}}

В этом правиле, помимо сохранения инварианта цикла, также доказывается завершение посредством выражения t {\ displaystyle t}t , называемого вариант цикла, значение которого строго уменьшается относительно хорошо обоснованного отношения < {\displaystyle <}<в некотором наборе доменов D {\ displaystyle D}D во время каждой итерации. Поскольку < {\displaystyle <}<хорошо обоснован, строго убывающая цепочка членов D {\ displaystyle D}D может иметь только конечную длину, поэтому t {\ displaystyle t}t не может уменьшаться бесконечно. (Например, обычный порядок < {\displaystyle <}<хорошо основан на положительных целых числах N {\ displaystyle \ mathbb {N}}\ mathbb {N} , но не на целых числах Z {\ displaystyle \ mathbb {Z}}\ mathbb {Z} ни на положительных вещественных числах R + {\ displaystyle \ mathbb {R} ^ {+}}\ mathbb {R} ^ {+} ; все эти множества подразумеваются в математическом, а не в вычислительном смысле, в частности, все они бесконечны.)

Учитывая инвариант цикла P {\ displaystyle P}P , условие B {\ displaystyle B}B должно означать, что t {\ displaystyle t}t не является минимальным элементом из D {\ displaystyle D}D , иначе тело S {\ displaystyle S}S не могло бы уменьшиться t {\ displaystyle t}t дальше, т.е. посылка правила была бы ложной. (Это одно из различных обозначений для полной правильности.)

Возобновление первого примера из предыдущего раздела, для доказательства полной правильности

[x ≤ 10], в то время как x < 10 do x := x + 1 done [ ¬ x < 10 ∧ x ≤ 10 ] {\displaystyle [x\leq 10]{\textbf {while}}\ x<10\ {\textbf {do}}\ x:=x+1\ {\textbf {done}}[\neg x<10\wedge x\leq 10]}{\ displaystyle [x \ leq 10] {\ textbf {while}} \ x <10 \ {\ textbf {do}} \ x: = x + 1 \ {\ textbf {done}} [\ neg x <10 \ wedge x \ leq 10]}

правило while для полной корректности может применяться, например, D {\ displaystyle D}D - неотрицательные целые числа в обычном порядке, а выражение t {\ displaystyle t}t - 10 - x {\ displaystyle 10-x}{\ displaystyle 10-x} , что, в свою очередь, требует доказательства

[x ≤ 10 ∧ x < 10 ∧ 10 − x ≥ 0 ∧ 10 − x = z ] x := x + 1 [ x ≤ 10 ∧ 10 − x ≥ 0 ∧ 10 − x < z ] {\displaystyle [x\leq 10\wedge x<10\wedge 10-x\geq 0\wedge 10-x=z]x:=x+1[x\leq 10\wedge 10-x\geq 0\wedge 10-x{\ displaystyle [x \ leq 10 \ клин x <10 \ клин 10-x \ geq 0 \ клин 10-x = z ] x: знак равно x + 1 [x \ leq 10 \ клин 10-x \ geq 0 \ клин 10-x <z]}

Неформально говоря, мы должны доказать, что расстояние 10 - x {\ displaystyle 10-x}{\ displaystyle 10-x} уменьшается в каждом цикле цикла, но всегда остается неотрицательным; этот процесс может продолжаться только конечное число циклов.

Предыдущую цель доказательства можно упростить до

[x < 10 ∧ 10 − x = z ] x := x + 1 [ x ≤ 10 ∧ 10 − x < z ] {\displaystyle [x<10\wedge 10-x=z]x:=x+1[x\leq 10\wedge 10-x{\ displaystyle [x <10 \ wedge 10-x = z] x: = x + 1 [x \ leq 10 \ wedge 10 -x <z]} ,

, что можно доказать следующим образом:

[x + 1 ≤ 10 ∧ 10 - x - 1 < z ] x := x + 1 [ x ≤ 10 ∧ 10 − x < z ] {\displaystyle [x+1\leq 10\wedge 10-x-1{\ displaystyle [x + 1 \ leq 10 \ wedge 10-x-1 <z] x: = x + 1 [x \ leq 10 \ wedge 10- х <z]} получается по правилу присваивания, а
[x + 1 ≤ 10 ∧ 10 - x - 1 < z ] {\displaystyle [x+1\leq 10\wedge 10-x-1{\ displaystyle [x + 1 \ leq 10 \ wedge 10-x-1 <z]} может быть усилено до [x < 10 ∧ 10 − x = z ] {\displaystyle [x<10\wedge 10-x=z]}{\ displaystyle [x <10 \ wedge 10-x = z]} правилом следствия.

Для второго примера предыдущего раздела, конечно, не может быть найдено выражение t {\ displaystyle t}t , которое уменьшается на пустое тело цикла, следовательно, завершение не может быть доказано.

См. Также

Примечания

Ссылки

Дополнительная литература

Внешние ссылки

  • KeY-Hoare - это полуавтоматическая система проверки, построенная на основе программы доказательства теорем KeY. Он содержит исчисление Хоара для простого языка while.
  • j-Алгомодульное исчисление Хоара - Визуализация исчисления Хоара в программе визуализации алгоритма j-Algo
Последняя правка сделана 2021-05-23 03:32:54
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте