Математическая логика и теория алгоритмов. Стенюшкина В.А. - 38 стр.

      13 Применения логики предикатов

      13.1 Строение математических теорем

      Рассмотрим следующую теорему: «Если точка лежит на биссектрисе угла,
то она равноудалена от сторон этого угла». Предусловием этой теоремы являе-
тся предложение «Точка лежит на биссектрисе угла», а постусловием – пред-
ложение «Точка равноудалена от сторон угла». Оба условия являются предика-
тами. Обозначим их соответственно А(x) и В (x), x∈Р, где Р –множество точек
плоскости. Тогда рассматриваемая теорема состоит в том, что импликация пре-
дикатов А(x)→ В (x), то есть предикат «Если точка x лежит на биссектрисе
угла, то она равноудалена от сторон этого угла», обращается в истинное выска-
зывание при всех x из множества Р. При помощи квантора общности это можно
записать так:
                          ∀ x (А(x)→ В (x)), x∈Р                        (13.1)
      Заметим, что словесная формулировка теоремы содержат описание мно-
жества объектов, о которых идет речь в теореме.
      13.2 Методы доказательства теорем

      Приведем формулировку принципа математической индукции.
      Пусть А(n) – произвольный предикат, заданный на множестве всех нату-
ральных чисел. Высказывание ∀ n А(n) истинно, если истинно высказывание
А(1) ∧ (∀k) (А (k) → А(k+1)). (Этот принцип, заметим, является одной из акси-
ом, определяющих натуральный ряд чисел).
      Под методом математической индукции понимают следующий способ
доказательства. Сначала проверяют истинность высказывания А(1). Затем,
предположив истинность высказывания А(k), доказывают истинность высказы-
вания А (k+1). Если доказательство верно для любого натурального k, то в соо-
тветствии с принципом математической индукции высказывание А(n) признае-
тся истинным для всех n.