Математическая логика и теория алгоритмов [Г. И. Анкудинов] (pdf) читать онлайн

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Государственное образовательное учреждение
высшего профессионального образования
СЕВЕРО-ЗАПАДНЫЙ ГОСУДАРСТВЕННЫЙ ЗАОЧНЫЙ
ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Г.И.Анкудинов
И.Г.Анкудинов
О.А.Петухов

МАТЕМАТИЧЕСКАЯ
ЛОГИКА И ТЕОРИЯ
АЛГОРИТМОВ
Утверждено редакционно-издательским советом университета
в качестве учебного пособия
ИЗДАНИЕ ВТОРОЕ

Санкт-Петербург
2003

85

УДК 512
Анкудинов
Г.И.,
Анкудинов
И.Г.,
Петухов
О.А.
Математическая логика и теория алгоритмов: Учеб. пособие.–
2-е изд. − СПб.: СЗТУ, 2003, 104 c.
Учебное пособие соответствует государственному образовательному
стандарту дисциплины “Математическая логика и теория алгоритмов”
направления подготовки дипломированных специалистов 654600 –
“Информатика и вычислительная техника” (Специальность 220100 –
“Вычислительные машины, комплексы, системы и сети”) и направления
подготовки бакалавров 552800 – “Информатика и вычислительная техника”.
В пособии излагаются разделы математической логики и теории
алгоритмов, необходимые для освоения общепрофессиональных и
специальных дисциплин специальности 220100. Достаточно подробно
изложены основы логики высказываний и логики предикатов, включая
приложение логики предикатов к доказательству правильности алгоритмов.
Пособие содержит вводный материал по логическому программированию и
клаузальной логике, а также основные понятия нечеткой и модальной логики.
Приведены основы теории алгоритмов и алгоритмической разрешимости,
доказательство эквивалентности моделей алгоритмов Тьюринга и рекурсивных
схем Клини. Пособие содержит также введение в теорию эффективной
вычислимости, переборных NP-полных и NP-трудных задач.
Во втором издании исправлены опечатки и неточности.
Рецензенты:
кафедра процессов управления и информационных систем СевероЗападного
государственного
заочного
технического
университета
(зав.кафедрой О.И.Золотов, канд.техн.наук, доц., А.Б.Шадрин, д-р техн.наук,
проф.);
В.В.Лохмотко, д-р техн.наук, проф., М.О.Колбанев, канд.техн.наук, доц.
(кафедра
информационных
управляющих
систем
Государственного
университета телекоммуникаций им. проф. М.А.Бонч-Бруевича).

© Северо-Западный государственный заочный технический университет, 2003
© Анкудинов Г.И., Анкудинов И.Г., Петухов О.А., 2003

86

Глава 1
ЛОГИКА ВЫСКАЗЫВАНИЙ
В основе стандартной (классической) логики лежит логика
высказываний (пропозициональная логика) и логика предикатов.
Высказывание это повествовательное предложение, в отношении
которого имеет смысл утверждение об его истинности или
ложности. Пример истинного высказывания: "Земля вращается
вокруг Солнца". Предикат это повествовательное предложение,
содержащее предметные (индивидные переменные), замена которых
на константные значения превращает рассматриваемое предложение
в высказывание – истинное или ложное.

1.1. Логические операции над высказываниями
Высказывание – это повествовательное предложение,
утверждающее что-то о чем-либо, причем высказывание может быть
истинным либо ложным. Высказывания могут быть простыми и
составными. Составные высказывания образуются из простых с
помощью связок НЕ, И, ИЛИ, ЕСЛИ-ТО, ТОГДА-И-ТОЛЬКОТОГДА.
В алгебре высказываний все высказывания рассматриваются с
точки зрения их логического значения или истинности. Считается,
что каждое высказывание либо истинно (И), либо ложно (Л).
Высказывание не может быть одновременно истинным и ложным.
Будем обозначать высказывания простыми латинскими буквами
A,B,C,.... Составные высказывания образуются из простых с
помощью логических операций над высказываниями. Перечислим
основные логические операции:
• отрицание,
• конъюнкция,
• дизъюнкция,
• импликация,
• эквивалентность.
87

Отрицание высказывания A образуется с помощью операции
отрицания и в данном тексте будет обозначаться ⎯A или ⎤A (читается:
"неверно, что A" или, короче "не A"). Логическую
Таблица 1.1
функцию,
соответствующую
зависимости
логического значения ⎯A от логического
A
⎯A
значения высказывания A, можно представить с
И
Л
помощью таблицы истинности (табл.1.1): если A
Л
И
истинно, то ⎯A ложно и наоборот.
Конъюнкцией двух высказываний A, B называется новое
высказывание, которое обозначается A&B
Таблица 1.2
(читается "A и B"). Конъюнкция A&B истинна
A B
A&B
тогда и только тогда, когда A и B одновременно
Л Л
Л
истинны, а в остальных случаях ложна (табл.1.2).
Л И
Л
Конъюнкцию также иногда именуют логическим
И Л
Л
произведением.
И И
И
Примечание. Кроме символа & в
литературе используются и другие обозначения конъюнкции: A /\ B,
A*B, AB.
Дизъюнкцией высказываний A и B называется новое
высказывание, которое обозначается A \/ B (читается: "A или B").
Дизъюнкция A\/B ложна тогда и только тогда, когда A и B
одновременно ложны, а в остальных случаях истинна (табл.1.3).
Дизъюнкцию также иногда именуют логической
Таблица 1.3
суммой.
A B
A\/B
Л Л
Л
Следует обратить внимание на то, что если в
Л И
И
таблице истинности для дизъюнкции заменим все
И Л
И
Л на И и все И на Л (как для операндов, так и для
И И
И
результата операции), то получим таблицу
истинности для конъюнкции).
Импликацией двух высказываний A и B
Таблица 1.4
называется
новое
высказывание,
которое
A B
A→B
обозначается A→B (варианты чтения: "Если A, то
Л Л
И
B"; "То, что A, влечет то, что B"; "A только тогда,
Л И
И
когда B"; "То, что A, есть достаточное условие
И Л
Л
того, что B"; "Чтобы A, необходимо, чтобы B").
И И
И
Высказывание A→B ложно тогда и только тогда,
когда A истинно, а B ложно (табл.1.4). В составе импликации A→B
88

высказывание A называется условием или посылкой, а высказывание
B – заключением или следствием.
Примечание. Импликация A→B может быть записана также как
B←A (читается: "B при условии, что A", "То, что B, есть необходимое
условие того, чтобы A", "Чтобы B, достаточно того, чтобы A".)
Эквивалентностью двух высказываний A и B называется новое
высказывание, которое обозначается A↔B ( читается: "A
эквивалентно B", "A, тогда и только тогда, когда
Таблица 1.5
B"; "A, если и только если B", "Чтобы A,
A B
A↔B
необходимо и достаточно, чтобы B"; "То, что A,
Л Л
И
есть необходимое и достаточное условие для
Л И
Л
И Л
Л
того, чтобы B"). Высказывание A↔B истинно
И И
И
тогда и только тогда, когда значения истинности
A и B совпадают (табл.1.5).
Часто в литературе, особенно в технических приложениях, для
логического значения "истина" вместо И используется обозначение
1, а для логического значения "ложь" вместо Л – обозначение 0.

1.2. Составные высказывания
С помощью логических операций, рассмотренных в п.1.1,
можно из простых высказываний строить различные составные
высказывания. Например, из высказываний A, B и C можно
построить составные высказывания
⎤(A & B) \/ C

и

A → [ B ↔ (A \/ C)].

Логическое значение составного высказывания зависит только от
логических значений образующих его элементарных высказываний.
Например, если A = 0, B = 1 и C = 0, то
⎤(A & B) \/ C = ⎤(0 & 1) \/ 0 =⎯0 \/ 0 =1 \/ 0= 1 и
A → [B ↔ (A \/ C)] = 0 → [1 ↔ (0 \/ 0)] =
0 → [1 ↔ 0] = 0 → 0 = 1.
Формулой исчисления высказываний называются

89

а) отдельные буквы, обозначающие переменные высказывания
(P1, P2,...,PN);
б) выражения вида ⎤(Ф), (Ф1)&(Ф2), (Ф1)\/(Ф2), (Ф1)→(Ф2),
(Ф1)↔(Ф2), где Ф, Ф1, Ф2 - некоторые формулы.
Формулу, состоящую из переменных P1, P2, ..., PN, логических
символов и скобок, будем обозначать
Таблица 1.6
Ф(P1, P2, ..., PN). Если в формулу Ф
P1 P2 P3
⎤(P1 & P2) \/ P3
вместо переменных P1, P2, ..., PN
0 0 0
1
0 0 1
1
подставить
высказывания A1, A2, ...,
0 1 0
1
то
получим
составное
AN,
0 1 1
1
высказывание Ф(A1, A2, ..., AN),
1 0 0
1
1 0 1
1
имеющее
конкретное
логическое
1 1 0
0
значение. Зависимость логического
1 1 1
1
значения Ф(A1, A2, ..., AN) от P1, P2, ...,
можно
выразить
таблицей
PN
истинности. Например, таблица 1.6 выражает такую зависимость для
формулы ⎤(P1 & P2 ) \/ P3. Формула исчисления высказываний Ф(P1,
P2,..., PN) называется тавтологией или тождественно истинной,
если ее значение для любых значений P1, P2,..., PN есть истина.

1.3. Основные тавтологии
Закон исключенного третьего:

⎯P \/ P .

(1.1)

Закон отрицания противоречия:
⎤(⎯P & P).

(1.2)

Закон двойного отрицания:
⎤ ⎤P↔ P.
Следующие
дизъюнкции.

законы

выражают

90

(1.3)
свойства

конъюнкции

и

Законы идемпотентности:
(P & P) ↔ P,

(1.4)

(P \/ P) ↔ P.

(1.5)

Законы упрощения:
(P1 & P2) → P1,

(1.6)

P1 → (P1 \/ P2).

(1.7)

Законы коммутативности:
(P1 & P2) ↔ (P2 & P1),

(1.8)

(P1 \/ P2) ↔ (P2 \/ P1).

(1.9)

Законы ассоциативности:
[(P1 & P2) & P3] ↔ [P1 & (P2 & P3)],

(1.10)

[(P1 \/ P2) \/ P3] ↔ [P1 \/ (P2 \/ P3)].

(1.11)

Законы дистрибутивности:
[(P1 \/ P2) & P3] ↔ [(P1 & P3) \/ (P2 & P3)],

(1.12)

[(P1&P2)\/P3]↔[(P1\/P3)&(P2\/P3)].

(1.13)

Закон де-Моргана:
⎤(P1 & P2) ↔ (⎯P1 \/⎯P2),

(1.14)

⎤(P1 \/ P2) ↔ (⎯P1 &⎯P2).

(1.15)

Следующие законы
эквивалентности.
Закон тождества:

выражают

свойства

P → P.

импликации

и

(1.16)

Закон контрапозиции:
(P1 → P2) ↔ (⎯P2 →⎯P1)).

(1.17)

Правило цепного заключения:
[(P1 → P2) & (P2 → P3)] → (P1 → P3).
91

(1.18)

Законы рефлексивности, симметричности и транзитивности:
P ↔ P,

(1.19)

(P1 ↔ P2) ↔ (P2 ↔ P1),

(1.20)

[(P1 ↔ P2) & (P2 ↔ P3)] → (P1 ↔ P3).

(1.21)

Закон противоположности:
(P1↔P2)↔(⎯P1↔⎯P2).

(1.22)

Следующие законы выражают зависимости между основными
логическими операциями.
Выражение конъюнкции через дизъюнкцию и отрицание и
дизъюнкции через конъюнкцию и отрицание:
(P1 & P2) ↔ ⎤(⎯P1 \/⎯P2),

(1.23)

(P1 \/ P2) ↔⎤ (⎯P1 & ⎯P2).

(1.24)

Выражение эквивалентности через конъюнкцию и импликацию:
(P1 ↔ P2) ↔ [(P1 → P2) & (P2 → P1)].

(1.25)

Выражение импликации через конъюнкцию и отрицание и через
дизъюнкцию и отрицание:
(P1 → P2) ↔ ⎤(P1 & ⎯P2),

(1.26)

(P1 → P2) ↔ (⎯P1 \/ P2).

(1.27)

Выражение конъюнкции и дизъюнкции через отрицание и
импликацию:
(P1 & P2) ↔ ⎤(P1 →⎯P2),

(1.28)

(P1 \/ P2) ↔ (⎯P1 → P2).

(1.29)

92

1.4. Равносильные формулы
Две формулы исчисления высказываний Ф1(P1,...,PN) и
Ф2(P1,...PN) называются равносильными, если они принимают
одинаковое значение для любых значений P1,...PN. Две равносильные
формулы имеют одну и ту же таблицу истинности и, наоборот,
формулы, имеющие одну и ту же таблицу истинности, равносильны.
Условие равносильности формул выражает
Теорема 1.1. Формулы Ф1(P1,...PN) и Ф2(P1,...PN) равносильны
тогда и только тогда, когда их эквивалентность
Ф1(P1,...PN) ↔ Ф2(P1,...PN)
является тавтологией.
Отношение равносильности обозначается символом
Например, из законов (1.12) и (1.13) следуют равносильности:
(P1 \/ P2) & P3 ⇔ (P1 & P3) \/ (P2 & P3),
(P1 & P2) \/ P3 ⇔ (P1 \/ P3) & (P2 \/ P3).

⇔.

(1.30)
(1.31)

Из законов (1.14) и (1.15) следуют равносильности:
(1.32)
(1.33)

⎤(P1 & P2) ⇔⎯P1 \/⎯P2,
⎤(P1 \/ P2) ⇔⎯P1 &⎯P2.
Из тавтологий (1.23,...,1.29) следуют равносильности:
P1 & P2 ⇔ ⎤(⎯P1 \/⎯P2),
P1 \/ P2 ⇔ ⎤(⎯P1 &⎯P2),
P1 ↔ P2 ⇔ (P1 → P2) & (P2 → P1),
P1 → P2 ⇔ ⎤(P1 &⎯P2),
P1 → P2 ⇔ ⎯P1 \/ P2,
P1 & P2 ⇔ ⎤(P1 →⎯P2),
P1 \/ P2 ⇔ ⎯P1 → P2.
Полезно также использовать следующие
логическими константами:
P \/ 1 ⇔ 1,

93

(1.34)
(1.35)
(1.36)
(1.37)
(1.38)
(1.39)
(1.40)
равносильности

с

(1.41)

P \/ 0 ⇔ P,
P & 1 ⇔ P,
P & 0 ⇔ 0.

(1.42)
(1.43)
(1.44)

Для упрощения формул исчисления высказываний полезны
следующие равносильности, называемые правилами склеивания:
(P1 & P2) \/ (P1 &⎯P2) ⇔ P1,
(P1 \/ P2) & (P1 \/⎯P2) ⇔ P1;

(1.45)
(1.46)

правила поглощения:
P1 \/ (P1 & P2) ⇔ P1,
P1 & (P1 \/ P2) ⇔ P1;

(1.47)
(1.48)

формулы Блейка - Порецкого:
(P1&P2)\/(P3&⎯P2) ⇔ (P1&P2)\/(P3&⎯P2)\/(P1&P3),
(P1\/P2) & (P3\/⎯P2) ⇔ (P1\/P2)&(P3\/⎯P2)&(P1\/P3)

(1.49)
(1.50)

и формулы равносильности:
P1 \/ (⎯P1 & P2) ⇔ P1 \/ P2,
P1 & (⎯P1 \/ P2) ⇔ P1 & P2,
P &⎯P ⇔ 0,
P \/⎯P ⇔ 1,
P & P ⇔ P,
P \/ P ⇔ P.
⎤⎯P ⇔ P.

(1.51)
(1.52)
(1.53)
(1.54)
(1.55)
(1.56)
(1.57)

Часто требуется упростить формулу исчисления высказываний,
т.е. получить формулу равносильную исходной, но содержащую по
возможности меньшее число пропозициональных букв и символов
логических операций. Например, дана формула
(X1\/X2\/X3)&(X1\/⎯X2\/X3)&(X1\/⎯X3)&(X2\/X3\/X4)&
(X1\/⎯X2\/⎯X3)& (X1\/ X3\/⎯X4)&(X1\/X2).

94

Применим к первым двум подформулам (X1\/X2\/X3)&(X1\/⎯X2\/X3)
равносильность (1.46), считая P1 = X1\/X3 и P2 = X2, тогда их можно
заменить одной подформулой (X1\/X3), что дает более простую
формулу, равносильную исходной:
(X1\/X3)&(X1\/⎯X3)(X2\/X3\/X4)&(X1\/⎯X2\/⎯X3)&(X1\/X3\/⎯X4)&(X1\/X2).
К подформулам (X1\/X3) и (X1 \/⎯X3) снова применим равносильность
(1.46) и получаем еще более простую формулу, равносильную
исходной:
X1& (X2\/X3\/X4)&(X1\/⎯X2\/⎯X3)&(X1\/X3\/⎯X4)& (X1\/X2).
Коммутативность конъюнкции позволяет переписать последнее
выражение, а равносильность (1.48) – выполнить дальнейшее
упрощение
X1&(X1\/⎯X2\/⎯X3)&(X1\/X3\/⎯X4)& (X1\/X2) & (X2\/X3\/X4)=
X1& (X2\/X3\/X4).
Если в формуле используются операции импликации и
эквивалентности, то, как правило, их следует преобразовать с
помощью равносильностей (1.36), (1.37) и (1.38).
Например:
((X1→X2) \/ (X1→X4)) → (X1 → (X2 \/ X3)) =
(⎯X1 \/ X2 \/⎯X1 \/ X4) → (⎯X1 \/ X2 \/ X3) =
(⎯X1 \/ X2 \/ X4) →(⎯X1 \/ X2 \/ X3) =
⎤(⎯X1 \/ X2 \/ X4) \/⎯X1 \/ X2 \/ X3 =
(X1 & ⎤(X2 \/ X4)) \/⎯X1 \/ X2 \/ X3 =
(X1 &⎯X2 &⎯X4) \/ ⎯X1 \/ X2 \/ X3 =
(⎯X2 &⎯X4) \/ ⎯X1 \/ X2 \/ X3 =
⎯X1 \/ X2 \/ X3 \/⎯X4.

95

1.5. Логическое следование
Кроме отношения равносильности, между формулами
исчисления высказываний на практике приходится рассматривать
отношение логического следования: формула Ф2(P1,...,PN) логически
следует из формулы Ф1(P1,...,PN), или
Ф1(P1,...,PN) ⇒ Ф2(P1,...,PN),
если Ф2(P1,...,PN) истинна на всех наборах значений P1,...,PN, на
которых Ф1(P1,...,PN) истинна.
Логическое следование Ф1⇒Ф2 означает, что из истинности Ф1
следует истинность Ф2, но если Ф1 ложна, то относительно Ф2
ничего сказать нельзя. Функция Ф1 в этом случае называется
импликантой для Ф2. Важное значение имеет
Теорема 1.2. Ф1(P1,...,PN) ⇒ Ф2(P1,...,PN) тогда и только
тогда, когда импликация Ф1(P1,...,PN)→ Ф2(P1,...,PN) является
тавтологией.
Пример 1.1. Необходимо выяснить, является ли одно составное
высказывание
логическим
следствием
другого.
Возьмем
высказывание: "Равные треугольники подобны". Это высказывание
можно записать символически Ф1 = A → B, где A = "Треугольники
равны", B = "Треугольники подобны".
Рассмотрим высказывание: “Треугольники подобны только в
случае их равенства", которое можно записать символически как
Ф2=B→A, где A и B определены выше. Является ли Ф2 логическим
следствием Ф1? Для получения ответа на этот вопрос рассмотрим
импликацию Ф3 = (A → B) → (B → A) и, чтобы проверить, является
ли она тавтологией, упростим эту формулу:
(A→B)→(B→A) = (⎯A \/ B)→(⎯B \/ A) = ⎤(⎯A \/ B) \/ ⎯B \/ A =
(⎤⎯A &⎯B) \/ ⎯B \/ A = ⎯B \/ A = B → A,
т.е. Ф3 не является тавтологией, следовательно, нельзя сказать, что
Ф2 является логическим следствием Ф1.

96

1.6. Логические функции
Логической функцией от n аргументов называют функции вида
n

f: {0,1} → {0,1},
т.е. областью определения логической функции являются
всевозможные n–местные векторы, компоненты которых принимают
значения из множества {0,1}={И,Л}, а областью значений – то же
множество {0,1}. Логические функции называют также булевыми
функциями, по имени англичанина Дж.Буля, разработавшего в XIX
веке основы логики высказываний. Другое название логических
функций – переключательные функции, поскольку они широко
применяются для анализа и синтеза логических устройств из
релейных (переключательных) элементов. Общее обозначение
логической функции: f(x1,x2,…,xn), где x1,x2,…,xn – логические
(булевы) переменные.
Дизъюнктивной нормальной формой (д.н.ф.) называется
формула, представляющая логическую функцию f(x1,x2,…,xn) в виде
дизъюнкции некоторого числа элементарных конъюнкций и
логических переменных с отрицанием или без отрицания, причем
под
элементарной
конъюнкцией
понимается
логическое
произведение любого числа неодинаковых логических переменных xi
(i=1,…,n) с отрицанием или без отрицания.
Пример д.н.ф.: f(x1,x2,x3)= x1 x 2 ∨ x1 x 2 x3 ∨ x1 x 2 x3 .
Каждую элементарную конъюнкцию можно представить в общем
виде

С = x1σ 1 x2σ 2 ... xnσ n , где
⎧ x , если σ i = 1;
xiσ i = ⎨ i
⎩ xi , если σ i = 0.

Элементарная

С = x1σ 1 x2σ 2 ... xnσ n

конъюнкция

называется

конституентой единицы функции f(x1, x2,…, xn), если она содержит
все n переменных функции и C⇒f(x1, x2,…, xn), т.е. f(σ1,σ2,…,σn)=1.

97

σ

σ

σ

n
1
2
Конституента единицы x1 x 2 ... x n принимает значение 1 только

на одном наборе (x1, x2, …, xn)=(σ1, σ2, …, σn).
Совершенной дизъюнктивной нормальной формой (с.д.н.ф.)
называется формула, представляющая логическую функцию
f(x1,x2,…,xn) в виде дизъюнкции некоторого числа конституент
единицы.
Конъюнктивной нормальной формой (к.н.ф.) называется
формула, представляющая логическую функцию f(x1,x2,…,xn) в виде
конъюнкции некоторого числа элементарных дизъюнкций и
логических переменных с отрицанием или без отрицания. Под
элементарной дизъюнкцией понимается логическая сумма любого
числа неодинаковых логических переменных xi (i=1,…,n) с
отрицанием или без отрицания.
Пример к.н.ф.: f(x1,x2,x3)= ( x1 ∨ x 2 )( x1 ∨ x 2 ∨ x3 )( x1 ∨ x 2 ∨ x3 ) .
Совершенной конъюнктивной нормальной формой (с.к.н.ф.)
называется формула, представляющая логическую функцию
f(x1,x2,…,xn) в виде конъюнкции некоторого числа конституент нуля
f(x1,x2,…,xn). Конституента нуля f(x1,x2,…,xn) принимает значение 0
только на одном наборе (x1,x2,…,xn).

1.7. Формальные теории и исчисление
высказываний
Формальная теория это
а) Множество правильно построенных формул (ППФ), или
выражений, определяющих язык теории.
б) Подмножество формул множества ППФ, называемых
аксиомами теории.
в) Правила вывода, т.е. конечное множество отношений
между формулами.

98

Доказательством называется конечная последовательность
формул Ф1,...,Фn, такая, что каждая Фi есть либо аксиома, либо
получена из предыдущих формул по одному из правил вывода.
Теоремой называется такая формула теории Ф, что
существует доказательство Ф1,...,Фn, где Фn=Ф.
Аксиоматическая теория полна, если присоединение к ее
аксиомам формулы, не являющейся теоремой, делает теорию
противоречивой, т.е. могут быть доказаны как Ф, так и "не Ф".
Интерпретацией формальной теории в содержательную
теорию называется соответствие теорем формальной теории
истинным утверждениям содержательной теории.
Пример формальной теории. Исчисление высказываний имеет
а) множество ППФ, определенное выше;
б) множество аксиом:
1. A→(B→A)
2. (A→ (B→C)) → ((A→B) → (A→C))
3. (⎤A→⎤B) → ((⎤A→B) →A);
в) правила вывода:
Ф ( A)
(правило подстановки).
Ф(B )
Ф, Ф → B
(правило Modus Ponens).
2.
B

1.

В записи правил вывода над чертой располагаются формулы,
называемые посылкой правила, из которых непосредственно
следуют формулы, стоящие под чертой и называемые заключением
правила.
Правило подстановки позволяет заменять в ППФ все
вхождения некоторой буквы на другую букву. Правило Modus
Ponens (MP) позволяет выводить формулу B из формул Ф и Ф→B.

99

Пример 1.2. Требуется доказать, что из A следует B→A, т.е.
A ⎟⎯ (B→A).
Доказательство. Имеем A. Тогда в соответствии с аксиомой 1
по правилу MP получаем

A, A → (B → A)
B→A

(MP) .

Интерпретацией исчисления высказываний является логика
высказываний.

В качестве дополнительной литературы по алгебре
высказываний и основам формальных теорий можно рекомендовать
[7, 8, 11, 13, 14].

Глава 2
ЛОГИКА ПРЕДИКАТОВ
2.1. Основные понятия теории множеств
Поскольку логика предикатов базируется на понятиях теории
множеств, приведем определения основных понятий этой теории.
Немецкий математик Георг Кантор, разработавший начала теории
множеств в 70-х годах XIX века, определял множество, как
объединение отдельных объектов в единое целое. Группа
математиков Н.Бурбаки дает такое определение: "Множество
образуется из элементов, обладающих некоторыми свойствами и
находящихся в некоторых отношениях между собой или с
элементами других множеств". Вместо термина "множество" могут
использоваться также наименования: "совокупность", "класс",
"система". Множество, не имеющее ни одного элемента, называется
пустым и обозначается символом в виде перечеркнутого кружка ∅.

100

Множество из n элементов обозначается {a1,a2,…,an}, а
множество из одного элемента a1 обозначается {a1}.
Конечное множество M можно задать перечислением всех его
элементов, например, M = {а,b,с,d,e,f}, при этом порядок записи
элементов не существенен, т.е. {a,b,c,d,e,f}={b,a,f,c,d,e}= {f,c,a,d,e,b}
и т.д.
Любое (конечное или бесконечное) множество можно задать
указанием общего свойства C всех его и только его элементов:
M = {x: x обладает свойством C}
или
M = {x ⎟ x обладает свойством C }.
Символ x в этом случае называется предметной переменной (в
дальнейшем мы узнаем, что утверждение "x обладает свойством C"
называется предикатом). Пример задания множества всех
действительных чисел, обладающих свойством C= 'x больше
единицы':
M = { x ⎟ x – действительное число, x>1}.
Пусть M = {a,b,c,d,e,f}. Мы говорим, например, что элемент b
принадлежит M или используем общепринятый символ
принадлежности ∈, например, b ∈ M.
Пусть M={a,b,c,d,e,f} и L={b,d,e}. Мы говорим, что L является
подмножеством M или, что каждый элемент L является элементом
M, или используя общепринятый символ включения множеств: L ⊂
M.
Множество всех подмножеств множества M называется
M
булеаном M и обозначается как 2 в степени M: 2 . Пусть M={a,b,c},
M
тогда 2 = {∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}.
Число
элементов,
или
мощность
множества
M
обозначается⎟M⎟.
M
Пример 2.1. Пусть M={a,b,c,d,e}, тогда ⎟M⎟=5. Для булеана 2 = 2

M

.

Операции над множествами. Дополнением подмножества L
множества M называется подмножество ⎯L, содержащее все
элементы M, не принадлежащие L:
⎯L ={x ⎟ x ∈ M, x не принадлежит L}.

101

Пересечением подмножеств M1 и M2 множества M называется
совокупность L всех элементов M, принадлежащих одновременно M1
и M2:
L = M1 ∩ M2 = { x ⎟ x ∈ M1, x ∈ M2 }.
Объединением подмножеств M1 и M2 множества M называется
совокупность L всех элементов M, принадлежащих первому или
второму подмножеству:
L = M1 ∪ M2 = { x ⎟ x ∈ M1 или x ∈ M2}.
Разность множеств M1 и M2:
L = M1 \ M2 = { x ⎟ x ∈ M1 и неверно, что x ∈ M2)}.
Декартовым произведением множеств M и L называется
множество всех упорядоченных пар элементов {(x,y)⎟ x ∈M, y ∈ L}.
В качестве символа декартова произведения обычно используется
символ ×, тогда
M × L = {(x,y) ⎟ x ∈ M, y ∈ L }.
Пример 2.2. Пусть M = {a,b,c} и L = {f,g,k}, тогда декартово
произведение M × L = {(a,f),(a,g),(a,k),(b,f),(b,g),(b,k),(c,f),(c,g),(c,k)}.

Бинарным отношением между элементами множеств M и L
называется подмножество M × L, например, R = {(a,f),(b,f),(b,k)}.
Декартово произведение n множеств:
M1 × M2 × ... × Mn = {(x1,x2,...,xn)⎟ x1 ∈ M1, x2 ∈ M2,..., xn ∈ Mn }.
Можно ввести также n-ю декартову степень множества M :
n

M = M × M × ... × M, где M в правой части повторяется n раз.
Пример 2.3. Пусть M = { a,b,c }, тогда

2

M = {(a,a), (a,b), (a,c), (b,a),

(b,b), (b,c), (c,a), (c,b), (c,c)}. Пусть M = {a,b}, тогда M
(a,b,a), (a,b,b), (b,a,a), (b,a,b), (b,b,a), (b,b,b)}.

102

3

= {(a,a,a), (a,a,b),

2.2. Определение предиката
Предикатом называется выражение, имеющее грамматическую
форму высказывания, но содержащее предметные переменные
некоторых множеств. Например, предложение "8 - четное число"
является высказыванием. Заменим "8" на "x", тогда предложение "xчетное число", где x принадлежит множеству натуральных чисел,
будет предикатом.
Выражение A(x1,x2,...,xn), содержащее предметные переменные
x1 ∈ M1, x2 ∈ M2,..., xn ∈ Mn, называется n-местным предикатом,
определенным на множествах M1, M2,..., Mn.
При замене предметных переменных константами из
соответствующих множеств предикат A(x1,x2,...,xn) превращается в
высказывание, которое может быть либо истинным, либо ложным.
Пример 2.4 . Пусть N = { 1,2,3,4,5,6 }, A(x) = "x - четное число", тогда
A(1) = Л, A(2) = И, A(3) = Л и т.д., т.е. значения аргументов 2, 4, 6
удовлетворяют предикату A(x), а значения 1, 3, 5 не удовлетворяют.

Множество истинности, или интенсионал, предиката
A(x1,x2,...,xn) – это подмножество его области определения
M1×M2×...×Mn, на котором этот предикат истинен:
{(x1, x2,..., xn)⎟ A(x1, x2,..., xn)=И}.
В дальнейшем будем в этом случае писать {(x1,x2,...,xn)⎟A(x1,x2,...,
xn)}, подразумевая, как это обычно и принято, что берутся значения
(x1,x2,..., xn), на которых A(x1,x2,..., xn)=И.
Пример 2.5. Для рассмотренного в примере 2.4 предиката множество
истинности { x ⎟ A(x)} = { 2,4,6 }.
Пример 2.6. Пусть N = { 1,2,3,4 } и B(x1,x2) = "x1>x2", тогда множество
истинности предиката B(x1,x2): {(x1,x2)⎟x1 > x2} = {(2,1), (3,1), (3,2), (4,1), (4,2),
(4,3)}.

Два n-местных предиката, определенных на одних и тех же
множествах M1, M2,..., Mn, называются равносильными, если
значения их для любых аргументов совпадают, т.е. они имеют одно и
то же множество истинности. Например, предикаты "x > 2" и "x - 2 >
0" равносильны.
103

Предикат
B(x1,x2,...,xn)
называется следствием предиката
если
B(x1,x2,...,xn)
удовлетворяется
любыми
A(x1,x2,...,xn),
аргументами, удовлетворяющими A(x1, x2,...,xn).
Пример 2.7. Предикат "n делится на 3" есть следствие предиката "n
делится на 6", где n - целое число.

Два n-местных предиката, определенные на одних и тех же
множествах, равносильны тогда и только тогда, когда каждый из них
является следствием другого.
Предикат называется
а) тождественно истинным, если значение его для любых
аргументов есть "истина";
б) тождественно ложным, если значение его для любых аргументов
есть "ложь";
в) выполнимым, если существует, по крайней мере, одна n-система
его аргументов, для которой значение предиката есть "истина".
Пример 2.8.
Предикат "x + y = y + x" является тождественно
истинным, предикат "x + 1= x" – тождественно ложным, предикат "x + y = 5" –
выполнимым.

Каждый
тождественно
истинный
предикат
является
выполнимым, но обратное неверно. Каждый выполнимый предикат
будет не тождественно ложным и обратно, каждый не тождественно
ложный предикат будет выполнимым.
Каждому n-местному предикату A(x1, x2,...,xn), определенному
на множествах M1,M2,...,Mn соответствует n-отношение R,
являющееся подмножеством декартова произведения M1 × M2 × ... ×
Mn и равное множеству истинности этого предиката
R = { (x1, x2,...,xn) ⎟ A(x1, x2,...,xn) }.
Обратно, каждому n-отношению R между элементами множеств
M1,M2,...,Mn соответствует предикат, множество истинности
которого есть R.

104

2.3. Операции над предикатами
Предикат A(x1,x2,...,xn) можно рассматривать как логическую
функцию, определенную на M1×M2×...×Mn и принимающую значения
на множестве {И,Л}. Простейшими логическими операциями над
предикатами, так же как и для высказываний являются: отрицание,
конъюнкция, дизъюнкция, импликация и эквивалентность.
Рассмотрим
предикаты
A(x1,x2,...,xn)
и
B(x1,x2,...,xn),
определенные на M1×M2×...×Mn.
Отрицанием предиката A(x1,x2,...,xn) называется новый nместный предикат ⎯A(x1,x2,... xn), множество истинности которого
является
дополнением
множества
истинности
предиката
A(x1,x2,...,xn), т.е.
{( x1,x2,...,xn) ⎟ ⎯A(x1,x2,...,xn)} =
M1 × M2 × ... × Mn \ {( x1,x2,...,xn) ⎟ A(x1,x2,...,xn }.
Конъюнкцией предикатов A(x1,x2,...,xn)
называется новый n-местный предикат

и

B(x1,x2,...,xn)

C(x1,x2,...,xn) = A(x1,x2,...,xn) & B(x1,x2,...,xn),
множество истинности которого есть пересечение
истинности A(x1,x2,..., xn) и B(x1,x2,..., xn), т.е.

множеств

{( x1,x2,...,xn) ⎟ C(x1,x2,...,xn)} =
{( x1,x2,...,xn) ⎟ A(x1,x2,...,xn)} ∩ {( x1,x2,...,xn) ⎟ B(x1,x2,...,xn)}.
A(x1,x2,...,xn)

Дизъюнкцией предикатов
называется n-местный предикат

и

B(x1,x2,...,xn)

D(x1,x2,...,xn) = A(x1,x2,...,xn) \/ B(x1,x2,...,xn),
множество истинности которого есть объединение
истинности A(x1,x2,...,xn) и B(x1,x2,...,xn), т.е.

множеств

{( x1,x2,...,xn) ⎟ D(x1,x2,...,xn)}=
{( x1,x2,..., xn) ⎟ A(x1,x2,..., xn)} ∪ {( x1,x2,..., xn) ⎟ B(x1,x2,..., xn)}.

105

Импликацией предикатов
называется предикат

A(x1,x2,...,xn)

и

B(x1,x2,...,xn)

I(x1,x2,...,xn) = A(x1,x2,...,xn) → B(x1,x2,...,xn),
который имеет значение ЛОЖЬ на тех и только на тех наборах
аргументов x1,x2,...,xn, на которых A(x1,x2,...,xn) имеет значение
ИСТИНА, а B(x1,x2,...,xn) - значение ЛОЖЬ.
Пусть M(A), M(B) и M(I) множества истинности A(x1,x2,...,xn),
B(x1,x2,...,xn) и I(x1,x2,...,xn), тогда M(I) = M ( A) ∪ M(B), где M ( A) дополнение множества M(A).
Эквивалентностью предикатов A(x1,x2,...,xn) и B(x1,x2,...,xn)
называется предикат
E(x1,x2,...,xn) = A(x1,x2,...,xn) ↔ B(x1,x2,...,xn),
который имеет значение истина на тех и только на тех наборах
аргументов x1,x2,...,xn, на которых значения истинности A(x1,x2,...,xn)
и B(x1,x2,...,xn) совпадают. Множество истинности M(E) для
эквивалентности предикатов A(x1,x2,...,xn) ↔ B(x1,x2,...,xn) есть
M(E) = [ M ( A) ∩ M (B ) ] ∪ [M(A) ∩ M(B)].
Пример 2.9. Даны универсальное множество M = {a,b,c,d,e,f} и два
подмножества L = {b,c,d} и K = {d,e,f}, и два предиката A(x) и B(x), причем
{x⎟A(x)=И}=L и {x⎟B(x)=И}=K, т.е. L и K являются множествами истинности
предикатов A(x) и B(x) соответственно. Требуется найти множество истинности
эквивалентности E(x)=A(x)↔⎤B(x).
Для решение этой задачи используем определение эквивалентности
предикатов:
{x⎟E(x)=И} = (⎯L∩ K) ∪ (L ∩⎯K) =
({a,e,f} ∩ {d,e,f}) ∪ ({b,c,d} ∩ {a,b,c}) =
{e,f} ∪ {b,c} = {e,f,b,c}.

2.4. Логические операции квантификации
Пусть A(x) – одноместный предикат, определенный на
множестве M. Универсальным высказыванием, соответствующим
106

A(x), называется высказывание "каждый элемент множества M
удовлетворяет предикату A(x)", которое будем обозначать ∀x A(x).
Высказывание ∀x A(x) считается истинным, если предикат A(x)
тождественно истинный, и ложным - в противном случае.
Символ ∀x называется квантором всеобщности по переменной
x, его читают: "для всех x" или "для каждого x" или "для любого x".
Выражение ∀x A(x) читается: "для всех x, A (x)" или "для каждого x,
A(x)".
Например,
∀x(x=x)
–
это
истинное
универсальное
высказывание, а ∀x(x > 2) – ложное универсальное высказывание.
Если A(x) – одноместный предикат, определенный на конечном
множестве {a1,a2,...,am}, то ∀x A(x) ↔ [A(a1) & A(a2) & ... & A(am)].
Таким образом, квантор всеобщности можно понимать как оператор
конъюнкции по квантифицируемой переменной.
Экзистенциональным
высказыванием,
соответствующим
предикату A(x), называется высказывание "существует элемент
множества M, удовлетворяющий предикату A(x)", которое
обозначается ∃x A(x), и считается истинным, если предикат A(x)
выполнимый, и ложным - в противном случае.
Символ ∃ называют квантором существования, а выражение
∃x, в котором этот квантор предшествует переменной x, читают:
"существует x такой, что ..." или "для некоторого x, ...". Например,
выражение ∃x A(x) читается: "существует x такой, что A(x) " или "для
некоторого x, A(x)".
Например,
∃x(x>2)
–
истинное
экзистенциональное
высказывание, а ∃x(x=x+1) – ложное экзистенциональное
высказывание.
Если A(x) - одноместный предикат, определенный на конечном
множестве {a1,a2,...,am}, то ∃x A(x) ↔ [A(a1) \/ A(a2) \/ ... \/ A(am)].
Таким образом, квантор существования можно понимать как
оператор дизъюнкции по квантифицируемой переменной.
Применение кванторов к n-местным предикатам. К nместному предикату можно применить n кванторов. Применение
квантора к n-местному предикату (n≥1) дает (n-1)- местный предикат.

107

Пример 2.10.

∃x1 A(x1,x2,...,xn) - (n-1)-местный предикат, у которого

x1 - связанная переменная, а x2,x3, ..., xn - свободные переменные. Если все
переменные n-местного предиката связаны, получаем 0-местный предикат, или
высказывание, например:
(∃x1,x2,...,xn) A(x1,x2,...,xn);
(∃x1,x2) (∀x3) B(x1,x2,x3).

2.5. Исчисление предикатов
Введем символы двух видов:
предметные переменные (x,y,z,x1,x2...) и
предикатные буквы (P,Q,R,P1,P2,...).
Из предикатных букв, предметных переменных, логических символов и скобок можно сформировать различные выражения,
некоторые из которых называются формулами.
Формулами исчисления предикатов являются
а) каждая предикатная буква и предикатная буква со
следующими за ней в скобках предметными переменными;
б) выражения ⎤(Ф), (Ф1)&(Ф2), (Ф1)\/(Ф2),(Ф1)→(Ф2),
(Ф1)↔(Ф2), ∀x (Ф) и ∃x Ф(x), где Ф,Ф1,Ф2 – некоторые формулы; x –
некоторая индивидная переменная, причем ⎤(Ф) называется
отрицанием формулы Ф, а (Ф1)&(Ф2), (Ф1)\/(Ф2), (Ф1)→(Ф2),
(Ф1)↔(Ф2) называются конъюнкцией, дизъюнкцией, импликацией и
эквивалентностью формул Ф1 и Ф2 соответственно; ∀x(Ф) и ∃x(Ф)
называются квантификацией формулы Ф по переменной x квантором
общности и существования соответственно.
Предметная переменная называется свободной, если она не
следует непосредственно за квантором и не входит в область
действия квантора по этой переменной, все другие переменные,
входящие в формулу, называются связанными.
Примечание. В общем случае формула исчисления предикатов может
иметь вид предикатной буквы, за которой в скобках следуют предикатные
переменные или функциональные буквы.

108

Интерпретацией формулы исчисления предикатов называется
конкретизация множеств, из которых принимают значения
предметные
переменные и конкретизация отношений и
соответствующих множеств истинности для каждой предикатной
буквы.
Пример 2.11. 0-местная формула ∀x(P(x) → Q(x)) ↔ ⎤∃x ( P(x) & Q(x))
ложна для интерпретации, при которой x∈{a,b,c,d,e}, {x⎟P(x)} = {a,b},
{x⎟Q(x)} = {a,b,c}.
Действительно, универсальное высказывание ∀x(P(x) → Q(x)) истинно,
поскольку {x⎟P(x)} ⊂ {x⎟Q(x)}. В то же время, ∃x(P(x) & Q(x)) истинно, т.к.
пересечение {x⎟P(x)} и {x⎟Q(x)} равно {a,b}, т.е. не пусто и, следовательно,
высказывание ⎤∃x(P(x) & Q(x)) ложно .
Таким образом, эквивалентность приводится к виду И↔Л, т.е. ложна.
Эта же 0-местная формула истинна для интерпретации, при которой x ∈
{a,b,c,d,e}, {x⎟P(x)}={a,b}, {x⎟Q(x)}={c,b},
поскольку в этом случае формулы ∀x(P(x) → Q(x)) и ⎤∃x(P(x) & Q(x)) ложны и,
следовательно, эквивалентность приводится к виду Л↔Л, т.е. истинна.

Пример 2.11 показывает, что существуют формулы исчисления
высказываний, истинность которых зависит от интерпретации.
Формула исчисления предикатов называется общезначимой,
если она тождественно истинна при любой интерпретации.
Общезначимая формула исчисления предикатов получается из
тавтологии исчисления высказываний при замене входящих в нее
пропозициональных букв предикатными буквами с произвольным
числом приданных предметных переменных.
Общезначимость формул, содержащих кванторы, требует
особого доказательства.
Приведем некоторые общезначимые формулы.
Законы де-Моргана для кванторов:
⎤∀x P(x) ↔ ∃x ⎤P(x),
Законы
дизъюнкцию:

⎤∃x P(x) ↔ ∀x ⎤P(x).
пронесения кванторов

(2.1)
через

(2.2)
конъюнкцию и

∀x[P(x) & Q(x)] ↔ [∀x P(x) & ∀x Q(x)],

(2.3)

∀x[P(x) \/ Q] ↔ [∀x P(x) \/ Q],

(2.4)

109

∃x[P(x) \/ Q(x)] ↔ [∃x P(x) \/ ∃x Q(x)],

(2.5)

∃x[P(x) & P] ↔ [∃x P(x) & P].

(2.6)

Законы пронесения кванторов через импликацию:
∀x[P(x) → Q(x)] → [∀x P(x) → ∀x Q(x)],
∀x[P(x) → Q(x)] → [∃x P(x) → ∃x Q(x)],

(2.7)
(2.8)

∀x[P(x) → Q] ↔ [∃x P(x) → Q].

(2.9)

Законы удаления
существования:

квантора

общности

и

введения

квантора

∀x P(x) → P(x),

(2.10)

P(x) → ∃x P(x).

(2.11)

Законы преобразования категорических высказываний:
∀x[P(x) → Q(x)] ↔ ⎤∃x[P(x) &⎤Q(x)],

(2.12)

∀x[P(x) → ⎤Q(x)] ↔ ⎤∃x[P(x) & Q(x)].

(2.13)

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

• истинные при любой интерпретации, т.е. общезначимые;
• ложные при любой интерпретации, т.е. противоречивые;
• формулы, истинность которых зависит от интерпретации.
Чтобы определить тип формулы, то сначала следует попытаться
установить общезначимость или противоречивость заданной
формулы (тем более, что для одноместных предикатов это
алгоритмически разрешимая задача) и, если это не удается сделать,
то перейти к установлению значения истинности формулы для
заданной интерпретации, например так, как было показано выше в
примере 2.11.
Пример 2.12. Требуется установит тип формулы
∀x(⎤P(x) → ⎤Q(x)) ↔ ⎤∃x(⎤P(x) & Q(x)).
Попытаемся установить общезначимость или противоречивость данной
формулы. Для этого левую часть заданной эквивалентности заменим
равносильной формулой ∀x(P(x) \/ ⎤Q(x) на основе (1.38), а правую часть формулой ∀x⎤(⎤P(x) & Q(x)) на основе (2.2). Далее, с учетом (1.14), правая часть
примет вид ∀x(P(x) \/ ⎤Q(x)), т.е. исходная формула преобразована к виду

110

∀x(P(x) \/ ⎤Q(x)) ↔ ∀x(P(x) \/ ⎤Q(x)), где левая часть равна правой.
Следовательно, заданная формула является общезначимой.

2.6. Логика доказательства правильности
алгоритмов и программ
Цель данного раздела – познакомить читателя с принципами
верификации (доказательства правильности) алгоритмов и
программ. Создание и весь последующий жизненный цикл
надежного
программного
обеспечения
для
современных
информационно-вычислительных систем – многоэтапный и
трудоемкий процесс, который упрощенно можно охарактеризовать
как перевод требований технического задания сначала в точные
спецификации и, наконец, в текст программы.
Для описания алгоритмов используются различные методы,
отличающиеся
степенью
детализации
и
формализации.
Теоретическое описание обычно дается в повествовательноформальном изложении, цель которого – обосновать без лишних
подробностей процедуру, предлагаемую в качестве алгоритма. Для
наглядного
представления
структуры
алгоритмов
широко
применяются графические средства: графы, блок-схемы, сети.
Формальное и полное описание алгоритмов осуществляется на
алгоритмических языках; оно содержит всю необходимую для
реализации алгоритма информацию.
Сложность
программного
продукта
как
объекта
проектирования – основная причина ошибок перевода спецификаций
в текст программы и, следовательно, ненадежности программного
обеспечения. Для снижения сложности проекта используют
технологию
модульного
проектирования
и
объектноориентированный подход.
Распространенный подход к обеспечению надежности
проектируемого программного обеспечения – это тестирование.
Цель тестирования – выявление ошибок, вкравшихся в программу на

111

разных стадиях проектирования. При таком подходе при написании
программ акцент делается на их тестируемость, т.е. на создание
программ, которые удобно тестировать, а безошибочность и
корректность программы в значительной степени зависят от
творческих способностей и интуиции разработчика.
В отличие от интуитивного подхода, который мы
охарактеризовали выше, рассматриваемый далее подход трактует
программирование как точную математическую науку. Этот подход
основан на том, что спецификация программ выражается средствами
логики, причем связь программ с их спецификацией осуществляется
путем определения семантики программ также средствами логики
(алгоритмическая логика Хоара* ). Этот подход открывает путь к
верификации (доказательству правильности) алгоритмов и программ
средствами логики.
В основе верификации программ (алгоритмов) – анализ
действия программ (алгоритмов) над данными. Для каждого
исходного состояния данных X, для которого выполнение
завершается, результирующее состояние данных Y является
определенным. Это значение Y единственно для данного X, поэтому
множество всех упорядоченных пар (X,Y) определяет функцию,
которую будем называть программной функцией.
Мы будем использовать символьные вычисления, чтобы
получить аналитическое выражение программной функции для
исследуемой программы. Программную функцию f для простой
программы P обозначим через [P] и определим выражением
[P]={(X,Y)⎥ Y=f(X)},
где X - состояние поля данных до выполнения P,
Y - состояние поля данных после выполнения P,
{(X,Y) ⎥ Y=f(X)} - множество пар (X,Y), таких, что Y=f(X).
Последовательные (линейные) структуры
Рассмотрим последовательность двух блоков g={(X,Y)} и
h={(Y,Z)}, изображенную на рис.2.1. Программная функция такой

*

Дал У., Дейкстра Э., Хоор К. Структурное программирование. – М: Мир, 1975.

X

p=
Рис.2.1.

Y

g

112

Z

h

последовательности является композицией h°g двух частных
функций h и g: [P]={(X,Z)⎥ Z=h(g(X))}.
Пример 2.13. Задана программа в виде последовательности операторов
присваивания на алгоритмическом языке PASCAL (рис.2.2). Требуется
определить функцию, реализуемую этим алгоритмом.
Рассмотрим поле данных (x,y,z), которое используется в данной
программе. Начальное значение поля данных (x0,y0,z0).
Процесс прослеживания состояния
x:= y + z; y:= x - z; z:= -x + y; поля данных после выполнения каждого
Рис.2.2.
оператора называется трассировкой. Его
удобно представить таблицей 2.1.
Таблица 2.1

Оператор

x

y

z

x:=y+z

x1=y0+ z0

y1=y0

z1=z0

y:=x-z

x2=x1

y2=x1-z1

z2=z1

z:=-x+y

x3=x2

y3=y2

z3=-x2+y2

После выполнения первого оператора присваивания первоначальное значение
x0 стирается и заменяется новым значением, x1=y0+z0, причем значения y и z не
меняются, т.е. y1=y0, z1=z0. После выполнения второго оператора присваивания
получаем:
x2 = x1= y0 + z0,
y2 = x1 - z1 = y0 + z0 - z0 = y0,
z2 = z1 = z0 .
После выполнения третьего оператора присваивания получаем:
x3= x2 = x1 = y0 + z0,
y3 =y2 = y0,
z3 = -x2 + y2 = -y0 -z0 + y0 = -z0.
Таким образом, функцию реализуемую алгоритмом, можно представить
как одновременное присваивание (x,y,z):= (y0+z0 , y0 , -z0) , в результате
которого первоначальное значение поля данных (x0,y0,z0) изменится на (y0+z0 ,
y0 , -z0).

113

Структуры с ветвлениями
Для программы с ветвлениями все возможные пути выполнения
определяются так называемым деревом выполнения (E-деревом).

f
X
p=

s

1

q

g

1
0

Y

0

h

r

1
0

Рис. 2.3.

Пример 2.14. Рассмотрим блок-схему программы на рис.2.3. Эта
программа имеет дерево выполнения, представленное на рис.2.4. Условия
ветвления выражаются предикатами s, q, r. Программная функция программы с
ветвлениями без циклов определяется как объединение композиций
программных функций, которые получаются непосредственно из E-дерева.
Необходимое и достаточное условие выполнения конкретной ветви
определяется композицией каждого предиката с предшествующей функцией
пути.
В рассматриваемом примере имеется пять путей выполнения,
пронумерованных как показано на рис. 2.4. Выпишем программную функцию
каждого пути:
1.

{(X,Y): s(X) & q(f(X)) & Y=g(f(X))}.

2.

{(X,Y): s(X) & ⎤ q(f(X)) & r(h(f(X))) & Y=g(h(f(X)))}.

3.

{(X,Y): s(X) & ⎤ q(f(X)) & ⎤ r(h(f(X))) & Y=h(f(X))}.

4.

{(X,Y): ⎤ s(X) & r(h(X)) & Y=g(h(X))}.

5.

{(X,Y): ⎤ s(X) & ⎤ r(h(X)) & Y=h(X)}.

114

f

1

q

0

1

h
s

g

1

g

2

r

0

3

1

g

0

h

1

4

r

0
Рис.2.4.

5

Результирующая программная функция может быть определена как условное
правило:
[P]={(X,Y) ⎥ s(X) & q(f(X)) → Y=g(f(X));
s(X) & ⎤ (q( f(X) )& r(h(f(X)))→ Y=g(h( f(X)));
s(X) & ⎤ (q(f(X))) & ⎤ (r(h(f(X)))) → Y=h(f(X));
⎤ s(X) & r(h(X))→ Y=g(h(X));

⎯⎤ s(X) &⎤ (r(h(X))) → Y=h(X)}.
Пример 2.15. Задан алгоритм с использованием операторов ветвления
(Рис.2.5).

IF x