Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Метод полной математической индукции

Метод полной математической индукции


Метод математической индукции — специальный метод доказательства, применяемый для доказательства истинности утверждений типа [math](\forall x\in \mathbb{N})(P(x))[/math], то есть [math](\forall x)(x\in \mathbb{N}\to P(x))[/math]. Такие утверждения выражают тот факт, что некоторое свойство [math]P[/math] присуще каждому натуральному числу. Сейчас изложим суть этого метода. Формальной основой метода математической индукции служит одна из аксиом, называемая аксиомой индукции (или математической индукции) и выражающая свойство естественного отношения порядка, имеющегося на множестве всех натуральных чисел. Эта аксиома такова. Если свойством [math]P[/math] обладает число 1 и для всякого натурального числа из того, что оно обладает этим свойством, следует, что и непосредственно следующее за ним натуральное число также обладает им, то и всякое натуральное число обладает свойством Р. Символически, на языке логики предикатов, эта аксиома записывается так:


[math]\Bigl(P(1)\land (\forall x)\bigl(P(x)\to P(x+1)\bigr)\Bigr)\to (\forall y)\bigl(P(y)\bigr).[/math]

Эта аксиома дает следующий метод доказательства утверждений, выражающих некоторые свойства всех натуральных чисел. Если нужно доказать утверждение [math](\forall y)(P(y))[/math], где [math]y\in \mathbb{N}[/math] ("Всякое натуральное число обладает свойством [math]P[/math]"), достаточно установить истинность высказывания [math]P(1)[/math] ("Число 1 обладает свойством [math]P[/math]") и доказать, что [math](\forall x)\bigl(P(x)\to P(x+1)\bigr)[/math], т.е. "Если [math]x[/math] обладает свойством [math]P[/math], то этим свойством обладает и число [math]x+1[/math], непосредственно следующее за [math]x[/math]".


Таким образом, логическая схема доказательства методом математической индукции может быть представлена следующим образом:


(1): [math]P(1)[/math] — устанавливается проверкой;
(2): [math](\forall x)\bigl(P(x)\to P(x+1)\bigr)[/math] — доказывается;
(3): [math]P(1)\land (\forall x)\bigl(P(x)\to P(x+1)\bigr)[/math] - из (1), (2) по правилу введения конъюнкции;
(4): [math]\bigl(P(1)\land (\forall x)\bigl(P(x)\to P(x+1)\bigr)\bigr)\to (\forall y)\bigl(P(y)\bigr)[/math]аксиома индукции;
(5): [math](\forall y)\bigl(P(y)\bigr)[/math] — из (3), (4) по правилу modus ponens.

При этом установление истинности утверждения [math]P(1)[/math] называется основанием или базой индукции; предположение об истинности утверждения [math]P(x)[/math] — предположением индукции; последующее доказательство истинности утверждения [math]P(x+1)[/math] — шагом индукции.


Методом математической индукции доказано утверждение о том, что число двоичных наборов длины [math]n[/math] (упорядоченных n-ок), составленных из нулей и единиц, равно [math]2^n[/math] (теорема 10.3), о представлении булевых функций (теорема 10.5), теорема 15.4 о дедукции. Неоднократно применялась индукция по числу логических связок, входящих в формулу логики высказываний или предикатов (см. теоремы 2.2, 22.3, 22.5).


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved