ВУЗ: Национальная металлургическая академия Украины
Категория: Учебное пособие
Дисциплина: Маркетинг
Добавлен: 06.02.2019
Просмотров: 2024
Скачиваний: 7
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНА МЕТАЛУРГІЙНА АКАДЕМІЯ УКРАЇНИ
В. В. Кузьменко, Г. Г. Швачич, В. М. Пасинков, Г. М. Бартєнєв
ОСНОВИ ДИСКРЕТНОЇ МАТЕМАТИКИ
Д
ОВІДКОВЕ КЕРІВНИЦТВО З ВПРАВАМИ ТА ЗАДАЧАМИ
Затверджено на засіданні Вченої ради академії
як навчальний посібник
Дніпропетровськ НМетАУ 2004
УДК 510.6
Кузьменко В. В., Швачич Г. Г., Пасинков В. М., Бартєнєв Г. М. Основи
дискретної математики. Довідкове керівництво з вправами та задачами
– Дніпропетровськ: НМетАУ, 2004. – 36 с.
В посібнику розглянуті основні визначення, прик-
лади розв’язання задач, представлені задачі та вправи
по темам, які потрібні при вивченні дисципліни “Осно-
ви дискретної математики”. Посібник необхідно вико-
ристовувати сумісно з конспектами лекцій по розділах
“Множини”, “Елементи алгебри логіки”, “Елементи те-
орії графів”
Призначений для студентів спеціальності 7.080401 –
інформаційні управляючі системи та технології.
Іл. 12. Бібліогр.: 17 найм.
Відповідальний за випуск Г. Г. Швачич, канд. техн. наук, проф.
Рецензенти: Б. І. Мороз, д-р техн. наук, проф. (Академія митної
Служби України)
Д. Г. Зеленцов, канд. техн. наук, доц. (УДХТУ)
© Національна металургійна академія
України, 2004
3
Т
ЕМА
1
М
НОЖИНИ
О
СНОВНІ ВИЗНАЧЕННЯ ТА ПРИКЛАДИ ВИРІШЕННЯ ЗАДАЧ З РОЗДІЛІВ
М
ЕТОДИ ЗАВДАННЯ МНОЖИН
.
О
ПЕРАЦІЇ НАД МНОЖИНАМИ
.
З
АКОНИ ОПЕРАЦІЙ НАД МНОЖИНАМИ
Р
ОЗДІЛ
Методи завдання множин
В
ИЗНАЧЕННЯ
: Інтуїтивне поняття множини. Нехай Р(х) означає
деяку властивість, тоді Р(а) буде означати ту саму властивість, але із замі-
ною х на а. Завдання множин в термінах властивостей досягається за до-
помогою інтуїтивного принципу абстракцій.
Інтуїтивний принцип абстракції, або аксіома згортання. Всяка
властивість Р(х) визначає деяку множину А за допомогою такої умови:
елементами множини А є ті і тільки ті предмети а, які мають властивість Р.
Згідно з принципом абстракції всяка властивість P(х) визначає єдину
множину, яку позначають {a | P(a)} і читають так: “Множина всіх тих пре-
дметів а, що Р(а)”.
Зауважимо, що властивість Р може являти собою спосіб побудови
елементів множини {a | P(a)}.
Нехай А – деяка множина, а Р(х) має вигляд х
≠ х. Тоді множина
{a
∈ A | P(a)} = {a ∈ A | a ≠ a}, очевидно, не має елементів. Із принципу
об’ємності випливає, що може існувати лише одна множина, яка немає
елементів. Ця множина називається пустою множиною і позначається
∅.
Приклади вирішення задач з розділу Методи завдання множин
1. Які з перелічених виразів є властивостями множин:
a) 3 ділить х;
b) х
<
х;
c) х
2
= 2;
d) х
2
+ 1
>
0.
Розв’язок. Властивостями є таки записи:
a) 3 ділить х;
b) х
<
х;
c) х
2
= 2;
d) х
2
+ 1
>
0.
2. Чи є властивостями множин наступні вирази:
a) для всіх х, у ху = ух;
b) існує таке х, що 2х
<
0
Розв’язок. Вирази:
4
a) для всіх х, у ху = ух;
b) існує таке х, що 2х
<
0 не є властивостями,
тому що їх не можна характеризувати як вірні чи хибні для певного х.
Р
ОЗДІЛ
Операції над множинами
В
ИЗНАЧЕННЯ
:
Введемо символи
⇔
,
∃х, ∀х,
⇒
які надалі будуть
служити для скорочення виразів “тоді і тільки тоді, коли”, “існує х такий,
що”, “для всякого х” і “слідує” або “випливає” відповідно.
Множина А називається підмножиною множини В(А
⊆
В), якщо всі
її елементи є також елементами множини В((А
⊆
В)
⇔
(а
∈
А
⇒
а
∈
В)).
При цьому множина В називається надмножиною множини А.
Тепер принцип об’ємності можна записати так:
А = В
⇔
(А
⊆
В і В
⊆
А).
Вираз А
⊂
В означає, що А
⊆
В і А не дорівнює В (А
≠
В). Якщо А
⊂
⊂
В, то множина А називається власною підмножиною множини В, а мно-
жина В – власною надмножиною множини А.
Покажемо, що пуста множина є підмножиною будь-якої множини А.
Припустимо, що твердження
∅
⊆
А хибне, тобто існує хоча б один еле-
мент х, що належить множині
∅
, який не є елементом множини А. Але
множина
∅
не має елементів. Отже, твердження
∅
⊆
А є істиною.
Приклади вирішення задач з розділу Операції над множинами
1. Чи є множина А = {a, b, c} підмножиною множини B = {a, b, c, d, e}?
Розв’язок. Множина А = {a, b, c} є власною підмножиною множини
B = {a, b, c, d, e}.
2. Чи є множина студентів юридичного факультету підмножиною множи-
ни всіх студентів університету?
Розв’язок. Множина студентів юридичного факультету – підмножина
множини всіх студентів університету.
3. Чи є множина парних натуральних чисел власною підмножиною мно-
жини всіх натуральних чисел?
Розв’язок. Множина парних натуральних чисел є власною підмножи-
ною множини всіх натуральних чисел.
5
4. Чи є множина натуральних чисел підмножиною множини всіх цілих чи-
сел, а множина цілих чисел – підмножиною множини всіх раціональних
чисел?
Розв’язок. Множина натуральних чисел є підмножиною множини
всіх цілих чисел, а множина цілих чисел – підмножиною множини всіх ра-
ціональних чисел.
Р
ОЗДІЛ
Закони операцій над множинами
В
ИЗНАЧЕННЯ
:
Нехай U – деяка множина. Тоді B(U) – множина всіх пі-
дмножин множини U. У цьому випадку множину U називають універсаль-
ною, а множину В(U) – множиною-степенем або булеаном множини U. На-
приклад, якщо U = {1, 3, 5}, то B(U) = {
∅
, {1}, {3}, {5}, {1, 3}, {1, 5}, {3, 5},
{1, 3, 5}}. Об’єднанням множин А і В називається множина, яка складається з
тих і тільки тих елементів, які входять до складу хоча б однієї з цих множин.
Одержана множина позначається А
∪
В тобто А
∪
В = {a | a
∈
A або a
∈
B}.
Приклади вирішення задач з розділу Закони операцій над множинами
5. Визначте елементи множин А = {1, 2, 3} та B = {1, 3, 4, 6 }, які входять
до об’єднання цих множин.
Розв’язок. Якщо А = {1, 2, 3} та B = {1, 3, 4, 6 } тоді А
∪
В = {1, 2, 3, 4, 6}.
6. Яке нове утворення матимемо при об’єднанні П – множини всіх парних
натуральних чисел, та Н – множини всіх непарних натуральних чисел?
Розв’язок. Нехай П – множина всіх парних натуральних чисел, а Н –
множина всіх непарних натуральних чисел; тоді П
∪
Н = N, де N – множина
всіх натуральних чисел.
В
ИЗНАЧЕННЯ
:
Перетином множин А і В називається множина, яка
складається з елементів, що входять до складу як множини А, так і множини
В. Одержана множина позначається А
∩
В, тобто А
∩
В = {a | a A і a
∈
B}.
Якщо А
∩
В = =
∅
, то множини А і В називаються такими, що не перети-
наються.