Основна. 1. Новиков Ф.А. Дискретная математика для программистов

1. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001.- С.19-26.

2. Коршунов Ю.М. Математические основы кибернетики. – М.: Энергоатом-издат, 1987. - С.24-44.

Додаткова

3. Сигорский В.П. Математический аппарат инженера. – К.: Техника, 1975. - С.86-97.

4. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986 - С.6-10.

Для практичних занять

5. Методичні вказівки і завдання до контрольних робіт з дисципліни «Основи дискретної математики» для студентів заочної форми навчання фахів 6.0804, 6.0915 / О.М. Мартинюк. – Одеса: ОНПУ, 2001. – С.4-6.

Лекція 2. Рівняння. Покриття і розбивки. Потужність

Вступ

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

Лекція містить три підрозділи:

2.1. Рівняння

2.2. Покриття і розбивки

2.3. Потужність множин. Зчисленні і континуальні множини.

2.1. Рівняння

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

1. Відповідно до тотожності 18 рівність перетвориться в симетричну різницю його лівої і правої частин, що прирівнюється (.

2. Отримане рівняння перетвориться до вигляду (MÇX)È(NÇ`X)=Æ де М и N деякі множини, що не містять Х.

3. Тому що об'єднання множин порожньо, якщо кожне з поєднуваних множин порожнє, перетворене в п.2 рівняння можна замінити системою двох рівнянь МÇC=Æ і NÇ`C=Æ.

4. Відповідно до тотожності 17 пари рівнянь п.3 мають сенс тоді і тільки тоді, коли NÌC і CÌ`M. Значить умова існування розв’язання - NÌ`M, а розв’язання рівняння - будь-яка множина Х така, що NÌCÌ`M.

Приклад. CÈС=D: 1. (CÈC)-D=Æ.

2. (CÈC)Ç`D)È ((XÈC)ÇD)=... =(`DÇC)È((C-D)Ç`C)=Æ.
3. `DÇC=Æ і (C-D)Ç`C=Æ.
4. Умова (C-D)ÌD чи CÌD; розв’язання (C-D)ÌCÌD.

2.2. Покриття і розбивки

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

Р={M_і|1 £ і £½M½, Æ ¹ M_і, M_і Ì M, ÈM_і = M}

Визначення. Розбивкою непорожньої множини М називається множина R його власних попарно непересічних підмножин, об'єднання яких дорівнює М:

R={М_і|1 £ і £ ½M½, Æ ¹ M_і, M Ì M, M_і Ç M=Æ, ÈM_і = M}

Підмножини множини М, що входять у покриття Р (розбивка R), тобто М₁, М₂, М₃,..., М_|M|, називаютьсякласами чи блоками покриття Р (розбивки R) і позначаються додатковими фігурними дужками: Р={{a, c}, {b, d, e}}, іноді – надкресленням без фігурних дужок.

Розбивка множини називається елементною, якщо кожен її клас - одноелементна множина, розбивка називається цілою, якщо складається з єдиного класу, що дорівнює вихідній множині. Елементна і ціла розбивки множин називаються тривіальними, інші, якщо існують, - нетривіальними.

Приклад.М={a, b, c, d, e, f}

P={{a, b, c,}, {b, d, e, f}, {e, f, a}}

R₁={{a, b}}, {c}, {d, e, f}}

R₂={{a}, {b}, {c}, {d}, {e}, {f}}

R₄={a, b, c, d, e, f}

2.3. Потужність множин. Зчисленні і континуальні множини

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

Порівняння множин зв'язане з установленням взаємооднозначної відповідності. Елементи множин М₁ і М₂ знаходяться у взаємооднозначній відповідності, якщо кожному елементу множини М₁ за деякім законом зіставлений єдиний елемент множини М₂ і навпаки. Такі множини називаються рівнопотужними (еквівалентними).

Приклад. Множина N рівно потужна множини N^2.

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

Теорема. Об'єднання скінченної чи зчисленної сукупності зчисленних множин також є зчисленною множиною.

Існують нескінченні множини, елементи яких не можна перерахувати.

Теорема Кантора. Множина усіх дійсних чисел інтервалу (0,1) числової осі незчисленна.

Усяка множина, еквівалентна множині всіх дійсних чисел інтервалу (0,1), називається континуальною (множиною потужності континууму).

Приклад. Множини ірраціональних, трансцендентних чисел незчисенні.

Теорема. Множина B(М) усіх підмножин деякої зчисленної множини М є множиною потужності континуума.

Нехай F(А) - множина усіх слів у скінченному алфавіті А. Будь-яка підмножина LÍF(A) називається мовою над алфавітом.

Приклад. Множина усіх мов над скінченним алфавітом є множиною потужності континуума.

Кардинальне число ãM множини М - це деЯкій об'єкт, що визначає потужність множини М (з розглянутої сукупності множин). У випадку скінченної множини М кардинальним числом ãМ=|M| кожної з множин розглянутої сукупності є натуральне число, що визначає число елементів у ньому і називане потужністю множини. Для нескінченних множин кардинальні числа називають трансфінітними.

Для кардинальних чисел скінченних множин можливі відношення:

1. ãM₁=ãM_2.

2. ãМ₁<ãM_2.

3. ãМ₁>ãM_2.

Приклад. M₁={1, 2, 3}, M₂={a, b, c}, \M₁\=\M₂\. M₃={1, 2, 3, 4}, M₄={a, b, c}, \M₃\>\M₄\.

При порівнянні нескінченних множин логічно можливі випадки:

1. Множини М₁ і М₂ рівно потужні, тобто ãМ₁=ãМ₂

2. Множини М₁ і М₂ не рівнопотужні, але одне з них, наприклад М₁, рівно потужне підмножині іншого - ãМ₁=ãМ₂^’ і М₂^’ÌM₂. У цьому випадку потужність множині М₁ менше потужності множині М₂, таким чином ãМ₁<ãM_2.

3. Множина М₁ еквівалентна (рівно потужна) деякій підмножині множині М₂ і, навпаки, множина М₂ еквівалентно (рівно потужна) деякій підмножині множині М₁. Випадок зводиться до першого.

Теорема Кантор-Бернштейна. Якщо множина М₁ еквівалентна (рівнопотужна) деякій підмножині множини М₂ і одночасно множина М₂ еквівалентна (рівнопотужна) деякій підмножині множини М₁, то множини М₁ і М₂ еквівалентні (рівнопотужні).

4. Множина М₁ не еквівалентна (нерівнопотужна) ніякій підмножині множини М₂ і множина М₂ не еквівалентна (нерівнопотужна) ніякій підмножині множини М₁, тобто М₁ і М₂ - непорівнянні. Цей випадок неможливий і множина усіх кардинальних чисел цілком упорядкована.

Приклад. M₁={mÎM\mÎN & m – квадрат натурального числа}, M₂=N, c}, ãM₁=ãM₂, M₃=(0, ¥), M₄=(0, 1), ãM₃>ãM₄.

Наслідок. Якщо справедливе включення МÉM₁ÉM₂, причому М і М₂ – еквівалентні (рівно потужні), то М і М₁ еквівалентні (рівно потужні).

Приклад. M=(0, 1), M₁=(0, 1,5), M₂=(0, 2), ãM=ãM₂, М₂ÉM₁ÉM, ãM=ãM₂=ãM₁.

Наслідок. Якщо М₁ÊM₂, то ãМ₁³ãМ₂.

Наслідок. Якщо М - довільна кінцева множина, то М<ã₀, де ã₀- кардинальне число множини натуральних чисел N (будь-якої зчисленної множини), називане алеф-нуль.

Теорема. У всякій нескінченній множини М можна виділити деяку зчисленну підмножину.

Теорема. Потужність множини В(М) усіх підмножин будь-якої непорожньої множини М більше потужності даної множини, тобто ãВ(М)>ãМ.

Приклад. M₁={0, 1}, M₂=B(M)={{(0, 1}, {0}, {1}, Æ}, ãM₁<ãM₂.

Наслідок. Не існує множин найбільшої потужності, множина усіх кардинальних чисел не має максимального елемента.

Контрольні запитання

1. Що таке рівняння? Як виконується розв’язання рівнянь?

2. Яка різниця між покриттям і розбивкою?

3. Які блоки покрить і розбивок можуть бути?

4. У чому різниця скінченних і нескінченних множин?

5. Чи усі множини можна перерахувати?

6. Як порівнюються нескінченні множини?

7. Чи е найбільша множина, як це підтвердити?