Математическое введение в декларативное программирование. Зюзысов В.М. - 31 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

Если для каждого натурального числа, удовлетворяющего свойству A(n), найдется
меньшее, удовлетворяющее этому свойству, то чисел n, для которых выполнено A(n), во-
обще нет.
Бесконечный спуск
∀n(A(n) ⊃ ∃m(m<n & A(m))) ⊃ ∀n ¬A(n)
Рассмотрим пример применения метода бесконечного спуска. Докажем, что аб-
сурдно предположение, что у каждого человека мать является человеком. В самом деле, за
все время существования Земли на ней жило конечное число людей. Пусть у каждого че-
ловека мать – человек. Упорядочим людей по моментам рождения. Список всех бывших
людей в порядке времени рождения назовем Книгой Судеб. Мать рождается раньше своих
детей, и поэтому в Книге Судеб она стоит раньше. Таким образом, для каждого человека
найдется стоящий раньше него в Книге Судеб. По принципу бесконечного спуска получа-
ем, что людей вообще нет и не было, что абсурдно. Полученное противоречие доказывает
утверждение.
Применение математической индукции, конечно же, содержит много тонкостей.
Приведем софизм, доказываемый при помощи неправильного применения индукции.
Задача. Все лошади одной масти. То, что все лошади одной масти, можно дока-
зать индукцией по числу лошадей в определенном табуне.
Если существует только одна лошадь, то она своей масти, так что база индукции
тривиальна. Для индуктивного перехода предположим, что существует n лошадей (с но-
мерами от 1 до n). По индуктивному предположению лошади с номерами от 1 до n–1 оди-
наковой масти и, аналогично, лошади с номерами от 2 до n имеют одинаковую масть. Но
лошади посередине с номерами с 2 до n–1 не могут изменять масть в зависимости от того,
как они сгруппированы – это лошади, а не хамелеоны. Поэтому лошади с номерами от 1
до n также должны быть одинаковой масти. Таким образом, все n лошадей одинаковой
масти. Что и требовалось доказать.
С методом математической индукции связано понятие индуктивного определения.
Базис индукции. Выражение вида A есть B.
Индуктивный переход. Если мы имеем выражения A
1
, …, A
n
типа B, то C, постро-
енное из них, также есть выражение типа B.
С каждым индуктивным определением связан принцип индукции по построению
объекта типа B.
Базис индукции. Каждый объект вида A обладает свойством θ.
Индуктивный переход. Если A
1
, …, A
n
обладают свойством θ, то и C им обладает.
Заключение индукции. Тогда любой объект типа B обладает свойством θ.
Этот принцип является логическим выражением следующего неявного пункта,
присутствующего в любом индуктивном определении: никаких других объектов типа B,
кроме полученных применением правил его определения, нет. Иными словами, множест-
во объектов типа B – минимальное из тех, которые включают базисные объекты и замкну-
ты относительно индуктивного перехода. В простых определениях эту минимальность
можно выразить следующим образом: объект должен получаться из базисных конечным
числом применений шагов определения.
Стоит отметить, что логическая индукция по построению вовсе не требует одно-
значности представления объекта в форме, соответствующей одному из пунктов его опре-
деления. Но для задания функций индукцией по построению такая однозначность необхо-
дима.
В качестве примера, приведем индуктивное определение множества термов и фор-
мул языка первого порядка.
Определение термов:
а) переменные и константы суть (атомарные) термы;
31

Страницы