Дискрегна математика 2

1. Зліченні та незліченні множини. Континуальні множини. Потужність множини. Теореми Кантора. 2

2. Відношення та їх властівості. Відношення еквівалентності та часткового порядку. Фактор-множина. 3

3. Зв’язаність і планарність графів. Методи перевірки зв’язності і критерії планарності графів. 4

4. Сполуки, перестановки, розміщення. Поліноміальна теорема. 6

5. Канонічні форми бульових функцій. Алгебра Жегалкіна. 6

6.Повнота і замкненість систем бульових функцій. Теорема (критерій) Поста. 8

Дискрегна математика

1. Зліченні та незліченні множини. Континуальні множини. Потужність множини. Теореми Кантора.

Озн. М-на А називається зліченою (зчисленною), якщо вона рівнопотужна м-ні нат.чисел N.

Дві мн-ни називаються рівнопотужними (тобто мають рівні потужності), якщо між ними існує взаємооднозначна відповідність (бієкція).

Рівнопотужність позначається: А~В (для скінч. мн-н А~ВА=В ).

Основні теореми:

1. Будь-яка нескінчена м-на М містить в собі злічену підмн-у.

Доведення :

Нехай М довільна неск. Мн. , - неск. -неск.

1.1 неск., А-зліч. Мн.

1.2 - зліч і

2. Будя-яка підмн-на В зліч. мн-ни А – або скінчена, або злічена.

3. Об’єднання скінченної або зліченної сукупності зліченних мн-н є зліченною мн-ю.

Наслідки останнбої теореми:

Наслідок 1: Мн-на всіх цілих чисел і множина всіх раціональних чисел є зліченими множинами.

Наслідок 2: Декартів добуток двох злічених мн-н є мн-ю зліченою.

Наслідок 3: Декартів добуток скінченої сукупності зліченіх мн-н є мн-ю зліченою.

Наслідок 4: Мн-на всіх многочленів від однієї змінної з раціональними коефіцієнтами є зліченою мн-ною.

Наслідок 5:Мн-на А* всіх слів в алфавіті А є зліченою мн-ною.

Озн. Незліченною мн-ною називається нескінчена мн-на, яка не є зліченою.

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

Доведення: Методом від супротивного. Припустимо, що мн-на чисел з (0,1) є зліченною.

Кожному дійсному числу з інтервала (0,1) відповідає нескінченний десятковий дріб вигляду 0, а₁ а₂ а_{3…………}-ірраціон.

Раціональні числа 0, в₁ в₂ в₃ ..... в_n перетворимо у 0, в₁ в₂ в₃ ... в_n-1 (в_n-1) 9999...

Тоді ці числа можна перенумерувати і записати так:

x₁=0, a₁₁ a₁₂ a₁₃ .......

x₂=0, a₂₁ a₂₂ a₂₃ ......

x₃=0, a₃₁ a₃₂ a₃₃ ......

....................................

x_k=0, a_k1 a_k2 a_k3 ..........

.........................................

Діагональний метод Кантора: ідучі по діагоналі таблиці будуємо y=0, d₁ d₂ d₃ ...d_k....( значення, яке не попало в перелік), де

d₁а₁₁; d₂а₂₂;.....d_nа_kk;..........

Звідси маємо, що y (0,1) і для довільного і y не дорівнює жодному x_і. Отже, такої нумерації не існує, і ця мн-на не є зліченною.

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

Теорема Кантора 2. Нехай М — нескінчена мн-на, а мн-на А є зліченною або скінченною підмножиною мн-ни М, то М\А~М (рівнопотужні).

Доведення. Від супротивного.

Нехай М₁=М\А. Мн-на М₁-незліченна (нескінч.) (припустимо, що вона зліч. Тоді (М\А)А=М, отже, виходить, що мн-на М є зліч.– суперечність), так як будь-яка нескінчена мн. містить в собі злічену мн-ну виділимо зліченну мн-ну В з М₁. Тоді (М\А)\В= М\(АВ). АВ~В (так як АВ і В –злічені мн-ни). Виконується:  М\А~М, що і потрібно було довести.

Наслідки теореми:

1) Якщо М — нескінчена мн-на, а мн-на А є зліченною або скінченною тоді М  А ~ М.

2) Мн-на ірраціональних чісел є континуальною (за теор. Кантора 2 R\Q~R).

Озн. Дійсне число, яке не є коренем жодного многочлена з раціональними коеф. наз. трансцедентним.

Наслідок 3: Мн-на трансцендентних чісел є континуальною.

Теорема Кантора 3: Нехай А–злічена мн-на, тоді мн-на (А) (мн-на всіх підмн-н зліченної мн-ни А ) є континуальною.

Доведення. А-зл. мн-на А~N~. Доведемо,  є континуальною мн-ною. Кожному елементу булеана С (С) ставимо у відповідність нескінчений кортеж з 0 і 1: t=( m₁,m₂,m₃,...., m_k,…..), де .

Доведемо, що мн-на кортежів з о і 1 є незліч. мн-ною. Доведення аналогічне доведенню Теор. Кантора

Доведемо, що мн-на кортежів з 0 і 1 є континуальною мн. претворимо кортежі у числа. Але ця відповідність не бієктивна. (одному і тому ж числу можуть відповідати різні кортежі). Розглянемо мн-ну Т–злічена мн-на всіх раціональних чисел, які в двійковій формі мають період 1. Тобто відкидаємо ті числа, з якими бієкція не можлива. Отримаємо (0,1)\Т~(N). Отже, з теореми Кантора 2, так як (0,1)\Т~(0,1) маємо (N) ~(0,1).