1   2   3   4   5   6   7
Ім'я файлу: Дискретна математика. Методичний посібник.pdf
Розширення: pdf
Розмір: 1376кб.
Дата: 22.04.2021
скачати

ЗМІСТ
ВСТУП .......................................................................................................................................... 2 1.
ОСНОВНІ ПОНЯТТЯ ТЕОРІЇ МНОЖИН ......................................................................... 3 1.1.
Основні позначення теорії множин ........................................................................... 3 1.2.
Операції над множинами ............................................................................................ 3 1.3.
Основні закони алгебри множин ................................................................................ 8 1.4.
Метод математичної індукції ................................................................................... 10 1.5.
Задачі для самостійного розв’язування ................................................................... 11 2.
БІНАРНІ ВІДНОШЕННЯ................................................................................................... 15 2.1.
Основні означення та позначення ............................................................................ 15 2.2.
Операції над відношеннями ...................................................................................... 16 2.3.
Властивості однорідних бінарних відношень ......................................................... 17 2.4.
Відношення еквівалентності ..................................................................................... 19 2.5.
Відношення порядку ................................................................................................. 21 2.6.
Задачі для самостійного розв’язування ................................................................... 23 3.
ЛОГІКА ВИСЛОВЛЮВАНЬ ............................................................................................. 30 3.1.
Основні означення та позначення ............................................................................ 30 3.2.
Рівносильні перетворення формул........................................................................... 32 3.3.
Логічне слідування. Аналіз міркувань .................................................................... 34 3.4.
Задачі для самостійного розв’язування ................................................................... 35 4.
ЛОГІКА ПРЕДИКАТІВ ...................................................................................................... 39 4.1.
Поняття предиката. Основні означення. ................................................................. 39 4.2.
Квантори ..................................................................................................................... 42 4.3.
Аналіз міркувань ........................................................................................................ 45 4.4.
Задачі для самостійного розв’язування ................................................................... 46
РЕКОМЕНДОВАНА ЛІТЕРАТУРА........................................................................................ 50

2
ВСТУП
Навчальна дисципліна "Дискретна математика та теорія алгоритмів" вивчається студентами факультету інформаційних технологій на протязі перших двох семестрів.
Актуальність вивчення основних понять та засад дискретної математики майбутніми спеціалістами в галузі інформаційних технологій зумовлена тим фактом, що основні способи подання та обробки інформації в інформаційних системах є дискретними за своєю природою [1, 2]. Тому важливою складовою процесу підготовки фахівців ІТ-сфери
є вироблення знань та навичок, які стосуються розуміння та використання сучасних моделей та методів обробки, аналізу та перетворення дискретної інформації.
Слід зазначити також велике методологічне значення вивчення дисципліни "Дискретна математика та теорія алгоритмів". Воно, зокрема, полягає у тому, що пере- важна більшість навчальних дисциплін, які входять до складу галузі знань 0501 —
"Інформатика та обчислювальна техніка", широко використовують позначення, поняття та моделі дискретної математики. У якості прикладу можна навести такі дисципліни, як "Алгоритми та структури даних", "Об’єктно-орієнтоване програмування", "Бази даних та знань", "Системи штучного інтелекту", "Математичне моделювання" тощо.
У методичному посібнику розглянуто навчальний матеріал, який входить до першої частини курсу «Дискретна математика та теорія алгоритмів». Посібник містить відомості з теорії множин, теорії бінарних відношень та математичної логіки, якій присвячено два останні розділи. На початку кожного розділу наведено основні позначення та означення, знання яких є обов’язковим для успішного засвоєння навчальної дисципліни. Важливі поняття та терміни, які уперше зустрічаються у тексті, виділено курсивом. Переважну більшість понять проілюстровано на змістовних прикладах.
Слід зазначити, що посібник має яскраво виражене практичне спрямування.
Основним його завданням є формування навичок із розв’язування задач із дискретними даними. При цьому перевагу надано графічним методам розв’язування задач, які, на думку автора, є наочними і більш доступними для першокурсників. Кожний підрозділ містить формулювання та детальний розв’язок значної кількості практичних завдань. У кінці кожного розділу наведено задачі для самостійного розв’язування, які можуть вико- ристовуватися студентами для підготовки до практичних занять, а також модульного та залікового контролю.
Виклад матеріалу у посібнику є надзвичайно стислим. Додаткові теоретичні відомості, обґрунтування тверджень, а також більш детальний розгляд відповідних розділів дискретної математики читач може знайти у підручниках, які наведені у переліку рекомендованої літератури. Велика кількість додаткових задач різної складності наведена у [9-12].

3
1. ОСНОВНІ ПОНЯТТЯ ТЕОРІЇ МНОЖИН
Основні означення, які мають відношення до теорії множин, можна знайти у підруч- никах [1-8].
1.1. Основні позначення теорії множин
x
A

— елемент x належить множині А.
x
A

— елемент x не належить множині А.
A
B

— множина А є підмножиною множини В (кожний елемент множини А нале- жить множині В).
A
B

— множина А є власною підмножиною множини B ( A
B

і
A
B

).

порожня множина (множина, яка не містить жодного елемента).
Uуніверсальна множина.
A потужність множини А (для скінченних множин потужність множини рівна числу елементів множини).
1.2. Операції над множинами
До основних операцій над множинами відносяться доповнення, перетин, об’єднан- ня, різниця, та симетрична різниця, для позначення яких використовуються відповідно символи
,
,
, \,
 

. Нижче наведено їх означення:


,
A
x x U x
A



доповнення множини А до універсальної множини U.


,
A
B
x x
A x
B
 


перетин множин А та В.


або
A
B
x x
A
x
B
 


об’єднання множин А та В.


\
,
A B
x x
A x
B



різниця множин А та В.

 

def
\
\
A B
A B
B A
 

симетрична різниця множин А та В (позначення def

читається як "рівне за визначенням").
Приклад 1.1. Нехай


5,6,...,30
U

— універсальна множина,
{6,8,9,10,12,14,
A

20,21,22,27}
,


3 6 |
непарне,
B
x
x
x




,


|
4 просте число
C
x x

 
. Вказати пе- релік елементів множини


\
D
B
A C


,
Розв’язок.
1) Задамо множини В та С переліком їх елементів:


9,15,21,27
B

,


7,9,13,15,19,25,27
C

2) Послідовно виконаємо операції над множинами: а)


5,6,8,10,11,12,14,16,17,18,20,21,22,23,24,26,28,29,30
C

б) Знайдемо симетричну різницю множини А та C за формулою:

 

\
\
A C
A C
C A
 

Оскільки


\
9,27
A C

,


\
5,11,16,17,18,23,24,26,28,29,30
C A

, то

4


5,9,11,16,17,18,23,24,26,27,28,29,30
A
C
 
в) Знайдемо різницю множин В та A C

:




\
15,21
B
A C


Відповідь:


15,21
D

Приклад 1.2. На діаграмі Ейлера-Венна зобразити множину \
C A
B

Розв’язок.
Зобразимо діаграми Ейлера-Венна для всіх операцій алгебри множин, які входять у формулу \
C A
B

, у порядку їх виконання:
A
A
B

Рис. 1.
A
B

\
C A
B

Рис. 2.
На правій діаграмі на рис. 2. зображена шукана множина.

5
Приклад 1.3. Довести, що для довільних множин А, В та С справджується рівність


\
\
C A
B
B
C
C A
   
Розв’язок.
Перший спосіб. Скористаємося діаграмами Ейлера-Венна. Для множини у лівій час- тині рівності відповідна їй діаграма зображена справа на рис. 2. Побудуємо діаграму для множини


\
B
C
C A
 
:
B
C

\
C A
Рис. 3.
Рис. 4. Діаграма Ейлера-Венна множини


\
B
C
C A
 
Порівняємо діаграми, наведені на рис. 2 (справа) та рис. 4. Легко переконатися, що вони ідентичні. Тому множини \
C A
B

та


\
B
C
C A
 
рівні.
Другий спосіб. Використаємо інтуїтивний принцип об’ємності, згідно до якого для доведення потрібної рівності достатньо довести, що

6


\
\
C A
B
B
C
C A
   
та


\
\
B
C
C A
C A
B
 


а) Доведемо перше включення. Нехай
\
x
C A
B


. Тоді


,
,
,
,
\ ,
\
,
,
x
C
x
C
x
C
x
A
x
C
x
A
x
C A
x
B
C
C A
x
C
B
x
A
B
x
C
x
C
x
A
B
x
B
x
B
 
 























   





 
 


 
















Таким чином ми показали, що довільний елемент х множини \
C A
B

є елементом мно- жини


\
B
C
C A
 
. Перше включення доведено. б) Доведемо друге включення. Нехай


\
x
B
C
C A
  
. Тоді
,
,
,
,
,
\
\ .
,
,
x
C
x
C
x
C
x
B
x
B
x
C
x
C
B
x
C A
B
x
C A
x
C
x
A
B
x
C
x
A
B
x
A
x
A
 
 











 











 








 


 















Ми показали, що довільний елемент х множини


\
B
C
C A
 
є елементом множини
\
C A
B

. Тому друге включення доведено.
Отже, множини \
C A
B

та


\
B
C
C A
 
є рівними.
Приклад 1.4. Із 40 програмістів 18 володіють мовою Pascal, 19 — мовою С++, 21 — мовою Java. Відомо, що 10 програмістів знають одночасно Pascal і С++, 7 — Pascal і Java,
8 — C++ і Java. Троє програмістів не володіють жодною із мов Pascal, С++, Java. Знайти кількість програмістів, які одночасно знають усі три мови програмування.
Розв’язок. У якості універсальної множини U візьмемо множину тих 40 програ- містів, про яких йде мова у задачі. Нехай Р, С, J — множини програмістів, які володіють мовами програмування Pascal, C++ та Java відповідно, і нехай х — шукана кількість програмістів, які одночасно знають усі три мови.
Перший спосіб. Для відшукання розв’язку скористаємося діаграмами Ейлера-Венна.
У кожній частині діаграми позначимо кількість елементів множини відповідної цій частині. Оскільки із 10 програмістів, які володіють і мовою Pascal, і мовою С++, х знає ще й мову Java, то 10 x

програмістів знають лише Pascal і С++ і не знають Java.
Позначимо це число на тій частині діаграми на рис. 5, яка відповідає множині


\
P
C
J

. Із застосуванням аналогічних міркувань отримуємо, що 7
x

програмістів знають лише мови Pascal і Java, 8 x

— лише мови С++ та Java.
Знайдемо тепер кількість програмістів, які володіють рівно однією із мов програму- вання Pascal, C++ та Java. Оскільки мову Pascal знає 18 програмістів, то кількість програмістів, які знають лише мову Pascal рівна

 

18 10 7
1
x
x
x
x




  
. Анало- гічно отримуємо, що

 

19 10 8
1
x
x
x
x


 
  
програмістів знають лише мову С++,

 

21 7
8 6
x
x
x
x


 
  
програмістів — лише мову Java. Позначимо отримані числа на діаграмі (див. рис. 5).

7
Рис 5. Діаграма до прикладу 1.4
Із урахуванням того, що загальна кількість програмістів рівна 40, ми можемо за- писати наступну рівність:

 
 

18 8
1 6
3 40
x
x
x
 
 


 
Перший доданок у лівій частині попередньої рівності відповідає кількості елементів мно- жини Р, останній — кількості програмістів, які не володіють жодною із мов. Після спро- щень отримаємо 36 40
x
 
. Звідси
4
x

Другий спосіб. Скористаємося формулою включень-виключень
P
C
J
P
C
J
P
C
P
J
C
J
P
C
J
  


        
Отримаємо
18 19 21 10 7 8 33
P
C
J
x
x
  



   

Множина P C
J
 
є множиною тих програмістів, які володіють принаймні однією із мов програмування Pascal, C++ чи Java. Тому
40 3 37
P
C
J
U
P
C
J
  
   
 
Отже, 37 33 x


. Звідси
4
x

Приклад 1.5. Нехай А — множина трикутників, В — множина чотирикутників, С —
множина правильних многокутників, D — множина многокутників, які мають принаймні один прямий кут, E — множина рівносторонніх многокутників. Вказати множини:
1)






\
D
A
E
A
C



2)


B
C
D
E
B


 
Розв’язок.
1) Виконаємо операції по черзі:

8 а)
D
A

— множина прямокутних трикутників. Позначимо цю множину через F.
б)

 
 

\
\
F
E
F E
E F



. Оскільки E
F
  
, то

 

\
\
F E
E F
E
F

 
в) A C E
 
г)





 

\
\
D
A
E
A
C
E
F
E





. Оскільки множини F та E не перетинаються, то


\
E
F
E
F


Відповідь:






\
D
A
E
A
C
F




, де F — множина прямокутних трикутників.
2) а) Знайдемо спочатку


B
C
D




B
C
D
B
C
B
D


   
. Оскільки B C

— множина правильних чотирикутників, а кожний правильний чотирикутник є квад- ратом, то B C
B
D
  
. Тому B C
B
D
B
D
    
. Отже,


B
C
D
B
D


 
— множина усіх чотирикутників, які мають хоча би один прямий кут. б) Скористаємося формулою \
A B
A
B
 
. Тоді отримаємо, що



 

\
B
C
D
E
B
B
D
E
B
E
B
B
D


      


Множина
E
B

— множина ромбів. Тому

 

\
E
B
B
D


— множина ромбів, які не є елементами множини
B
D

, тобто множина усіх ромбів, які не є квадратами.
Відповідь: Множина усіх ромбів, які не є квадратами.

  1   2   3   4   5   6   7

скачати

© Усі права захищені
написати до нас