Вопросы по курсу Дискретная математика
![]()
|
Свойства разности и дополнения:Определение Объединением множеств А и В называется множество, обозначаемое А ![]() ![]() ![]() Свойства объединения множеств: 1. ![]() 2. ![]() 3. ![]() 4. ![]() 5. ![]() 6. ![]() Определение Пересечением множеств А и В называется множество, обозначаемое А ![]() ![]() ![]() Свойства пересечения множеств: 1. ![]() 2. ![]() 3. ![]() 4. ![]() 5. ![]() 6. ![]() Определение Разностью множеств А и В называется множество, обозначаемое А\В, (А-В), определяемое ![]() ![]() Свойства разности множеств: 1.Если ![]() 2.ЕслиАВ,тоА\В=. 3. А \ В = А \ (А ![]() Имеют место следующие равенства: A\Ø = A. Ø\A = Ø. A\I = Ø. I\A = Ā. A\A = Ø. Определение Симметрической разностью множеств А и В называют множество, обозначаемое АΔВ (А―В), определяемое AΔB ≡ (A\B) ![]() ![]() Имеет место равенство: AΔB = (A ![]() ![]() Имеют место следующие равенства: АΔВ = BΔA – коммутативность. АΔI = Ā. АΔØ = A. Способы задания множеств. Способы задания множеств. 1. Перечислением своих элементов. A={a,b,c,...}. 2. Через описание ограничительного свойства. A={x| P(x)} - A множество таких элементов x, которые обладают свойством P(x). В дальнейшем мы будем пользоваться общепринятыми обозначениями множеств: N - множество натуральных чисел, Z - множество целых чисел, Q - множество рациональных чисел, C - множество комплексных чисел, R - множество действительных чисел, ![]() Универсальное множество. (?) Истинным, строгим или собственным подмножеством множества А называется такое его подмножество В, что В ![]() ![]() ![]() ![]() По отношению к множеству А - пустое множество и само множество А называется несобственным, нестрогим или не истинным подмножествами множества А. Таким образом, мы имеем следующие свойства множеств: 1. А ![]() ![]() ![]() ![]() 2. А ![]() ![]() ![]() 3. А ![]() ![]() ![]() 4. А ![]() ![]() ![]() 5. А ![]() ![]() ![]() ![]() 6. А ![]() ![]() ![]() ![]() 7. А ![]() ![]() ![]() ![]() Первые четыре свойства следуют из введенных ранее определений. Покажем выполнение остальных свойств. Свойство 5. Докажем его методом от противного. Пусть А ![]() ![]() ![]() ![]() Тогда существует такой элемент а ![]() ![]() ![]() ![]() Получили противоречие: а ![]() ![]() ![]() Свойство 6. Так как А ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Свойство 7. Так как В ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Если все рассматриваемые в ходе рассуждений множества являются подмножествами некоторого фиксированного множество J, то это множество называют универсальным ( для рассматриваемого набора множеств) множеством или универсом. Таким образом, универс - это такое множество, что любое рассматриваемое множество является его подмножеством. Рассмотрим множество А={a,b,c}. Найдем все его различные подмножества. Это: пустое множество ![]() ![]() Характеристическая функция множества. Характеристической функцией ХA множества А называется одноместная функция, равная 0 на элементах множества А и 1 за пределами А. Характеристическая функция называется частичной, если она не определена за пределами А. Множество А называется примитивно рекурсивным, если его характеристическая функция примитивно рекурсивна. Множество А называется частично рекурсивным, если его характеристическая функция частично рекурсивна. Множество А называется рекурсивно перечислимым, если существует двухместная частично рекурсивная функция ƒ(a,x) такая, что уравнение ƒ(a,x) = 0 имеет решение тогда и только тогда, когда а Î А. Задачу кластеризации удобно формулировать использую характеристическую функцию. Характеристическая функция может принимать два значения: 0 - если элемент не принадлежит кластеру, и 1 - если элемент принадлежит кластеру. Используя характеристическую функцию, опишем кластеры следующей матрицей разбиения: ![]() где k-ая строчка матрицы ![]() ![]() ![]() Матрица ![]() ![]() ![]() Для оценки качества разбиения используется критерий разброса, показывающий сумму расстояний от объектов до центра своего кластера. Для евклидового пространства этот критерий записывается так [1]: ![]() где ![]() ![]() ![]() Кластеризацию объектов ![]() ![]() Булеан. Пусть А произвольное конечное n- элементное множество. Найдем мощность множества P(A), |P(А)|= ![]() ![]() ![]() Для определения величины |Р(А)| воспользуемся формулой бинома Ньютона. ![]() Получаем, ![]() |