Метод математичної індукції

О С Н О В И Д И С К Р Е Т Н О Ї

М А Т Е М А Т И К И

МЕТОДИЧНІ ВКАЗІВКИ ДО ПРАКТИЧНИХ ЗАНЯТЬ

ДЛЯ СТУДЕНТІВ СПЕЦІАЛЬНОСТЕЙ

“ІНФОРМАЦІЙНІ УПРАВЛЯЮЧІ СИСТЕМИ І ТЕХНОЛОГІЇ”,

“ЛІКУВАЛЬНО-ДІАГНОСТИЧНІ КОМПЛЕКСИ” ТА

“МЕДИЧНІ ПРИЛАДИ ТА СИСТЕМИ”

Затверджено Методичною радою НТУУ “КПІ”

Київ

“ПОЛІТЕХНІКА”

Основи дискретної математики. Методичні вказівки до розв’язання задач для студентів спеціальностей “Інформаційні управляючі системи і технології”, “Лікувально-діагностичні комплекси” та “Медичні прилади та системи” / Уклад.: А.А. Шумська. – К.: ІВЦ «Політехніка», 2007. – 53 с.

Гриф надано Методичною радою НТУУ «КПІ»

(Протокол № ____ від _________ 2007 р.)

Н а в ч а л ь н е в и д а н н я

О С Н О В И Д И С К Р Е Т Н О Ї

М А Т Е М А Т И К И

МЕТОДИЧНІ ВКАЗІВКИ

до розв’язання задач для студентів спеціальностей

“Інформаційні управляючі системи і технології”,

“Лікувально-діагностичні комплекси”

та “Медичні прилади та системи”

Укладач: Алла Антонівна Шумська, к.ф.-м. наук, доц.

Відповідальний редактор: М.М.Савчук, д.ф.-м.н., проф.

Рецензент: О.Є.Архипов, д. техн. наук, проф.

Редактор хххххххххххххххххх

Темплан 2007 р., поз. ххх

Підп. до друку хх.хх.2007. Формат 60×84 . Папір друк. № 3. Друк офс.

Ум. друк. арк. 0,93. Обл.-вид. арк. 1,0. Зам. № ххх. Наклад 100 пр.

___________________________________________________________

Інформаційно-видавничий центр “Політехніка”

Друкарня НТУУ “КПІ”

03056, Київ-56, просп. Перемоги, 37

Зміст

1. Метод математичної індукції................................. 4

2. Множини................................................. 6

3. Відношення............................................... 15

4. Алгебраїчні структури..................................... 25

5. Логіка висловлювань....................................... 31

6. Булеві функції............................................ 37

7. Графи................................................... 43

Список використаної літератури............................. 28

Метод математичної індукції

Метод математичної індукції – це один з найбільш поширених методів доведення математичних тверджень, в яких фігурують слова “для довільного натурального ”. Доведення за допомогою цього методу завжди складається з двох етапів: базис індукції та індукційний крок.

1. Базис індукції. Перевіряємо, що сформульоване твердження виконується для найменшого можливого значення .

2. Індукційний крок. Припускаємо, що твердження виконується для деякого довільного натурального . Доводимо, що це твердження виконується також і для .

Успішне виконання обох цих кроків і означає, що дане твердження є справедливим для будь-якого натурального .