Математическая логика, Унучек С.А., 2018

Математическая логика, Унучек С.А., 2018.

   В основе настоящего пособия положен курс лекций и практических занятий по математической логике, который на протяжении нескольких лет читается студентам различных факультетов МГТУ МИРЭА. В пособии рассмотрены следующие темы: элементы теории множеств и комбинаторики, булевы функции, бинарные отношения, основы теории графов, основы теории алгоритмов, минимизация конечных автоматов, вошедшие в программу подготовки специалистов и бакалавров очной и очно-заочной форм обучения. По каждой теме даны теоретические сведения (основные определения и теоремы), приведены решения типовых задач, приложены задачи для самостоятельного решения.
Учебное пособие предназначено для студентов высших учебных заведений, изучающих дисциплины «Математическая логика и теория алгоритмов» и «Дискретная математика», обучающихся по направлениям подготовки 01.03.02 «Прикладная математика и информатика», 01.03.04 «Прикладная математика», 09.03.01 «Информатика и вычислительная техника», 09.03.02 «Информационные системы и технологии», 09.03.03 «Прикладная информатика», 09.03.04 «Программная инженерия», 11.03.02 «Инфокоммуникационные технологии и системы связи» и так далее. Пособие также может быть полезно студентам других специальностей и преподавателям, а также всем желающим начать самостоятельное изучение математической логики.




Простые и сложные высказывания.
Определение 1.1. Высказыванием называется утверждение, о котором в данной ситуации можно сказать, что оно истинно или ложно. Истинность или ложность, приписываемые некоторому утверждению, называются его значением истинности.

Пример 1.1.
Предложения «Квадрат действительного числа есть число неотрицательное» и «три больше пяти» являются высказываниями, первое из которых всегда истинно, а второе - ложно. Утверждение «Завтра будет дождь» также является высказыванием, но его истинность (ложность) зависит от ситуации.

Предложения «Кто пришел?» и «Подойдите ко мне» высказываниями нс являются.
Высказывания будем обозначать буквами латинского алфавита х, у, z и т.д. В математической логике истинные значения обозначают символом «1», а ложные - «0».

В разговорной речи для образования сложного предложения из простых используются союзы «и», «или», «нет», «если ..., то» и т.д. В логике для этого используют логические связки.

ОГЛАВЛЕНИЕ.
ГЛАВА 1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ МАТЕМАТИЧЕСКОЙ ЛОГИКИ.
1.1. Высказывания и логические связки.
1.1.1. Простые и сложные высказывания.
1.1.2. Условные высказывания.
1.1.3. Эквивалентные высказывания.
1.2. Задачи для самостоятельного решения.
ГЛАВА 2. БУЛЕВЫ ФУНКЦИИ И СПОСОБЫ ИХ ЗАДАНИЯ.
2.1. Определение булевой функции.
2.2. Способы задания булевых функций.
2.2.1. Табличный способ чада мин.
2.2.2. Векторный способ задания булевой функции.
2.2.3. Носитель функции алгебры логики.
2.2.4. Геометрический способ задания двоичной функции.
2.2.5. Способы задания функций алгебры логики, изучаемые в нашем курсе.
2.3. Элементарные булевы функции.
2.3.1. Двоичные функции одной переменной.
2.3.2. Булевы функции двух переменной.
2.3.3. Формулы.
2.3.4 Приоритет выполнения булевых функций.
2.3.5. Алгоритм определении таблицы истинности булевой функции по формуле.
2.3.6. Основные эквивалентности (законы) алгебры логики.
2.4. Задачи для самостоятельного решения.
ГЛАВА 3. РАССУЖДЕНИЯ И ДОКАЗАТЕЛЬСТВА.
3.1. Схемы рассуждений.
3.2. Задачи для самостоятельного решения.
ГЛАВА 4. СПЕЦИАЛЬНЫЕ ПРЕДСТАВЛЕНИЯ БУЛЕВЫХ ФУНКЦИЙ.
4.1. Дизъюнктивные и конъюнктивные нормальные формы.
4.2. Совершенная дизъюнктивная нормальная форма.
4.2.1. Алгоритм построения СДНФ булевой функции.
4.3. Совершенная конъюнктивная нормальная форма.
4.3.1. Алгоритм построения СКНФ булевой функции.
4.3.2. Выражение сложения по модулю 2, эквивалентности и импликации через другие элементарные функции.
4.4. Многочлен Жегалкина.
4.5. Различные алгоритмы построения многочлена Жегалкина.
4.5.1. Алгоритм 1 (посредством СДНФ).
4.5.2. Алгоритм 2 (метод неопределенных коэффициентов).
4.5.3. Алгоритм 3 (метод треугольника).
4.6. Задачи для самостоятельного решения.
ГЛАВА 5. ГЕОМЕТРИЧЕСКИЙ МЕТОД МИНИМИЗАЦИИ НУЛЕВЫХ ФУНКЦИЙ.
5.1. Постановка задачи минимизации.
5.1.1. Основные определения.
5.1.2. Алгоритм построения минимальной ДНФ.
5.2. Геометрический метод построения минимальной ДНФ
булевых функций трех переменных.
5.2.1. Задание функции на двоичном кубе.
5.2.2. Грани булевого куба.
5.2.3. Сокращенная ДНФ.
5.2.4. Ядро функции.
5.2.5. Тупиковые и минимальные ДНФ.
5.2.6. Функция Патрика.
5.3. Задачи для самостоятельного решения.
ГЛАВА 6. МЕТОД КВАЙНА - МАК-КЛАСКИ МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИИ.
6.1. Склейка соседних наборов.
6.2. Алгоритм Квайна - Мак-Класки.
6.3. Задачи для самостоятельного решения.
ГЛАВА 7. МЕТОД КАРНО МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ.
7.1. Представление функции алгебры логики картой Карно.
7.2. Алгоритм Карно минимизации булевых функций.
7.3. Задачи для самостоятельного решения.
ГЛАВА 8. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ.
8.1. Введение в теорию множеств.
8.1.1. Основные понятия теории множеств.
8.1.2. Операции над множествами.
8.1.3. Основные свойства множеств.
8.2. Диаграммы Венна.
8.3. Задачи для самостоятельного решения.
ГЛАВА 9. КОМБИНАТОРИКА.
9.1. Основные комбинаторные принципы.
9.2. Перестановки, размещения, сочетания.
9.3. Комбинаторные тождества.
9.4. Задачи для самостоятельного решения.
ГЛАВА 10. ОТНОШЕНИЯ.
10.1. Основные определения.
10.2. Способы задания бинарных отношений.
10.3. Виды отношений.
10.4. Свойства бинарных отношений.
10.5. Эквивалентность и порядок.
10.6. Задачи для самостоятельного решения.
ГЛАВА 11. ГРАФЫ.
11.1. Основные определения теории графов.
11.2. Способы задания графов.
11.3. Графы специального вида.
11.4. Клики.
11.5. Метрические характеристики графов.
11.6. Задачи для самостоятельного решения.
ГЛАВА 12. ГРАФЫ И БИНАРНЫЕ ОТНОШЕНИЯ.
12.1. Задание бинарных отношений графом.
12.2. Задачи для самостоятельного решения.
ГЛАВА 13. ЛОГИКА ПРЕДИКАТОВ. КВАНТОРЫ.
13.1. Исчисление предикатов.
13.2. Кванторы.
13.3. Префиксная нормальная форма.
13.3.1. Алгоритм представления формулы в виде ПНФ.
13.4. Задачи для самостоятельного решения.
ГЛАВА 14. АЛГОРИТМ.
14.1. Понятие алгоритма.
14.2. Общие свойства алгоритма.
14.3. Способы задания алгоритмов.
14.4. Вилы алгоритмов.
14.5. Рекурсия.
14.6. Вычислимые функции, разрешимые и перечислимые множества.
14.6.1. Свойства перечислимых и разрешимых множеств.
14.7. Теория рекурсивных функций.
14.7.1. Свойства рекурсивных функций.
14.8. Тезис Черча.
14.9. Разрешимость алгоритмов.
14.10. Эффективность алгоритмов.
14.10.1. Основные классы роста порядка сложности.
ГЛАВА 15. МАШИНА ТЬЮРИНГА.
15.1. Принцип работы машины Тьюринга.
15.2. Тезис Тьюринга.
15.3. Свойства машины Тьюринга как алгоритма.
15.4. Примеры составления программ машины Тьюринга.
15.5. Задачи для самостоятельного решения.
ГЛАВА 16. НОРМАЛЬНЫЙ АЛГОРИТМ МАРКОВА.
16.1. Подстановки.
16.2. Принцип нормализации Маркова.
16.3. Примеры составления нормальных алгоритмов Маркова.
16.4. Задачи для самостоятельного решения.
ГЛАВА 17. КОНЕЧНЫЕ АВТОМАТЫ.
17.1. Понятие конечного автомата.
17.2. Способы задания конечных автоматов.
17.2.1. Табличный способ задания.
17.2.2. Графический способ задания.
17.2.3. Система булевых функций.
17.2.4. Канонические уравнения автомата.
17.3. Примеры конечных автоматов.
17.3.1. Элемент задержки.
17.3.2. Двоичный сумматор.
17.3.3. Автомат сравнения на равенство.
17.3.4. Автомат-экзаменатор.
ГЛАВА 18. МИНИМИЗАЦИЯ АВТОМАТОВ.
18.1. Инициальные автоматы.
18.2. Отличимость конечных автоматов.
18.3. Алгоритм построения приведенных автоматов.
18.4. Задачи для самостоятельного решения.
СПИСОК ЛИТЕРАТУРЫ.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Математическая логика, Унучек С.А., 2018 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по математике :: математика :: Унучек :: логика