Элементы дискретной математики, Ананичев Д.С., Андреева И.Ю., Гредасова Н.В., Костоусов К.В., 2015

Элементы дискретной математики, Ананичев Д.С., Андреева И.Ю., Гредасова Н.В., Костоусов К.В., 2015.

  В учебном пособии рассматриваются элементы дискретной математики: логические исчисления, предикаты, булевы функции, комбинаторика, теория графов, автоматы и алгоритмы. Приведено решение типовых задач.
Предназначается для студентов всех форм обучения всех специальностей.




Исчисление предикатов.
Метод доказательства формул, содержащих переменные, путём непосредственной подстановки в них предметных констант называется методом интерпретаций, или методом моделей. Подстановка констант позволяет интерпретировать формулу как содержательное утверждение об элементах конкретного множества. Поэтому такой метод, апеллирующий к содержательному смыслу интерпретированной формулы называют семантическим, то есть смысловым. Это удобно при доказательстве выполнимости формул или их неэквивалентности, поскольку и в том, и в другом случае достаточно найти одну подходящую подстановку (интерпретацию).

Метод интерпретации можно применять и для исследования истинности формул на конечных предметных областях, так как если область М конечна, М={m1,m2>...,mn}, то кванторы выражают конечные формулы логики высказываний:
X : P(X,Y) = Р(m1)& Р(m2)&...& Р(mn),
X : P(X,Y) = P(m1)v P(m2)v...v Р(mn).

В этом случае все кванторные формулы можно заменить указанным способом и получить, содержащие только символы предикатов и логических операций, после чего проверить истинность можно конечным числом подстановок констант.

Для большинства же предметных областей доказательство тождественной истинности формул методом интерпретаций связано с большими трудностями. Поэтому применяется другой приём — аксиоматизация, т. е. построение формальной системы и порождение исследуемых формул из аксиом с помощью процедур вывода.

Содержание
1. Логические исчисления
Множество, отношения, функции
Множества
Основное свойство множеств
Способы задания множеств
Операции с множествами
Свойства  А, В, С
Отношения
Основное свойство
Теорема (об отношениях эквивалентности)  
Структуры порядка
Операции с отношениями
Функции
2. Предикаты
Операции над предикатами
Кванторы
Предикатные формулы. Тавтологии
Исчисление предикатов
3. Булевы функции
Определение и примеры
Суперпозиция функций
Тождества
Дизъюнктивная нормальная форма БФ
Полиномы Жегалкина
Замкнутые классы БФ
Теорема Поста
4. Комбинаторика
Основные правила
Элементарные комбинаторные функции
Свойства числа сочетаний
Задача (о кроликах)
5. Теория графов
Определение и задание графа
Операции с множествами
Изоморфизм графов
О сложности алгоритмов
Маршруты
Связность
Эйлеровы пути
Деревья
Потоки в сетях
Алгоритм поиска максимального потока
Расстояние в графах
Двудольные графы
Алгоритм проверки двудольности связного графа
Паросочетание
Плоские и планарные графы
6. Автоматы и языки
Языки
Операции с языками
Автоматы. Распознаватели
Моноид переходов конечного автомата
Распознавание автоматом и моноидом
Свойства распознаваемых языков
Замкнутость множества распознаваемых языков относительно произведения и итерации
Рациональность и распознаваемость языков/



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Элементы дискретной математики, Ананичев Д.С., Андреева И.Ю., Гредасова Н.В., Костоусов К.В., 2015 - fileskachat.com, быстрое и бесплатное скачивание.

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


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




Теги: учебник по математике :: математика :: Ананичев :: Андреева :: Гредасова :: Костоусов