хай M – множина всіх тих множин, що не є елементами самих себе. Розглянемо питання: а чи є сама множина M елементом самої себе? Якщо припустити, що M M, то із означення множини M випливає M M. Якщо ж припустимо, що M M, то з того самого означення дістанемо M M.
Близьким до парадокса Рассела є парадокс цирульника. Цирульник – це мешканець міста, який голить тих і тільки тих мешканців міста, які не голяться самі. Виникає проблемаз визначенням множини C усіх тих мешканців міста, яких голить цирульник. Міркуючи аналогічно тому, як це було зроблено в парадоксі Рассела, дійдемо висновку, що цирульник голить себе в тому й тільки в тому випадку, коли він не голить сам себе, тобто цирульник належить множині C тоді й лише тоді, коливінне належить C.
Багато хто із математиків на початку ХХ ст. не надавав цим парадоксам особливого значення, оскільки в той час теорія множин була відносно новою галуззю математики й не зачіпала інтересів більшості фахівців. Однак їхні більш відповідальні та проникливі колеги зрозуміли, що виявлені парадокси стосуються не тільки теорії множин і побудованих на ній розділів класичної математики, але й безпосередньо пов'язані з логікою взагалі, яка є головним інструментом математики.
Зокрема, парадокс Рассела можна переформулювати в термінах логіки й таким чином додати до відомих із давніх часів логічних парадоксів: парадокса брехуна (людина, яка завжди каже неправду, одного разу мовить: Те, що я сказав, – брехня), парадокса всемогутньої істоти (чи може всемогутня істота створити такий камінь, який вона не зможе підняти?) тощо.
Гостро постало питання про обґрунтування засад математики. На початку двадцятого століття виникли три основні напрями досліджень з обґрунтування сучасної математики. Коротко подамо суть кожного з них.
1. Логіцизм. Основною тезою логіцизму є положення, що першооснова математики – це логіка, а математика – лише частина логіки, тобто всі математичні істини складають власну підмножину множини всіх логічних істин.
Основні ідеї й методи логіцизму було вперше викладено у великій праці А. Уайтхеда і Б. Рассела "Принципи математики", що вийшла друком на початку другого десятиріччя ХХ ст.
136
Незважаючи на те що в межах логіцизму проблему обґрунтування математики не було остаточно розв'язано, усе ж було зроблено чимало для з'ясування деяких важливих аспектів логічної структури математики.
2. Інтуїціонізм. Основними засадами інтуїціонізму є такі:
1)основою математики вважають поняття натурального числа, причому систему натуральних чисел покладають інтуїтивно відомою;
2)усі інші математичні об'єкти будують на основі натуральних чисел суто конструктивно за допомогою скінченної кількості застосувань скінченної кількості конкретних операцій.
Доведення існування математичного об'єкта зводиться до побудови конкретного алгоритму, тобто визнаються лише конструктивні доведення існування математичних об'єктів. Зокрема, не визнається доведення існування математичних об'єктів методом від супротивного;
3)закон виключеного третього незастосовний до нескінченних множин (закон виключеного третього – це логічна аксіома, згідно з якою із двох тверджень A та не A тільки одне істинне);
4)визнається абстракція потенційної нескінченності та відкидається абстракція актуальної нескінченності.
Обґрунтування математики в межах інтуїціонізму натрапляє на дві основні перешкоди: значну частину її важливих розділів не вдається побудувати засобами інтуїціонізму або ж така побудова має досить громіздкий і штучний вигляд, який не задовольняє переважну більшість як математиків-теоретиків, так і практиків.
Наступним кроком у розвитку інтуїціонізму є конструктивний напрям (або конструктивізм), що розвивається на основі уточненого поняття алгоритму.
3. Формалізм. Засновником формалізму вважають Д. Гільберта. Цей напрям є подальшим поглибленням аксіоматичного методу в математиці. Основою будь-якої аксіоматичної теорії є перелік неозначуваних (первинних) понять і список аксіом, тобто положень, які беруть за вихідні та істинність яких декларують із
137
самого початку. Додатково означають логічні правила, за допомогою яких з одних тверджень (зокрема аксіом) дістають інші.
Гільберт і його послідовники вважали, що кожен розділ математики можна повністю формалізувати, тобто за допомогою формальних виразів (формул) подати всі аксіоми, а всі математичні (логічні) доведення звести до суто формальних перетворень над формулами.
Саме на основі ідей формалізму Е. Цермело 1908 року побудував першу формальну аксіоматичну теорію множин (систему Цермело–Френкеля, або ZF). Пізніше було запропоновано багато видозмін і вдосконалень ZF і кілька інших аксіоматичних теорій множин.
Проаналізувавши всі парадокси теорії множин, можна дійти висновку, що всі вони зумовлені необмеженим застосуванням
принципу абстракції (або принципу згортання), згідно з яким для будь-якої властивості P(x) існує відповідна множина елементів x, які мають властивість P. Якщо відкинути це припущення, то всі відомі парадокси теорії множин стають неможливими. Наприклад, із парадокса Рассела випливало б, що не існує множина множин, які не є елементами самих себе.
В усіх існуючих аксіоматичних теоріях множин неможливість антиномій ґрунтується на обмеженнях принципу згортання, тобто на обмеженні допустимих множин.
138
Розділ 3 КОМБІНАТОРИКА
Комбінаторика (інша назва – комбінаторний аналіз) – це розділ сучасної дискретної математики, що вивчає способи вибору й розміщення певних предметів, досліджує властивості та формулює методи обчислення кількостей різноманітних конфігурацій, які можна утворити з цих предметів. Оскільки конкретний вигляд (матеріальна сутність) предметів, які обирають і розміщують, не має для комбінаторного аналізу жодного значення, то при формулюванні та розв'язуванні задач комбінаторики використовують загальні поняття й терміни теорії множин і відношень. Особливо слід наголосити, що всі множини, з якими має справу комбінаторика, скінченні. Далі скрізь у цьому розділі під словами множина чи підмножина розумітимемо скінченні множини.
Користуючись мовою теорії множин, можна сказати, що комбінаторика вивчає різноманітні властивості множин, які можна утворити з підмножин певної скінченної множини. При цьому кожного разу задають певні правила, за якими формуються ці множини і підмножини.
Кількість елементів (потужність) основної скінченної множини називають розмірністю комбінаторної задачі.
Комбінаторні задачі мають давню історію. Однак тривалий час комбінаторика не привертала до себе уваги математиків. Пояснюється це значною мірою тим, що, оскільки комбінаторні задачі формулюють для скінченних множин, то для переважної більшості таких задач існує тривіальний метод їх розв'язання – перебір. Пошук зручніших алгоритмів і методів для задач малої розмірності не викликає інтересу в дослідників, тому що виграш порівняно з тривіальним алгоритмом перебору незначний. Водночас комбінаторні задачі великої розмірності навіть за умови застосування найефективніших алгоритмів потребують такої кількості операцій (обсягу обчислень), що стають практично нерозв'язними.
Ситуація кардинально змінилася з появою ЕОМ. З'явилась реальна можливість для розв'язання комбінаторних задач доста-
тньо великої розмірності. Виявилося, що для таких задач різноманітні вдосконалення й оптимізація відповідних алгоритмів зумовлюють істотний виграш у часі та пам'яті. Це, у свою чергу, дає змогу додатково збільшити розмірність задач, які можна розв'язувати за допомогою "хороших" алгоритмів. Розробка й дослідження загальних принципів побудови оптимальних комбінаторних алгоритмів для розв'язування різноманітних комбінаторних задач – одні з найважливіших проблем сучасної теорії та практики програмування.
3.1.Комбінаторні обчислення дляосновнихтеоретико-множиннихоперацій.
Формула включення-виключення
Якщо A та B – довільні скінченні множини, то безпосередньо із означення теоретико-множинних операцій випливають спів-
відношення | A \ B | = | A | – | A ∩ B | і | B \ A | = | B | – | A ∩ B |.
Як і раніше, через |M| позначено кількість елементів скінченної множини M.
Очевидно також, що коли множини A та B не перетинаються,
тобто A ∩ B = , то | A B | = | A | + | B |. Зокрема, |
|
|
||
| A B | = | A \ B | + | B \ A |. |
|
|
||
Для довільних множин A та B маємо |
|
|
|
|
| A B | = | A | + | B | – | A ∩ B |. |
|
|
||
А для трьох множин A, B, C справджується така рівність: |
|
|||
| A B C | = | A | + | B | + | C | – |
|
|
||
– (| A ∩ B | + | A ∩ C | + | B ∩ C |) + | A ∩ B ∩ C |. |
|
|||
При обчислюванні за формулою |
|
потрібно |
послідовно |
|
|
|
(3.1) |
||
додавати й віднімати певні кількості. |
Тому метод обчислення за |
|||
(3.1) |
|
|
|
|
цією формулою дістав назву методу (принципу) включення та
виключення.
Приклад 3.1.
1. Зі 100 студентів факультету англійську мову знає 61 студент, французьку – 43, німецьку – 26, англійську і французьку – 25, англійську й німецьку – 17, французьку й німецьку – 14, усі три мови знають 8 студентів. Скільки студентів не знають жодної з трьох мов?
140