Сысоев МАТЕМАТИЧЕСКАЯ ЛОГИКА Учебное пособие Липецк Липецкий государственный технический университет 2013 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» С.В. Ткаченко А.С. <...> 100 ВВЕДЕНИЕ Дискретная математика – одна из важнейших составляющих современной математики. <...> В отличие от традиционной математики (математического анализа, линейной алгебры), методы и конструкции которой имеют в основном числовую интерпретацию, дискретная математика имеет дело с объектами нечисловой природы: множествами, логическими высказываниями, алгоритмами, графами. <...> Благодаря этому обстоятельству дискретная математика впервые позволила распространить математические методы на сферы и задачи, которые ранее были далеки от математики. <...> Алгебра высказываний – раздел математической логики, изучающий строение (форму, структуру) сложных логических высказываний и способы установления их истинности с помощью алгебраических методов. <...> Алгебру высказываний иначе еще называют алгеброй логики, логикой высказываний. <...> . Однако наибольшего развития дискретная математика достигла в связи с запросами практики, приведшими к появлению новой науки – кибернетики и её теоретической части – математической кибернетики (XX в.) <...> Приоритет операций Предложение, относительно которого имеет смысл говорить, что его содержание истинно или ложно, называется высказыванием. <...> Всякое сложное высказывание, составленное из некоторых исходных высказываний посредством применения операций 1 – 8, называют формулой алгебры высказываний. <...> Если задать значения всех переменных элементарных высказываний, то сама формула примет определенное значение. <...> Равносильность формул Две формулы А и В называются равносильными, если они принимают одинаковые значения на одном и том же списке переменных <...>
Математическая_логика.pdf
УДК 517(07)
Т 484
Рецензенты: кафедра информатики, прикладной математики и механики ФГБОУ
ВПО «Омский государственный университет путей сообщения»;
Скуратов А.П. – канд. техн. наук, доц., Липецкий филиал НОУ ВПО «Международный
институт компьютерных технологий».
Ткаченко, С.В.
Т 484 Математическая логика. [Текст]: учеб. пособие / С.В. Ткаченко,
А.С. Сысоев. Липецк: Изд-во Липецкого государственного технического
университета, 2013. – 99 с.
ISBN 978-5-88247-649-5
Пособие является одной из частей системы учебных пособий по дискретной
математике. Рассматриваются основные разделы дисциплины «Теория графов и
математическая логика», в частности математическая логика.
Данное пособие может быть рекомендовано студентам направлений 231300.62
«Прикладная математика», 221400.62 «Управление качеством», 221700.62
«Стандартизация и метрология», а также преподавателям, которые преподают
математическую логику студентам всех направлений.
УДК 517(07)
Т 484
Издается по решению РИС ЛГТУ.
ISBN 978-5-88247-649-5
© ФГБОУ ВПО «Липецкий государственный
технический университет», 2013
© Ткаченко С.В., Сысоев А.С., 2013
Стр.3
СОДЕРЖАНИЕ
ВВЕДЕНИЕ.......................................................................................................... 8
1. Булевы алгебры ................................................................................................ 9
1.1. Высказывание. Логические операции. Формулы алгебры высказываний.
Приоритет операций ............................................................................. 9
1.2. Равносильность формул ........................................................................12
1.3. Закон двойственности ...........................................................................14
1.4. Тождественно истинные и ложные формулы .......................................15
1.5. Дизъюнктивные и конъюнктивные нормальные формы ......................18
1.6. Совершенная дизъюнктивная и конъюнктивная нормальные формы ..23
2. Булевы функции ..............................................................................................29
2.1. Представление булевой функции формулой алгебры высказываний.
Таблицы истинности ...................................................................................29
2.2. Алгебра Жегалкина ...............................................................................35
3. Теорема о функциональной полноте (теорема Поста). Примеры функционально-полных
базисов .....................................................................................39
4. Дифференцирование булевых функций ..........................................................45
5. Интегрирование булевых функций .................................................................49
6. Минимизация булевых функций .....................................................................54
6.1. Непосредственная минимизация...........................................................54
6.2. Карты Карно .........................................................................................55
6.3. Метод Квайна – Мак-Класки ................................................................58
ИНДИВИДУАЛЬНОЕ ДОМАШНИЕ ЗАДАНИЕ (ВАРИАНТЫ) ......................65
ИДЗ 1. Таблицы истинности булевых функций ..............................................65
ИДЗ 2. СДНФ и СКНФ....................................................................................71
ИДЗ 3. Алгебра Жегалкина .............................................................................71
ИДЗ 4. Полнота систем булевых функций ......................................................71
ИДЗ 5. Минимизация булевых функций .........................................................71
ИНДИВИДУАЛЬНОЕ ДОМАШНЕЕ ЗАДАНИЕ (ПРИМЕР ВЫПОЛНЕНИЯ)72
Стр.6
Пример выполнения ИДЗ 1 .............................................................................72
Пример выполнения ИДЗ 2 .............................................................................75
Пример выполнения ИДЗ 3 .............................................................................77
Пример выполнения ИДЗ 4 .............................................................................81
Пример выполнения ИДЗ 5 .............................................................................88
ПРОМЕЖУТОЧНЫЙ КОНТРОЛЬ ЗНАНИЙ ....................................................93
Тестовые задания для защиты ИДЗ.................................................................93
Тест 1...............................................................................................................93
Тест 2...............................................................................................................94
Тест 3...............................................................................................................95
Тест 4...............................................................................................................96
Тест 5...............................................................................................................97
Примеры контрольных работ..............................................................................98
Контрольная работа № 1 .................................................................................98
Контрольная работа № 2 .................................................................................98
КОНТРОЛЬНЫЕ ВОПРОСЫ .............................................................................99
БИБЛИОГРАФИЧЕСКИЙ СПИСОК ............................................................... 100
Стр.7