- •Множества. Основные понятия.
- •Операции над множествами и их свойства.
- •Декартово произведение. Разбиение множеств.
- •Алгебра множеств
- •Отношение. Бинарное отношение
- •Алгебра бинарных отношений
- •Отображение. Виды отображений
- •Отношение порядка. Изоморфизм упорядоченных множеств.
- •Алгебраические системы. Изоморфизм алгебраических систем.
- •Функции алгебры логики.
- •Формулы. Реализация функций формулами.
- •Эквивалентность формул. Свойства элементарных булевых функций.
- •Двойственные функции. Принцип двойственности
- •Разложение булевых функций по переменным. Сднф.
- •Разложение булевых функций по переменным. Скнф.
- •Полнота и замкнутость.
- •Представление булевых функций в виде полинома Жегалкина. Теорема Жегалкина.
- •Классы т0, т1.
- •Класс s.
- •Класс м.
- •Класс l
- •Задача минимизации булевых функций.
- •Задача минимизации булевых функций в геометрической постановке.
- •Сокращенные днф.
- •Тупиковые днф и решение задачи минимизации.
- •Графы. Основные понятия.
- •Орграфы. Основные понятия.
- •Маршруты. Цепи. Циклы. Связность.
- •Операции над графами
- •30.Двудольные графы.
- •31. Планарные графы.
- •32. Эйлеровы и гамильтоновы графы
- •33. Дерево. Лес
- •34. Графическое разбиение.
- •35. Способы задания графов
- •36. Типы связности орграфов
- •38. Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала.
- •39. Задача о максимальном потоке и минимальном разрезе. Алгоритм Форда-Фалкерсона.
- •40. Теорема Форда-Фалкерсона
Декартово произведение. Разбиение множеств.
Декартовым призведением множеств называется множество всех возможных пар, такое что первый элемент взят с первого множества, второй со второго. Порядок важен.
А={a1;a2;a3} B={b1;b2)
AxB={(a1,bi);(a1,b2);(a2,b1);(a2,b2);(a3,b1);(a3,b2)}
некомуттативно
AxB≠BxA
AxB=A^2=B^2 (A=B) (Декартов квадрат)
Декартовым произведением множеств А1,А2,...,Аn называется множество всех упорядоченых последовательностей, таких что первый элемент есть первое множество..., n элемент принадлежит n множеству
Ax(BxC)={(a,d)}={(a,(b,c))} (a,b,c):a принадлежит А; b принадлежит B; с принадлежит С. d принадлежит BxC
R(A) – множество непустых подмножеств А таких, что они попарно не пересекаются и их объединение совпадает с А.
R(A)={А1,А2,… Аk}; 1)Любое А системы не пустое: Ai(i=1..k); 2)Они попарно не пересекаются: AiAj=(ij); 3)Их объеденение даёт исходное мно-во А: А1А2… Аk=A
= А1А2… Аk (*)
Само конкретное разбиение опредиляется правилом R. Элементы А1,А2,… Аk наз. классами разбиения или прямыми слогаемыми. Если для семейства А1,А2,… Аk выполняются св-ва 1-3, то их объединение наз. прямой суммой. Разбиение наз. тривиальным, если каждое из мн-в Аi одноэлементно (|Ai|=1, Ai-прямые слагаемые). Разбиение R’(A) наз. подразбиением разбиения множества R’’(A), если каждый элемент R’(A), является подмножеством некоторого элемента разбиения R’’(A). Тривиальное разбиение является подразбиением любого другого разбиения. |…|-мощность мн-ва; |А|=0; |А|=n; |A|< ; |A|= ; А={2,10,1}; R1(A)={{2},{1},{10}}; R2={{2,10},{1}}; R3={{2,1},{10}}; R4={{10,1},{2}}; R5={{2,1,10}}=A
Алгебра множеств
Пусть А — некоторое множество.
Множество всех подмножеств множества А называется булеаном на множестве А. 2^А — булеан. 2^A={{a1}, {a2}, {a3}, {a1,a2}, {a1,a3}, {a2,a3}, A,
Мощность булеана: |2^A|=2^|A|=2^n |A|=n-мн-тво n-элементов
Алгебраическая система — это множество, наделённое некоторой структурой. Сама структура задаётся при помощи операций и возможно некоторых свойств. Если над элементами булеана, как над множеством проводить опеации объединения, пересечения, дополнения до множества А, то в результате получим подмножество множества А, то есть элементы Булеана.Такое свойство называется замкнутостью.
1.А=А
2. АА=А
3. А(ВС)=(АВ)С
4.А(ВС)=(АВ)(АС)
5.(АВ)=АВ
6. АВ=ВА
7.А(ВВ)=А
Система тождеств выбирается таким образом, что любое другое тождество является их следствием. В этом случае выбранная система тождеств называется системой аксиом, а тождество называется аксиомой.
Тождества являются следствием системы аксиом, если оно может быть получено из какой-то аксиомы путём тождественных преобразований, используя только эту систему аксиом.
(АВ)=(АВ) => АВ=(АВ)=>АВ=АВ=>АВ= АВ
Система аксиом 1-7 не единственная
1')А=А
2') АА=А
3') А(ВС)=(АВ)С
4')А(ВС)=(АВ)(АС)
5') АВ=АВ
6') АВ= ВА
Операции над множ-ми можно интерпретировать как операции над некоторыми физ. объектами, тогда система аксиом трактуется как правила тождественных преобразований физичских объектов, которые рассматриваются.