ВУЗ:
Составители:
5.4 Доказательство контрпримером
Многие математические гипотезы имеют в своей основе форму: «Все объекты со
свойством A обладают свойством B». Мы можем записать это в виде формулы
∀x (A(x)⊃B(x)),
где A(x) обозначает предикат «x обладает свойством A», B(x) – «x обладает свойством B».
Если число возможных значений х является конечным, то в принципе доказательство мо-
жет быть проведено с помощью разбора случаев, то есть непосредственной проверкой вы-
полнимости гипотезы для каждого объекта. В случае если число объектов не является ко-
нечным, то такой возможности не существует даже в принципе. Однако для
доказательства ложности гипотезы достаточно привести хотя бы один пример (называе-
мый в этом случае контрпример), для которого гипотеза не выполнима.
5.5 Математическая индукция
В математических доказательствах часто используется принцип математической
индукции, который формулируется следующим образом: если какое-то высказывание P(n),
зависящее от натурального параметра n, доказано для n = 0 и при произвольном n удается
из истинности P(n) обосновать истинность P(n+1), то P(n) истинно для всех n.
Приведем пример доказательства по индукции. Доказать, что сумма трех после-
довательных кубов натуральных чисел делится на 9.
Базис индукции. 1
3
+2
3
+3
3
= 36 и делится на 9.
Индуктивный переход. Что произвести индуктивный переход, нужно предполо-
жить доказываемое утверждение для n и затем доказать его для n+1. Пусть n
3
+ (n+1)
3
+
(n+2)
3
делится на 9. Тогда
(n+1)
3
+ (n+2)
3
+ (n+3)
3
= (n+1)
3
+ (n+2)
3
+ n
3
+9n
2
+27n +27 =
(n
3
+(n+1)
3
+ (n+2)
3
)+(9n
2
+27n +27).
Но все слагаемые в последней скобке делятся на 9, а первая скобка делится на 9 по пред-
положению, значит, и исходная сумма делится на 9. Таким образом, мы установили, что
делимость суммы, начинающейся с n, влечет делимость суммы, начинающейся с n+1.
Следовательно, утверждение доказано для всех n.
Итак, в математической индукции имеется индуктивный базис – утверждение, что
свойство выполнено для самого маленького из рассматриваемых чисел, и индуктивный
переход – обоснование перехода от числа n к числу n+1.
Математическая индукция
A(0) & ∀n (A(n) ⊃ A(n+1)) ⊃ ∀n A(n)
Принцип математической индукции допускает несколько переформулировок, кото-
рые в классической логике эквивалентны исходному принципу.
Первая из них – возвратная индукция. Здесь переход происходит не от одного зна-
чения к следующему, а от всех предыдущих значений к последующему, шаг индукции пе-
реводит не от A(n) к A(n+1), а от ∀x<n A(x) к A(n). Как ни парадоксально, при таком пере-
ходе не требуется базиса индукции. В самом деле, поскольку условие x<0 тождественно
ложно, то, поскольку из лжи следует все что угодно, имеем ∀x(x<0 ⊃ A(x)), а отсюда по
индуктивному переходу имеем A(0).
Возвратная индукция
∀x(∀y(y<x ⊃ A(y)) ⊃ A(x)) ⊃ ∀x A(x)
Еще одна переформулировка метода математической индукции была известна еще
древним грекам. Это – метод бесконечного спуска.
30
Страницы
- « первая
- ‹ предыдущая
- …
- 28
- 29
- 30
- 31
- 32
- …
- следующая ›
- последняя »
