Множества. Основные понятия.
Множество–совокупность объектов, хорошо различимых нашей логикой или интуицией.
Множество–совокупность объектов, объединенных общим свойством.
А, К, К1, К2 – обозначения множеств. Объекты, входящие в множества наз. элементами множества. а, b, a1 – обозначения элементов множества. аК – а элемент К, аК – а не элемент К.
Два множества равны, если они состоят из одних и тех же элементов или когда они являются подмножествами друг друга. АВ, АВ
Множество, не имеющее элементов наз. пустым множеством. .
Часть множества – подмножество. ТА – Т- подмножество А (возможно Т=А). Равенство множеств означает, что они состоят из одних и тех же элементов. ТВ – Т - собственное подмножество В (ТВ). , , , – отношения включений.
Из понятия множества следует, что элементы множеств не упорядочены и не повторяются.
Имеется 2 способа задания множеств: 1)Описание; 2)Перечисление. При описании задается свойство, объединяющее элементы во множество: К={а:} (или К={а}). При перечислении перечисляются все элементы, входящие в множество: L={2,3,10}, L={a1,a2,a3}. При работе с мн-вами удобно использовать графы, язык диаграм Эйлера-Вьена. Множество наз. универсальным если любое другое множество является его подмножесвом. Обозначается I. Изображается на диаграмме Вьена как множество точек прямоугольника.
Свойства множеств: 1)А; 2)АI; 3)АА(рефлективность); 4)АВ,ВА=>А=В(антисимметричность); 5) АВ,ВС=>АС(транзитивность).
При работе с мн-вами удобно использовать графы, язык диаграм Эйлера-Вьена. Множество наз. универсальным если любое другое множество является его подмножесвом. Обозначается I. Изображается на диаграмме Вьена как множество точек прямоугольника.
I
-
Содержание
- Множества. Основные понятия.
- Операции над множествами и их свойства.
- Декартово произведение. Разбиение множеств.
- Алгебра множеств
- Отношение. Бинарное отношение
- Алгебра бинарных отношений
- Отображение. Виды отображений
- Отношение порядка. Изоморфизм упорядоченных множеств.
- Алгебраические системы. Изоморфизм алгебраических систем.
- Функции алгебры логики.
- Формулы. Реализация функций формулами.
- Эквивалентность формул. Свойства элементарных булевых функций.
- Двойственные функции. Принцип двойственности
- Разложение булевых функций по переменным. Сднф.
- Разложение булевых функций по переменным. Скнф.
- Полнота и замкнутость.
- Представление булевых функций в виде полинома Жегалкина. Теорема Жегалкина.
- Классы т0, т1.
- Класс s.
- Класс м.
- Класс l
- Задача минимизации булевых функций.
- Задача минимизации булевых функций в геометрической постановке.
- Сокращенные днф.
- Тупиковые днф и решение задачи минимизации.
- Графы. Основные понятия.
- Орграфы. Основные понятия.
- Маршруты. Цепи. Циклы. Связность.
- Операции над графами
- 30.Двудольные графы.
- 31. Планарные графы.
- 32. Эйлеровы и гамильтоновы графы
- 33. Дерево. Лес
- 34. Графическое разбиение.
- 35. Способы задания графов
- 36. Типы связности орграфов
- 38. Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала.
- 39. Задача о максимальном потоке и минимальном разрезе. Алгоритм Форда-Фалкерсона.
- 40. Теорема Форда-Фалкерсона