Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

ДМ_МУ_практ(1 часть)

.pdf
Скачиваний:
98
Добавлен:
16.03.2016
Размер:
1.51 Mб
Скачать

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

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

МЕТОДИЧНІ ВКАЗІВКИ до практичних занять з дисципліни

«ДИСКРЕТНА МАТЕМАТИКА» (Частина 1)

для студентів усіх форм навчання напряму 6.050101 – Комп’ютерні науки

ЗАТВЕРДЖЕНО кафедрою Інформаційних управляючих систем. Протокол № 4 від 10.11.11

Харків 2012

Методичні вказівки до практичних занять з дисципліни «Дискретна математика» (Частина 1) для студентів усіх форм навчання напряму 6.050101 – Комп’ютерні науки / Упоряд.: Н.В. Васильцова, Л.Е. Чала. – Харків: ХНУРЕ,

2012. – 68 с.

Упорядники: Н.В. Васильцова, Л.Е. Чала

Рецензент

В.О. Філатов, д-р техн. наук, проф. кафедри ШІ

ЗМІСТ

ВСТУП……………………………………………………………………….. 5

1 МНОЖИНИ. АЛГЕБРА МНОЖИН……………………………………... 6

1.1Мета заняття……………………………………………………………... 6

1.2Методичні вказівки з організації самостійної роботи студентів……... 6

1.3Контрольні запитання і завдання………………………………………. 7 1.3.1 Контрольні запитання…………………………………………………. 7 1.3.2 Контрольні завдання………………………………………………….. 8

1.4Приклади аудиторних і домашніх задач………………………………. 9

2 ВІДНОШЕННЯ ТА ОПЕРАЦІЇ НАД НИМИ…………………………… 14

2.1

Мета заняття……………………………………………………………...

14

2.2

Методичні вказівки з організації самостійної роботи студентів……...

14

2.3

Контрольні запитання і завдання……………………………………….

15

2.3.1 Контрольні запитання…………………………………………………. 15

2.3.2 Контрольні завдання…………………………………………………..

16

2.4

Приклади аудиторних і домашніх задач……………………………….

19

3 ФУНКЦІОНАЛЬНІ ВІДНОШЕННЯ …………………………………….

23

3.1

Мета заняття……………………………………………………………...

23

3.2

Методичні вказівки з організації самостійної роботи студентів……...

23

3.3

Контрольні запитання і завдання……………………………………….

23

3.3.1 Контрольні запитання…………………………………………………. 23

3.3.2 Контрольні завдання…………………………………………………..

24

3.4

Приклади аудиторних і домашніх задач……………………………….

25

4 БУЛЕВІ ФУНКЦІЇ ТА ПЕРЕТВОРЕННЯ……………………………….

26

4.1

Мета заняття……………………………………………………………...

26

4.2

Методичні вказівки з організації самостійної роботи студентів……...

26

4.3

Контрольні запитання і завдання……………………………………….

27

4.3.1 Контрольні запитання…………………………………………………. 27

4.3.2 Контрольні завдання…………………………………………………..

28

4.4

Приклади аудиторних і домашніх задач……………………………….

29

5 НОРМАЛЬНІ ФОРМИ ЗОБРАЖЕННЯ БУЛЕВИХ ФУНКЦІЙ……….

34

5.1

Мета заняття……………………………………………………………...

34

5.2

Методичні вказівки з організації самостійної роботи студентів……...

34

5.3

Контрольні запитання і завдання……………………………………….

34

5.3.1 Контрольні запитання…………………………………………………. 34

5.3.2 Контрольні завдання………………………………………………….. 35

3

5.4 Приклади аудиторних і домашніх задач………………………………. 36

6 МІНІМІЗАЦІЯ БУЛЕВИХ ФУНКЦІЙ…………………………………... 40

6.1 Мета заняття……………………………………………………………... 40 6.2 Методичні вказівки з організації самостійної роботи студентів……... 40 6.3 Контрольні запитання і завдання………………………………………. 41 6.3.1 Контрольні запитання…………………………………………………. 41 6.3.2 Контрольні завдання………………………………………………….. 41 6.4 Приклади аудиторних і домашніх задач………………………………. 44 7 ФУНКЦІОНАЛЬНА ПОВНОТА НАБОРІВ БУЛЕВИХ ФУНКЦІЙ…... 47 7.1 Мета заняття……………………………………………………………... 47 7.2 Методичні вказівки з організації самостійної роботи студентів……... 47 7.3 Контрольні запитання і завдання………………………………………. 48 7.3.1 Контрольні запитання…………………………………………………. 48 7.3.2 Контрольні завдання………………………………………………….. 48 7.4 Приклади аудиторних і домашніх задач………………………………. 49 8 ЛОГІКА ТА ОБЧИСЛЕННЯ ВИСЛОВЛЕНЬ…………………………… 53 8.1 Мета заняття……………………………………………………………... 53 8.2 Методичні вказівки з організації самостійної роботи студентів……... 53 8.3 Контрольні запитання і завдання………………………………………. 54 8.3.1 Контрольні запитання…………………………………………………. 54 8.3.2 Контрольні завдання………………………………………………….. 55 8.4 Приклади аудиторних і домашніх задач………………………………. 57 9 ЛОГІКА ТА ОБЧИСЛЕННЯ ПРЕДИКАТІВ……………………………. 61 9.1 Мета заняття……………………………………………………………... 61 9.2 Методичні вказівки з організації самостійної роботи студентів……... 61 9.3 Контрольні запитання і завдання………………………………………. 62 9.3.1 Контрольні запитання…………………………………………………. 62 9.3.2 Контрольні завдання………………………………………………….. 62 9.4 Приклади аудиторних і домашніх задач………………………………. 64

ПЕРЕЛІК ПОСИЛАНЬ……………………………………………………… 67

4

ВСТУП

Дисципліна «Дискретна математика» входить до складу дисциплін циклу природничо-наукової підготовки бакалаврів з напряму 6.050101 – «Комп’ютерні науки» і є однією з базових математичних дисциплін цього циклу.

Матеріал, який пропонується для вивчення першої частини дисципліни, складається з таких розділів: «Основи теорії множин»; «Відношення та їх властивості»; «Булева алгебра»; «Елементи математичної логіки («Логіка та обчислення висловлень», «Логіка та обчислення предикатів)».

Добір і викладення практичного матеріалу цих розділів дисципліни виконано з урахуванням вимог фундаментальної освіти з комп’ютерних наук, інформаційних технологій, сучасних інженерних і соціально-економічних напрямків з високим рівнем автоматизації та комп’ютеризації.

Методичні вказівки призначені для студентів молодших курсів, які спеціалізуються в області комп’ютерних наук і зобов’язані використовувати отримані практичні знання і навички при проектуванні та упровадженні інформаційно-управляючих систем і систем штучного інтелекту. Однак практичний матеріал з дисципліни «Дискретна математика» буде також корисним для тих, хто намагається підвищити кваліфікацію в напрямках (розділах дисципліни), що перелічені вище.

Для вивчення першої частини дисципліни «Дискретна математика» студент повинен мати знання математики в обсязі середньої школи і деякі основні поняття з розділів дисципліни з вищої математики.

У методичні вказівки з дисципліни «Дискретная математика» входить перелік литератури (підручники, навчальні посібники і монографії), яку можна використовувати для уточнювання матералу або, за бажанням, для більш глибокого вивчення деяких теоретичних положень і практичних прикладів.

5

1 МНОЖИНИ. АЛГЕБРА МНОЖИН

1.1 Мета заняття

Ознайомлення на практичних прикладах з основними поняттями теорії множин. Вивчення способів задання множин і способів визначення множин за допомогою операцій над деякими іншими множинами. Вивчення інструментів наочного подання відношень між множинами. Аналіз формул і тотожностей, які виражають властивості операцій алгебри множин. Вивчення і використання методів доведення тотожностей алгебри множин.

1.2 Методичні вказівки з організації самостійної роботи студентів

Під час підготовки до практичного заняття необхідно повторити лекційний матеріал, розділи літератури [1-10] з таких питань: інтуїтивне поняття множини (кантеровська теорія множин, її парадокси); скінченні й нескінченні множини; універсальна і порожня множини; способи задання множин; множина і підмножини, булеан множини; геометрична інтерпретація множин (круги Ейлера і діаграми Венна); операції на множинах; загальне визначення алгебри, поняття алгебри множин; аксіоми алгебри множин; тотожні перетворення формул алгебри множин.

Підготовка і виконання практичного заняття проводиться у два етапи. Перший етап пов’язаний з вивченням на практичних прикладах наступних основних понять і визначень теорії множин: множина, елемент множини, клас (сімейство), мультимножина, упорядкована множина, кортеж, довжина (розмірність) кортежу, скінченні, нескінченні, зчисленні множини, порожня множина, універсальна множина (універсум), способи задання множин, потужність множини, рівнопотужні множини, рекурсивно задана множина, підмножина, відношення приналежності і включення, властива і невластива підмножини, булеан множини, (множина-степень), теоретико-множинні операції на множинах, об’єднання множин, перетин множин, розбиття множини, різниця множин, доповнення (заперечення) множини, диз’юнктивна сума (симетрична різниця), геометричне подання множин і операцій над ними, загальне поняття алгебри, носій алгебри, сигнатура, бінарна та унарна операції, алгебра множин, закони алгебри множин, двоїсті символи.

При виконанні першого етапу студент повинен запропонувати і записати індивідуальний приклад для кожного з розглянутих вище понять і визначень.

6

Другий етап виконання практичного заняття пов’язаний з вирішенням практичних завдань, представлених у підрозділі 1.3, на основі запропонованих типових прикладів (див. підрозділ 1.4).

1.3 Контрольні запитання і завдання 1.3.1 Контрольні запитання

1.Що таке множина? Наведіть приклади різних множин.

2.Які способи задання множин Ви знаєте?

3.Що таке порожня множина? Обґрунтуйте необхідність використання порожньої множини.

4.Що таке універсальна множина? Наведіть приклади універсальних

множин.

5.Дайте визначення скінченної і нескінченної множини.

6.Дайте визначення счисленної множини.

7.Що таке потужність множини?

8.Дайте визначення підмножини. Наведіть приклади підмножин.

9.Яке відношення між множинами називають строгим включенням, а яке нестрогим включенням?

10.Чим відрізняється поняття включення ( або ) від поняття приналежності ( )?

11.У яких випадках можна говорити, що множини A , B і C рівні?

12.Які операції над множинами дозволяють будувати нові множини, використовуючи вже існуючі?

13.Яка пріоритетність виконання операцій над множинами?

14.Які способи графічної ілюстрації операцій над множинами Ви

знаєте?

15.Поясніть узагальнене поняття алгебри. Наведіть приклади алгебр.

16.Що таке алгебра множин?

17.Яка операція над множинами називається бінарною?

18.Яка операція над множинами називається унарною?

19.Назвіть основні аксіоми (закони) алгебри множин.

20.Які властивості має порожня множина та універсальна множина?

21.Опишіть принцип двоїстості в алгебрі множин, наведіть приклади двоїстих символів.

22.Поясніть способи перетворення формул алгебри множин.

7

1.3.2 Контрольні завдання

 

 

 

Завдання

1. Опишіть словами

кожне із

множин:

а)

A {x N | x ділиться на 2 і х делиться на 3};

б) A {x | x A і x B};

в)

A {x | x A і x B}.

 

 

 

Завдання 2.

Перелічить елементи множини {x | x ціле і

x2 100}.

 

Завдання 3.

Перелічить елементи множини

 

 

 

X {x | x голосна буква українського алфавіту}.

Завдання 4. Опишіть множину {a, b, c, d, e, f , g, h, i, j} за допомогою характеристичної властивості.

Завдання 5. Перелічить підмножини множини . Завдання 6. Перелічить підмножини множини {a, b, c, d}.

Завдання 7. Визначите кількість елементів у кожній множині:

а) { , { }}; б) {{ , { }}}; в)

{ ,{ }, a, b, {a, b},{a, b, {a, b}}}; г);

{1, 2, 3, {1, 2, 3}}; д) { ,{ },{ ,{ }}}.

 

Завдання 8. Нехай множина перших 20 натуральних чисел це універсум. Запишіть такі її підмножини: A – підмножина парних чисел; B – підмножина непарних чисел; C – підмножина квадратів чисел; D – підмножина простих чисел.

Завдання 9. Чи рівні між собою множини A і B (якщо ні, то чому?):

а) A {2, 5, 4}, B {5, 4, 2};

б) A {1, 2, 4, 2}, B {1, 2, 4};

 

в) A {2, 4, 5}, B {2, 4, 3};

 

г) A {1, {2, 5}, 6},

B {1, {5, 2}, 6};

 

д) A {1, {2, 5}, 6},

B {1, 2, 5, 6}.

 

Завдання 10. Доведіть, що A B (A \ B) (B \ A) (A B) , де A і B

множини.

 

 

 

 

 

 

 

 

 

Завдання

11.

Нехай A {1, 2, 3, 4, 5, 6, 7},

B {4, 5, 6, 7, 8, 9,10},

C {2, 4, 6, 8,10}, а U {1, 2, 3, ...,10}. Визначити множини: 1) A C ; 2) A B ;

 

 

 

 

 

3) A (B C) ; 4) ( A B) C ; 5) ( A B) ; 6) A B ; 7) A B ; 8) A B .

Завдання

12. Чи

існують такі множини A ,

B , C , що A B ,

A C , ( A B) \ C ?

Завдання 13. Доведіть наступну рівність ( A B) A A B .

8

Завдання 14. Доведіть рівність A B A B .

Завдання 15. Доведіть за допомогою тотожних перетворень співвідношення: A \ ( A \ B) B \ (B \ A) ; (A \ B) \ C (A \ C) \ (B \ C) . Результат перевірте за допомогою діаграм Ейлера-Венна.

Завдання 16. У якому відношенні перебувають множини A і B , якщо

A \ B B \ A ?

Завдання 17. Покажіть справедливість тотожностей: а)

A B B A B ; б) ( A B C) ( A B C) B C .

Завдання 18. Виходячи з відношення приналежності, доведіть

справедливість наступних виразів: а) A (B \ A) A B ; б)

A (B \ A) ;

в) A \ (A B) A \ B ; г) A \ (B C) (A \ B) (A \ C).

 

Завдання 19. Використовуючи діаграми Эйлера-Венна, покажіть рівность двох множин ( A B) A B .

Завдання 20. Для кожної з наведених нижче множин використовуйте діаграму Ейлера-Венна і заштрихуйте ті її частини, які зображують задані множини: 1) A B ; 2) ( A B) ; 3) ( A B) A B ; 4) A (B C) ; 5) (B C) A; 6) B ( A C) ; 7) ( A B C) .

Завдання 21. Знайдіть наступні множини: а) { }; б) { } { }; в)

{ , { }} \ ; г) { , { }} \ {{ }}.

1.4 Приклади аудиторних і домашніх завдань

Завдання 1. Пояснити, чому 3 {1, 2, 3, 4}, а {1, 2} {{1, 2, 3},{2, 3},1, 2}.

Розв’язок.

Множина {1, 2, 3, 4} складається із чотирьох елементів, одним із яких є 3, тому приналежність даного елемента множині записується як 3 {1, 2, 3, 4}.

Множина {{1, 2, 3},{2, 3},

1, 2}

складається із чотирьох

елементів:

множини {1, 2, 3}, множини {2,

3},

об’єкта (елемента множини)

1 і об’єкта

(елемента множини) 2. У складі цих елементів не існує множини {1, 2}, отже, співвідношення записується як {1, 2} {{1, 2, 3},{2, 3},1, 2}.

Завдання 2. Нехай задана множина A {3, 6, 9,12,15,18, 21, 24}. Описати цю множину за допомогою характеристичної властивості.

9

Розв’язок.

Множина A за допомогою характеристичної властивості записується так:

A {x | 0 x 24 і x кратне 3}.

Завдання 3. Довести, що множини A {2, 5, 4, 2} і B {5, 4, 2} рівні між собою.

Доведення.

Дві множини A і B рівні (тотожні) тоді й тільки тоді, коли кожний елемент A є елементом B і навпаки. Для даних множин ця умова виконується, отже, вони рівні між собою, тобто A B .

Завдання 4. Довести, що порожня множина є підмножиною будь-якої множини.

Доведення.

Припустимо, що існує множина A така, що A. Це означає, що в є

деякий елемент a , що не міститься в

A . Але це неможливо,

тому що не

містить жодного елемента.

 

 

 

 

 

 

 

 

Завдання 5. Нехай

A {a,b,c, f , g, d}, B {b,c, g, k,l}.

Знайти A B ,

A B , A \ B , A B .

 

 

 

 

 

 

 

 

 

Розв’язок.

 

 

 

 

 

 

 

 

 

A B {a, b, c, f , g, d, k, l},

 

 

A B {b, c, g},

 

 

A \ B {a, f ,d},

A B ( A B) \ (A B) {a, f , d, k, l}.

 

 

 

 

 

Завдання 6. Нехай M1 {x | sin x 1}, M 2 {x

 

2 k, де k N0}.

2

 

 

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

Розв’язок.

 

 

 

 

 

 

 

 

 

Крок 1. Покажемо, що M1 M 2 .

 

 

 

 

 

x M1 sin x 1 x

 

2 k,

де k N0 x M 2

M1 M 2 .

2

 

 

 

 

 

 

 

 

 

Крок 2. Покажемо, що M 2 M1 .

 

 

 

 

 

x M 2 x

 

2 k,

де k

N0

sin x 1 x M1

M 2 M1.

2

 

 

 

 

 

 

 

 

 

За результатами виконання кроків 1 і 2 робимо висновок, що M1 M 2 . Завдання 7. Довести, що A A B A \ B , де A і B множини.

Розв’язок.

Крок 1. Покажемо, що A A B A \ B

x A x A і x B або x A і x B x A B або x A \ B

10

Соседние файлы в предмете Дискретная математика