Войти
Доказательство по исчерпанию, также известное как доказательство по делам, доказательство по делу анализ, полная индукция или метод грубой силы - это метод математического доказательства, в котором доказываемое утверждение разбивается на конечное число случаев или наборов эквивалентных случаев, и где каждый тип случая проверяется, чтобы увидеть, выполняется ли рассматриваемое предложение. Это метод прямого доказательства. Доказательство путем исчерпания средств обычно состоит из двух этапов:
Распространенность цифровых компьютеров значительно повысило удобство использования метода исчерпания (например, первое компьютерное доказательство теоремы о четырех цветах в 1976 г.), хотя такие подходы также могут быть оспорены на основе математическая элегантность. Экспертные системы могут использоваться для получения ответов на многие из задаваемых им вопросов. Теоретически доказательство методом исчерпания можно использовать всякий раз, когда число случаев конечно. Однако, поскольку большинство математических наборов бесконечны, этот метод редко используется для получения общих математических результатов.
В изоморфизме Карри – Ховарда доказательство исчерпанием и анализ случая связаны с ML- стиль сопоставление с образцом.
Подтверждение исчерпание может быть использовано для доказательства того, что если целое число является идеальным кубом, то оно должно быть либо кратным 9, либо на 1 больше, чем на 9, либо на 1 меньше, чем кратно 9.
Доказательство :. Каждый идеальный куб является кубом некоторого целого числа n, где n либо кратно 3, либо 1 больше, чем кратное 3, либо 1 меньше, чем кратное 3. Итак, эти три случая являются исчерпывающими:
Математики предпочитают избегать доказательств истощение с большим количеством дел, которые рассматриваются как неэлегантно. Чтобы проиллюстрировать неэлегантность таких доказательств, взгляните на следующие доказательства того, что все современные летние Олимпийские игры проводятся в годы, кратные 4:
Доказательство : Первые современные летние Олимпийские игры проводились в 1896 году, а затем каждые 4 года (не считая тех лет, когда игры не проводились из-за Первой и Второй мировых войн). Поскольку 1896 = 474 × 4 делится на 4, следующие Олимпийские игры будут в году 474 × 4 + 4 = (474 + 1) × 4, что также делится на четыре, и так далее (это доказательство на математическая индукция ). Следовательно, утверждение доказано.
Утверждение также может быть доказано исчерпанием возможностей перечисления каждого года, в котором проводились летние Олимпийские игры, и проверки того, что каждое из них можно разделить на четыре. По данным на 2016 год, всего 28 летних Олимпийских игр, это доказательство истощения - 28 случаев.
Помимо того, что доказательство истощения менее элегантно, он также потребует дополнительного случая каждый раз, когда проводится новая Летняя Олимпиада. Это должно быть противопоставлено доказательству с помощью математической индукции, которое доказывает утверждение на неопределенное время в будущем.
Не существует верхнего предела количества дел, разрешенных в доказательстве по исчерпанию. Иногда бывает всего два-три случая. Иногда их могут быть тысячи или даже миллионы. Например, строгое решение шахматного эндшпиля головоломки может включать рассмотрение очень большого количества возможных позиций в дереве игры этой задачи.
Первое доказательство теоремы о четырех цветах было доказательством исчерпания с 1936 случаями. Это доказательство было спорным, потому что большинство случаев было проверено компьютерной программой, а не вручную. Самое короткое известное доказательство теоремы о четырех цветах сегодня насчитывает более 600 случаев.
Как правило, вероятность ошибки во всем доказательстве увеличивается с количеством случаев. Доказательство с большим количеством случаев оставляет впечатление, что теорема верна только по совпадению, а не из-за какого-то основного принципа или связи. Другие типы доказательств, такие как доказательство по индукции (математическая индукция ), считаются более элегантными. Однако есть некоторые важные теоремы, для которых не было найдено другого метода доказательства, например
