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

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

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

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


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

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


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


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

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


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


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

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


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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

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


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

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