Статья 404

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

Правильность программы была доказана методом рассуждений от противного. Другим способом доказательства правильности программ является метод математической индукции. Этот метод удобно проиллюстрировать на арифметических примерах, поскольку в арифметике доказательства по индукции применяются очень часто и большинство читателей, по-видимому, с ними встречались. Напомним суть дела.
Пусть требуется показать, что все неотрицательные числа обладают свойством. Вначале доказываем, что 0, т.е. что 0 обладает свойством. Затем доказываем, что всякий раз, когда истинно, также истинно. После этого заключаем, что каждое неотрицательное целое число обладает свойством. В символической форме последовательность действий можно записать следующим образом.
Как убедиться в том, что заключение следует из посылок. Рассуждаем от противного.