Доведення вичерпуванням (метод витягів, метод вичерпування, метод грубої сили) — один з методів доведення тверджень у математиці. При доведенні вичерпуванням твердження розбивається на скінченну кількість випадків, де істинність кожного випадку доводиться окремо.. Даний метод є прямим доведенням. Доведення методом вичерпування зазвичай включяє три етапи: Розбиття твердження на скінченну кількість випадків. Доведення того, що множина випадків є вичерпною, тобто немає жодного пропущеного випадку. Доведення істинності кожного з виокремлених випадків.

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

Приклад Довести, що, якщо ціле число є досконалим кубом, то воно має бути кратним 9, на 1 більше ніж кратним 9, або на 1 менше ніж кратним 9.

Доведення: Кожен досконалий куб — це куб деякого цілого числа , де або є кратним 3, або на 1 більше, ніж кратне 3, або на 1 менше ніж кратне 3. Отже, маємо наступну множину випадків для розгляду: Випадок 1: якщо , то , що є кратним 9. Випадок 2: якщо , то , що є на 1 більше, ніж кратне 9. Наприклад, якщо , тоді . Випадок 3: якщо , то , що є на 1 менше, ніж кратне 9. Наприклад, якщо , тоді .

Елегантність

Математики зазвичай намагаються уникати доведень методом вичерпування, коли кількість випадків є великою, оскільки такі доведення вважаються неелегантними або неефективними. Прикладом того, як такі доведення можуть бути неелегантними, є доведення твердження, що всі сучасні літні Олімпійські ігри відбуваються в роки, які кратні 4.

Доведення: Перші літні Олімпійські ігри в сучасній історії відбулися в 1896 році, і потім кожні 4 роки відповідно (не враховуючи виняткові ситуації, такі як відміна/перенесення ігор через Першу та Другу світові війни та пандемію COVID-19. Оскільки ділиться на 4, наступні Олімпійські ігри відбудуться в році, який також є кратний чотирьом, і так далі (доведення методом математичної індукції. Отже, твердження доведено.

Твердження також можна довести методом вичерпування, навівши перелік всіх цих років, в яких проводилися літні Олімпійські ігри, і перевіривши, що кожен з них кратний чотирьом. З огляду на те, що станом на 2016 рік було проведено 28 літніх Олімпійських ігор, маєм 28 розглянутих випадків.

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

Кількість розглянутих випадків

Загалом немає обмеження на кількість розглянутих випадків у доведенні вичерпуванням. Іноді буває лише два чи три випадки, які треба довести. Проте зазвичай кількість випадків може сягати тисяч чи навіть мільйонів. Наприклад, строге розв'язання шахової композиції ендшпілю може включати аналіз дуже великої кількості можливих позицій на дошці в дереві гри цієї задачі.

Перше доведення теореми чотирьох фарб було доведенням методом вичерпування з 1834 випадками. Це доведення було доволі контроверсійним, оскільки більшість випадків перевірялися комп'ютером, а не людиною. Найлаконічніше доведення, відоме на сьогодні, включає більше 600 випадків.

Загалом, ймовірність помилки в загальному доведенні зростає зі збільшенням кількості розглянутих випадків. Доведення з великою кількістю випадків може виглядати більше як випадковість, ніж як доведення з чіткими логічними зв'язками. Інші типи доведення, такі як математична індукція вважаються більш елегантними. Проте існують важливі теореми, для яких не знайдено жодного іншого методу доведення, такі як:

Доведення того, що не існує скінченної проєктивної площини порядку 10. Класифікація простих скінченних груп. Гіпотеза Кеплера. Проблема трійок Буля — Піфагора.

Див.також Доказові обчислення Математична індукція Доведення від супротивного Індукція (логіка)

Примітки