Путилов С.В., Корпачева М.А., Сорокина М.М. Математическая логика:
Алгебра высказываний. Булевы функции. Логика предикатов. Формализованное исчисление высказываний. Изд. 2, испр.

2024. 176 с.

Типографская бумага

Аннотация

Учебное пособие содержит теоретический материал и практические задания по традиционным для высших учебных заведений разделам дисциплины «Математическая логика». Рассматриваются следующие темы и их приложения: алгебра высказываний, булевы функции, логика предикатов, формализованное исчисление высказываний. Для самостоятельной работы по каждой теме предлагается достаточное количество задач с алгоритмами их решения.

Пособие предназначено для студентов... (Подробнее)

Оглавление

Оглавление				3
Принятые обозначения				7
Введение				9
Глава 1. Алгебра высказываний (АВ)				13
§ 1. Логические операции АВ				13
1. Понятие высказывания				13
2. Логические операции				14
§ 2. Формулы (слова) АВ				15
1. Алфавит языка АВ				15
2. Формулы (слова) АВ				15
3. Таблица истинности формулы АВ				16
§ 3. Классификация формул АВ				18
1. Тавтологии				18
2. Основные правила получения тавтологий				19
3. Выполнимые, опровержимые и тождественно ложные формулы				19
§ 4. Равносильные формулы АВ				20
1. Равносильные формулы				20
2. Признак равносильности				20
3. Отношение эквивалентности				21
4. Основные равносильности АВ				21
5. Равносильные преобразования формул				23
§ 5. Нормальные формы для формул АВ				23
1. Нормальные формы				23
2. Полная система связок (ПСС)				24
3. Существование ДНФ и КНФ				25
§ 6. Совершенные нормальные формы для формул АВ				25
1. Совершенные нормальные формы				25
2. Замечательное свойство СКО и его приложения				26
3. Существование СДНФ				27
4. Замечательное свойство СДО и его приложения				28
5. Существование СКНФ				29
§ 7. Логическое следствие				31
1. Понятие логического следствия				31
2. Признаки логического следствия				31
3. Логическое следствие и правила логических умозаключений				33
3.1. Правило логического вывода				33
3.2. Правила логических умозаключений				33
3.3. Метод доказательства от противного				34
4. Алгоритм нахождения логического следствия из данной совокупности посылок				36
5. Понятие теоремы в АВ				38
5.1. Взаимно обратные и взаимно противоположные теоремы				38
5.2. Необходимые и достаточные условия				39
Глава 2. Булевы функции				40
§ 1. Булевы функции от одной переменной				40
§ 2. Булевы функции от двух переменных				40
1. Стрелка Пирса и штрих Шеффера				41
2. Множество булевых функций от двух переменных				42
§ 3. Булевы функции от n переменных				42
§ 4. Булевы функции и формулы АВ				45
§ 5. Полные системы булевых функций				46
§ 6. Специальные классы булевых функций				46
1. Теорема Поста				48
§ 7. Приложение булевых функций к релейно-контактным схемам				52
1. Для схемы из двух последовательно соединенных контактов x и y				53
2. Для схемы из двух параллельно соединенных контактов x и y				53
Глава 3. Логика предикатов				55
§ 1. Понятие предиката				55
§ 2. Классификация предикатов				56
§ 3. Множество истинности предиката				57
§ 4. Равносильные предикаты. Следствие предиката				57
§ 5. Логические операции над предикатами				58
1. Отрицание				58
2. Конъюнкция				59
3. Дизъюнкция				61
4. Импликация и эквиваленция				62
§ 6. Кванторные операции над предикатами				64
1. Квантор общности				64
2. Квантор существования				66
§ 7. Формулы логики предикатов				67
1. Алфавит логики предикатов				67
2. Классификация формул логики предикатов				69
3. Тавтологии				70
4. Равносильные преобразования формул логики предикатов				75
5. Приведенная форма				76
6. Предваренная нормальная форма				77
7. Проблема разрешимости				79
8. Проблема разрешимости для формул на конечных множествах				79
9. Проблема разрешимости для формул от одноместных предикатных переменных				80
10. Проблема разрешимости для ∀-формул и ∃-формул				84
§ 8. Приложения логики предикатов				85
1. Символьная запись математических определений				86
2. Строение математических теорем				86
3. Методы доказательства теорем				88
4. Логика предикатов в алгебре множеств				90
Глава 4. Формализованное исчисление высказываний				92
§ 1. Система аксиом и теория формального вывода				92
1. Первоначальные понятия аксиоматической теории				92
2. Понятие вывода и его свойства				94
3. Производные правила				99
§ 2. Полнота и другие свойства формализованного исчисления высказываний				101
1. Синтаксис и семантика				101
2. Лемма о выводимости				102
3. Полнота формализованного исчисления высказываний				105
4. Непротиворечивость формализованного исчисления высказываний				107
5. Разрешимость формализованного исчисления высказываний				108
6. Независимость системы аксиом формализованного исчисления высказываний				108
7. Независимость аксиомы (А1)				109
8. Независимость аксиомы (А2)				112
9. Независимость аксиомы (А3)				113
Примерный перечень вопросов к зачёту и экзамену по учебной дисциплине «Математическая логика»				115
Задачи и упражнения для самостоятельного решения				117
1. Алгебра высказываний				117
2. Булевы функции				138
3. Логика предикатов				165
Список литературы				174

Об авторах

Путилов Сергей Васильевич

Кандидат физико-математических наук, доцент кафедры математического анализа, алгебры и геометрии ФГБОУ «Брянский государственный университет имени академика И. Г. Петровского». Заведующий кафедрой алгебры (1999–2013), кафедрой алгебры и геометрии (2013–2017), кафедрой математического анализа, алгебры и геометрии (2017–2023) БГУ имени академика И. Г. Петровского. Лауреат премии академика И. Г. Петровского (1985). Почетный работник высшего профессионального образования Российской Федерации (2009).

Корпачева Марина Александровна

Сорокина Марина Михайловна

Доктор физико-математических наук, профессор кафедры математического анализа, алгебры и геометрии ФГБОУ «Брянский государственный университет имени академика И. Г. Петровского». Лауреат премии академика И. Г. Петровского (1993).