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

Кратко изложен теоретический материал по 
дисциплине «Математическая логика и теория 
алгоритмов», приведены примеры решения типовых задач, представлены задачи различной 
сложности для решения на практических занятиях и самостоятельной работы. 

Г. Е. Михальченко

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

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

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

 

Министерство науки и высшего образования Российской Федерации 
Сибирский федеральный университет 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Г. Е. Михальченко 
 
 
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ  
АЛГОРИТМОВ 
 
 
Учебное пособие 
 
 
 
 
 
 
 
 
 
 
 
 
 
Красноярск 
СФУ 
2018 

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

Алгебра высказываний 

3 

ОГЛАВЛЕНИЕ 
 
 
Введение ..........................................................................................................  4 
Глава 1. Алгебра высказываний ................................................................  5 
1.1. Высказывания и операции с ними ..........................................................  5 
1.2. Формулы алгебры высказываний ...........................................................  7 
1.3. Отношения логического следования и равносильности ......................  9 
1.4. Свойства операций с высказываниями ..................................................  12 
1.5. Нормальные формы формул алгебры высказываний ...........................  13 
Задачи к главе 1. Алгебра высказываний .....................................................  19 
 
Глава 2. Булевы функции ............................................................................  23 
2.1. Определение и свойства булевых функций ...........................................  23 
2.2. Нормальные формы булевых функций ..................................................  25 
2.3. Классы функций, сохраняющих постоянные (P0, P1) ...........................  26 
2.4. Класс самодвойственных функций (S) ...................................................  26 
2.5. Алгебра и полином Жегалкина ...............................................................  28 
2.6. Класс линейных функций (L) ..................................................................  30 
2.7. Класс монотонных функций (M) ............................................................  32 
2.8. Полнота систем булевых функций .........................................................  34 
2.9. Булевы функции и релейно-контактные схемы ....................................  38 
2.10. Релейно-контактные схемы в ЭВМ ......................................................  41 
Задачи к главе 2. Булевы функции ................................................................  44 
 
Глава 3. Логика предикатов .......................................................................  48 
3.1. Понятие предиката. Множество истинности предиката.   
Виды предикатов .............................................................................................  48 
3.2. Операции над предикатами и их свойства ............................................  49 
3.3. Формулы логики предикатов и их виды ................................................  52 
3.4. Равносильность формул логики предикатов .........................................  53 
3.5. Нормальные формы формул логики предикатов ..................................  55 
3.6. Логическое следование формул. Правило резолюций .........................  57 
Задачи к главе 3. Логика предикатов ............................................................  58 
 
Глава 4. Элементы теории алгоритмов ....................................................  62 
4.1. Машины Тьюринга ...................................................................................  62 
4.2. Рекурсивные функции .............................................................................  66 
Задачи к главе 4. Машины Тьюринга ............................................................  69 
 
Заключение .....................................................................................................  72 
Библиографический список ........................................................................  73 
 

ВВЕДЕНИЕ 
 
 
Математическая логика, как и классическая, исследует процессы 
умозаключений и позволяет из истинности одних суждений делать выводы 
об истинности или ложности других независимо от их конкретного содержания. Использование в логике математических методов (алгебраизация 
логики и построение логических исчислений) стало началом развития математической логики – новой области математики. Основная задача математической логики – это формализация знаний и рассуждений. Математика 
является наукой, в которой все утверждения доказываются с помощью 
умозаключений, поэтому математическая логика, по существу, – наука 
о математике. 
Математическая логика дала средства для построения логических 
теорий и вычислительный аппарат для решения задач. Она нашла широкое 
применение в различных областях науки и техники (например, в лингвистике, в теории релейно-контактных схем, в экономике, в вычислительной 
технике, в информационных системах и др.). Понятия математической логики лежат в основе таких ее приложений, как базы данных, экспертные 
системы, системы логического программирования. Эти же понятия становятся методологической основой описания анализа и моделирования автоматизированных интегрированных производств. 
Применение в логике математических методов становится возможным тогда, когда суждения формулируются на некотором точном языке. 
На практике множество элементарных логических операций является обязательной частью набора инструкций всех современных микропроцессоров 
и, соответственно, входит в языки программирования. Это важнейшее 
практическое приложение методов математической логики.  
 
 

Алгебра высказываний 

5 

ГЛАВА 1. АЛГЕБРА ВЫСКАЗЫВАНИЙ 

 
 
1.1. Высказывания и операции с ними 
 
В известном труде Аристотеля «Органон» (IV в. до н. э.) есть раздел 
о правильных умозаключениях «Силлогистика». До XVII века в Европе 
логика развивалась на основе логики Аристотеля. Попытку превратить 
логику в математическую науку в XVII веке предпринял Готфрид Вильгельм Лейбниц (1646–1716), но решительного успеха не добился. Однако 
в современной математической логике его конструктивный подход отражается в применении так называемых таблиц истинности. 
Современный вид математическая логика приобрела в 80-е годы 
XIX века в трудах Готлиба Фреге (1848–1925). Он построил аксиоматику 
логики высказываний, ввел понятие предиката и др. 
Определение. Высказыванием называется повествовательное предложение, которое может быть либо истинным, либо ложным. Истина («И» 
или «1») и ложь («Л» или «0») называются истинностными значениями 
высказываний.  
Высказывания обозначаются буквами A, B, C, …; их истинностные 
значения [A], [B], [C], … соответственно. Таким образом, 
 

[A] = 1,
если  истинное высказывание;
0,
если  ложное высказывание.
A
A



 

 
Примеры:  
1) A – «2 – простое число», [A] = 1; 
2) B – «Cолнце светит» [B] = 1, если солнце светит;  
3) C – «x + y > 1» – не высказывание;  
4) D – «3 < 1», [D] = 0.  
Приведенные высказывания нельзя разбить на части, также являющиеся высказываниями. Высказывания «Неверно, что 3 < 1» или «2 – простое число», или «3 < 1» таковыми не являются. Высказывания, построенные из простых с помощью связок «не», «и», «или» и сочетаний «если ..., 
то ...», «... тогда и только тогда, когда ...» носят специальные названия. 
Приведем соответствующие определения. 
Определение. Отрицанием высказывания A называется высказывание A («Не A», «Неверно, что A»), которое истинно тогда, когда A ложно 
и ложно тогда, когда A истинно.  
Данное и следующие далее определения удобно приводить с помощью так называемой таблицы истинности. Для отрицания она имеет вид 

Глава 1 

6 

 
A 
A

0 
1 

1 
0 

 
Если A – «2 – простое число», то A – «Неверно, что 2 – простое 
число» или «2 не является простым числом». Если B – «Солнце светит», то 
B – «Неверно, что солнце светит» или «Солнце не светит».  
Определение. Конъюнкцией высказываний A и B называется высказывание A ˄ B («A и B»), которое истинно тогда и только тогда, когда 
истинны оба высказывания.  
Таблица истинности операции конъюнкции имеет вид 
 
A 
B 
A
B


0 
0 
0 

0 
1 
0 

1 
0 
0 

1 
1 
1 

 
Пример. Если A – «2 – простое число», B – «Солнце светит», то A ˄ B – 
«2 – простое число и солнце светит».  
Определение. Дизъюнкцией высказываний A и B называется высказывание A ˅ B («A или B»), которое ложно тогда и только тогда, когда ложны 
оба высказывания.  
Таблица истинности операции дизъюнкции имеет вид 
 
A 
B 
A
B


0 
0 
0 

0 
1 
1 

1 
0 
1 

1 
1 
1 

 
Определение. Импликацией высказываний A и B называется высказывание A → B («Если A, то B», или «Из A следует B»), которое ложно тогда 
и только тогда, когда A истинно, а B ложно. При этом A называется посылкой, B – следствием или заключением.  
Таблица истинности операции импликации имеет вид  
 
A 
B 
A → B 

0 
0 
1 

0 
1 
1 

1 
0 
0 

1 
1 
1 

 
Пример. Предложение «Если я лягу поздно, то встану тоже поздно» 
является импликацией высказываний «Я лягу поздно» и «Я встану поздно».  

Алгебра высказываний 

7 

Определение. Эквиваленцией высказываний A и B называется высказывание A ↔ B («A тогда и только тогда, когда B», или «A необходимо 
и достаточно для B»), которое истинно только тогда, когда оба высказывания имеют одинаковые истинностные значения.  
Таблица истинности операции эквиваленции имеет вид  
 
A 
B 
A ↔ B 

0 
0 
1 

0 
1 
0 

1 
0 
0 

1 
1 
1 

 
Пример. Определить истинностное значение высказывания A
B
C


, 
если [A] = 0, [B] = 1, [C] = 0. 
Решение. 
Из определения конъюнкции высказываний следует, что [B ˄C] = 0. 
Из определения отрицания высказывания следует, что [ B
C

] = 1. Из 
определения операции эквиваленции следует, что [ A
B
C


] = 0. 
Коротко эти рассуждения можно записать так: 
 
A 
0 
↔ 
 
 
 
0 

B
C

 
1   0 
0 
1 

 
Пример. Определить истинностное значение высказывания (P ˅ Q) → 
(R ↔ S ), если [P] = 1, [Q] = 0, [R] = 0, [S] = 0. 
Решение. 
 
(P ˅ Q) 
1   0 
1 
1 

→ 
 
 
 
0 

(R ↔ S ),
0    0 
0    1 
0 

 
 
1.2. Формулы алгебры высказываний 
 
Определение. Пропозициональной переменной называется переменная, обозначающая высказывания.  
Обозначения – P, Q, R, … A, B, C, … X, Y, … .