Аляев Ю.А., Тюрин С.Ф. Дискретная математика и математическая логика

Учебник. — Москва: Финансы и статистика, 2006. — 368 с.— ISBN 5-279-03045-7.Рассматриваются основные темы дискретной математики и математической логики: теория множеств, элементы комбинаторики, теория графов, теория переключательных функций и автоматов, теория кодирования, формальная логика, логические исчисления, формальные теории и теория алгоритмов, элементы теории нечетких множеств. Сложные вопросы математики рассматриваются на простых примерах. Большая часть материала снабжена методическими разработками авторов. Имеются задания для самостоятельной работы студентов. Для студентов вузов, обучающихся по специальностям «Прикладная информатика в экономике», «Экономика и управление на предприятии», а также для преподавателей.Содержание:
ПредисловиеДИСКРЕТНАЯ МАТЕМАТИКА
Множества и алгебраические системы. Булевы алгебры
Основные понятия теории множеств
Основные операции над множествами
Декартово произведение множеств
Соответствия и функции
Отношения
Использование множеств в языке ПаскальЭлементы общей алгебры
Операции на множествах
Группа подстановок Галуа
Алгебра множеств (алгебра Кантора)
Алгебраические системы. Решетки
Задание множеств конституентами
Решение уравнений в алгебре множествЭлементы комбинаторики
Комбинаторные вычисления
Основные понятия комбинаторики
Размещения
Перестановки
Сочетания
Треугольник Паскаля
Бином Ньютона
Решение комбинаторных уравненийОсновные понятия теории графов
Способы задания графов
Характеристики графов
Понятие о задачах на графах
Задача о Ханойской башнеПереключательные функции и способы их задания
Понятие о переключательных функциях
Двоичные переключательные функции и способы их задания
Основные бинарные логические операции
Понятие о переключательных схемах и технической реализации переключательных функций
Использование логических операций в теории графовЭлементарные двоичные переключательные функции и функциональная полнота систем переключательных функций
Элементарные переключательные функции одной переменной
Элементарные переключательные функции двух переменных
Функциональная полнота систем переключательных функций
Базисы представления переключательных функций
Пример анализа и определения свойств ПФ, заданной десятичным номеромОсновные законы булевой алгебры и преобразование переключательных функций
Основные законы булевой алгебры переключательных функций
Равносильные преобразования. Упрощение формул алгебры переключательных функций
Преобразование форм представления переключательных функцийМинимизация переключательных функций
Цель минимизации переключательных функций
Основные понятия и определения, используемые при минимизации
Аналитические методы минимизации переключательных функций
Минимизация переключательных функций по картам Карно
Метод поразрядного сравнения рабочих и запрещенных наборов
Минимизация переключательных функций, заданных в базисе {Ф, И, НЕ}
Минимизация систем переключательных функций
Минимизация переключательных функций методом неопределенных коэффициентовПонятие об автомате и его математическом описании
Основные определения теории конечных автоматов
Описание конечных детерминированных автоматов таблицами переходов-выходов и графами
Понятие о технической интерпретации конечных автоматов
Синтез комбинационных автоматов в заданном базисе
Булева производная
Элементарные автоматы памяти на основе комбинационного автомата и задержки
Синтез автомата — распознавателя последовательностиЭлементы теории кодированияМАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ
Понятие об алгоритмах. Схемы алгоритмов
Понятие об алгоритме и теории алгоритмов
Схемы алгоритмов
Рекурсивные функции
Машина Тьюринга
Машина Поста
Нормальные алгорифмы А.А. Маркова
Универсальная абстрактная машина
Разрешимость в теории алгоритмов. Проблема самоприменимости
Сложность алгоритма
Представление схемы алгоритма эквивалентным автоматом
Представление схемы алгоритма микропрограммой с двумя типами микрокомандЭлементы формальной логики
Предмет формальной логики
Понятие и его виды
Отношения между понятиями
Операции над понятиями
Суждение и его характеристикаУмозаключение
Виды умозаключений
Непосредственное умозаключение
Опосредованное дедуктивное умозаключение. Фигуры силлогизма
Дополнительные виды силлогизмов
Индуктивные умозаключения. Математическая индукцияЛогика высказываний
Семантика логики высказываний
Синтаксис логики высказываний. Формулы логики высказываний
Формализация высказываний
Интерпретации, разрешимость, выполнимость, общезначимость
Логическая равносильность. Законы логики
Формы представления формул логики высказываний
Проблема дедукции в логике высказыванийПроверка правильности логических выводов. Метод резолюций
Закон контрапозиции
Логическое следование. Проверка правильности логических выводов
Силлогизмы в логике высказываний
Получение следствий из данных посылок
Метод резолюцийСинтаксис и семантика языка логики предикатов
Понятие предиката
Кванторы и связанные переменные
Синтаксис языка логики предикатов. Формулы логики предикатов и формализация суждений
Семантика формул логики предикатовТождественные преобразования формул логики предикатов
Операции над предикатами
Основные равносильности логики предикатов
Тождественные преобразования формул
Универсум ЭрбранаИспользование метода резолюций в логике предикатов
Подстановка и унификация
Резольвенция и факторизация
Метод резолюций в логике предикатов
Принцип логического профаммированияЛогические исчисления
Понятие о формальных теориях
Исчисление высказываний
Исчисление предикатов
Система натурного вывода
Понятие о математической лингвистике
Формальный язык
Формальные грамматики и их свойства
Теоремы ГёделяНеклассические логики
Современные модальные логики
Понятие о теории неопределенности
Элементы теории нечетких множеств и нечеткая логика
Нечеткие алгоритмыЛитература
Приложение 1. Варианты контрольных заданий по дисциплине «Дискретная математика»
Приложение 2. Варианты контрольных заданий по дисциплине
«Математическая логика»