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

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

УЧЕБНИК

Москва
КУРС
ИНФРА-М
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 находится в СДНФ (СКНФ), если выполняются сле-
дующие условия: