Дискретні структури Лекція 1. Множини та операції над ними 1.1. Основні означення 1.2. Операції над множинами 1.3. Діаграми Ейлера 1.4. Алгебра множин 1

1.1. Основні означення Множина - обєднання в одне ціле обєктів, що добре розрізняються думкою або інтуїцією. Елементи множини - обєкти, що утворюють множину. Належність елементів множині: 1) якщо m є елемент, який належить множині М, то використовується запис 2) якщо m є елемент, який не належить множині М, то використовується запис 2

Скінченна множина - множина, яка містить скінченне число елементів. Нескінченна множина - множина, що містить нескінченне число елементів. Пуста множина - множина, що не містить жодного елемента. Задання множин: 1) перерахування елементів. У разі перерахування використовують фігурні дужки {}. Наприклад, множину М цифр десяткового алфавіту можна задати у вигляді М={0, 1, …, 9}. 2) перерахування властивостей елементів Цю ж саму множину можна задати й інакше, як М={i|i – ціле, }, де справа від вертикальної риски зазначається властивість елементів цієї множини. 3

Підмножина – множина М, будь-який елемент якої дорівнює елементу множини М. - знак включення підмножини. Дві множини рівні в тому разі, коли вони складаються з одних і тих самих елементів. якщо Х=Y, то Y=X; якщо Х=Y та Y=Z, то Х=Z. 4

Порядок елементів у множині не є суттєвим. Множини {3,4,5,6} і {4,5,6,3} являють собою одну й ту саму множину. Множини не містять однакових елементів. Так, множина простих дільників числа 60 дорівнює {2,3,5}, а не {2,2,3,5}. Слід розрізняти обєкт і множину, єдиним елементом якої є цей обєкт. Так множина {1,2} становить обєкт, який є елементом множини {{1,2}}. Множини {{1,2}} і {1,2} не рівні, оскільки перша – одноелементна множина, що має єдиний елемент {1,2}, а друга має два елементи 1 і 2. 5

1.2. Операції над множинами Обєднанням (сумою) множин А і В називається множина, що складається з усіх елементів, які належать хоча б одній з множин А або В. тоді, коли х є елементом хоча б однієї з множин А або В. Приклад:{1,2,3}U{1,3,4}={1,2,3,4}. 6

Перетином (добутком, перерізом) множин А і В називається множина, що складається з елементів, які належать як до множини А, так і до множини В. Різницею множин А і В або відносним доповненням множини В до А називається множина, що складається з усіх елементів, які належать А і не належать до В. Приклад: {1,2,3} {1,3,4}={1,3} A\B або А-В Приклад:А={1,3,4,5}, B={1,2,3} А–В={4,5} 7

Універсальна (повна, одинична) множина І (позначається також U) – множина, для якої всі інші множини є підмножинами. Абсолютне доповнення множини А до універсальної множини І - множина, що визначається за співвідношенням. Основні рівності 8

1.3. Діаграми Ейлера Діаграма Ейлера для множини А (заштриховано ) Діаграма Ейлера для об'єднання двох множин А і В U A AB U 9

Діаграма Ейлера для перетину двох множин А і В Діаграма Ейлера для різниці двох множин А-В та В-А AB U AB U AB U 10

1.4. Алгебра множин Асоціативні закони для об'єднання і перетину Комутативні закони для об'єднання і перетину Дистрибутивні закони для об'єднання і перетину 11

закони ідемпотентості закони поглинання закони де Моргана 12