Контрольная работа - Основы дискретной математики

Работа добавлена на сайт samzan.net:

Операції над множинами

1. Довести тотожність (AB) = AB, використовуючи означення операцій над множинами.

Розв‘язання:

З вищенаведеного рівняння маємо такі операції над множинами:

об’єднання множин АВ= {a| aA або aB}

перетин множин АВ= {a| aA i aB}

доповнення множили А=U-A={a| aU i aA}

а(AB)  а  (AB)  – визначення доповнення

 (а (AB))  – визначення 

 ((аA)  (aB))  – визначення об’єднання

 (аA)  (aB)  – закон логіки де Моргана

 (аA)  (aB)  – визначення 

 (аА)  (аB)  – визначення доповнення

.  а (AB) – визначення перетину

2. Довести тотожність (AB) = AB, використовуючи означення операцій над множинами.

(AB) = AB

Доведення:

З вищенаведеного рівняння маємо такі операції над множинами:

об’єднання множин АВ= {a| aA або aB}

перетин множин АВ= {a| aA i aB}

доповнення множили А=U-A={a| aU i aA}

а(AB)  а  (AB)  – визначення доповнення

 (а (AB))  – визначення 

 ((аA)  (aB))  – визначення перетину

 (аA)  (aB)  – закон логіки де Моргана

 (аA)  (aB)  – визначення 

 (аА)  (аB)  – визначення доповнення

.  а (AB) – визначення об’єднання

3. Спростити всі вирази типу XOY, де X,Y{,U,A,A},O {,,\,÷}.

Розв‘язання:

В таблиці побудуємо всі можливі варіанти виразів типу XOY, де X,Y{,U,A,A},O {,,\,÷}:

( - пуста множина; U – універсальна множина; A – множина; A - доповнення множини)



об‘єднання



перетин

різниця

симетрична різниця





























A





A



A



A



















A



A



A















A









A



A



A





A





A



A



A



A



A



A



A





A



A



A



A



При спрощенні вищезазначених виразів застосовуємо визначення дій ,,\,÷, а саме:

об’єднання множин АВ= {a| aA або aB}

перетин множин АВ= {a| aA i aB}

різниця множин В\А = {a| aB i aA}

симетрична різниця множин А÷В={a| aB i aA або aA i aB}

Також, при спрощенні виразів мають місце такі тотожності:

згідно закону ідемпотентності:

А  A = A

А  A = A

властивості тотожності:

А   = A

А  U = A

властивості доповнення:

А  A= U

А  A= 

4. Спростити вирази, пояснивши кожну проміжну дію.

а) ( A\A)  (÷A)  (UA);

б) (AA)∩( AUA);

в) BC( ABC)( ABC).

Розв‘язання:

а) ( A\A)  (÷A)  (UA)

Спростимо вирази: A\A = A; ÷A = A; UA = U

Маємо: AAU

AAU = (за пріоритетом операцій) = A(AU) = (за формулами з завдання 3) = AA = A.

Відповідь: ( A\A)  (÷A)  (UA) =А

б) (AA)∩( AUA)

Застосуємо дистрибутивний закон  A((A)∩( UA))

Згідно з властивостями порожньої множини A =A  A(A∩( UA))

UA=A A(A∩A)

A∩A=A  AA = U – закон виключення третього

Відповідь: (AA)∩( AUA)= U

в) BC( ABC)( ABC) = застосовуємо дистрибутивний закон

= BC(BC(АA))= застосовуємо закон виключення третього

= BC(BCU)= BC((BC)U)= властивість універсальної множини

=B(C(BC))= B((CB)(CC))= застосовуємо дистрибутивний закон

= B((CB)U)=BU= U властивість універсальної множини

або

BC( ABC)( ABC) = застосовуємо дистрибутивний закон

= BC((АA)BC)= застосовуємо закон виключення третього

= (BC) ((АA)BC)= застосовуємо де Моргана

=(BC)((АA)BC)= застосовуємо закон виключення третього

=(BC)((АA)(BC))=

=(BC)(U(BC))= властивість універсальної множини

=(BC)(BC)= U застосовуємо закон виключення третього

Відповідь: BC( ABC)( ABC) = U

Метод математичної індукції

5. Довести методом математичної індукції, що 5∙23n-2 + 33n-1 кратне 19.

Доведення:

Спершу зауважу, що ціле число а ділиться на b тоді, і тільки тоді, коли виконується рівняння a=mb.

1) Перевіремо, чи буде рівняння кратне 19 при n=1. В цьому випадку формула набуває вигляду:

Значить, при n=1 рівняння дорівнює 19, тобто кратне 19.

2) Допустимо, що рівняння є істинним при будь-якому довільному натуральному n=k, кратне 19, тобто рівняння кратне 19.

Тоді розглянемо, чи буде вірне твердження при n=k+1

Таким чином, вираз кратний 19.

Таким чином, довели, що рівняння кратне рівняння при n=1, також це твердження істинне при будь якому довільному натуральному n=k,та істинне при наступному n=k+1. В силу принципу математичної індукції це означає, що рівняння кратне 19 для всіх натуральних n.

Комбінаторика

6. Нехай слово – це послідовність 5 різних букв алфавіту {а,б,в,г,д,е,ж,з}. Скільки всього таких слів?

Розв‘язання:

Першою буквою слова може бути одна з 8-ми множини {а,б,в,г,д,е,ж,з}.

Таким чином, якщо перша буква відібрана та за умовою задачі слово має різні букви, тобто не повторюються, то другу букву можна відібрати (8-1=7) способами.

3 букву: 8-2=6 способами.

4 букву: 8-3=5 способами.

5 букву: 8-4=4 способами.

Згідно основного правила комбінаторики, з множини{а,б,в,г,д,е,ж,з} можна скласти 8*7*6*5*4= 6720 слів, при умові, що всі букви будуть різні.

Відповідь: 6720 слів

7. Нехай слово – це послідовність 5 букв алфавіту {а,б,в,г,д,е,ж}, в якій немає двох однакових букв підряд. Скільки всього таких слів?

Розв‘язання:

Першою буквою слова може бути одна з 7-ми множини {а,б,в,г,д,е,ж}.

Так як за умовою задачі в слові не може бути немає двох однакових букв підряд, то при відборі наступної букви потрібно її виключити. Тобто друга буква може бути відібрана (7-1=6) способами.

При відборі третьої букви виключаємо тільки попередньо відібрану букву, тобто другу. Таким чином третю букву можна відібрати (7-1=6) способами.

Четверту букву можна відібрати (7-1=6) способами.

П‘яту букву можна відібрати (7-1=6) способами.

Згідно основного правила комбінаторики, з множини{а,б,в,г,д,е,ж} можна скласти 7*6*6*6*6= 9072 слів, при умові, що підряд не буде дві однакові букви.

Відповідь: 9072 слів.

8. В футбольному клубі 3 воротарі і 18 польових гравців. До гри допускається 1 воротар та 10 польових гравців. Скільки різних варіантів повинен розглянути тренер при формуванні команди?

Розв‘язання:

Потрібно вибрати 1 із 3 воротарів і 10 з 13 польових гравців.

Вибір воротаря: варіанти

Вибір польових гравців: варіантів

Кількість варіантів формування команди:

Відповідь: 131274 варіантів

9. Скільки різних слів можна одержати, переставляючи букви в слові „математика”?

Розв‘язання:

Слово „математика” включає наступні букви:

м – 2 (k1)

а – 3 (k2)

т – 2 (k3)

е – 1 (k4)

и – 1 (k5)

к – 1 (k6)

Загальна кількість букв – 10 (n)

Зробимо розрахунок згідно

Відповідь: 151200 слів

10. Скількома способами можна розставити 4 різні фігури на шаховій дошці?

Розв‘язання:

Маємо 64 клітинки шахової дошки (n) та 4 шахових фігури (k).

Для того, щоб порахувати скількома способами можна фігури розставити на шаховій дошці, зробимо наступний аналіз.

Для того, щоб розмістити першу фігуру на шаховій дошці, є 64 варіанти.

Після того,як вибрали місце для першої фігури, залишилось (64-1=63) клітинки. Значить, другу фігуру можна розмістити 63 способами.

Після розстановки двох фігур, залишається (64-2=62) клітинки. Третю фігуру можна розмістити 62 способами.

Залишається (64-3=61) клітинка. Четверту фігуру можна розмістити 61 способом.

Згідно основного правилу комбінаторики, розставити чотири різні фігури можна

(64*63*62*61=15 249 024) способами.

Відповідь: 15 249 024 способів.

11. На першому курсі факультету комп’ютерних наук вчиться 14 студентів-відмінників, на другому – 13, на третьому – 12, на четвертому – 11, на п’ятому – 7, на шостому – 6. Треба сформувати команду на олімпіаду з програмування з шести студентів, по одному студенту-відміннику з кожного курсу. Скількома способами це можна зробити?

Розв‘язання:

Для того, щоб сформувати команду на олімпіаду, потрібно з кожного курсу відібрати по 1 студенту-відміннику.

Команду із 6 студентів можна сформувати стількома способами: 14х13х12х11х7х6=1009008

Відповідь: 1009008 способів.

12. Скільки цілих невід’ємних розв’язків має рівняння х1+х2+х3+х4+х5=12?

Розв‘язання:

Нехай маємо цілі невід‘ємні числа х1, х2, х3, х4, х5, сума яких дорівнює 12:

тоді маємо скласти комбінацію з 5-ти елементів по m, взявши х1 – першого типу, х2 – другого, ... х5 – п’ятого.

Отже, число цілих невід‘ємних розв‘язків маємо: , де n=5 m=12

Відповідь: 4368 розв‘язків.

13. Скількома способами можна розмістити 5 різних книг на двох полицях?

Розв‘язання:

Полиць k =2, книги n = 5

1) Якщо на першій полиці знаходиться 5 різних книг,а на другій - 0. Їх можна розмістити 5! = 1*2*3*4*5 = 120 способами.

Якщо на першій полиці знаходиться 0 книг,а на другій - 5. Їх можна розмістити 5! = 1*2*3*4*5 = 120 способами.

При такому варіанті розміщення книг можливо 240 варіантів.

2) Якщо на першій полиці знаходиться 4 різних книг,а на другій - 1. Чотири книжки на полиці х можна розмістити 4! = 1*2*3*4 = 24 способами. Одну книгу відібрати з п‘яти – 5 варіантів. В такий спосіб книги можна розставити 24*5 = 120 способами.

Якщо на першій полиці знаходиться 1 книга, а на другій - 4. Їх можна розмістити 4!*5 = (1*2*3*4)*5 = 120 способами.

При такому варіанті розміщення книг можливо 240 варіантів.

3) Якщо на першій полиці знаходиться 3 різні книги,а на другій - 2. Їх можна розмістити таким чином.

Відібрати будь-які 2 книжки з п‘яти:

2 книги можна розставити 2! = 1*2 = 2 способами;

3 книги можна розставити 3!= 1*2*3=6 способами.

Таким чином книжки можна розставити 2!*3!*10=6*2*10=120 способами.

Якщо на першій полиці знаходиться 2 різні книги,а на другій - 3. Їх можна розмістити таким чином.

Відібрати будь-які 2 книжки з п‘яти:

3 книги можна розставити 3!= 1*2*3=6 способами.

2 книги можна розставити 2! = 1*2 = 2 способами;

Таким чином книжки можна розставити 3!*2!*10=6*2*10=120 способами.

При такому варіанті розміщення книг можливо 240 варіантів.

4) 5 різних книг на двох полицях (240+240+240 =720) способів.

Відповідь: 720 способів.

Відношення

14. Знайти Декартові добутки множин

а) {1,2,3}×{a,b},

б) {x,y}×{x,y,z},

в) ×{a,b}.

Розв‘язання:

а) Нехай А1={1,2,3}; А2={a,b},

тоді А1×А2= {1,2,3}×{a,b}= {(1,а), (1,b), (2,a), (2,b), (3,a), (3,b)}

б) Нехай А1={x,y}, А2={x,y,z},

тоді А1×А2={x,y}×{x,y,z}= {(x,x), (x,y), (x,z), (y,x), (y,y), (y,z)}

в) Нехай А1=, А2={a,b}

тоді А1×А2=.×{a,b}= 

15. Виписати всі елементи відношення R = {(x,y)| x+y=x2–y2}, яке задано на множині {1,2,-1,0,7,8,9}.

Розв‘язання:

x	y	x+y=x2–y2
2	1	ИСТИНА
-1	1	ИСТИНА
1	-1	ИСТИНА
0	-1	ИСТИНА
1	0	ИСТИНА
0	0	ИСТИНА
8	7	ИСТИНА
9	8	ИСТИНА

Відповідь: (2,1); (-1,1); (1,-1); (0,-1); (1,0); (0,0); (8,7); (9,8).

16. Побудувати рефлексивне замикання відношення {(1,2),(2,3),(1,3)}.

Розв‘язання:

Дане відношення R={(1,2),(2,3),(1,3)} не є рефлексивним. Побудуємо замикання, якому буде властива ця ознака.

Рефлексивне замикання відношення повинно містити всі пари виду (а,а)

Побудуємо рефлексивне замикання:

Rі={(1,2),(2,3),(1,3),(1,1),(2,2),(3,3)}

Відповідь: Rі={(1,2),(2,3),(1,3),(1,1),(2,2),(3,3)}

17. Побудувати симетричне замикання відношення {(1,2),(2,3),(1,3)}.

Розв‘язання:

Дане відношення R={(1,2),(2,3),(1,3)} не є симетричним. Побудуємо замикання, якому буде властива ця ознака.

Симетричне замикання відношення повинно містити всі пари, які будуть симетричні даним:

Rs={(1,2),(2,3),(1,3),(2,1),(3,2),(3,1)}

Відповідь: Rs={(1,2),(2,3),(1,3),(2,1),(3,2),(3,1)}

18. Побудувати транзитивне замикання відношення {(a,b),(d,c),(c,b),(b,c)}.

Розв‘язання:

Дане відношення R= {(a,b),(d,c),(c,b),(b,c)} не є транзитивним. Побудуємо замикання, якому буде властива ця ознака.

Маємо пари (a,b) та (b,c), отже відношення повинно містити пару (а,с)

Маємо пари (d,c) та (c,b), отже відношення повинно містити пару (d,b)

Маємо пари (c,b) та (b,c), отже відношення повинно містити пару (с,с)

Маємо пари (b,c) та (c,b), отже відношення повинно містити пару (b,b)

Додаємо спочатку ці пари:

Rt {(a,b),(d,c),(c,b),(b,c), (а,с),(d,b),(с,с),(b,b)}.

З цього виразу видно, що всі необхідні пари включені.

Транзитивне замикання відношення має вигляд:

Rt {(a,b),(d,c),(c,b),(b,c), (а,с),(d,b),(с,с),(b,b)}.

Відповідь: Rt {(a,b),(d,c),(c,b),(b,c), (а,с),(d,b),(с,с),(b,b)}.

1. Организация медицинской помощи в сельской местности
2. от простого к сложному следуя разработанной методике
3. провал чи традиційна крива ЖЦТ
4. Тема ’ 16- Географія країн релігійного туризму.html
5. Введение3 I РОЛЬ И ЗНАЧЕНПИЕ МОТИВАЦИИ ТИПЫ МОТИВАЦИЙ
6. Расчет стандартных посадок для подшипников скольжения, червячного колеса и вала
7. явление сложное и многостороннее
8. разному- Управление делами министерство ведомство; Общий отдел исполнительные органы власти;
9. 2014 г
10. . Фамилия имя отчество больного
11. темарский детский сад 1 Теремок Лямбирского муниципального района РМ Танец Мы ~ дети сол
12. Тема- Русская народная сказка СивкаБурка Тип урока- изучение нового
13. Методичні РЕКОМЕНДАЦІЇ до виконання курсових робіт по дисципліні «Макроекономіка»
14. Что такое ген Генетическая точка зрения.html
15. мирацидий; корацидий; адолескарий; спороциста; церкарий
16. Роль схемы в процессе реализации государственного стандарта
17. .300HPX GZI 1.600HPX Titnium Сабвуферы GZTW 20TX GZTW 25TX GZTW 30TX GZTW 38TX Активные сабвуферы GZTB 200XCT Корпусные сабву
18. Разработка роботизированного технологического комплекса механической обработки деталей типа фланец
19. тема рішень кожного з них
20. Учет расчетов с покупателями и заказчиками, расчетов по претензиям

Материалы собраны группой SamZan и находятся в свободном доступе