Математическая логика и теория алгоритмов

А.В. ПРУЦКОВ, Л.Л. ВОЛКОВА

УЧЕБНИК

Москва
КУРС
ИНФРА-М
2023

МАТЕМАТИЧЕСКАЯ
ЛОГИКА
И ТЕОРИЯ АЛГОРИТМОВ

Рекомендовано 
Научно-методическим советом Федерального 
государственного бюджетного образовательного учреждения 
высшего образования «Рязанский государственный 
радиотехнический университет» в качестве учебника 
для студентов высших учебных заведений, 
обучающихся по направлению подготовки 
2.09.03.04 «Программная инженерия» (квалификация “Бакалавр”)

УДК 51(075.8)
ББК 22.12я73
 
П 85

© А.В. Пруцков, 
 
Л.Л. Волкова, 2016
© КУРС, 2016

Пруцков А.В., Волкова Л.Л.
Математическая логика и теория алгоритмов: учебник / 
А.В. Пруцков, Л.Л. Волкова. — Москва: КУРС: ИНФРА-М, 
2023. — 152 с.

ISBN 978-5-906818-74-4 (КУРС)
ISBN 978-5-16-012180-2 (ИНФРА-М, print)
ISBN 978-5-16-105018-7 (ИНФРА-М, online)

Учебник представляет собой готовое решение для методического обеспечения дисциплины «Математическая логика и теория алгоритмов». В учебник 
включены лекции, практические задания и вопросы к экзамену, подготовленные за десятилетнее преподавание этой дисциплины в высших и средних 
учебных заведениях. 
Учебник подготовлен для студентов учреждений высшего профессионального образования по направлениям подготовки «Прикладная информатика» 
и «Программная инженерия», и полностью соответствует Федеральным Государственным образовательным стандартам по данным направлениям.

УДК 51(075.8)
ББК 22.12я73

П58

Р е ц е н з е н т ы:
А.Н. Пылькин — д-р техн. наук, профессор, декан факультета вычислительной 
техники Рязанского государственного радиотехнического университета;
А.Е. Кузнецов — д-р техн. наук, профессор, заместитель директора НИИ 
обработки аэрокосмических изображений «Фотон» (г. Рязань)

ISBN 978-5-906818-74-4 (КУРС)
ISBN 978-5-16-012180-2 (ИНФРА-М, print)
ISBN 978-5-16-105018-7 (ИНФРА-М, online)

ФЗ 
№ 436-ФЗ
Издание не подлежит маркировке 
в соответствии с п. 1 ч. 4 ст. 11

Предисловие

Учебник составлен из лекций и практических заданий, которые 
автор использовал для преподавания одноименной дисциплины на 
протяжении более десяти лет. Курс преподавался студентам технических специальностей и направлений, связанных с программированием, как очной, так и заочной форм обучения: 230101 — «Вычислительные машины, комплексы, системы и сети», 230104 — «Системы автоматизированного проектирования», 230105 — «Программное 
обеспечение вычислительной техники и автоматизированных систем», 
230106 — «Применение и эксплуатация автоматизированных систем 
специального назначения», 230700 — «Прикладная информатика», 
231000 — «Программная инженерия» в высших и средних учебных 
заведениях. Номера специальностей и направлений приводятся такими, какими они были на момент чтения лекций по данным дисциплинам. За это время автором были изданы учебное пособие [40] и методические указания к практическим занятиям и контрольным работам 
[37, 39, 42], материалы которых были включены в этот учебник. Часть 
материалов лекций, посвященных основам логики высказываний, 
были уже изданы в учебнике [16].
Как и название дисциплины, учебник разделен на две части: 
часть, посвященную математической логике, и часть, посвященную 
теории алгоритмов. В первой части большое внимание уделено классическим логикам: логике высказываний, логике предикатов и связанными с ними темами. Широкое использование неклассических 
логик (главным образом, нечетких) делает их актуальными, поэтому 
этому типу логик посвящено несколько разделов первой части. Во 
второй части рассматриваются различные подходы к описанию алгоритмических моделей, способы сравнения алгоритмов и классификация алгоритмов по трудоемкости. Изложение материала сознательно упрощено, чтобы сделать его более понятным для неподготовленного читателя. Некоторые разделы математической логики и 
теории алгоритмов, не имеющие, по мнению автора, большого значения, опущены.
Во время предподавания дисциплины «Математическая логика и 
теория алгоритмов» автор учебника следил за выходом новинок по 
этой теме и на их основе улучшал курс. Основу материала этого учебника составила книга А.К. Гуца [10]. Достоинствами этой книги является простота изложения разделов математической логики и теории алгоритмов, особенно неклассических логик. Также большое 
влияние на содержание лекций этого учебника оказала книга 
В.А. Мощенского [29]. Раздел, посвященный логической модели 

представления знаний, основан на лекциях С.П. Хабаров а, размещенных в сети Интернет.
Каждая тема имеет примерно одну структуру: минимальный теоретический материал, необходимый для ее освоения, и один или несколько поясняющих примеров. Конец примера обозначается символом . Конец доказательства теоремы обозначается символом .
Наиболее важные темы в рамках этого курса снабжены практическими заданиями различной сложности. Это позволяет проводить 
практики по этому курсу, постепенно усложняя материал.
Материалы учебника содержат вопросы, которые автор обычно 
задавал студентам на лекциях. Надеюсь, что они покажутся читателю 
интересными. Ответы на вопросы приведены в соответствующем 
разделе на странице 193.
Библиографический список организован следующим образом. 
В начале идут публикации на русском языке, затем — на иностранных языках, и в конце — список Интернет-ресурсов. Список имеет 
сплошную нумерацию.

Глава 1.
МАТЕМАТИЧЕСКАЯ ЛОГИКА

1.1. МАТЕМАТИЧЕСКАЯ ЛОГИКА 
И ПРЕДМЕТ ЕЕ ИЗУЧЕНИЯ

Математическая логика — это наука о формах и способах мышления, их математическом представлении и операциях над ними.
Существуют три формы мышления:
1) понятие;
2) высказывание;
3) умозаключение.
Понятие выделяет существенные признаки объекта, которые отличают его от других объектов. Объекты, объединенные понятием, 
образуют множество. Например, понятие «компьютер» объединяет 
множество электронных устройств, предназначенных для обработки 
информации. Это понятие трудно спутать с понятием «автомобиль».
Понятие имеет две характеристики:
1) содержание;
2) объем.
Содержание понятия составляет совокупность существенных признаков объекта. Например, содержание понятия «персональный 
компьютер» можно раскрыть так: «Это универсальное электронное 
устройство для обработки информации, предназначенное для одного пользователя».
Объем понятия «персональный компьютер» выражает всю совокупность (сотни миллионов) существующих в настоящее время в 
мире персональных компьютеров.
Высказывание (суждение, утверждение) строится на основе понятий 
и по форме является повествовательным предложением, например 
высказывание R – «Сегодня ясно». В высказывании утверждаются или 
отрицаются свойства реальных предметов и отношения между ними. 
Поэтому высказывание может быть истинным или ложным.
Истинным будет высказывание, в котором связь понятий правильно отражает свойства и отношения реальных вещей, например: 
«Москва — столица России».
Ложным высказывание будет в том случае, когда оно не соответствует действительности, например: «Париж — столица США».
Умозаключение позволяет из известных фактов (истинных высказываний) получать заключение, т.е. новый факт.

Например, из факта «Все углы треугольника равны» можно вывести истинность высказывания «Этот треугольник равносторо нний».
Математическую логику можно подразделить на классическую и 
неклассическую.
В классической логике высказывания принимают одно из двух логических значений: 1 («истина») и 0 («ложь»).
К классической логике относят логику высказываний и логику 
предикатов.
Основной особенностью неклассической логики является то, что в 
ней не выполняется закон «исключения третьего»:

╞ (A  A ),

где ╞ — символ общезначимости, т.е. выражение истинно при любом 
значении высказывания A; «» — операция дизъюнкции (логического сложения).
Следовательно, в неклассической логике высказывание A может 
принимать другие значения, отличные от значений «истина» и 
«ложь».
К неклассическим логикам относят:
• нечеткую логику;
• модальные логики;
• временны´е логики;
• алгоритмические логики.
Неклассические логики предназначены для расширения возможностей описания высказываний и введения новых операций над 
ними.

1.2. ЛОГИКА ВЫСКАЗЫВАНИЙ

1.2.1. Введение в логику высказываний

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

Логика высказываний — это раздел математической логики, изучающий высказывания, операции над ними и их свойства.
Логические операции можно разделить на основные и вспомогательные.
Основные логические операции:
1) логическое отрицание, обозначаемое как A  (другие обозначения: ¬A,  ~ A) (читается «не A»), — это высказывание, которое истинно, если A ложно, и ложно, если A истинно.
2) конъюнкция (логическое умножение) AB (A&B, AB, AB) 
(«A и B») — это высказывание, которое истинно только в том случае, 
если A истинно и B истинно;

3) дизъюнкция (логическая сумма) A  B (AB) («A или B, или 
оба») — это высказывание, которое ложно только в том случае, если 
A ложно и B ложно.
Вспомогательные логические операции:
1) импликация (следование) AB (A B) («A влечет B», «если A, 
то B») — это высказывание, которое ложно только в том случае, если 
A истинно и B ложно;
2) эквивалентность A ~ B (A B, A B) («A эквивалентно B») — 
это высказывание, которое истинно только тогда, когда A и B оба 
истинны или оба ложны.
От вспомогательных операций можно перейти к основным по 
следующим равносильным формулам:
• от импликации:

 
XY  X  Y; 
(1.18)

• от эквивалентности:

 
X ~ Y  XY X
_
Y
_
  ( X   Y)(X  Y
_
). 
(1.19)

Эти и другие пронумерованные равносильные формулы приведены в разделе 1.2.10 «Равносильные формулы логики высказываний».

1.2.1.2. Соглашение о расстановке скобок

Введем соглашение о расстановке скобок, основанное на порядке выполнения логических операций. Соглашение позволит избежать двусмысленности в случае, если все или часть скобок в формуле опущены.
Приоритет логических операций (в порядке убывания):
1) эквивалентность;
2) импликация;
3) дизъюнкция;
4) конъюнкция;
5) отрицание.
Будем использовать следующий порядок выполнения логических 
операций:
1) выбирается последовательно слева направо операция с максимальным приоритетом;
2) выбранная операция имеет область действия, которую ограничивают только скобки и границы формулы.
Из порядка выполнения логических операций следует, что каждые следующие скобки ставятся внутри или в стороне от существующих скобок, но никогда не снаружи.
Пример 1.1. Расставить скобки:
1) 
A ~ BC  D ~ E 
A ~ ((B(C  D)) ~ E);

2) 
A  B ~ CD ·E 
(A  B) ~ (C(D · E));
3) 
A  B · CDE 
(A  (B · C))(DE);
4) 
AB ~ CDE 
(AB) ~ (C(DE)). 
Данное правило несколько отличается от широко распространенного, но, по мнению авторов, имеет более простую формулировку.

1.2.2. Способы представления логических формул

Логическая формула, включающая переменные X1, X2, …, Xn, — 
это n-арная операция на множестве [0; 1]. Существует 2n различных 
наборов значений переменных, на которых формула принимает значения 0 или 1.
Операции отрицание, конъюнкция и дизъюнкция можно рассмат ривать как логические формулы от двух переменных.
Набор логических операций, с помощью которого можно представить (выразить) все логические формулы, называется функционально-полным или базисом. Основными базисами являются:
1) булевый базис, состоящий из конъюнкции, дизъюнкции и отрицания;
2) базис NOR, состоящий из стрелки Пирса;
3) базис NAND, включающий штрих Шеффера.
В настоящем учебнике используется только булевый базис.
Логическая формула может быть записана одним из следующих 
способов:
• аналитическим — формула задается в виде алгебраического выражения, состоящего из операций одного или нескольких базисов, 
применяемых к логическим переменным;
• табличным — формула задается в виде таблицы истинности (соответствия), которая содержит 2n строк (по числу наборов аргументов), n столбцов по числу переменных и один столбец значений функции. В такой таблице каждому набору аргументов соответствует значение на них формулы;
• числовым — формула задается в виде десятичных (восьмеричных, 
шестнадцатеричных) эквивалентов номеров тех наборов аргументов, на которых функция принимает значение 1. Нумерация наборов начинается с нуля. Аналогичным образом логическая формула может быть задана по нулевым значениям.
Пример 1.2. Формула задана аналитически:

 
(
) (
)
Y
Z X Y
Z
+
+
  Y
Z
+
.

Записать формулу в табличном и числовом представлениях.
Решение. Переход к другому представлению возможен и в таком 
виде. Однако лучше преобразовать формулу, чтобы упростить процесс перехода к другому представлению.

Опустим отрицание до переменных по законам де Моргана (1.8)–
(1.9):

(
) (
)
Y
Z X Y
Z
+
+
  Y
Z
+
  Y Z  X YZ– Y–Z.

Сократим одинаковые слагаемые по формуле (1.10) и перегруппируем их:

Y–Z  X  YZ–  Y–Z   X YZ–   Y–Z .

По полученному выражению построим таблицу истинности, каждая строка которой состоит из набора значений переменных и значения формулы (табл. 1.1).

Таблица 1.1

Номер набора
X
Y
Z
f(X, Y, Z)  X  YZ–  Y–Z

0
0
0
0
0
1
0
0
1
1
2
0
1
0
1
3
0
1
1
0
4
1
0
0
1
5
1
0
1
1
6
1
1
0
1
7
1
1
1
1

Чтобы записать числовое представление формулы, необходимо 
выписать номера наборов, на которых формула принимает значение 
1: 1, 2, 4, 5, 6, 7, и номера наборов, на которых формула принимает 
значение 0: 0, 3.
Тогда формула X  YZ–  Y–Z имеет два числовых представления. 
В первом случае перечисляются все наборы, на которых формула 
принимает зачение 1:

f(1, 2, 4, 5, 6, 7)  1.

Во втором — перечисляются все наборы, на которых формула 
равна 0:
f(0, 3)  0.
Все три перечисленных представ ления эквивалентны и описывают одну формулу. 

1.2.3. Нормальные формы логики высказываний

1.2.3.1. Простые нормальные формы

Чтобы определить, равносильны ли формулы (являются ли формулы тождественными), необходимо привести их к нормальной фор

ме. В логике высказываний существуют простые нормальные формы: 
конъюнктивная нормальная форма (КНФ) и дизъюнктивная нормальная форма (ДНФ), а также совершенные конъюнктивная и дизъюнктивная нормальные формы (СКНФ и СДНФ соответственно).
Обязательными требованиями пребывания формулы в любой 
нормальной форме являются следующие:
1) в формуле присутствуют только основные логические операции;
2) отрицание относится только к элементарным высказываниям.
Формулы вида X1 · X2 · … · Xn и X1  X2  …  Xn, где X1, X2, …, Xn — элементарные высказывания, называются соответственно элементарной 
конъюнкцией и элементарной дизъюнкцией. Элементарные конъюнкции (дизъюнкции), в которых каждая переменная имеет не более 
одного вхождения с отрицанием или без, называются конъюнктами 
(дизъюнктами).
КНФ — это конъюнкция конечного числа элементарных дизъюнкций (произведение сумм).
ДНФ — это дизъюнкция конечного числа элементарных конъюнкций (сумма произведений).
Пример 1.3. Определить, к какой простой форме относятся формулы:
1) A  B · C — ДНФ;
2) (A  B) · C — КНФ;
3) (A  B)C — не является нормальной формой, потому что в 
формуле присутствуют вспомогательные логические операции;
4) (A  BC)D — не является нормальной формой, потому что 
A  BC не является элементарной дизъюнкцией.
Формулы, которые не находятся ни в одной нормальной форме, 
можно привести к нормальным формам с помощью преобразований. 
Теорема 1.1. Для любой формулы A существует равносильная формула B, находящаяся в КНФ (ДНФ), и причем не одна.
Для любой формулы существует множество равносильных формул, находящихся в одной из простых нормальных форм. Поэтому 
необходимо приводить формулы к таким КНФ и ДНФ, которые 
нельзя упростить далее с помощью равносильных формул и элементарных поглощений.

1.2.3.2. Совершенные нормальные формы

В отличие от простых нормальных форм совершенные формы 
обладают свойством единственности.
Формула A находится в СДНФ (СКНФ), если выполняются следующие условия: