Основы дискретной математики. Учебное пособие для студентов вузов РИО

Description

Предисловие Часть 1. Множества. Графы Глава 1. Теория множеств Введение 1.1. Теория "четких" множеств 1.1.1. Основные определения и способы задания множеств 1.1.2. Операции над множествами 1.1.3. Алгебра множеств и основные тождества 1.1.4. Упорядоченные наборы 1.1.5. Декартово произведение множеств 1.1.6. Соответствия на множествах 1.1.7. Отношения на множествах 1.1.8. Алгоритмы упорядоченных множетсв 1.1.9. Понятие модели Вопросы для самоконтроля 1.2. Теория нечетких множетсв и отношений 1.2.1. Основные определения. Понятие лингвистической переменной 1.2.2. Алгебра нечетких множеств 1.2.3. Нечеткие отношения 1.2.4. Алгебра нечетких отношений Вопросы для самоконтроля Глава 2. Теория графов 2.1. Общие понятия 2.2. Неориентированные и ориентированные графы 2.2.1. Основные определения и способы задания 2.2.2. Структурные характеристики графов 2.2.3. Матричное представление графов 2.2.4. Операции над графами 2.2.5. Числовые характеристики графов 2.2.6. Обходы графов. Эйлеровы графы. Гамильтоновы пути и контуры 2.2.7. Деревья. Основные определения 2.2.8. Алгоритмы построения покрывающих деревьев 2.2.9. Паросочетания и покрытия 2.2.10. Задача определения путей и кратчайших путей на графах Вопросы для самоконтроля 2.3. Графы типа сетей 2.3.1. Транспортные сети. Основыне определения 2.3.2. Теорема Форда-Фалкерсона. Алгоритм нахождения максимального потока транспортной сети 2.3.3. Сети Петри 2.3.4. Графовое представление сети Петри. Правила функционирования 2.3.5. Моделирование дискретных систем на сетях Петри Вопросы для самоконтроля Список литературы к Части 1 Часть 2. Математическая логика для инженера Раздел 1. Логические методы анализа и синтеза схем Глава 1. Теория функций алгебры логики (Алгебра логики) 1.1. Общие сведения. Историческая справка 1.2. Основные определения 1.3. Элементарные булевы функции 1.4. Функционально полные системы элементарных булевых функций 1.5. Формулы алгебры логики. Принцип суперпозиции 1.6. Основыне законы (равносильности) алгебры логики 1.7. Закон двойственности формул алгебры логики 1.8. Аналитическая запись функций алгебры логики в ДСНФ и КСНФ 1.9. Задача минимизации логической схемы 1.10. Методы минимизации функций алгебры логики 1.11. Задачи анализа и синтеза логических схем Вопрсы для самоконтроля Глава 2. Пороговая логика 2.1. Общие сведения о пороговых элементах и пороговых функциях 2.2. Функциональнвя полнота системы пороговых функций 2.3. Разновидности пороговых элементов 2.4. Пороговый элемент с регулируемыми параметрами Глава 3. Нейронная логика 3.1. Биологический нейрон как пороговый элемент 3.2. Формальная модель биологического нейрона 3.3. Логические элементы на основе формальных нейронов Глава 4. Нечеткая логика 4.1. Общие соображения 4.2. Характеристическая функция нечеткого множества. Нечеткие пременные 4.3. Операции на нечетких множествах. Законы нечеткой логики 4.4. Функции нечетких переменных 4.5. Равносильность функций нечетких переменных Глава 5. Временная логика 5.1. Понятие временной булевой функции 5.2. основные свойства временных булевых функций Глава 6. Многозначная логика 6.1. Осеновные определения. Элементарные функции k-значной логики 6.2. Нормальные формы многозначных логических функций 6.3. Функционально полные системы многозначных логических функций 6.4. Минимизация многозначных логических функций Раздел 2. Математическа логика. Анализ рассуждений и алгоритмы вывода Глава 7. Логика высказываний 7.1. Что такое правильное рассуждение? 7.2. Основные понятия и определения логики высказываний 7.3. Алгебра высказываний 7.4. Исчисление высказываний 7.5. Алгоритмы доказательства теорем в исчисдении высказываний Вопросы для самоконтроля Глава 8. Логика предикатов первого порядка 8.1. Общие сведения 8.2. основные понятия и определения логики предикатов 8.3. Алгебра предикатов 8.4. Язык описания предикатов 8.5. Логическок следование и теорема дедукции 8.6. Нормальные формы в логике предикатов первого порядка 8.7. Особенности вывода в лоогике предикатов первого порядка 8.8. Стандартизация предикатных формул Вопросы для самоконтроля Глава 9. Теоретические основы построения доказательства теорем в исчислении предикатов 9.1. Общие соображения о процедуре доказательства теорем 9.2. Универсум Эрбрана и эрбрановская база 9.3. Семантическое дерево. Теорема Эрбрана 9.4. Основные определения 9.5. Методы резолюций. Резольвента. Резолюция Вопросы для самоконтроля Глава 10. Алгоритмы вывода в исчислении предикатов первого порядка 10.1. Семантическая резолюция. Основные определения 10.2. Алгоритм семантической резолюции (PI-вывод) 10.3. Алгоритм семантической гиперрезолюции 10.4. Алгоритм семантической резолюции с упорядоченными дизъюнктами(OI-вывод) 10.5. Алгоритм линейной реолюции (OL-вывод) Вопросы для самоконтроля Глава 11. Стратегии поиска эффективыной процедедуры доказательства теорем и алгоритмы их реализации 11.1 Стратегия упрощения 11.2. Стратегия очищение 11.3. Стратегия упорядочения 11.4. Алгоритм звлечения ответа при доказательстве теорем методом резолюций Вопросы для самоконтроля Список литературы к Части 2