Looks like no one added any tags here yet for you.
Объединение множеств
A ∪ B - множество, состоящее из элементов принадлежащих хотя бы одному из множеств A или B
Дополнение множества
¬А - множество, состоящее из элементов, принадлежащих универсуму и одновременно не принадлежащих множеству А
Симметрическая разность множеств
A △ B - множество, из элементов, принадлежащих либо только А, либо только В
Свойство коммутативности (закон перестановки)
Результат операций не зависит от порядка аргументов (от перестановки аргументов результат не меняется).
Свойство дистрибутивности (распределительный закон)
Пересечение A с объединением B и C равно объединению пересечений А с В и А с С. Объединение А с пересечением В и С равно пересечению объединений А и В с А и С.
Критерий равенства двух множеств (метод двух включений)
А=В тогда и только тогда, когда каждый элемент из А принадлежит В и каждый элемент из В принадлежит А.
Равные множества (определение)
Множества равны тогда и только тогда, когда они состоят из одних и тех же элементов.
Свойсиво ассоциативности
От изменения расстановки скобок результат операции меняться не будет.
А ∩ (В ∩ С) = (А ∩ В) ∩ С
А ∪ (В ∪ С) = (А ∪ В) ∪ С
Законы Де Моргана
Дополнение объединения множеств равно пересечению их дополнений
Бинарное отношение на множествах - ...
Бинарным отношением (англ. binary relation) R из множества A в множество B называется подмножество прямого произведения A и B и обозначается: R⊂A×B.
Способы задания бинарных отношений
1) Перечислить
2) По правилу
3) Таблица/Прямоугольная система координат
4) Матрица
5) Графически (овалы с линиями)
6) Графом (точки, дуги, петли и другое)
Область определения отношения - ...
Область значений отношения - ...
- множество всех первых
координат упорядоченных
пар из R - "Dom (R)".
- множество всех вторых
координат упорядоченных
пар из R - "Im (R)".
Обратное отношение - ...
- отношение, взятое в обратном порядке по отношению к данному.
Существует bR^-1a тогда и
только тогда, когда
существует аRb, а значит должно быть задано
R = { (y, x) | x из Х, y из Y}
Множество - ...
- совокупность объектов произвольной природы, которые рассматриваются как единое целое
Способы задания множеств
1) Перечисление
2) По правилу
3) Порождающая процедура
4) Диаграммы Венна
5) Аналитический (Через другие множества)
Подмножество - ...
Отличие собственных и несобственных подмножеств
А является подмножеством множества В, если каждый элемент множества А принадлежит множеству В;
Несобственные подмножества для А: А и пустое множество;
Собственные - все остальные
Булеан множества - ...
- множество всех подмножеств множества А, обозначается Р(А) или 2^A
Пересечение множеств
A ∩ B - множество, состоящее из элементов, одновременно принадлежащих и А, и В
Разность множеств
A - B (A / B) - множество, состоящее из элементов принадлежащих множеству А и не принадлежащих множеству В
Декартово произведение множеств - ...
А х В - множество всех упорядоченных пар, где на первой позиции стоит элемент из множества А, а на второй из множества В.
Прямое произведение 4-х множеств - ...
A x B x C x D - множество всех упорядоченных четверок, где на первой позиции стоит элемент из множества А, на втором из множества В, на третьем из множества С, а на четвертом из множества D.
Кортеж (вектор) - ...
- упорядоченный набор из произвольных n элементов (х₁, х₂, ..., хₙ).
Равенство упорядоченных пар/кортежей - ...
Кортежи равны, если имеют одинаковую длину и их элементы с одинаковыми номерами совпадают.
Если разной длины, то не сравнимы
Законы поглощения
Объединение первого множества с пересечением его со вторым множеством равно изначальному множеству. А ∪ (А ∩ В) = А
Пересечение первого множества с объединением его со вторым множеством равно изначальному множеству. А ∩ (А ∪ В) = А
Законы склеивания
Объединение пересечения первого множества со вторым и пересечения первого множества с дополнением второго равно первому множеству.
(А ∩ В) ∪ (А ∩ ¬В)=А
Пересечение объединения первого множества со вторым и объединением первого множества с дополнением второго равно первому множеству.
(А ∪ В) ∩ (А ∪ ¬В)=А
Композиция отношений
Композиция отношений R⊆A×B и S⊆B×C есть отношение T⊆A×C, такое что:
T = (R ∘ S)
{(a, c): ∃b∈B: (a,b)∈R и (b, c)∈S}
Степень отношения
Степень отношения R^n ⊆ A×A, определяется следующим образом:
R^n=^(n−1)∘R;
R^1=R;
R^0={(x,x): x∈A}
Теорема об ассоциативности композиции отношений (формулировка)
Для любых трех отношений R, S и T таких, что композиции R ∘ S и S ∘ T определены, выполняется равенство (R ∘ S) ∘ T = R ∘ (S ∘ T).
Порядок выполнения композиции отношений не влияет на результат. (R ∘ S) ∘ T = R ∘ (S ∘ T)
Симметричное отношение - ...
- отношение в котором для каждой пары элементов множества типа (a, b) выполнение отношения aRb влечет выполнение bRa
R - симметрично если для ∀a,b ∈A: aRb ⇒ bRa
Асимметричное отношение - ...
- отношение, в котором для каждой пары элементов множества типа (a, b) выполнение отношения aRb не влечет выполнение bRa.
(R - асимметрично если для ∀a,b ∈ A: aRb ⇒ ¬ bRa)
Антисимметричное отношение - ...
- отношение, в котором для каждой пары элементов множества (a, b) выполнение aRb и bRa влечёт a=b.
(R - антисимметрично если для ∀a,b ∈ A: aRb ∧ bRa ⇒ a=b)
Несимметричное отношение - ...
- отношение, при котором не у всех пар есть обратные.
(a,b,с,d ∈ A: aRb ∧ bRa и cRd ∧ ¬dRc)
Рефлексивность - ...
- свойство, говорящее, что каждый элемент множества находится в отношении R с самим собой
Антирефлексивность - ...
- свойство, говорящее, что каждый элемент множества не находится в отношении R с самим собой
Свойство транзитивности отношения
Отношение R транзитивно, если для любого элемента a, b, c принадлежащего множеству A верно, что: если есть aRb и bRс, то есть и aRc (aRb и bRc ⇒ aRc)
Нетранзитивность
Отношение R нетранзитивно, если есть и транзитивные, и антитранзитивные тройки в отношении
Нерефлексивность
Отношение R нерефлексивно, если есть элементы, которые относятся сами к себе, а также те, которые не относятся сами к себе (a ,b ∈ A: (aRa) и ¬(bRb))
Свойство антитранзитивности отношения
Отношение R антитранзитивно, если выполняется условие: из a есть путь в b, а из b есть путь в c, тогда НЕ может быть пути из a в c (aRb и bRc ⇒ ¬(aRc))
Замыкание отношения относительно свойства
Замыкание R относительно свойства P − минимальное по включению надмножество R, обладающее свойством P.
Отношение эквивалентности
Отношение, которое рефлексивно, симметрично и транзитивно.
Классы эквивалентности - ...
- подмножества, образованные в результате разбиения множества, которое является отношением эквивалентности.
Порождающий элемент
Некоторый элемент находящийся в отношении R, со всеми элементами соответствующего класса.
Разбиение множества
Множество непустых подмножеств множества А, так что:
1) подмножества попарно не пересекаются
2) объединение этих подмножеств равно исходному множеству
Теорема про разбиение и классы эквивалентности
<A> - разбиение A, тогда и только тогда, когда <A> = [A] по некоторому отношению R
или
Если R - отношение эквивалентности на A, то множество классов эквивалентности [A] от R образую разбиение <A>
Отношения строгого и нестрогого частичного порядка
Отношение строгого частичного порядка — отношение на множестве, обладающее свойствами антирефлексивности, асимметричности и транзитивности.
Отношение нестрогого частичного порядка Partial order — отношение на множестве, обладающее свойствами: рефлексивности, антисимметричности и транзитивности.
Отношения строгого и нестрогого линейного порядка
Отношение строгого линейного (полного) порядка Strict linear (total) order — отношение строгого частичного порядка, в котором для любых двух элементов a и b существует либо aRb, либо bRa.
Отношение нестрогого линейного (полного) порядка — отношение нестрогого частичного порядка, в котором для любых двух элементов a и b существует либо aRb, либо bRa.
Отношение соответствия
1) Одно-однозначное (Взаимно-однозначное):
Каждому элементу из A соответствует ровно 1 элемент из B.
2) Одно-многозначное:
Каждому элементу из множества A ставится в соответствие несколько элементов из множества B, но каждому элементу из B ставится в соответствие только 1 элемент из A.
3) Много-однозначное:
Каждому элементу из множества A ставится в соответствие только один элемент множества B, но каждому элементу из B ставится в соответствие несколько элементов из A.
4) Много-многозначное:
Каждому элементу из множества A ставится в соответствие несколько элементов множества B и каждому элементу из B соответствует несколько элементов из A
Линейно упорядоченное множество
Для любого a, b принадлежащих множеству A существует только либо aRb, только либо bRa
(a и b - сравнимы)
Частично упорядоченное множество
Не для всех a, b принадлежащих A справедливо отношение R aRb или bRa
(не все a и b сравнимы)
Функциональное отношение
Функциональное отношение - это бинарное отношение xRy, в котором каждому элементу x принадлежащему множеству X, соответствует не более одного элемента y принадлежащего множеству Y
Частично определена (Не доопределена) функция
Если в отношение существует x принадлежащий множеству X, такой, что в отношении нет пары xRy
Какими свойствами обладает отношение, когда нельзя определить свойство симметричности однозначно ?
Симметричностью и антисимметричностью
Какими свойствами обладает отношение, когда нельзя определить свойство транзитивности однозначно ?
Транзитивностью и антитранзитивностью