85693 (Комбінаторика)

Розділ I. Елементи теорії множин

§1.1. Поняття множини

Поняття множини є одним з фундаментальних у математиці. Воно належить до понять яким не можна дати строге означення, тобто до так званих первісних, які не можна визначити через простіші поняття. Інтуєтивно множину розуміють як сукупність (сімейство, набір, зібрання, клас) деяких, обєктів об’єднаних за певною ознакою чи властивістю. Наприклад; множина студентів першого курсу, сукупність тих із них, які здали вступні екзамени без трійок і сімейство зірок Великої Ведмедиці, система трьох рівнянь з 3-ма невідомими, множина цілих чисел.

Об’єкти, із яких складається множина, називаються її елементами. Множини позначається великими буквами, а її елементи малими. Те, що елемент а належить множені А записується так а А. Запис а є А або а А означає, що елемент а не належить множені А.

Окремі найважливіші множини мають загальноприйняте позначення

• N – множина натуральних чесел (1, 2, 3, 4…)

• Z – множина цілих чисел (…-3, -2, -1, 0, 1, 2, 3…)

• Q – множина раціональних чисел (Z + дробові числа)

• I – множина всіх ірраціональних чисел

• R – множина дійсних чисел ( Q + ірраціональні чисела)

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

Множина, яка містить скінчену кількість елементів називається скінченою.

Запис A={a₁, a₂, a₃… a_n} означає, що множина А скінчена і містить n елементів. Множина Х={x₁, x₂… , x_n….} – є незкінченою. Множина, яка не містить жодного елементу називаєтся порожньою і позначається символом .

Приклади: Множина дійсних коренів рівняння x²+1=0, множина усіх цілих чисел, що діляться на 4, але не діляться на 2.

Нехай P(x) – деяка властивість (закон, правило, форма) числа х, тоді запис

{x| P(x)} означає множину всіх тих чисел х, для яких виконується властивість Р(х). Наприклад:

1. {x|x є R, x² + 3x + 4 =0} множина тих дійсних чисел х, які є розв’язками рівняння x² + 3x + 4 =0.

2. А={x| x є z, |x|≤100} – множина тих цілих чисел модуль яких не більший за 100, тобто елеменетами множини А є цілі числа по порядку від -100 до +100.

Множину можна подати у вигляді відрізку на числовій осі:

x

-3 -2 -1 0 1 2 3 4 5 6

мал.1.1

А={x| x є R, 2 ≤ x < 5} A=[2,5)

Числові проміжки позначаються так:

Нехай а і b – дійсні числа, причому а

Розглянемо числові множини.

• [a; b] = {x|a ≤ x ≤ b } – закритий відрізок, сегмент;

• (a; b) = {x|a < x < b } – відкритий інтервал;

• (a; b] = {x|a < x ≤ b } – напівінтервал, напіввідкритий інтервал,

• [a; b) = {x|a ≤ x < b } – напівсегмент;

• (- ∞; + ∞) = {x|- ∞ < x < + ∞ } – нескінченно відкритий інтервал.

Введемо інтервал, що називається околом точки. Нехай х₀ – довільне дійсне число. Околом точки х₀ називається будь-який інтервал (α; β), що містить цю точку, тобто α < x₀ < β. Так околом точки x₀ = 1 є інтервал ( - 0,5; 1,5), (0,2) і т. д.

Інтервал ( x₀ – Е, x₀ + Е ), де Е > 0 називається Е – околом точки х₀, при цьому точку х₀ називають центром, а число Е – радіусом околу. Цей окіл буде досить малий, якщо число Е теж буде мале.

Нехай задано дві множини А і В. Якщо кожен елемент множини А є елементом мнгожини В, то множину А називають підмножиною множини В і пишуть А В (А міститься в В).

Наприклад N Z. Очевидно, що кожна множина є своєю підмножиною, а порожня множина є підмножиною будьякої множини.

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

Множину, різні підмножини якої доводиться розглядати в процесі вивчення якогось питання, називають універсальною множиною.

У поцесі вивчення множин і функцій бувають корисними певні графічні зображення. У випадку множин застосовується діаграми Ейлера-Венна. На цих діаграмах схематично зображається універсальна множина у вигляді прямокутника, а різні підмножини універсальної множини у вигляді кругів.(мал.1.2).

А не має спільних елементів з В і С , а В і С мають спільні елементи.

мал.1.2

§1. 2 Операції над множинами. Об’єднання і переріз двох множин.

Об’єданням двох множин А і В, називається множина А U В, елементи якої належать хочаб одній із цих множин.(мал.1.3)

мал.1.3

Об’єдання декількох множин.

A_i = A₁ U A₂ U A₃ U…U A_n

A_i ={x | x є А₁ або х є А₂ або х є А₃ або …х є А_n }

Перерізом двох множин А і В називається множина А ∩ В елементи якої належать як і множині А, так і множені В. (мал.1.4)

А ∩ В={x | х є А і х є В}

A_i={x | x є А₁ і х є А₂, х є А₃…х є А_n}

мал.1.4

Властивості об’єдання і перерізу множин:

1. Комутативний (переставний) закон

А U B = В U А;

А ∩ В = В ∩ А;

1. Асоціативний (сполyчний) закон.

А ∩ (В ∩ С) = (А ∩ В) ∩ С

А U (В U С) = (А U B) U С

1. Дистрибутивний (розподільний) закон.

А U (В ∩ С)=(А U B) ∩ (А U С)

А ∩ (В U С)=(А ∩ В) U (А ∩ С)

1. А U Ø = А.

2. А ∩ Ø = Ø.

Ці закони легко довести за допомогою діаграм. Доведемо 3-й дистрибутивний закон:

А U (В С) = (А U B) ∩ (А U С)

А U (В U С) (А U B) ∩ (А U С)

мал.1.5 мал.1.6

А ∩ (В U С)=(А ∩ В) U (А ∩ С)

А ∩ (В U С) (А ∩ В) U (А ∩ С)

мал.1.7 мал.1.8

§1. 3 Різниця і доповненя множин.

На відміну від об’єднання і перізу множин, операція віднімання визначається лише для двох множин якщо вони перетенаються.

Різницею множин А та В називається множина А\В, яка складається зусіх тих елементів, які належать множині А і не належать В.(мал.1.9)

А \ В = {x | x є A I x ¢ B}

мал.1.9

Властивості різниці :

• А \ В ≠ В \ А – не комутативна .

• А \ (В \ С) ≠ (А \ В) \ С – не асоціативна

• А U Ø = А.

• А ∩ Ø = Ø.

• (B U C) \ A=(B \ A) U (C \ A) – дисрибутивний закон віднімання відносно об’єдання;

• (B ∩ C) \ A = (B \ A) ∩ (C \ A) – дистрибутивний закон віднімання відносно перерізу;

Якщо А є В, то різницю В \ А називають доповненням множини А до множини В і записують - = В \ А

мал.1.10

Отже, доповненням до підмножини А в множину В називається множина всіх елементів із множини В, які не належать А

Властивості доповнення, якщо А В

Для довільних підмножин А і В універсальної множини М, доповнення до множин А і В дорівнюють перерізу множин , а доповнення до перізу множин А і В дорівнює об’єднанню їх доповнень .

Доведемо цей закон за допогою діаграм Ейлера – Венна:

1) ||| = ||| =

||| =

мал.1.11 мал.1.12

2)

||| = ||| -

# =

мал.1.3 мал.1.4

Розділ 2. МНОЖИНИ З ВІДНОШЕННЯМ

§ 2. 1. Упорядковані пари. Прямий (декартів) добуток множин.

Множини {1,5} і {5,1}, що містять одні і ті ж самі елементи, рівні, причому запис порядку їх елементів не має значення. Проте, якщо розглядати на площині дві точки А (1,5) і В (5,1), то порядок запису їх координат (1 ; 5) має принципове значення. Можна навести і інші приклади, коли треба врахувати порядок розміщення елементів множини (вектор на площині, вектор у просторі). У зв’язку з цим вводиться поняття упорядкованої сукупності об’єктів, зокрема упорядкованої пари.

Упорядкована пара це двоелементна множина, елементи якої розміщені в певному порядку.

Якщо а є А і b є В, то пару утворену з цих елементів позначають (a; b).

Елемент а називають лівою (першою) координатою (компонентою), а

b – правою (другою) координатою упорядкованої пари (а; b).

Множини А і В тут нерівноправні. При утворенні пари ставимо на перше місце елемент з А, а на друге – елемент з В. Припустимо, що користуючись таким правилом, ми утворили всі можливі пари, в яких на першому місці стоїть елемент з А, а на другому – з В. Множина всіх цих пар і називається прямим добутком.

Прямим (декартовим) добутком множин А і В називається множина усіх можливих пар, перші елементи яких належать множині А, а другій множині В і позначається А х В.

Отже, А х В = {(а; b)| а є А, b є В}

Декартів добуток множин не комутативний

А х В ≠ В х А

А х В = В х А лише тоді, коли А = В або одна із множин порожня.

Щодо асоціативного закону, то йому декарті добуток не підлягає навіть тоді, коли множини А, В і С рівні. Отже, якщо А ≠ Ø, то А х (А х А) ≠ (А х А) х А.

Для прямого добутку справедливі такі дистрибутивні закони:

(А В) х С = (А х С) (В х С)

А х (В С) = (А х В) (А х С)

(А ∩ В) х С = (А х С) ∩ (В х С)

А х (В ∩ С) = (А х В) ∩ (А х С)

А х (В \ С) = (А х В) \ (А х С)

Декартів добуток АхА називають декартовим квадратом і позначається

А ² = А х А = {(a, b) | а є А, b є А}

Декартів добуток множин А, В, С визначається так само як і декартів добуток двох множин

А х В х С = {(a, b, с) | а є А, b є В, с є С}

Декарті добуток А х А х А називається декартовим кубом і позначається

А ³ = А х А х А

Якщо множину дійсних чисел R = (- ∞: + ∞) можна ототожнювати з числовою прямою, то декартів квадрат R х R дійсних чисел можна ототожнювати з числовою площиною. Очевидно, R х R – сукупність всіх можливих упорядкованих пар дійсних чисел (х; y).

Таким чином, числову площину можна розглядати як прямий добуток числової вісі на себе. Якщо представити собі два екземпляри числової вісі, які перетинаються в точці О під прямим кутом, то їх можна розглядати як координатні вісі прямокутної декартової системи на площині.

У зв’язку з цим прямий добуток множин і називають декартовим.

§ 2. 2. Бінарні відношення. Способи задання відношень.

Поняття відношень між множинами відносяться до числа фундаментальних понять математики. І не тільки тому, що воно лежить в основі визначення таких важливих понять математики, як функції і відображення, але й тому, що в будь–якій науці вивчаються не тільки самі об’єкти, але і зв’язки між ними.

Розглянемо бінарне відношення, тобто відношення між двома елементами однієї або різних множин.

Спочатку розглянемо приклад бінарного відношення між елементами двох множин А і В.

А = {Сашко, Борис, Володя, Галя, Таня, Оленка}