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

Изложены темы, традиционно изучаемые в курсе 
математической логики и теории алгоритмов: алгебра логики и исчисление высказываний, логика 
и исчисление предикатов, формальные аксиоматические теории, теория алгоритмов и теория вычислительной сложности.

Ю. В. Вайнштейн, Т. Г. Пенькова, В. И. Вайнштейн

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

Учебное пособие

ИНСТИТУТ КОСМИЧЕСКИХ  
И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

Министерство науки и высшего образования Российской Федерации 
Сибирский федеральный университет 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Ю. В. Вайнштейн, Т. Г. Пенькова, В. И. Вайнштейн 

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

 
 
Учебное пособие 
 
 
 
 
 
 
 
 
 
 
 
 
Красноярск 
СФУ 
2019 

УДК 510.6(07) 
ББК 22.122я73 
В145 
 
Р е ц е н з е н т ы : 
Л. Ф. Ноженкова, доктор технических наук, профессор, зав. отделом прикладной информатики Института вычислительного моделирования СО РАН; 
Г. М. Рудакова, кандидат физико-математических наук, профессор кафедры информационно-управляющих систем Сибирского государственного университета науки и технологий имени академика 
М. Ф. Решетнева 
 
 
 
 
 
 
 
Вайнштейн, Ю. В. 
В145 
 
Математическая логика и теория алгоритмов : учеб. пособие / Ю. В. Вайнштейн, Т. Г. Пенькова, В. И. Вайнштейн. – 
Красноярск : Сиб. федер. ун-т, 2019. – 110 с. 
ISBN 978-5-7638-4076-6 
 
Изложены темы, традиционно изучаемые в курсе математической логики и теории алгоритмов: алгебра логики и исчисление высказываний, логика 
и исчисление предикатов, формальные аксиоматические теории, теория алгоритмов и теория вычислительной сложности. 
Предназначено для студентов направления подготовки 09.03.04 «Программная инженерия». Также будет полезно студентам направлений 
09.03.02 «Информационные системы и технологии», 27.03.03 «Системный 
анализ и управление». 
 
Электронный вариант издания см.: 
УДК 510.6(07) 
http://catalog.sfu-kras.ru 
ББК 22.122я73 
 
 
 
 
 
ISBN 978-5-7638-4076-6 
© Сибирский федеральный 
университет, 2019 

Оглавление 

3 

ОГЛАВЛЕНИЕ 

 
 
Введение ...............................................................................................  
4 
 
1. Алгебра логики ...............................................................................  
6 
1.1. Введение в алгебру логики ...........................................................  
6 
1.2. Формулы алгебры логики .............................................................  21 
1.3. Законы алгебры логики .................................................................  29 
1.4. Стандартные формы представления   
формул алгебры логики ................................................................  33 
1.5. Функционально полные системы  
элементарных булевых функций ..................................................  39 
Практические задания ..........................................................................  47 
 
2. Формальные теории .......................................................................  59 
2.1. Исчисление высказываний как формальная теория ...................  59 
2.2. Исчисление предикатов  как формальная теория .......................  65 
2.3. Автоматическое доказательство теорем.  
Принцип резолюций ......................................................................  74 
Практические задания ..........................................................................  80 
 
3. Теория алгоритмов ........................................................................  88 
3.1. Основные понятия теории алгоритмов ........................................  88 
3.2. Машина Тьюринга .........................................................................  92 
3.3. Вычислимые по Тьюрингу функции ...........................................  96 
Практические задания ..........................................................................  98 
 
Заключение ..........................................................................................  107 
 
Библиографический список .............................................................  108 
 
 

Введение 

4 

ВВЕДЕНИЕ 

 
 
Дисциплина «Математическая логика и теория алгоритмов» 
изучает алгебру логики и исчисление высказываний, логику и исчисление предикатов, формальные аксиоматические теории, а также основные понятия теории алгоритмов и теории вычислительной сложности. 
В учебном плане образовательной программы 09.03.04 «Программная инженерия» СФУ дисциплина «Математическая логика 
и теория алгоритмов» обеспечивает освоение общепрофессиональных 
компетенций: ОПК-1 «Владение основными концепциями, принципами, теориями и фактами, связанными с информатикой»; ДОПК-1 
«Способность использовать основные законы естественно-научных 
дисциплин в профессиональной деятельности». Таким образом, курс 
позволяет формировать математическую и информационную культуру студента, обеспечивает приобретение систематизированных знаний, умений и навыков в области математической логики и теории алгоритмов, изучения ее основных методов, механизмов их развития 
и применения для решения научных и практических задач в области 
будущей профессиональной деятельности. 
В результате изучения дисциплины студент должен знать специальную терминологию, которая является частью языка современной математики, основы логики высказываний, логики предикатов, 
теории алгоритмов и теории вычислительной сложности алгоритмов, 
принципы построения формальных теорий, способы применения логических функций. Также студент должен уметь проводить формально-логические построения на основе теории и формул математической логики, строить доказательства теорем в классических теориях 
исчисления высказываний и предикатов, строить и анализировать алгоритмы для решения прикладных задач. Кроме того, студент должен 
получить практические навыки использования языка математической 
логики для представления знаний о предметных областях, построения 
математических теорий как аксиоматических теорий и интерпретации 
формул теории и её моделей.  
Логика известна человечеству с древнейших времён и представляет собой искусство правильно рассуждать. Термин «логика» (от греч. 
logos) означает рассуждение, слово, понятие, разум. Признанным ос

Введение 

5 

нователем науки о логике является древнегреческий философ Аристотель, заложивший теоретически основы логики как науки. Основная 
функция логики состоит в построении последовательности вывода одних утверждений из других, т. е. в выявлении формальных условий 
правильного мышления. На протяжении истории сфера конкретных 
интересов логики существенно менялась. Существует логика неформальная, формальная, диалектическая, логика исследования и др.  
В учебном пособии представлены разделы, классически отнесенные к формальной, а именно математической логике: алгебра логики, формальные аксиоматические теории и теория алгоритмов. 
В первой главе рассмотрены формулы алгебры логики, законы алгебры логики, стандартные формы представления формул алгебры логики и функционально полные системы элементарных булевых функций. Во второй главе представлены классические исчисления математической логики: исчисление высказываний и исчисление предикатов, 
а также метод резолюций для автоматического доказательства теорем. 
Последняя глава курса посвящена теории алгоритмов. В ней представлена одна из моделей алгоритмов – машина Тьюринга, а также затронуты вопросы оценки вычислительной сложности алгоритмов. 
В конце каждой главы приведены практические задачи. Также пособие снабжено библиографическим списком. 
Настоящее учебное пособие главным образом предназначено 
для студентов, изучающих математическую логику и теорию алгоритмов, имеющих базовую подготовку по дискретной математике, 
математическому анализу, информатике и программированию.  
В дополнение к материалу, изложенному в первой главе пособия, 
рекомендуется ознакомиться с основными понятиями, изучить принятую в области алгебры логики терминологию, рассмотреть основные 
приложения алгебры высказываний к логико-математической практике 
[2; 4; 8; 12; 15; 19; 21; 22]. Для получения более подробной информации о формальных теориях рекомендуется обратиться к источникам [5; 
11; 15; 20; 24]. Подробнее познакомиться с теорией вычислимых 
функций и конкретными вычислимыми моделями (машина Тьюринга 
и вычислимые функции) можно в [6; 9; 13; 14; 17; 25; 26]. Для активного самостоятельного решения задач по математической логике и теории алгоритмов рекомендуется использовать задачники [3; 7; 10; 16].  
 
 

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

6 

1. АЛГЕБРА ЛОГИКИ 

1.1. Введение в алгебру логики 

 
Рассмотрим двухэлементное множество B и двоичные переменные, принимающие значения из B. Его элементы часто обозначают 0 
и 1, однако они не являются числами в обычном смысле. Наиболее 
распространенная интерпретация двоичных переменных: «да» – 
«нет», «истинно» (И) – «ложно» (Л). Поэтому будем считать, что 
B = {0, 1}, рассматривая 0 и 1 как некоторые формальные символы. 
Алгебра, образованная двухэлементным множеством B = {0, 1} 
вместе со всеми возможными операциями на нем, называется алгеброй логики.  
Функцией 
алгебры 
логики 
(логической 
функцией) 
от 
nпеременных называется n-арная операция на множестве {0, 1}. Логическая функция f (x1, x2, x3, …, xn) – это функция, принимающая значения 0, 1. Множество всех логических функций обозначается P2, множество всех логических функций n переменных – P2 (n). 
Исходным понятием математической логики является «высказывание». Высказыванием называется повествовательное предложение, о котором можно сказать в данный момент, что оно истинно или 
ложно, но не то и другое одновременно. Логическим значением высказывания являются «истина» или «ложь».  
 
Пример 
Повествовательное предложение «3 – это простое число» является истинным высказыванием, а «3,14… – рациональное число» – 
ложным; «Юго-восточный берег озера Виви является географическим 
центром России» – истинным, а «Красноярск – столица России» – 
ложным, «Число 8 делится на 2 и на 4» – истинным, а «Сумма чисел 2 
и 3 равна 8» – ложным и т. п. 
Такие высказывания называют простыми, или элементарными. 
При формальном исследовании сложных текстов понятие «простые 
высказывания» замещают понятием «пропозициональные переменные» (от лат. propositio – предложение), которое обозначают прописными буквами латинского алфавита «A», «B», «C» и т. д. 
«Истинность» или «ложность» предложения есть истинностное значение высказывания. Каждому высказыванию сопоставляется 

1. Алгебра логики 

7 

переменная, равная 1, если высказывание истинно, и равная 0, если 
высказывание ложно. 
 
Пример 
1. Если A:= «3 – это простое число», то A = 1. 
2. Если B:= «Красноярск – столица России», то B = 0. 
3. Если C:= «Москву основал Юрий Долгорукий», то C = 1. 
4. Если D:= «В прямоугольном треугольнике квадрат гипотенузы равен сумме квадратов катетов», то D = 1. 
5. Если E:= «2  2 = 5», то E = 0. 
Следующие утверждения не являются высказываниями. 
1. a + b = 2. 
2. Математика – интересный предмет. 
П р и м е ч а н и е : символ «:=» означает, что пропозициональной 
переменной, стоящей слева, необходимо присвоить значение высказывания, стоящего справа от символа. 
Высказывания, которые получаются из простых предложений 
с помощью грамматических связок «не», «и», «или», «если…, то…», 
«… тогда и только тогда, когда…» и т. п., называют сложными, или 
составными. Для обозначения грамматических связок вводят символы, которые называют логическими (или пропозициональными) связками.  
Обычно рассматривают следующие логические связки: 
отрицание (читается «НЕ», обозначается «»),  
конъюнкция (читается «И», обозначается «»),  
дизъюнкция (читается «ИЛИ», обозначается «»), 
импликация (читается «ЕСЛИ… ТО…», обозначается «»), 
эквивалентность (читается «…ТОГДА И ТОЛЬКО ТОГДА, 
КОГДА…», обозначается «»). 
Для построения сложных пропозициональных высказываний 
используют вспомогательные символы «(»,«)» – скобки. 
 
Пример 
Если A1:= «3 – вещественное число», то A1 = 1. 
Если A2:= «3 – целое число», то A2 = 1. 
Если высказывание «3 – вещественное или целое число», то его 
формула записывается (A1  A2) = 1. 
Правила построения сложных высказываний в виде последовательности пропозициональных переменных, логических связок 

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

8 

и вспомогательных символов определяют возможность формального 
описания любого текста. При этом высказывания, из которых делают 
вывод новых высказываний, называют посылками, а получаемое высказывание – заключением.  
Множество пропозициональных переменных T = {A, B, C, …} 
с заданными над ними логическими операциями F = {; ; ; ; } 
формируют алгебру высказываний, т. е. Aв = T; F. 
 
Логические операции 
Из простых высказываний с помощью операций над высказываниями или логических операций (связок) строят сложные высказывания, т. е. логические операции в логике представляют собой действия, 
образующие новые понятия на основе существующих. Рассмотрим 
следующие логические операции: конъюнкция, дизъюнкция, инверсия, импликация и эквивалентность. 
Отрицанием высказывания А называется высказывание А (читается: «не А» или «неверно, что A»), которое истинно тогда и только 
тогда, когда высказывание А ложно. Чтобы составить отрицание А 
достаточно в разговорном языке сказать «неверно, что А». 
 
Пример 
А := «Каспаров – чемпион мира по шахматам». 
А := «Неверно, что Каспаров – чемпион мира по шахматам». 
Отрицание высказывания А будем обозначать ¬А или A. Высказывание A истинно, если высказывание А ложно, и ложно, если А истинно. Другими словами, логическое значение высказывания A связано с логическим значением высказывания А, как указано в табл. 1, 
называемой таблицей истинности операции отрицания. 
 
Таблица 1 
 
А 
A

0 
1 

1 
0 

 
Определение отрицания с помощью приведенной таблицы 
(и других логических операций с помощью таблиц истинности) появилось как результат длительного опыта и полностью оправдало себя 
на практике. 

1. Алгебра логики 

9 

Конъюнкцией высказываний А и B называется высказывание 
А  B, или А & B (читается: «А и В»), истинное тогда и только тогда, 
когда истинны оба высказывания А и B. В разговорной речи конъюнкции соответствует союз «И».  
 
Пример 
А := «Треугольник прямоугольный». 
B := «Треугольник равнобедренный». 
А  B := «Треугольник прямоугольный и равнобедренный». 
Логическое значение конъюнкции указано в табл. 2. 
 
Таблица 2 
 
А 
B 
А  B 

0 
0 
0 

0 
1 
0 

1 
0 
0 

1 
1 
1 

 
Практика полностью подтвердила, что именно такое распределение значений истинности наиболее соответствует тому смыслу, который придается в процессе мыслительной деятельности связующему 
союзу «и». 
Дизъюнкцией высказываний А и B называется высказывание 
А  B (читается: «А или В»), ложное тогда и только тогда, когда ложны оба высказывания А и B. В разговорной речи конъюнкции соответствует союз «ИЛИ». 
 
Пример 
А := «Петров программист». 
B := «Петров филолог». 
А  B := «Петров программист или филолог». 
Логическое значение дизъюнкции указано в табл. 3. 
 
Таблица 3 
 
А 
B 
А  B 

0 
0 
0 

0 
1 
1 

1 
0 
1 

1 
1 
1 

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

10 

Импликацией высказываний А и B называется высказывание 
А  B (читается: «А влечет за собой B» или «из А следует B», или «если 
А, то B»), ложное тогда и только тогда, когда А истинно, а B ложно.  
 
Пример 
А := «Треугольник равносторонний». 
B := «В треугольнике все углы равны». 
А  B := «Если треугольник равносторонний, то все углы равны». 
Логическое значение высказывания А  B связано с логическим 
значением высказываний А и В, как указано в табл. 4. 
 
Таблица 4 
 
А 
B 
А  B 

0 
0 
1 

0 
1 
1 

1 
0 
0 

1 
1 
1 

 
В высказывании А  B высказывание А называется посылкой, 
или антецедентом, а B – следствием, или консеквентом. Импликация 
призвана отразить процесс рассуждения, умозаключения. Общая характеристика этого процесса следующая: если мы исходим из истинной посылки и правильно (верно) рассуждаем, то мы приходим к истинному заключению (следствию, выводу). Другими словами, если 
мы исходили из истинной посылки и пришли к ложному выводу, значит, рассуждение построено неверно. Это обосновывает результаты: 
1  0 = 0 и 1  1 = 1. Первые две строки табл. 4 обосновываются 
практическими примерами. 
Импликация играет важную роль в логике высказываний. При 
учете смыслового содержания высказывания (а не только значений истинности), оборот «если, то» подразумевает причинно-следственную 
связь. Истинность импликации означает лишь то, что если истинна 
посылка, то истинно и заключение. При ложной посылке заключение 
всегда истинно.  
 
Пример 
Рассмотрим четыре высказывания: 
A := «Дважды два четыре» = 1; 
B := «Дважды два пять» = 0;