МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ

“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

ФІЗИКО-ТЕХНІЧНИЙ ІНСТИТУТ

О с н о в и д и с к р е т н о ї

М А Т Е М А Т И К И

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

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

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

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

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

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

Київ

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

2007

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

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

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

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

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

Приклади розв’язання типових задач

Задача 1. Довести, що для будь-якого натурального числоділиться на 7.

Розв’язання.

• Базис індукції. Якщо , то числоділиться на 7.

• Індукційний крок. Припустимо, що для довільного числоділиться на 7. Примаємо

.

Отримане число ділиться на 7, оскільки воно є різницею двох цілих чисел, кожне з яких ділиться на 7 (зменшуване ділиться на 7 за припущенням індукції).

Задача 2. Довести, що для будь-якого натурального має місце тотожність

.

Розв’язання.

• Базис індукції. Якщо , то, тобто тотожність виконується.

• Індукційний крок. Припустимо, що тотожність вірна для , тобто

.

Доведемо тотожність для .

,

що і треба було довести.

Задача 3. Довести, що для будь-якого натурального.

Розв’язання.

• Базис індукції. Якщо , то , тобто твердження вірне.

• Індукційний крок. Нехай при дана нерівність виконується, тобто .Доведемо справедливість нерівності при . Маємо:

.

Отже, на основі принципу математичної індукції дане твердження доведене для будь-якого натурального .

A1

1. Довести, що ділиться на 6 для будь-якого натурального .

2. Довести, що

для будь-якого натурального .

3. Обчислити суму .

4. Довести, що для довільного натурального виконується нерівність.

5. Нехай тавідповідно катети та гіпотенуза прямокутного трикутника. Довести, щодля будь-якого натурального.

B1

1. Довести, що для будь-якого натурального числоділиться на 23.

2. Довести, що .

3. Довести, що

.

4. Довести, що сума кубів трьох послідовних натуральних чисел ділиться на 9.

5. Довести, що для будь-якого натурального числоділиться на 6.

6. Довести, що .

C1

1. Довести, що для будь-якого натурального.

2. Довести, що різних прямих, які проходять через одну точку ділять площину начастин.

3. Довести, що для будь-якого натурального

.

4. Довести, що для будь-якого натурального

.

5. Довести, що

.