Введение в логику

Логический вывод – дедукция

Показывать лекцию целиком
Записаться

Дедукция

Дедуктивный метод вывода – это метод вывода "от общего к частному". Из истинности некоторого общего утверждения делается вывод об истинности частного случая. Следующие рассуждения являются классическим примером дедуктивного вывода, известным со времен античных философов:

  • Все греки – люди.
  • Сократ – грек.
  • Следовательно: Сократ – человек.
    •

    Вот более современный пример, использующий тот же метод вывода:

  • Каждый школьник изучает информатику.
  • Пётр – школьник.
  • Следовательно: Пётр – изучает информатику.
    •

    А вот пример некорректного вывода:

  • Каждый школьник изучает информатику.
  • Пётр – не школьник.
  • Следовательно: Пётр – не изучает информатику.
    •

    А этот вывод вполне корректен и соответствует правилам логики:

  • Каждый школьник изучает информатику.
  • Пётр – не изучает информатику.
  • Следовательно: Пётр – не школьник.
    •

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

    В математике для доказательства часто используется метод математической индукции. Хотя в названии используется слово "индукция", метод является примером дедуктивного вывода от общего к частному. В простом варианте метод математической индукции сводится к следующему способу доказательства. Пусть необходимо доказать истинность некоторого свойства Q(N), зависящего от значения целого числа N. Достаточно доказать два утверждения:

  • Вначале доказать истинность Q(N0) для некоторого частного случая N = N0. Обычно N0 равно 0 или 1.
  • Далее необходимо доказать общее утверждение: Из справедливости Q(k) для k >= N0, следует справедливость Q(k + 1).

    • Если оба предыдущих пункта доказаны, то утверждение Q(N) справедливо для всех частных случаев, где N >= N0.

    Пример 1: Доказать Q(N):

    $$ \sum_{i=1}^{N}i^2 = \frac{N * (N+1) * (2*N+1)}{6} $$

  • Базис индукции: (N 0 = 1)
  • Шаг индукции: Пусть $$\sum_{i=1}^{k}i^2 = \frac{k * (k+1) * (2*k+1)}{6}$$. Тогда $$\sum_{i=1}^{k+1}i^2 = \frac{k * (k+1) * (2*k+1)}{6}+(k+1)^2 = \frac{k+1 * ((k+1)+1) * (2*(k+1)+1)}{6}$$.

    • Базис и шаг индукции доказаны. Отсюда следует справедливость утверждения для любого значения N >= 1.

    Пример 2: Число слов длины n в алфавите T из m символов равно: k = mn.

    Доказательство индукцией по длине слова.

  • Базис индукции: N0 = 1. Слов длины 1 ровно m – это символы алфавита T.
  • Шаг индукции: Пусть предположение утверждения выполняется для слов длины k, - таких слов mk. Докажем, что в этом случае утверждение остается истинным и для слов длины k + 1. Действительно, пусть построено множество слов длины k. Тогда можно построить множество слов длины k + 1 следующим образом. Каждое слово длины k можно продолжить одним из символов алфавита, получая слово длины k +1. Таким образом, каждое слово длины k порождает m слов длины k + 1. Никаких других слов длины k + 1, кроме порожденных таким способом, не существует. Отсюда следует, что число слов длины k + 1 равно: mk * m = mk+1, что и требовалось доказать.

    • Следовательно, наше утверждение справедливо для слов произвольной длины (n >= 1)

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^