25. Принцип математической индукции

---

ВПЕРЁД ⇒

Принцип математической индукции

⇐ НАЗАД

Пропозиции и предикаты

---

Принцип математической индукции

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

Пусть $P(x_1,x_2,...,x_n)$ - предикатная функция на множестве неотрицательных целых чисел $X$:

$⟨⟨x_1,...,x_n⟩,y⟩\in P$, где $⟨x_1,...,x_n⟩\in X^n$ и $y\in \{ИСТИНА,ЛОЖЬ\}$

Пусть также требуется доказать, что из истинности $P(0,x_2,...,x_n)$ следует истинность $P(1,x_2,...,x_n)$, из истинности $P(1,x_2,...,x_n)$ следует истинность $P(2,x_2,...,x_n)$, из истинности $P(2,x_2,...,x_n)$ следует истинность $P(3,x_2,...,x_n)$ и т.д. Иначе говоря, требуется доказать, что $P(k,x_2,...,x_n)$ истинно при любом неотрицательном целом значении $k$.

Ниже представленный способ доказательства истинности $P(k,x_2,...,x_n)$ носит название принципа математической индукции:

1. Сначала проверяют, что предикат $P(k,x_2,...,x_n)$ истинен при $k=0$, то есть убеждаются в выполнении начального условия: $P(0,x_2,...,x_n)=true$.
2. Затем в общем (символьном) виде доказывается, что при переходе от $P(k,x_2,...,x_n)$ к $P(k+1,x_2,...,x_n)$ истинность $P(k+1,x_2,...,x_n)$ сохраняется. Иначе говоря, обосновывается шаг индукции, то есть доказывается, что из истинности $P(k,x_2,...,x_n)$ следует истинность $P(k+1,x_2,...,x_n)$.
3. Если первые два шага выполнены, то делаем вывод, что $P(k,x_2,...,x_n)$ истинно при любом неотрицательном целом значении $k$.

---

ВПЕРЁД ⇒

Принцип математической индукции

⇐ НАЗАД

Пропозиции и предикаты

---

Источники

Категория

Математическая-логика Математическая-логика

Теги

• Логика Логика
• Множество Множество
• Функция Функция
• Математическая-индукция Математическая-индукция
• Индукция Индукция
• Предикат Предикат