Материал: discrete_mathematics

Незважаючи на те що в межах логіцизму проблему обґрунтування математики не було остаточно розв'язано, усе ж було зроблено чимало для з'ясування деяких важливих аспектів логічної структури математики.

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 не перетинаються,

цією формулою дістав назву методу (принципу) включення та

виключення.

Приклад 3.1.

1. Зі 100 студентів факультету англійську мову знає 61 студент, французьку – 43, німецьку – 26, англійську і французьку – 25, англійську й німецьку – 17, французьку й німецьку – 14, усі три мови знають 8 студентів. Скільки студентів не знають жодної з трьох мов?

140

Позначимо через A, B, C множини студентів, які знають англійську, французьку та німецьку мову. Тоді кількість студентів, які знають принаймні одну мову, згідно з (3.1) становить

| A B C | = | A | + | B | + | C | –

–(| A ∩ B | + | A ∩ C | + | B ∩ C |) + | A ∩ B ∩ C | =

=61 + 43 + 26 – (25 + 17 + 14) + 8 = 92.

Отже, шукана кількість дорівнює 100 – 92 = 8.

2. Знайти кількість натуральних чисел, що не перевищують 1000 і не діляться ні на 3, ні на 5, ні на 7.

Позначимо через Ak множину натуральних чисел, що не перевищують 1000 і діляться на k. Множиною натуральних чисел, що не перевищують 1000 і діляться або на 3, або на 5, або на 7, є множина

A3 A5 A7,

а шуканою множиною є

E \ (A3 A5 A7),

де множина-універсум E – всі натуральні числа від1 до 1000. Тоді

| E \ (A3 A5 A7) | = | E | – | E ∩ (A3 A5 A7) | =

= | E | – | A3 A5 A7 |

(див. співвідношення (2.3)).

| E | = 1000, а вираз | A3 A5 A7 | обчислюють за (3.1). Крім того, | Ak | = [1000/k] і Ak ∩ Al = Am, де m – найменше спільне кратне чисел k і l (через [x/y] позначено цілу частину від ділення x на y). ◄ Нарешті, розглянемо останню теоретико-множинну операцію –

Формулу (3.2) часто називають основним правилом комбіна торики (або правилом множення).

Нехай потрібно виконати одну за одною n дій. Якщо першу дію можна виконати k1 способами, другу – k2 способами і т. д., а n-ту – kn способами, то всі n дій разом можна виконати k1k2…kn способами.

Приклад 3.2.

1. Кількість слів довжиною m в алфавіті A (|A| = n) становить |Am| = |A|m = nm. Цей результат випливає також із того, що побудову одного зі слів довжиною m можна розкласти на m кроків (або дій): перший крок – вибір першої літери слова, другий –

141