Дискретная математика

51

2)Скількома способами можна поставити в ряд 7 хлопців та 5 дівчат так, щоб при цьому дві дівчини не стояли поруч?

3)Три робочих повинні зробити 10 різних деталей. Перший – 3 деталі, другий – 2, а третій – 5. Скількома способами вони можуть розподілити між собою роботу?

4)На заводі виробляються деталі трьох типів, яки потрібні для різних видів готової продукції. Відомо що для 55% готової продукції потрібні деталі першого типу, для 45% готової продукції потрібні деталі другого типу, для 40% - третього типу; для 20% готової продукції потрібні деталі першого та другого типу; 17% - першого та третього типу; 16% - другого та третього типу. Скільки відсотків готової продукції потребують всі три типа деталей?

17.1) Скількома способами можна сформувати групу №1 з трьох учнів і одного викладача, якщо є 80 учнів і 3 викладача; чи групу №2 з п’яти учнів і двох викладачів, якщо є 20 учнів і 3 викладача?

2)Скількома способами можна по кругу поставити 5 різних ляльок та 3 різні м’які іграшки так, щоб при цьому м’які іграшки не стояли поруч?

3)Дев’ятьох студентів необхідно розподілити на три групи по 3 студента, для відправлення цих груп на різні конференції. Конференції проходять у різних п’ятьох містах, з яких необхідно вибрати три. Скількома способами можна відправити цих студентів на можливі конференції?

4)Лікар веде чотири палат з номерами 1,2,3,4. Скільки способів обходу лікарем палат так, щоб порядок заходу лікарем до палати не відповідав її номеру?

18.1) У фортепіанному гуртку навчається 10 чоловік, у гуртку художнього слова - 15, у вокальному гуртку - 12 і у фотогуртку – 20 чоловік. Скількома способами можна сформувати трупу з чотирьох читців, трьох піаністів, п’яти співаків і одного фотографа?

2)Скількома способами можна розставити 9 різних книжок на полиці так, щоб дві задані книжки стояли поруч?

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

52

3)Два вчителя повинні розподілити групу з 12 чоловік на дві підгрупи по 6 чоловік для проведення лабораторних робіт. Скількома способами вони це можуть зробити?

4)Скільки шестизначних чисел діляться хоча б на одне з чисел 24, 18? Скільки з них діляться рівно на одне з них?

19.1) На біржу фірма має відрядити двох брокерів, трьох дилерів і одного менеджера. Скількома способами це можна зробити, якщо до складу фірми входять 15 брокерів, 10 дилерів, і 5 менеджерів?

2)Скількома способами можна розподілити виріб 5 однакових деталей та інших 7 однакових деталей на двох станках, які можуть виробляти обидва ці типа деталей, якщо хоча б по одній деталі повинен зробити кожен зі станків?

3)Скількома способами можна розкласти 9 різних предметів у чотири однакових ящики так, щоб у трьох з них опинилося по 2 предмета, а в одному - 3?

4)Скільки чотирьохзначних чисел діляться хоча б на одне з чисел 2, 12, 16? Скільки з них діляться рівно на два з них?

20.1) У лотереї розігрується 12 призів. Усього 40 квитків. Виймається 4 квитка. Скількома способами їх можна вийняти так, щоб принаймні два з них були виграшні?

2)На двох дачних ділянках необхідно посадити 3 черешні, 5 яблунь та 6 абрикосів. Скільки варіантів може бути такої посадки, якщо хоча б по одному дереву повинно бути посаджено на кожної ділянки?

3)Скількома способами можна розділити 12 різних ручок на 3 набора по 4 в кожному, а потім ці набори поділити між трьома учнями, при цьому не обов’язково, щоб кожен учень отримав набір?

4)70% людей люблять м’ясо, 50% - люблять молоко, 40% - люблять рибу. Хоча б один з цих продуктів люблять усі. М'ясо та молоко – люблять 33%, м'ясо та рибу – 27%, молоко та рибу – 24%. Скільки людей люблять усі три продукти?

21.1) У вазі стоїть пронумеровані 12 червоних і 7 рожевих гвоздик. Скількома способами можна вибрати з вази п’ять квітів так, щоб усі вони були одного кольору?

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

53

2)Скількома способами можна переставити букви в слові «оборонятись», щоб однакові букви не стояли поряд?

3)Скількома способами можна розділити 10 різних чашок, та 10 різних тарілок на п’ять наборів по дві чашки та дві тарілки?

4)У гардероб здають пальта 5 чоловік. Назад їм вертають пальта навмання. Скільки способів видачі пальт так, щоб не одно з них не досталося хазяїну?

22.1) Для привітання зі святом дівчат, яких у класі 10, хлопці вирішили купити по п’ять книг двох різних видів із 15, запропонованих видавництвом «Факт». Скільки існує різних способів отримання подарунків дівчатами?

2)Скількома способами можна поставити у колонну 8 чоловіків та 5 жінок так, щоб при цьому жінки стояли поруч?

3)В гуртожиток необхідно поселити у три двохмісні кімнати 6 дівчат, та три трьохмісні кімнати 9 хлопців. Скількома способами це можна зробити, якщо має значення тільки хто з ким буде в одній кімнаті?

4)У кіно продали 6 квитків з номерами місця. Люді займають ці 6 міст, але навмання. Скільки способів посадки людей так, щоб кожен з них не сидів на своєму місці?

23.1) Перший станок випустив 10 деталей з котрих 2 браковані, а другий станок випустив 15 деталей з 4 бракованими. Навмання вибираємо станок и 5 деталей зроблених на ньому. Скількома способами можна їх вибрати, щоб серед них було рівно 2 браку?

2)Скількома способами можна по кругу поставити 3 учня першого класу та 5 учнів другого класу так, щоб всі учні першого класу стояли поруч?

3)У вазі стоять пронумеровані 14 червоних гвоздик. Скількома способами можна зробити з них три букета по три гвоздики, та один букет з п’яти гвоздик?

4)Студенти групи університету можуть мати читацький квіток чи пропуск до гуртожитку, хоча одне обов’язково. Юнаків у групі 14; а студентів, які мають читацький квіток усього – 26. Дівчат з пропуском стільки ж, скільки й юнаків з читацьким квитком, дівчат з читацьким квитком та пропуском до гуртожитку було – 4. Скільки всього було студентів у групі?

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

54

24.1) Перший станок випустив 10 деталей з котрих 2 браковані, а другий станок випустив 15 деталей з 4 бракованими. Навмання вибираємо станок и 5 деталей зроблених на ньому. Скількома способами можна їх вибрати, щоб серед них було хоча б 2 браку?

2)Скількома способами можна переставити букви в слові «попередження», щоб однакові букви не стояли поряд?

3)Комісія складається з голови, та ще трьох відділів: перший по прийманню документів з двох чоловік; другий по проведенню письмового екзамену з чотирьох чоловік; третій по перевірки письмових робіт екзамену з трьох чоловік. На кафедрі 10 чоловік, скількома способами можна їх розподілити для утворення цієї комісії?

4)Знайти кількість цілих додатних чисел від 200 до 9000, які діляться рівно на два з чисел 16, 18, 15.

25.1) Для хлопців, яких було 12, дівчата на 23 лютого вирішили купити ручки трьох різних видів по чотири кожного виду. Всього у магазині їм було запропоновано 10 різних видів. Скільки існує різних способів отримання подарунків хлопцями?

2)Необхідно зробити 18 карток по 6 кожного варіанту для написання контрольної роботі студентами першого курсу. Скількома способами може бути розподілена ця робота між трьома асистентами кафедрі, якщо всі завдання на кожен варіант відомі?

3)Як можна розподілити 20 різних бусинок, для створення трьох бус: перше з 8, друге – з 7, та третє – з 5 бусинок?

4)Група з 8 чоловік писала анкету без фамілій. Скільки способів повернення цієї анкети так, щоб не один чоловік не получив своєї анкети?

Завдання 9. Знайти формулу, еквівалентну даній, що має m логічних операцій.

1.

C Þ

Ú

(m=1).

B

BA Ú BC Þ B

2.

(A Þ B)Ù

Ú B

(m=1).

AB

3.

Ú

Ú B

(m=2).

A Þ B

C Þ B

4.

(m=2).

ABC Ú ABC Ú ABC

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

55

5.

AB Ú

(m=1).

AB Ú AB

6.

(m=1).

(A Ú B)(B Þ A)Ú BC Ú AB

Ú BC

7.

AC Ú

(m=2).

BC Ú AB Ú AC

8.

Ú (

(m=1).

AB Ú BC

A

Þ B)Ú A Ú AC

9.

(A Þ B)(AÚ BC)(A Þ C)Ú

(m=1).

C

10.

(A Ú (B Þ C))(A Ú B Ú C)(A Ú D Ú C)

(m=1).

11.

AB Þ

(m=3).

СB Û А

Ú BC

Ú A Ù (B Ú C Û AB Þ

)

12.

C

Ú BA

(m=2).

B

C

13.

A Ú B Û C Ú A Þ

Ú AB

(m=2).

BC

14.

A Û B Ú

(m=1).

C Ù (A Þ BC)Ú (B Þ A)

(BA Û B Ú C Þ

)Ù A

15.

A Û B Ù

(m=1).

C Ú A

16.

(A Ú BC)Ù (A Þ B)Ù (A Þ C)Ú

(m=1).

C

17.

C Ú A Þ

Ú AB Û A Ú B

(m=2).

BC

A Ù (B Ú C Þ

Û BA)

18.

A Û B Ù

(m=1).

C Ú A

19.

(m=1).

BA Ú BC Ú C Þ B Þ B

A Ù (B Ú C Û AB Þ

)Ú C

20.

Ú BA

(m=2).

C

B

21.

(m=1).

BC Ú AB

Ú (A Ú B)Ù (B Þ A)Ú BC

22.

(

(m=1).

A

Þ B)Ú A Ú AB Ú BC

Ú AC

23.

B Ú

(m=1).

C Ù (A Þ BC)Ú (B Þ A)Û A

24.

(A Ú B Ú C)Ù (A Ú (B Þ C))Ù (AÚ D Ú C)

(m=1).

25.

Ú

Ú B

(m=2).

C Þ B

A Þ B

Завдання 10. За допомогою еквівалентних перетворень довести, що є протиріччям або тавтологією.

1.((X Ù Y )Þ (X Ú (X Ù Y )))Ù ((X Ú (X ÙY ))Þ (X Ù Y )).

2.(A Þ B)Ù (C Þ D)Þ (AÚ C Þ B Ú D).

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

56

3.(X Þ Y )Ù (Y Þ X )Ù ((X Ù Y )Ú (X Ù Y )).

4.((A Þ B)Þ A)Þ A .

5.((X Þ Y )Ù (Y Þ Z ))Þ X Þ Z .

6.(A Þ B)Þ ((B Þ C)Þ (A Þ C)).

7.(A Þ B)Ú (B Þ A).

8.(XY Ú X Z )Û ((X Þ Y )Ù (X Þ Z )).

9.A Ù B Ú A Ù B Ú A Ù B Ú A Ù B .

10.(X Þ Y )(X Þ Y )Ù X .

11.(A Þ B)Ù (С Þ D)Þ (A Ú C Þ B Ú D).

12.(A Þ (B Þ C))Þ ((D Þ B)Þ (A Þ (D Þ C))).

13.(A Þ (B Þ C))Þ ((A Þ B)Þ (A Þ C)).

14.A Ú B Þ ((A Þ C)Ù (B Þ D)Þ C Ú D).

15.((X Ú (X Ù Y ))Þ (X ÙY ))Ù ((X Ù Y )Þ (X Ú (X ÙY ))).

16.(C Þ D)(A Þ B)Þ (С Ú А Þ B Ú D).

17.((X Ù Y )Ú (X Ù Y ))(X Þ Y )(Y Þ X ).

18.(Y Þ Z )(X Þ Y )Þ X Þ Z .

19.(X Þ Y )Ù (X Þ Z )Û X Y Ú X Z .

20.(A Ù B)Ú (A Ù B)Ú (A Ù B)Ú (A Ù B).

21.(С Þ D)(A Þ B)Þ (A Ú C Þ B Ú D).

22.B Ú A Þ ((B Þ D)(A Þ C)Þ D Ú C).

23.(C Þ B)Ú (B Þ C).

24.A Þ B Ú С Û B Ù C Ù A .

25.ZX Þ YZX Þ Z Ú X .

Завдання 11. Побудувати ДДНФ і ДКНФ двома способами: за допомогою елементарних перетворень; за допомогою таблиць істинності.

1. (X Ú Y Ú Z )(X Þ Y )(X Û Z ).

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

57

2.(XY Ú Z Ú ZX )Û (XY Þ Z ).

3.(XY Þ Z )Û XY .

4.(XY Ú Z )Þ (X Û ZY ).

5.(Y Û X Þ Z )Ú (XY Û Z ).

6.(Y Ú XZ )(Y Ú Z )(Y Û X ).

7.Y Û X Ú ZX Ú XY Þ Z .

8.(Y Û X )Z Þ X .

9.XY Ú YZ Þ Z Û XZ .

10.(XY Û YZ )(Z Þ X ).

11.(Y Ú ZX )(XY Û Z Þ X ).

12.(XY Û Z )Ú (XY ).

13.(XYZ Ú Y X Z )Þ Y Ú Z .

14.XY Ú Z Û (XY Þ Z ).

15.Z Û XY Û Y X Þ Z .

16.(YX Þ XYZ )Ú XY .

17.(X Ú Y Û ZX )Þ XY .

18.XY Û Z Ú X Þ YX .

19.(X Ú Z Þ Y )X .

20.(X Ú Y )Û Z Þ X .

21.(X Ú Y )(X Û ZY ).

22.(X Û Y )Þ (Z Ú X Þ Y ).

23.(Z X Û XZ )Ú YX .

24.X Y Û Z Ú X Þ YX .

25.(XY Þ Z )(ZX Û Y ).

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

58

Завдання 12. Знайти поліном Жегалкіна двома методами: 1) за допомогою ДДНФ, 2) з допомогою основних властивостей без використання таблиць.

1.f = x ® y × z

2.f = x × y ® z

3.f = z ® y × x

4.f = x Ú y ® z

5.f = x × y ® z

6.f = x × y ® z

7.f = x × y ® z

8.f = x Ú y ® z

9.f = z × x ® y

10.f = x ® y × z

11.f = y ® z Ú x

12.f = y ® z × x

13.f = x ® z Ú y

14.f = x ® z Ú y

15.f = x ® y × z

16.f = y ® x × z

17.f = y ® x × z

18.f = z Ú x ® y

19.f = x Ú y ® z

20.f = x ® y ® z

21.f = (x ® y) × z

22.f = (x ® y) × z

23.f = (x ® y) × z

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

59

24.f = x ×( y ® z)

25.f = x Ú ( y ® z)

Завдання 13. Для наведеного графа виконати наступні завдання:

1)знайти остовне дерево мінімальної ваги;

2)за допомогою алгоритму Дейкстра знайти найкоротший шлях у графі між першою вершиною та вершиною з найбільшим номером;

3)знайти максимальний потік в мережі (дуги спрямовані зліва направо).

Навести розв’язання задач за шагами відповідних алгоритмів.

1)

2)

3)

4)

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

60

5)

6)

7)

8)

9)

10)

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com