МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”
ФІЗИКО-ТЕХНІЧНИЙ ІНСТИТУТ
Д и с к р е т н и й а н а л і з 1 множини та відношення
МЕТОДИЧНІ ВКАЗІВКИ ДО ПРАКТИЧНИХ ЗАНЯТЬ
ДЛЯ СТУДЕНТІВ НАПРЯМІВ ПІДГОТОВКИ
“БЕЗПЕКА ІНФОРМАЦІЙНИХ І КОМУНІКАЦІЙНИХ СИСТЕМ” ТА “ПРИКЛАДНА МАТЕМАТИКА”
Затверджено Методичною радою НТУУ “КПІ”
Київ
“ПОЛІТЕХНІКА”
2010
Дискретний аналіз 1.Множини та відношення. Методичні вказівки до розв’язання задач для студентів напрямів підготовки “Безпека інформаційних і комунікаційних систем” та “Прикладна математика” / Уклад.: А.А. Шумська. – К.: ІВЦ «Політехніка», 2010. – 53 с.
Гриф надано Методичною радою НТУУ «КПІ»
(Протокол № ____ від _________ 2010 р.)
Н а в ч а л ь н е в и д а н н я
Д и с к р е т н и й а н а л і з 1
МНОЖИНИ ТА ВІДНОШЕННЯ
МЕТОДИЧНІ ВКАЗІВКИ
до розв’язання задач для студентів напрямів підготовки “Безпека інформаційних і комунікаційних систем” та “Прикладна математика”
Укладач: Алла Антонівна Шумська, к.ф.-м. наук, доц.
Відповідальний редактор: М.М.Савчук, д.ф.-м.н., проф.
Рецензент: О.Є.Архипов, д. техн. наук, проф.
Редактор хххххххххххххххххх
Темплан 2010 р., поз. ххх
Підп. до друку хх.хх.2010. Формат 60×84 . Папір друк. № 3. Друк офс.
Ум. друк. арк. 0,93. Обл.-вид. арк. 1,0. Зам. № ххх. Наклад 100 пр.
___________________________________________________________
Інформаційно-видавничий центр “Політехніка”
Друкарня НТУУ “КПІ”
03056, Київ-56, просп. Перемоги, 37 Зміст
Метод математичної індукції . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . 4
Множини . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Відношення . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Алгебраїчні структури . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Логіка висловлювань . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . 33
Список використаної літератури . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1. Метод математичної індукції
Метод математичної індукції – це один з найбільш поширених методів доведення математичних тверджень, в яких фігурують слова “для довільного натурального ”. Доведення за допомогою цього методу завжди складається з двох етапів: базис індукції та індукційний крок.
Базис індукції. Перевіряємо, що сформульоване твердження виконується для найменшого можливого значення .
Індукційний крок. Припускаємо, що твердження виконується для деякого довільного натурального . Доводимо, що це твердження виконується також і для.
Успішне виконання обох цих кроків і означає, що дане твердження є справедливим для будь-якого натурального .
Приклади розв’язання типових задач
Задача 1. Довести, що для будь-якого натурального числоділиться на 7.
Розв’язання.
Базис індукції. Якщо , то числоділиться на 7.
Індукційний крок. Припустимо, що для довільного числоділиться на 7. Примаємо
.
Отримане число ділиться на 7, оскільки воно є різницею двох цілих чисел, кожне з яких ділиться на 7 (зменшуване ділиться на 7 за припущенням індукції).
Задача 2. Довести, що для будь-якого натурального має місце тотожність
.
Розв’язання.
Базис індукції. Якщо , то, тобто тотожність виконується.
Індукційний крок. Припустимо, що тотожність вірна для , тобто
.
Доведемо тотожність для .
,
що і треба було довести.
Задача 3. Довести, що для будь-якого натурального.
Розв’язання.
Базис індукції. Якщо , то , тобто твердження вірне.
Індукційний крок. Нехай при дана нерівність виконується, тобто .Доведемо справедливість нерівності при . Маємо:
.
Отже, на основі принципу математичної індукції дане твердження доведене для будь-якого натурального .
A1
Довести, що ділиться на 6 для будь-якого натурального .
Довести, що
для будь-якого натурального .
Обчислити суму .
Довести, що для довільного натурального виконується нерівність.
Нехай тавідповідно катети та гіпотенуза прямокутного трикутника. Довести, щодля будь-якого натурального.
B1
Довести, що для будь-якого натурального числоділиться на 23.
Довести, що .
Довести, що
.
Довести, що сума кубів трьох послідовних натуральних чисел ділиться на 9.
Довести, що для будь-якого натурального числоділиться на 6.
Довести, що .
C1
Довести, що для будь-якого натурального.
Довести, що різних прямих, які проходять через одну точку ділять площину начастин.
Довести, що для будь-якого натурального
.
Довести, що для будь-якого натурального
.
Довести, що
.