енг. Теоретический минимум. Теоретический минимум Определение множества
 Скачать 0.67 Mb.
|
Теоретический минимум: 1. Определение множества: Множество: - неупорядоченный набор уникальных элементов; - совокупность объектов произвольной природы, которые рассматриваются как единое целое; - совокупность объектов произвольной природы, объединенных общими свойствами. 2. Способ задания множества: 1) Перечисление (подходит для конечных множеств): Множество может быть задано перечислением всех его элементов ил списком. В этом случае элементы множества записывают внутри фигурных скобок. A = {1, 2, 3, 4, 5} B = {куб, шар, пирамида, конус} 2) Описанием общего (характеристического свойства, объединяющего элементы): Указание характеристического свойства элементов, т.е. такого свойства, которым обладает каждый элемент, принадлежащий множеству, и не обладает ни один элемент, который ему не принадлежит. 5 17 | x N x x A 3) Порождающая процедура описывает способ получения элементов множества из уже полученных элементов, либо из других объектов. Этот способ используется для бесконечных множеств. a) M = {1, 1, 2, 3, 5, 8, 13, 21…} 1 2 2 1 , 1 , 1 n n n m m m m m - порождающая процедура 4) Графическое задание множеств с помощью диаграмм Эйлера-Венна: 3. Равенство двух множеств: А=В, А равно В, если они состоят из одних и тех же элементов. B x A x x : A=B – Равные множества — это множества, которые включают в себя одни и те же элементы, то есть являются эквивалентными по отношению друг к другу. )) ( ) (( ) ( A x B x B x A x B A Определение через подмножества: Множество A называется равным множествe B, если множество A является нестрогим подмножеством B, а множество B является нестрогим подмножеством A. A=B ( A B B A ) 4. Счетные и несчетные множества: Бесконечное множество называется счётным, если все его элементы можно пронумеровать натуральными числами. Бесконечное множество называется несчётным, если все его элементы нельзя пронумеровать натуральными числами. 5. Булеан множества: Булеан – множество всех подмножеств множества А. Обознач. Р(А) или А 2 Теорема: Мощность булеана множества А вычисляется по формуле А 2 , А А Р 2 ) ( 6. Декартово произведение: Декартово произведение множеств - множество из всех возможных кортежей длины N (Количество множителей), элементы которых принадлежат перемножаемым множествам. AxB={(a,b)|a A b B} 7. Упорядоченная пара: Упорядоченная пара – кортеж из двух элементов. (a,b) 8. Кортеж (структурированное множество): Кортеж – последовательность элементов, или совокупность элементов, в которой каждый элемент занимает определенное место. Кортеж - упорядоченный набор фиксированной длины. Элементами данной совокупности называются компонентами кортежа. - Отличие от обычного множества: кортеж может содержать одинаковые по значению компоненты, например, точка с координатой (5, 5). 9. Равенство упорядоченных пар / кортежей: Два кортежа одинаковой размерности (две упорядоченные пары) равны тогда и только тогда, когда их одноименные компоненты совпадают. (a,b,c) = (a,b,c) 10. Свойство коммутативности: Коммутативность – переместительность, переместительный закон. A B B A A B B A 11. Свойство дистрибутивности: Дистрибутивность – распределительность, распределительный закон, свойство, связывающее сложение и умножение чисел и выражающееся тождествами: ) ( ) ( ) ( ) ( C A B A C B A C A B A C B A 12. Свойство ассоциативности: Ассоциативность – сочетательность, сочетательный закон, свойство сложения или умножения: ) ( ) ( ) ( ) ( C B A C B A C B A C B A 13. Законы поглощения: A A B A A A B A ) ( ) ( 14. Законы склеивания: A B A B A A B A B A ) ( ) ( ) ( ) ( _ _ 15. Законы де Моргана: __ __ _________ __ __ _________ ) ( ) ( B A B A B A B A 16. Бинарное отношение на множествах: Гомогенным бинарным отношением на множестве называется множество упорядоченных пар элементов этого множества. Гетерогенным бинарным отношением двух множеств называется множество упорядоченных пар, принадлежащих декартовому произведению этих множеств. 17. Способы задания бинарных отношений: 1) Правило: словесное описание (подходит для бесконечного/большого количества пар) 5 : ) , ( y B A y x 2) Перечисление (подходит для небольшого количества пар): )... 1 , 3 ( ), 2 , 1 ( Означает указать множество пар, для которых это отношение выполняется. 3) Матрица отношения: Матрицей бинарного отношения на множествах X и Y называется матрица порядка m × n, в которой элемент ij q , стоящий на пересечении i-ой строки и j-го столбца определяется так: ij q , 0 , 1 случае противном в Ry x если j i 4) График отношения: 5) Табличный: Интерпретация бинарного отношения как подмножества прямого произведения, которое изображают аналогично тому, как в декартовых координатах на плоскости изображают подмножества декартова квадрата числовых множеств. 6) Граф отношения: Построение графа отношения. Пусть X и Y – конечные множества. Граф бинарного отношения на множествах X и Y строится следующим образом: - элементы множеств X и Y изображаются точками на плоскости, - если имеет место xRy, то на рисунке изображается стрелка, ведущая от точки, соответствующей элементу x, к точке, соответствующей элементу 18. Обратное отношение: Обратным отношением для отношения B A R R называется отношение A B R R R T 1 , область определения которого – множество B, а область значений – множество A. Оно существует только тогда, когда существует отношение R. Если }, , | ) , {( B b A a b a R то }. , | ) , {( B b A a a b R T Обратное отношение - отношение, взятое в обратном порядке по отношению к данному. B A R - отношение на AxB, тогда } ) , ( : ) , {( 1 R b a a b R на BxA aRb a bR 1 19. Применение отношения: R y x xRy M x B y M R A M B A R ) , ( }, : | { ] [ : , 20. Композиция отношений: Композицией бинарных отношений , B A R C B S называется такое отношение на C A : } ) , ( ) , ( : | , : ) , {( S c b R b a B b C c A a c a S R T 21. Композитная степень отношения: Степень отношения A A R n - это композиция отношений, которая определяется следующим образом: } | ) , {( 0 1 1 A x x x id R R R R R R A o o on on 22. Теорема об ассоциативности композиции отношений: R S T R S T ) ( ) ( , B A R , C B S , D C T Пусть отношение R задано на множестве B A , отношение S задано на множестве C B , отношение T задано на множестве D C , тогда композиция R S T задана на D A , и при любой расстановке скобок результирующее множество будет одинаковым. 23. Свойство рефлексивности: Бинарное отношение R на множестве A называется рефлексивным, если каждый элемент этого множества находится в бинарном отношении с самим собой: ) ( : xRx M x - Отношение делимости; - Каждая вершина графа имеет петлю; - Главная диагональ матрицы состоит из единиц. 24. Свойство иррефлексивности (антирефлексивность): ) ( : xRx M x - Отношение неравенства или перпендикулярности; - НИ ОДНА из вершин графа не имеет петель; - Главная диагональ матрицы состоит из нулей. 25. Свойство корефлексивности: yRx xRy M y x : , (Если есть отношение, то на графе это либо петля, либо двустороннее ребро) 26. Свойство симметричности: yRx xRy M y x : , (Если есть отношение, то на графе это либо петля, либо двустороннее ребро) - отношение равенства, параллельности; - в графе есть ребро (у,х), если есть ребро (х,у); - симметрия матрицы относительно главной диагонали. 27. Свойство асимметричности: ) ( : , yRx xRy M y x - если в графе есть ребро (х,у), то точно НЕТ ребра (у,х) (на графе нет двусторонних рёбер и петель); 28. Свойство антисимметричности: y x yRx xRy M y x : , (На графе нет двустронних ребер) -отношение “<=”. 29. Свойство транзитивности: xRz yRz xRy M z y x : , , (Если есть путь из x в y и путь из y в z, то есть путь из x в z) - отношение параллельности прямых; - если есть ребра (х,у) и (у,z), то есть и ребро (x,z); - отношение “<”. 30. Свойство интранзитивности (антитразитивности): ) ( : , , xRz yRz xRy M z y x (Если есть путь из х в у и путь из у в z, то нет пути из x в z) (Петель нет) - отношение “больше на 4”. 31. Свойство евклидовости: yRz xRz xRy M z y x : , , (Если есть путь из x в y и путь из x в z, то есть путь из y в z) 32. Свойство связности: 2 , : , , A R xRz xRy y x A y x (У графа одна компонента связности) 33. Отношение эквивалентности: В отношении эквивалентности соблюдаются рефлексивность, симметричность и транзитивность (т.е. у каждой вершины есть петля, каждое ребро двустороннее) 34. Класс эквивалентности: ) : , ( : y x Г y x R Г (Г максимально по включению) Класс эквивалентности – подмножества, образованные в результате разбиения множества отношением эквивалентности Они попарно не пересекаются, а их объединение дает исходное множество. Обозначение: ] [ 0 x Г Г Опр Порождающий элемент класса эквивалентности – некоторый элемент, находящийся в отношении R со всеми элементами соответствующего класса. } : { aRx x a Обозначения: [a] – класс эквивалентности, порожденный элементом a. R A - множество всех классов эквивалентности по отношению R. 35. Разбиение множества: Разбиением множества A называется система множеств i А такая что: A A A i i : , i A Ø, A A U i i , j i A A j i : Ø 36. Разбиение множества на классы эквивалентности: Разбиением множества на классы эквивалентности называется разбиение множетсва отношением эквивалентности. } | ] {[ / A x x A A R R R 37. Теорема про разбиение и классы эквивалентности: Для того, чтобы отношение R позволяло разбить множество X на классы, необходимо и достаточно, чтобы R было отношением эквивалентности. - разбиение А R A по некоторому отношению эквивалентности R. 38. Отношение предпорядка: Отношение предпорядка – бинарное отношение, которое обладает такими свойствами, как рефлексивность и транзитивность. ( ). 39. Отношение частичного порядка (нестрогого порядка): Отношение частичного порядка – бинарное отношение, которое обладает такими свойствами, как рефлексивность, транзитивность и антисимметричность. ( , предпорядок + антисимметричность) 40. Отношение линейного (полного) порядка: Отношение полного (линейного) порядка – бинарное отношение, которое обладает такими свойствами, как рефлексивность, транзитивность, антисимметричность и связность. ( , частичный порядок + связность) 41. Отношение строгого порядка: Отношение строгого порядка – бинарное отношение, которое обладает такими свойствами, как иррефлексивность, транзитивность, антисимметричность и связность. ( , асимметричность + транзитивность) 42. Частично упорядоченное множество: Частично упорядоченным множеством называется множество, на котором задано отношение частичного порядка (пара , M , где M – множество, а - отношение частичного порядка на M). 43. Линейно упорядоченное множество: Линейно упорядоченным множеством называется частично упорядоченное множество, все элементы которого попарно сравнимы. 44. Диаграмма Хассе: Диаграмма Хассе – графовая визуализация частично упорядоченного множества. (Конкретно, для частично упорядоченного множества , S диаграмма представляет каждый элемент S как вершины на плоскости и отрезки или кривые, идущие вверх от элемента x к элементу y, если x y и не существует элемента z, для которого x < z < y). 45. Минимальный/максимальный элемент в ЧУМе: Элемент M a называется минимальным, если не существует элемента b < a. Другими словами, a – минимальный элемент, если дл любого элемента M b либо b > a, либо b = a, либо b и a несравнимы. (Локальный минимум) Элемент M a называется максимальным, если не существует элемента b > a. Другими словами, a – максимальный элемент, если для любого элемента M b либо b < a, либо b = a, либо b и a несравнимы. (Локальный максимум) 46. Наименьший/наибольший элемент в ЧУМе: Элемент a называется наименьшим, если для любого элемента M b имеет место неравенство a b Элемент a называется наибольшим, если для любого элемента M b имеет место неравенство a b 47. Цепь и антицепь: Если частичный порядок R таков, что для любых двух элементов M y x , либо R y x ) , ( , либо R x y ) , ( , то говорят, что множество M является цепью; если же частичный порядок R таков, что для любых различных M y x , ни одно из включений - R y x ) , ( , R x y ) , ( - не выполняется, то говорят, что M является антицепью. 48. Замыкание отношения: Замыкание отношения R относительно свойства P – минимальное по включению множество, подмножеством которого является R, обладающее заданным свойством P. Рефлексивное замыкание: o r R - рефлексивное отношение o A r id R A a a a R R R } | ) , {( Симметричное замыкание : 56. Функция (тотальная): (Функциональное + тотальное отношение) Функция называется тотальное, если для любого х определено значение у. : хRy х 57. Инъекция: Инъекция – инъективная функция (Любому у соответствует не более 1 х) 58. Сюръекция: Сюръекция – сюръективная функция (Для любого у существует х) 59. Биекция: Биекция – функция, которая является и сюръективной, и инъективной. (Любому у соответствует только 1 х) |
S
R - симметричное отношение o
}
)
,
(
|
)
,
{(
1
R
b
a
a
b
R
R
R
R
R
S
Транзитивное замыкание: o
t
R - транзитивное отношение o
}
:
|
)
,
{(
2
bRc
aRb
b
c
a
R
R
R
R
R
o
t
o
49. Сокращение отношения:
Сокращение отношения относительно свойства P – минимальное по включению подмножества R, не обладающее заданным свойством P.
Рефлексивное замыкание: o
r
R - иррефлексивное отношение o
A
r
id
R
A
a
a
a
R
R
R
\
}
|
)
,
{(
\
Симметричное замыкание : o
S
R - антисимметричное отношение o
S
R
R
Транзитивное замыкание: o
t
R - антитразитивное отношение o
ot
o
o
t
R
R
R
R
R
R
R
R
\
\
\
3 2
50. Функциональное отношение (право-уникальное):
Каждому элементу из X соответствует не более одного элемента Y
)
(
)
(
)
(
:
,
,
z
y
xRz
xRy
Y
z
y
X
x
51. Инъективное отношение (лево-уникальное):
Каждому элементу из Y соответствует не более одного элемента X
)
(
)
(
)
(
:
,
,
,
z
x
zRy
xRy
Y
z
y
X
z
x
52. Сюръективное отношение (право-тотальное):
Каждому элементу из Y соответствует не менее одного элемента X
)
(
:
:
xRy
X
x
Y
y
53. Лево-тотальное отношение:
Каждому элементу из X соответствует не менее одного элемента Y
)
(
:
:
xRy
Y
y
X
x
54. Отношения соответствия:
Синоним бинарного отношения. Виды:
One-to-one (инъективное и функциональное)
One-to-many(инъективное и не функциональное)
Many-to-one(не инъективное и функциональное)
Many-to-many(не инъективное и не функциональное)
55. Частичная функция (неопределенная):
(Функциональное отношение) Функция называется частичной, если существует такой х, что для него не существует значения у.
xRy
x :
Обозначение:
A
f :
→