Дудаков С.М. Математическое введение в информатику

Подождите немного. Документ загружается.

3.2. Семантика 51

Alg Add;

arg x, y;

u = x; v = 0;

while v < y do

u = succ (u) ;

v = succ (v) ;



end;











Add = u;

end;

Рис. 3.2: Сложение чисел.

1. Res δ определен тогда и только тогда, когда Φ

(v) определено;

2. Если Res δ определен, то Res δ = Φ

(v).

Рассмотрим несколько примеров.

Пример 3.12. Алгоритм Max на рис. 3.1 на стр. 38 вычисляет функ-

цию f (x, y) = max {x, y}. Например,

Res (Max, 1, 3) = 3;

Res (Max, 5, 2) = 5.

Задача 3.14. Докажите, что результаты вызовов из предыдущего

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

Теперь напишем несколько алгоритмов для вычисления арифметиче-

ских функций.

Пример 3.13. Начнем со сложения (рис. 3.2). Прежде всего отме-

тим, что для любого состояния τ имеет место

(τ) (u) = τu + 1, Π

(τ) (v) = τv + 1.

Рассмотрим произвольное состояние

σ = {(x, x

) , (y, y

) , (u, u

) , (v, v

)}.

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

= {(x, x

) , (y, y

) , (u, x

) , (v, 0)}.

52 Глава 3. Структурированные программы

Начнем строить последовательность состояний





для цикла:

= σ

; σ

i+1

= Π





Очевидно, что

= {(x, x

) , (y, y

) , (u, x

+ i) , (v, i)}.

Далее, σ

|= v < y тогда и только тогда, когда i < y

. Это означает,

что последним элементом последовательности будет

= {(x, x

) , (y, y

) , (u, x

+ y

) , (v, y

)},

так как это — первый элемент последовательности, для которого не

выполняется σ

|= v < y. Из этого следует, что Π

(σ) = σ

(σ) (u) = x

+ y

= σx + σy.

По определению семантики присваивания имеем

Π (σ) (Add) = σx + σy.

Это и означает, что наш алгоритм выполняет сложение натураль-

ных чисел.

Res (Add, x

, y

) = x

+ y

Пример 3.14. Теперь вычитание (рис. 3.3 на стр. 53). Напомним, что

у нас нет отрицательных чисел, поэтому мы напишем программу для

вычисления функции bx − yc, где

bxc =

x + |x|

То есть, bxc = x, если x ≥ 0, и bxc = 0, если x ≤ 0.

Рассмотрим произвольное состояние

σ = {(x, x

) , (y, y

) , (u, u

) , (v, v

)}.

Перед началом цикла мы получим состояние

= {(x, x

) , (y, y

) , (u, y

) , (v, 0)}.

Построим последовательность состояний





для цикла:

= σ

; σ

i+1

= Π





3.2. Семантика 53

Alg S;

arg x, y;

u = y; v = 0;

while u < x do

u = succ (u) ;

v = succ (v) ;



end;

S = v;

end;

Рис. 3.3: Вычитание чисел.

Очевидно, что

= {(x, x

) , (y, y

) , (u, y

+ i) , (v, i)}.

Для теста имеем:

|= u < x ⇐⇒ y

+ i < x

Если x

≤ y

, то последним элементом последовательности будет σ

так как для него уже будет σ

6|= u < x. Если же x

≥ y

, то последним

элементом будет первое σ

, для которого σ

6|= u < x, то есть y

+ j ≥

. Очевидно, что первым из таких j будет x

− y

. Следовательно,

последний элемент последовательности:

−y

= {(x, x

) , (y, y

) , (u, y

+ x

− y

) , (v, x

− y

)}.

Получаем, что

Π (σ) (S) =

(

0, если σx ≤ σy

σx − σy, если σx ≥ σy

Это точно соответствует тому, что мы хотели.

Задача 3.15. Напишите алгоритм, проверяющий четность заданного

числа, и докажите его правильность.

Пример 3.15. Рассмотрим пример алгоритма, для вычисления НОД

методом Евклида. См. рис. 3.4 на стр. 55.

В (1) мы проверяем специальные случаи, когда один из аргументов

равен 0. В этом случае мы полагаем результат равным второму ар-

гументу. Заметим, что если оба аргумента равны 0, то результа-

том тоже будет 0, поэтому рассматривать этот случай отдельно

не нужно.

54 Глава 3. Структурированные программы

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

аргументы на неравенство. Поэтому мы включили два специальных

фрагмента (2). В результате их выполнения переменная u содержит

результат сравнения.

Строки (4) содержат обычный шаг алгоритма Евклида, когда от

большего числа отнимается меньшее. Так как вычитание в нашем язы-

ке отсутствует, то мы используем строки (3) для его выполнения.

∗

Задача 3.16. Докажите правильность алгоритма Euclid.

Задача 3.17. Напишите алгоритмы, которые выполняют:

1. умножение двух чисел;

2. нахождение целой части частного двух чисел;

3. нахождение остатка от деления двух чисел;

4. вычисление факториала числа;

5. проверку, является ли число простым,

и докажите их правильность

Естественно, что можно написать много разных алгоритмов, которые

будут вычислять одну и ту же (частичную) функцию.

Определение 3.18. (Эквивалентность алгоритмов) Алгоритмы

A и B называются эквивалентными, если они вычисляют одну и ту

же (частичную) функцию:

= Φ

Следствие 3.5. Алгоритмы A и B эквивалентны тогда и только то-

гда, когда они имеют одинаковое число аргументов n и для любых

v ∈ ω

или Res (A, v) и Res (B, v) одновременно неопределены, или од-

новременно определены и при этом

Res (A, v) = Res (B, v) .

∗

Задача 3.18. Верно ли следующее утверждение:

Если Π

(σ) = Π

(σ) для любого состояния σ, то A и B эк-

вивалентны?

3.2. Семантика 55

Alg Euclid;

arg x, y;

if x = 0 then

Euclid = y;

else

if y = 0 then

Euclid = x;











(1)

else

if x = y then

u = 0;

else

u = succ (0) ;

end;











(2)

while u = succ (0) do

if x < y then

v = 0; w = x;

while w < y do

v = succ (v) ; w = succ (w) ;

end;











(3)

y = v;

else

v = 0; w = y;

while w < x do

v = succ (v) ; w = succ (w) ;

end;











(3)

x = v;

end;











(4)

if x = y then

u = 0;

else

u = succ (0) ;

end;











(2)

end;

Euclid = x;

end;

Рис. 3.4: Алгоритм Евклида.

56 Глава 3. Структурированные программы

Верно ли обратное к нему утверждение? Докажите.

Пример 3.16. Рассмотрим следующие алгоритмы.

Alg A;

arg x, y;

A = y;

end;

Alg B;

arg a, b;

B = b;

end;

Alg C;

arg u, v;

C = u;

end;

Эти три алгоритма вычисляют двухместные функции:

(p, q) = Φ

(p, q) = q; Φ

(p, q) = p.

Таким образом, первые два эквивалентны, а третий не эквивалентен

первым двум.

3.3

∗

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

Изучим некоторые свойства структурированных программ.

Сначала продемонстрируем, что значение переменных, которые не

встречаются в левой части оператора присваивания в программе Π, не

изменяется.

Лемма 3.4. (О сохранении значения) Если Π — программа, x —

переменная x 6∈ LVar (Π), σ, τ — состояния и Π (σ) = τ, то σx = τx.

Доказательство. Индукция по построению программы Π.

Базис индукции.

Π ∼ y = e; где y — переменная, e — выражение. Очевидно, что y 6∼ x,

иначе x ∈ LVar (Π). По определению семантики для оператора присва-

ивания Π (σ) = τ и при этом τy = σ (e) и τz = σz для всех переменных

z 6∼ y. Так как x 6∼ y, то τ x = σx.

Шаг индукции.

 1. Пусть Π ∼ Π

. По индукции для любого состояния σ если

(σ) = ρ, то σx = ρx. По индукции для любого состояния ρ

если Π

(ρ) = τ, то τx = ρx. По определению семантики для следования

имеем τ = Π (σ) = Π

(Π

(σ)) = Π

(ρ). Следовательно, τx = ρx = σx.

 2. Пусть

Π ∼











if T then

else

end;

3.3.

∗

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

По индукции для любого состояния σ

(σ) (x) = σx, Π

(σ) (x) = σx.

Если σ |= T , то

Π (σ) (x) = Π

(σ) (x) = σx.

В противном случае

Π (σ) (x) = Π

(σ) (x) = σx.

Следовательно, Π (σ) (x) = σx.

 3. Для неполного ветвления доказательство аналогично.

 4. Пусть

Π ∼







while T do

end;

Так как Π (σ) определено, то существуют число n и последовательность

состояний





i=0

такие, что

= σ, σ

i+1

= Π





, σ

|= T ⇐⇒ i < n, σ

= τ.

По индукционному предположению Π

(ρ) (x) = ρx для любого состоя-

ния ρ. Следовательно,

x = Π





(x) = σ

x = σx.

x = Π





(x) = σ

x = σx,

и т.д. В конце концов получим, что σ

x = σx, то есть, что τx = σx.

Задача 3.19. Обоснуйте шаг для неполного ветвления.

Следующее утверждение показывает, что для работы программы су-

щественно значение только тех переменных, которые в ней используют-

ся.

Лемма 3.5. (О неиспользуемых переменных) Для любой про-

граммы Π и любого состояния σ

Π (σ)  Var (Π) = Π (σ  Var (Π)) .

Доказательство. Индукция по построению программы.

58 Глава 3. Структурированные программы

∗

Задача 3.20. Докажите лемму.

∗

Задача 3.21. Докажите эту же лемму с заменой множества

Var (Π) на произвольное множество переменных V такое, что

Var (Π) ⊆ V .

Следствие 3.6. (О двух состояниях) Если

σ  Var (Π) = τ  Var (Π) ,

то

Π (σ)  Var (Π) = Π (τ)  Var (Π) .

Следствие 3.7. (О результате) Если Π (σ) определено, то

Π (σ) = Π (σ  Var (Π)) ∪ σ  (dom σ \ Var (Π)) .

Задача 3.22. Докажите оба следствия.

Определение 3.19. (Замена переменных) Если a — это выраже-

ние, тест или программа, x

, . . . , x

— переменные, e

, . . . , e

— вы-

ражения, то с помощью

(a)

...

мы будем обозначать результат замены в a всех переменных x

на

выражения e

Пример 3.17. Пусть e ∼ succ (x). Тогда (e)

∼ succ (y).

Замену можно определить и индукцией по построению выражений,

тестов и программ.

Определение 3.20. (Замена переменных) Для выражений:

1. если e ∼ c, c — константа, то (c)

...x

...e

∼ c;

2. если e ∼ x

, то (e)

...x

...e

∼ e

;

3. если e ∼ z, z — переменная, z 6∼ x

для i = 1, . . . , n, то (e)

...x

...e

∼ z;

4. если e ∼ o (d

, . . . , d

), o — операция, d

, . . . , d

— выражения, то

(e)

...x

...e

∼ o



)

...x

...e

, . . . , (d

)

...x

...e



3.3.

∗

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

Для теста T ∼ d

◦ d

, где d

, d

— выражения:

(T )

...x

...e

∼ (d

)

...x

...e

◦ (d

)

...x

...e

∗

Задача 3.23. Дайте определение замены для программы индукцией

по построению программы.

Лемма 3.6. (О результате замены) Если x — переменные, e — вы-

ражения, то

1. если d — выражение, то (d)

— выражение;

2. если T — тест, то (T )

— тест.

Доказательство. Индукция по построению выражения d или теста

T .

∗

Задача 3.24. Докажите лемму.

Замечание 3.2. Очевидно, для того, чтобы результат замены

(Π)

...x

...e

, где Π — программа снова был программой, необходимо, чтобы

было переменной для каждого x

∈ LVar (Π).

Задача 3.25. Приведите пример, доказывающий необходимость этого

условия.

Покажем, что это условие является одновременно и достаточным.

Лемма 3.7. (О результате замены) Пусть Π — программа, x — пе-

ременные, e — выражения, причем если x

∈ LVar (Π), то e

— пере-

менная. Тогда (Π)

— программа.

Доказательство. Индукция по построению программы Π.

∗

Задача 3.26. Докажите лемму.

Заметим, что замена осуществляется не последовательно, а одновре-

менно, то есть нельзя сначала заменить x

на e

, затем x

на e

и так

далее.

Пример 3.18. Пусть T ∼ x < y. Тогда (T )

∼ y < z, то есть мы

заменили x на y, а y на z. Если бы мы осуществляли замену не одно-

временно, а последовательно, то получили бы следующее



(T )



∼ (y < y)

∼ z < z.

Как видим, результат получился другой.

60 Глава 3. Структурированные программы

Введем понятие замены переменной для состояний.

Определение 3.21. (Замена переменных) Если σ — состояние,

, . . . , x

, y

, . . . , y

—переменные, то с помощью (σ)

...x

...y

мы обозна-

чаем следующее множество τ :

τ = (σ \ {(x

, v) : i = 1, . . . , n, v ∈ ω}) ∪ {(y

, σx

) , . . . , (y

, σx

)}.

Рассмотрим пример.

Пример 3.19. Пусть σ = {(x, 1) , (y, 2)}. Тогда

(σ)

= {(y, 1) , (z, 2)}.

Замечание 3.3. Результат замены переменных в состоянии может

не быть состоянием, так как может не быть отображением. Напри-

мер, для состояния σ из предыдущего примера:

(σ)

= {(y, 1) , (y, 2)}

не является отображением.

Сформулируем достаточное условие для того, чтобы результат замены

был состоянием.

Лемма 3.8. Если все переменные y

не входят в dom σ и все они по-

парно различны, то

(σ)

...x

...y

будет состоянием.

Задача 3.27. Докажите, лемму.

Задача 3.28. Приведите пример, доказывающий, что условие из лем-

мы не является необходимым.

Отметим одно из очевидных свойств замены.

Лемма 3.9. (Обратимость замены) Пусть a — выражение, тест,

программа или состояние. x

, . . . , x

— переменные. Предположим, что

переменные y

, . . . , y

не встречаются в a и попарно различны. Тогда



(a)

...x

...y



...y

...x

совпадает с a.