- •Дискретна матЕматика
- •1. Зліченні та незліченні множини. Теореми Кантора.
- •2. Відношення та їх властівості. Відношення еквівалентності та часткового порядку. Фактор-множіна.
- •Операції над відношеннями:
- •3. Зв’язність і планарність графів. Методи перевірки зв’язності і критерій планарності графів.
- •Перевірка зв’язності графів.
- •Плоскі та планарні графи.
- •4. Сполуки, перестановки, розміщення. Поліноміальна теорема.
- •5. Канонічні форми бульових функцій. Алгебра Жегалкіна.
- •6.Повнота і замкненість сістем бульвих функцій. Теорема Поста.
- •Чудові класи замкнених ф-цій
Дискретна матЕматика
1. Зліченні та незліченні множини. Теореми Кантора.
Озн. М-на, рівнопотужна м-ні нат.чисел N, наз. Зліченою.
Рівнопотужні — значить між ними є взаємооднозначна відповідність; кожному ел-ту можна надати номер—злічена м-на.
А~N — рівнопотужна. ={a1,a2,...,an,...}
Злічені: N(2)~N, де N(2) — м-на квадратів чисел.
Т1.2. Будь-яка нескінчена м-на М містить злічену мн-у.
Т1.3. Довільна підм-на злічен. М-ни є м-ною або зліч. або скінч.
Т1.4. Об’єднання скінченної або зліченної сукупності зліченних мн-н є зліченною мн-ю.
Наслідок 1: Мн-на всіх цілих чисел — мн-на злічена.
Наслідок 2: Мн-на раціональних чисел є мн-ною зличеною.
Наслідок 3: Декартів добуток двох злічених мн-н є мн-ю зліченою.
Наслідок 4: Декартів добуток скінченої кількості зліченіх мн-н є мн-ю зліченою.
Т1.5 Кантора. Мн-на дійсних чисел з інтервалу (0,1) є мн-на незліченою.
Нехай мн-на R з інтервала (0,1) є зліченною.
Кожному дійсному числу з інтервала (0,1) відповідає нескінченний десятковий дріб вигляду 0, а1 а2 а3 ... – іраціонал.
Раціональні числа 0, в1 в2 в3 ..... вn перетворимо у 0, в1 в2 в3 ... вn-1 (вn-1) 9999...
Злічимо числа з (0,1):
а1=0, x11 x12 x13 ...x1n....
a2=0, x21 x22 x23 ...x2n...
a3=0, x31 x32 x33 ...x3n...
....................................
an=0, xn1 xn2 xn3 ......xnn....
.........................................
В цей перелік не попало як мінімум b=0, d1 d2 d3 ...dn....,де
d1x11(0,9);
d2x22(0,9);
................................
dnxnn(0,9);
................................
Звідси маємо, що ця мн-на незліченна.
Озн. Мн-на рівнопотужна мн-ні дійсних чисел з інтервалу (0,1) наз. контінуальною або мн-ною потужності континуум.
Т1.6 Кантора Якщо М — незлічена мн-на, а мн-на А є зліченною або скінченною підмножиною мн-ни М, то М\А~М (рівнопотужні).
Від супротивного.
Нехай М1=М\А. Якщо М1-незліченна, за Т1.2 виділимо скінченну мн-ну В з М1. Тоді М1 \В= М2 незліченна. Утворімо дві мн-ни М1=М\А=М2 об’єд В
М=М2 об’єд (А об’єд В)
тоді В~A об’єд B — бо дві злізенні
M2~M2
тоді М2 об’єд В ~(А об’єд В) об’єд М2
М\А~М
Що і треба довести.
Наслідок 1: Якщо М — нескінчена мн-на, а мн-на А є зліченною або скінченною тоді М об’єд А ~ М.
Наслідок 2: Мн-на ірраціональних чісел є контінуальною.
Озн. Число, яке не є коренем жодного мн-на з раціональними коеф. наз. трансцедентним.
Наслідок 3: Мн-на транціндентних чісел є контінуальною.
Т1.7 Кантора: Мн-на В(А) (мн-на всіх підмн-н зліченної мн-ни А ) є контіну-альною.
А – зліченна, тоді А~N
Тоді В(А)~В(N). Покажемо що В(N) – контінуальна.
Від супротивного. N–зліченна
Припустимо В(N)-зліченна, тоді В(N)={В1, В2, В3, ..., Вn, ... }, Bi з N
Тоді є взаємнооднозначна відповідність Вi і mi1 mi2 mi3 .....
mij {0,1} min=1, якщо n з Bi; 0, якщо n не з Bi
Тоді аналогічно доведеню Т1.5 маємо, що В(N) – незліченна.
2. Відношення та їх властівості. Відношення еквівалентності та часткового порядку. Фактор-множіна.
Озн. Підмн-на R з Mn (n-го декартового степеня мн-ни М) наз. n-місним або n-арним відношенням на мн-ні М.
а1,а2,а3,....,аn знаходяться у відношенні R, якщо кортеж (а1,а2,а3,....,аn) належіть R.
Приклади:
1) R1 – "менше або дорівює": 2 R1 17, 1 R1 m,...
2) R2 – "знаходяться на одній відстані від (0,0)": (3,2) R2 (2,3), (0,0) R2 (0,0),....
3) на мн-ні студентів факультету
R3 – "є однокурсниками"