Отношение порядка. Изоморфизм упорядоченных множеств.

Бинарное отношение на множестве А называется отношением порядка, если оно одновременно рефлективно, антисимметрично и транзитивно.

Пусть р-произвольное отображение декартового произведения

(a1,a2,...,an)(A1,A2,...An) (возможноА1=А2=...An) на множестве, состоящее из 2 элементов {1,0}. Такое отображение называется предикатом.

Совокупность тех наборов (a1,a2,...,an) которые р отображает в истину задает n-арное отношение R. RA1*A2*...*An которые однозначно определяет р.

Два упорядоченных множества называются изоморфными (одинаковыми с точки зрения структуры) если существует также биективное отображение :A1→А2 такое что если a1b=>(a)2(b)

Для изображения конечных упорядоченных множеств используется диаграмма Хассе. Идея диаграмм Хассе состоит в том, что мы не рисуем того, что мы можем установить по рефлексивности и транзитивности. Два элемента называются сравнимыми, если ab или ba. Упорядоченное множество, любые два элементы которого сравнимы, называется линейно-упорядоченным.

2^А нельзя линейно упорядочить отношением включения.

Линейно упорядоченое множество называют цепью.

9. Содержание

   • Множества. Основные понятия.
   • Операции над множествами и их свойства.
   • Декартово произведение. Разбиение множеств.
   • Алгебра множеств
   • Отношение. Бинарное отношение
   • Алгебра бинарных отношений
   • Отображение. Виды отображений
   • Отношение порядка. Изоморфизм упорядоченных множеств.
   • Алгебраические системы. Изоморфизм алгебраических систем.
   • Функции алгебры логики.
   • Формулы. Реализация функций формулами.
   • Эквивалентность формул. Свойства элементарных булевых функций.
   • Двойственные функции. Принцип двойственности
   • Разложение булевых функций по переменным. Сднф.
   • Разложение булевых функций по переменным. Скнф.
   • Полнота и замкнутость.
   • Представление булевых функций в виде полинома Жегалкина. Теорема Жегалкина.
   • Классы т0, т1.
   • Класс s.
   • Класс м.
   • Класс l
   • Задача минимизации булевых функций.
   • Задача минимизации булевых функций в геометрической постановке.
   • Сокращенные днф.
   • Тупиковые днф и решение задачи минимизации.
   • Графы. Основные понятия.
   • Орграфы. Основные понятия.
   • Маршруты. Цепи. Циклы. Связность.
   • Операции над графами
   • 30.Двудольные графы.
   • 31. Планарные графы.
   • 32. Эйлеровы и гамильтоновы графы
   • 33. Дерево. Лес
   • 34. Графическое разбиение.
   • 35. Способы задания графов
   • 36. Типы связности орграфов
   • 38. Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала.
   • 39. Задача о максимальном потоке и минимальном разрезе. Алгоритм Форда-Фалкерсона.
   • 40. Теорема Форда-Фалкерсона