Карточки Дискретка - Коллоквиум 1 | Quizlet

Объединение множеств

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

Какими свойствами обладает отношение, когда нельзя определить свойство симметричности однозначно ?

Симметричностью и антисимметричностью

Какими свойствами обладает отношение, когда нельзя определить свойство транзитивности однозначно ?

Транзитивностью и антитранзитивностью