Принцип модифицированной простой индукции

Министерство образования и науки Российской Федерации

новосибирский государственный технический университет

______________________________________________________________________

 

 

Веретельникова Е.Л.

 

ТеОРетическая информатика

Часть 1.

Доказательство правильности

Утверждено Редакционно-издательским советом университета
в качестве учебного пособия по курсу «Теоретическая информатика»

для студентов направления  27.03.04

 

Новосибирск
2015

УДК

Рецензенты:

И.Л. Еланцева, канд. техн. наук, доцент,
Г.В.Саблина, канд. техн. наук

 

Работа подготовлена на кафедре автоматики для студентов
 1 курса АВТФ, обучающихся по направлению 27.03.04
«Управление в технических системах»

 

Веретельникова Е.Л.

Теоретическая информатика: учеб.. пособие / Е.Л. Веретельникова. – Новосибирск: Изд-во НГТУ, 2015. – Ч.1. Доказательство правильности. 49 с.

 

ISBN

 

В работе изложен теоретический материал и рассмотрены многочисленные примеры для освоения основных принципов и приемов доказательства правильности программ, представленных блок-схемами или записанных на языках высокого уровня. Материал подразделен на четыре основные темы и сгруппирован таким образом, чтобы изучению одной темы соответствовало одно-два аудиторных занятия. В рамках каждой темы предлагаются упражнения для самостоятельной работы и контрольные вопросы.

Пособие будет полезно для студентов, изучающих программирование и интересующихся вопросами доказательства правильности программ.

© Новосибирский государственный
технический университет, 2015

Глава 1. МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ

Математическая индукция представляет собой некоторый общий способ доказательства в математике. Он, хотя об этом не всегда явно говорят, положен в основу всех приемов доказательства правильности программ для вычислительных машин. Данная глава знакомит читателя с математической индукцией – фундаментальным способом доказательства в математике.

Обычно математическую индукцию вводят как метод доказательства утверждений о положительных числах. В данном пособии сформулированы и проиллюстрированы на примерах самые простые версии этого метода – простая и строгая индукция, необходимые для понимания сути методов доказательства правильности программ. Обобщение этого метода на случай любых вполне упорядоченных множеств рассмотрено в других учебных пособиях [1], [3].

Простая индукция

Принцип простой индукции

Пусть S(N) — некоторое высказывание о целом числе N и требуется доказать, что S(N) справедливо для всех положи­тельных чисел N.

Согласно простой математической индукции, для этого необходимо

1. Доказать, что справедливо высказывание S(1).

2. Доказать, что если для любого положительного числа N справедливо высказывание S(N), то справедливо и высказы­вание S(N + 1).

Из приведенных выше двух утверждений вытекает, что S(N) справедливо для всех положительных чисел. Этот факт интуитивно очевиден, хотя при аксиоматической трактовке целых чисел сам принцип в такой формулировке следует рассматривать как аксиому. Из первого положения индукции следует, что справедливо S(1), а из второго — что справед­ливо S(2), если справедливо S(1). Но S(1) справедливо, сле­довательно, должно быть справедливо и S(2). Из второго положения индукции вытекает также, что справедливо S(3)> если справедливо S(2). Таким образом, поскольку мы знаем, что S(2) справедливо, то, следовательно, справедливо S(3) и т. д. Отсюда интуитивно видно, что эти два положения вместе доказывают справедливость S(1), S(2), S(3), ..., S(N)....

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

Пример 1.1. Мы хотим доказать, что для любого поло­жительного числа п сумма первых л положительных целых чисел равна п • (п + 1)/2, т. е.

1+2 + ...+ N=N• (N+1)/2

для любого положительного числа N. Используя простую индукцию, неооходимо только доказать, что

1. «Сумма» верна для N=1, т.е. 1 = 1• (1 + 1)/2. Это очевидно.

2. Если сумма первых п положительных целых чисел равна п • (п + 1)/2, то сумма первых п+1 положительных целых чисел равна (п +1) • [(п + 1)+1]/2, т. е. мы предпола­гаем, что формула 1 + 2 + ...+ N = п • (п + 1)/2,  справедлива. Это гипотеза индукции. На ее основании мы должны по­пытаться доказать, что справедлива формула

1 + 2 + ...+ N + (п +1) = (п +1) • [(п + 1)+1]/2.

Докажем это следующим образом:

1 + 2 + ...+ N + (п +1) = (1 + 2 + ...+ N )+ (п +1) =

[п • (п + 1)/2] + (п +1) =[(п² + п)/2] + (п +1) =

(По гипотезе индукции)

[(п² + п)/2] + [(2п + 2)/2] =( п² + 3п + 2)/2 =

(п + 1) • (п + 2)/2 = (п +1) • [(п + 1)+1]/2.

Что и требовалось доказать.

Поскольку мы доказали справедливость двух утверждений, то по индукции формула 1 + 2 + ... + п = п • (п + 1)/2 считается справедливой для любого положительного числа п.

Принцип модифицированной простой индукции

Иногда необходимо доказать, что высказывание S(N) справедливо для всех целых N³N₀. Для этого можно довольно легко модифицировать принцип простой индукции. Чтобы доказать, что высказывание S(N) справедливо для всех целых N, необходимо:

1. Доказать, что справедливо S(N₀)-

2. Доказать, что если S(N) справедливо для всех целых п³N₀, то справедливо и S(N+ 1).

В частности, если требуется доказать справедливость некоторого высказывания S(N) для любых положительных целых п (т. е. для N³0), то надо:

1. Доказать, что справедливо S(0).

2. Доказать, что для всех неотрицательных целых п справедливо S(N+1), если справедливо S(N).

Пример 1.2. Для любого неотрицательного числа п доказать, что

2⁰ + 2¹ + 2² + … + 2^N = 2^N+1 – 1.

Используя простую индукцию, мы должны

1. Доказать, что 2⁰ = 2⁰⁺¹ – 1   

Это  очевидно, так как   2⁰ = 1 = 2⁰⁺¹ – 1 = 2¹ – 1= 2 – 1 = 1.

2. Доказать, что если для всех неотрицательных целых п справедливо

2⁰ + 2¹ + 2² + … + 2^N = 2^N+1 – 1.

то справедлива и формула

2⁰ + 2¹ + 2² + … + 2^N + 2^N+1 = 2^(N+1)+1 – 1.

Высказывание 2⁰ + 2¹ + 2² + ... + 2 ^N = 2^N+1 – 1называется гипотезой индукции. Второе положение доказывается следующим образом:

2⁰ + 2¹ + 2² + … + 2^N + 2^N+1 = (2⁰ + 2¹ + 2² + … + 2^N ) + 2^N+1 =

( 2^N+1 – 1) + 2^N+1 = ( 2^N+1 + 2^N+1 ) – 1 =

(По гипотезе
индукции)

(2×2^N+1 + 2^N+1 ) – 1 = 2^N+2 – 1 = 2^(N+1)+1 – 1.

Иногда нужно доказать справедливость высказывания S(N) для целых п, удовлетворяющих условию п₀£п£M₀. Так как между п₀ и M₀ находится конечное число целых чисел, то справедливость S(N) можно доказать простым перебором всех возможных вариантов. Однако легче, а иногда и необходимо (если, например, мы не знаем конкретных значений п₀ и M₀) доказать S(N) по индукции. В этом случае можно воспользоваться одним из двух вариантов индукции:

Простая нисходящая индукция

1.Доказать, что справедливо S (п₀)

2. Доказать, что если справедливо S (п),то для любых целых п₀ £п£M₀–1 справедливо и S(N + 1).

Простая восходящая индукция

1. Доказать, что справедливо S(M₀).

2. Доказать, что если справедливо S(N), то для любых целых п₀+1£п£M₀ справедливо и S(N – 1).

Интуитивно понятно, что этого достаточно для доказательства справедливости S(N) при любых N, удовлетворяющих условию п₀ £п£M₀.

---

Дата добавления: 2018-05-12; просмотров: 407; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!