Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Основная коллекция
Артикул: 764372.01.99
Кратко изложен теоретический материал по дисциплине «Математическая логика и теория алгоритмов», приведены примеры решения типовых задач, представлены задачи различной сложности для решения на практических занятиях и самостоятельной работы. Предназначено для студентов направления 09.03.02 «Информационные системы и технологии», а также других направлений (09.03.04 «Программная инженерия», 27.03.03 «Системный анализ и управление», 27.03.04 «Управление в технических системах»).
Михальченко, Г. Е. Математическая логика и теория алгоритмов : учебное пособие / Г. Е. Михальченко. - Красноярск : Сиб. федер. ун-т, 2018. - 74 с. - ISBN 978-5-7638-3932-6. - Текст : электронный. - URL: https://znanium.com/catalog/product/1816545 (дата обращения: 29.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
Кратко изложен теоретический материал по 
дисциплине «Математическая логика и теория 
алгоритмов», приведены примеры решения типовых задач, представлены задачи различной 
сложности для решения на практических занятиях и самостоятельной работы. 

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

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

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

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

 

Министерство науки и высшего образования Российской Федерации 
Сибирский федеральный университет 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Г. Е. Михальченко 
 
 
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ  
АЛГОРИТМОВ 
 
 
Учебное пособие 
 
 
 
 
 
 
 
 
 
 
 
 
 
Красноярск 
СФУ 
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, … . 

Глава 1 

8 

Определение.  
1. Пропозициональная переменная является формулой.  
2. Если F и G – формулы, то формулами также являются 
 
( F ), (F ˄ G), (F ˅ G), (F → G), (F ↔ G), 
 
3. Других формул нет.  
Примеры:  
1) ((X ˅ Y) → Z), ((( X ) → Y) ↔ X) – формулы; 
2) (Z ˅ (X ˄ Y)) и ((Z ˅ X) ˄ Y) – разные формулы;  
3) Z → X ˅ Y – не формула.  
Далее рассмотрим классификацию формул алгебры высказываний, 
для чего понадобится понятие интерпретации формулы. 
Определение. Говорят, что задана интерпретация I = (A1, A2, …, An) 
формулы F(X1, X2, …, Xn), если в ней переменные заменяют определенными 
высказываниями: X1 = A1, X2 = A2, …, Xn = An. 
Высказывание, полученное в результате интерпретации, будем обозначать  
F(I) = F (A1, A2, …, An). 
 
Формулы алгебры высказываний делятся на четыре (иногда на три) 
вида, в зависимости от истинностных значений высказываний, которые 
можно получить в результате интерпретаций этих формул. 
Определение. Формула F называется тавтологией (|= F) или тождественно истинной, если при любой интерпретации I она становится истинным высказыванием  
I ([F(I)] = 1). 
 
Пример. Показать, что тавтологиями являются формулы  
 
X ˅ X , (X ˄ Y) → X. 
 
Решение. 
Достаточно составить их таблицы истинности:  
 
X 
X
X
X


0 
1 
1 

1 
0 
1 

 
X 
Y 
X ˄ Y 
(X ˄ Y) → X 

0 
0 
0 
1 

0 
1 
0 
1 

1 
0 
0 
1 

1 
1 
1 
1 

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

9 

Определение. Формула F называется выполнимой, если существует 
такая её интерпретация I, в результате которой она становится истинным 
высказыванием  
I ([F(I)] = 1). 
 
Составив таблицу истинности для формулы (X ˅ Y) → X, можно 
убедиться в том, что она выполнима. 
Определение. Формула F называется опровержимой, если существует такая её интерпретация I, в результате которой она становится 
ложным высказыванием  
I ([F(I)] = 0). 
 
Приведенная выше выполнимая формула одновременно является 
и опровержимой (нужно взять интерпретации, при которых [X] = 0, [Y] = 1). 
Определение. Формула F называется противоречием или тождественно ложной, если при любой интерпретации I она становится ложным 
высказыванием  
I ([F(I)] = 0). 
 
Упражнение. Показать, что противоречиями являются формулы  
 

,  (
)
.
X
X
X
Y
X



 

 
Приведем теоремы, полезные для отыскания тавтологий. 
Теорема. Если формула F – тавтология, то формула F  – противоречие и наоборот.  
Теорема (правило заключения). Если формулы F и F → G – тавтологии, то формула G также является тавтологией.  
Доказательство: Проведем доказательство от противного то есть 
предположим, что G не является тавтологией. Тогда существует такая интерпретация I0, при которой [G(I0)] = 0. Так как [F(I0)] = 1, то [F(I0) → 
G(I0)] = 0. Это противоречит условию теоремы о том, что F → G тавтология. 
Значит наше предположение неверно и G – тавтология. Теорема доказана. 
Теорема (правило подстановки). Если формула F(…, X, …), содержащая переменную X, является тавтологией, то формула F(…, G, …), полученная подстановкой в формулу F вместо переменной X любой формулы 
G, также является тавтологией.  
 
 
1.3. Отношения логического следования и равносильности  
 
Рассмотрим отношение логического следования между формулами 
алгебры высказываний. 

Глава 1 

10 

Определение. Формула G логически следует из формулы F, если при 
всех интерпретациях I, при которых F(I) истинно, G(I) также истинно. При 
этом пишут F => G.  
Пример. Доказать, что (X ˄ Y) ˄ Z => X.  
Доказательство следует из того, что конъюнкция (X ˄ Y) ˄ Z истинна 
тогда и только тогда, когда истинны все ее компоненты, значит, когда истинно X. 
Пример. Доказать, что P → Q => P ˅ Q.  
Данное отношение между формулами становится очевидным, если 
построить таблицы истинности для обеих формул: 
 
P 
Q 
P → Q 
P  
P
Q

 

0 
0 
1 
1  
1  

0 
1 
1 
1 
1  

1 
0 
0 
0  
0  

1 
1 
1 
0  
1  

 
Теорема. Из F логически следует G тогда и только тогда, когда тавтологией является импликация F → G.  
Доказательство: 
1. Пусть F => G. Тогда для каждой интерпретации I, такой что [F(I)] = 1, 
имеем [G(I)] = 1. Поэтому [F(I) → G(I)] = 1, то есть |= F → G. 
2. Пусть |= F → G. Тогда для тех I, для которых [F(I)] = 1, также 
[G(I)] = 1. По определению логического следования это означает, что 
F => G. 
Теорема доказана. 
Данное выше определение понятия логического следования обобщается следующим образом. 
Определение. Формула G логически следует из формул F1, F2, …, Fk. 
(F1, F2, …, Fk => G), если при всех интерпретациях, при которых истинны 
F1(I), F2(I), …, Fk(I), истинно высказывание G(I).  
Теорема. Из F1, F2, …, Fk логически следует G тогда и только тогда, 
когда тавтологией является импликация (((F1 ˄ F2) ˄ …) ˄ Fk) → G.  
Рассмотрим пример применения на практике понятия логического 
следования. 
Пример. Верно ли рассуждение? 
Если я пойду завтра на первое занятие, то должен буду встать рано, 
а если я пойду вечером на танцы, то лягу спать поздно. Если я лягу спать 
поздно, а встану рано, то я буду вынужден довольствоваться пятью часами 
сна. Я не в состоянии обойтись пятью часами сна. Следовательно, я должен 
или пропустить завтра первое занятие, или не ходить на танцы.