x-uni.com
регистрация / вход
сейчас на линии 69 чел.
x-uni.com
x-uni.com
 
Математика
Биология
Литература
Русский язык
ВИДЕО
Физика
Химия
История
Английский
 
ВИДЕО
 
 
регистрация / вход
сейчас на линии 69 чел.
Элементы дискретной математики, Ананичев Д.С., Андреева И.Ю., Гредасова Н.В., Костоусов К.В., 2015

Элементы дискретной математики, Ананичев Д.С., Андреева И.Ю., Гредасова Н.В., Костоусов К.В., 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. Автоматы и языки
Языки
Операции с языками
Автоматы. Распознаватели
Моноид переходов конечного автомата
Распознавание автоматом и моноидом
Свойства распознаваемых языков
Замкнутость множества распознаваемых языков относительно произведения и итерации
Рациональность и распознаваемость языков

Скачать бесплатно на сайте fileskachat.com
Скачать бесплатно на сайте yadi.sk

Предложения интернет-магазинов

Математика. Теория вероятностей и дискретная математика: Элементы теории, решение задач

Автор(ы): Баюк Олег Александрович, Маркарян Елена Георгиевна   Издательство: Просвещение, 2013 г.  Серия: Сложные темы ЕГЭ

Цена: 333 руб.   Купить

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


Биология. 5-9 классы. Программы для общеобразовательных организаций. ФГОС

Автор(ы): Андреева Алла Евгеньевна, Ефимова Татьяна Михайловна, Андреева Наталья Дмитриевна   Издательство: Мнемозина, 2015 г.  Серия: Биология

Цена: 145 руб.   Купить

В сборник включены программы по биологии, соответствующие Федеральному государственному образовательному стандарту общего образования второго поколения.


Программы для общеобразовательных учреждений. Биология. 5-11классы

Автор(ы): Трайтак Дмитрий Илларионович, Андреева Алла Евгеньевна, Андреева Наталья Дмитриевна   Издательство: Мнемозина, 2011 г.  Серия: Биология

Цена: 138 руб.   Купить

В сборник включены программы по природоведению и биологии для общеобразовательных учреждений. Публикуемые в сборнике нормативные документы будут полезны учителям, методистам, руководителям общеобразовательных учреждений. 2-е издание, исправленное.


Математика для гуманитариев: задачи и решения

Автор(ы): Просветов Георгий Иванович   Издательство: Альфа-Пресс, 2008 г.

Цена: 215 руб.   Купить

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

ПЕДСОВЕТ / ФОРУМ

Новости образования

Новости науки

флаг италииX-UNI рекомендует репетитора итальянского языка: yuliyavenezia (Скайп).

Репетитор по Скайпу без посредников

Неограниченная аудитория, свободный график. Начните свой бизнес здесь!