Елементи комбінаторики 2

ЕЛЕМЕНТИ КОМБІНАТОРИКИ

§ 1. Поняття множини. Операції над множинами

Поняття множини належить до первісних понять математики, якому не дається означення Множину можна уявити собі як су­купність деяких предметів, об'єднаних за довільною характерис­тичною ознакою Наприклад, множина учнів класу, множина цифр десяткової нумерації (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), множина натуральних чисел, множина зернин у даному колосі, множина букв українського алфавіту, множина точок на прямій

Предмети, з яких складається множина, називаються її елементами і позначаються малими буквами латинського алфавіту. Наприклад, а
= 5 - елемент множини цифр десяткової нумерації Для позначення множин використовують великі букви латинсь­кого алфавіту або фігурні дужки, всередині яких записуються елементи множини При цьому порядок запису елементів не має значення Наприклад, множину цифр десяткової нумерації мож­на позначити буквою М
(чи будь-якою великою буквою латин­ського алфавіту) або записати так {1, 3, 5, 2, 4, 6, 8, 7, 9, 0}

Належність предмета даній множині позначається символом , а неналежність - символом (інколи ) Наприклад, число 7 А
, де А
- множина чисел першого десятка, а число 12 A
.

Множини бувають скінченні і нескінченні. У скінченній
множині
міститься певна кількість елементів, тобто кількість елементів скінченної множини виражається натуральним чис­лом Наприклад, множина М
цифр десяткової нумерації скінчен­на і містить десять елементів. У нескінченній
множині
- нескін­ченна кількість елементів. Наприклад, множина натуральних чисел, множина точок прямої - нескінченні множини.

Множина, в якій немає жодного елемента, називається порож­ньою
і позначається символом . Наприклад, множина точок перетину двох паралельних прямих - порожня множина

Якщо множина В
складається з деяких елементів даної мно­жини А
(і тільки з них), то множина В
називається підмножиною
множини А
. У такому разі співвідношення між множинами А
і В
позначається так В
А
(читається "В
міститься в А
" або "В
— підмножина А
"). Якщо В
може й дорівнювати А
, то вживається символ В
А
. Знак називається знаком нестрогого включення, а знак - знаком строгого включення.

Порожня множина є підмножиною будь-якої множини, тобто А
.

Саму множину А
можна розглядати як підмножину А
, тобто А
А
.

Множину задають двома основними способами:

1) переліченням всіх її елементів;

2) описанням характеристичної властивості її елементів. Наприклад: а) В
= {-,,-} - множина, задана переліченням елементів; б) X
- множина коренів квадратного рівняння х²

= 25. Множина X
задана характеристичною властивістю елементів - бути коренем рівняння х²

= 25". Цю саму множину можна зада­ти і переліченням її елементів: X
= {-5; 5}.

Дві множини називаються рівними, якщо вони складаються з тих самих елементів. Наприклад, множини коренів рівняння х
²
= 25 і |x
| = 5 рівні між собою. Справді, X
= {-5; 5} і Y
= {-5; 5}, де Y
- множина розв'язків рівняння |x
|-5. Отже, X
=
Y
.

Над множинами виконуються певні операції (дії). Зазначимо три з них.

Переріз множин. Перерізом множин А і В називається множина С, яка складається з усіх тих і тільки тих елемен­тів, які належать коленій з даних множин А і В.

Приклад
1. Нехай А
- множина всіх дільників числа 32, тобто А
= {І, 2, 4, 8, 16, 32), а В
- множина всіх дільників чис­ла 24, тобто В
= {1, 2, 3, 4, 6, 8, 12, 24}. Тоді перерізом множин А
і В
є множина С
= {1, 2, 4, 8}, яка складається зі спільних дільників чисел 32 і 24.

Схематично переріз множин А
і В
можна зобразити за допо­могою фігур. Символічно позначається так: С
= А В
і читається: "С
є перерізом А
і В
".

Приклад
2. Нехай М
- множина прямокутників, N
- множина ромбів, тоді Р
= М N
- множина квадратів.

Об'єднання множин. Об'єднанням (або сумою) двох мно­жин А і В називається така множина С, яка складається з

усіх елементів множин А і В, і тільки з них.

Позначається це так: С = А В
і читається: "С
є об'єднанням А
і В
".

Якщо множини А
і В
мають спільні елементи, тобто А В
0, то кожний з цих спільних елементів береться в множину С
тільки один раз.

Приклад
3. А
={1,2, 3,4}, В
= {3, 4, 5, 6}, тоді С
= {1,2,3,4,5,6}.

Приклад
4. Q
- множина раціональних чисел, І
- мно­жина ірраціональних чисел. Тоді множиною R
всіх дійсних чисел буде об'єднання множин Q
і І
, тобто R
=
Q
І
.

Операції над множинами широко використовуються в мате­матиці та інших науках, а також у практиці. Наприклад, розв'яз­ками системи рівнянь є переріз множин розв'язків кожного рів­няння, а об'єднання їх є множиною розв'язків сукупності рів­нянь.

Віднімання множин. Доповнення множини. Різницею двох множин А і В називається така множина С, яка складається з усіх елементів множини А, що не належать множині В.

Позначається це так: С
= А \ В
і читається: "С
є різницею А
і В
".

Приклад
5. а) А
= {5,6, 8, 12}, В
= {5, 6}, тобто В
А
, тоді С
= А \ В
= {8, 12};

б) А
= {5, 6, 8, 12}, В
= {8, 12, 1, 2}, тоді С
= А\ В
= {5, 6};

в) А
= {5, 6, 12}, В
= {1, 2}, тоді С
= А \ В
= {5, 6, 12};

г) А
= {5, 6}, В
= {5,6, 12}, тобто В
А
, тоді С
= А\ В
= .

У випадку, коли А
В
, то різниця С
= А
\ В
називається доповненням
множини
В
відносно множини А
і позначаєть­ся С_А
В
.