Варіант 1

1

2

Варіант 2

1

2

Варіант 3

1

2

Варіант 4

1

2

Варіант 5

1

2

Варіант 6

1

2

Варіант 7

1 )

2

Варіант 8

1

2

Варіант 9

1

2

Варіант 10

1

2

Варіант 11

2

Варіант 12

1

2

Варіант 13

1

2

Варіант 14

1

2

Варіант 15

1

2

Варіант 16

1

2

Варіант 17

1

2

Варіант 18

1

2

Варіант 19

1

2

Варіант 20

1

2

Варіант 21

1

2

Варіант 22

1 )

2

Варіант 23

1

2

Варіант 24

1

2

Варіант 25

1

2

Варіант 26

1

2

Варіант 27

1

2

Варіант 28

1

2

Варіант 29

1

2

Варіант 30

1

2

Практична робота №4

1 Тема

Нормальні формули ДДНФ, ДКНФ.

2 Мета

Навчитися приводити формули до ДДНФ і ДКНФ.

3 Порядок виконання роботи

3.1 Виконати завдання відносно варіанту

Завдання

Побудувати ДДНФ та ДКНФ для заданої функції по таблиці істинності та за допомогою еквівалентних перетворень

4 Відповіді до приведених завдань

5 Висновок (по меті)

Зразок виконання нульового варіанту

х	у	z	F(x,y,z)
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

ДДНФ:

ДКНФ:

Завдання до практичної роботи №4

Варіант 1

1

2

Варіант 2

1 )

2

Варіант 3

1

2

Варіант 4

1

2

Варіант 5

1

2

Варіант 6

2

Варіант 7

1

2

Варіант 8

1

2

Варіант 9

1

2

Варіант 10

1

2

Варіант 11

1

2

Варіант 12

1

2

Варіант 13

1

2

Варіант 14

1

2

Варіант 15

1

2

Варіант 16

1

2

Варіант 17

1

2

Варіант 18

1

2

Варіант 19

1

2

Варіант 20

1

2

Варіант 21

1

2

Варіант 22

1 )

2

Варіант 23

1

2

Варіант 24

1

2

Варіант 25

1

2

Варіант 26

2

Варіант 27

1

2

Варіант 28

1

2

Варіант 29

1

2

Варіант 30

1

2

Практична робота №5

1 Тема

Елементи комбінаторного аналізу

2 Мета

Навчитися розв’язувати задачі комбінаторного аналізу

3 Порядок виконання роботи

3.1 Виконати завдання відносно варіанту 1-8

4 Відповіді до приведеного завдання

5 Висновок

Теоретичні відомості

Основні формули комбінаторики

Практичні завдання

ВАРІАНТ 1

1 Під час дослідження читацьких смаків студентів виявилось, що 60% читають журнал А, 50% - журнал В, 50% - журнал С, 30% - журнал А і В, 20% - журнал В і С, 40% - журнал А і С, 10% - журнал А, В і С. Скільки відсотків студентів: а) не читає жодного журналу; б) читає тільки 2 журнали; в) читає не менше двох журналів?

2 Розклад на день містить 5 уроків. Визначити кількість таких можливих розкладів при виборі з 11 дисциплін за умови, що жоден предмет не стоїть у розкладі двічі на день.

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

4 На футбольний турнір треба послати збірну команду в складі: тренер, його помічник, 2 асистенти, 20 футболістів, лікар і 2 масажисти. Тренерський склад може бути відібраний з 10 спеціалістів, футболісти - з 25 спортсменів, лікаря треба вибрати одного з трьох, а масажистів - двох з п'яти. Скількома способами може бути укомплектована така команда?

5 Із цифр 1,2,3,4,5,6,7,8,9 утворюють різні п'ятицифрові числа, що не мають однакових цифр. Визначити кількість чисел, в яких зустрічаються цифри 7,8,9 одночасно.

6 Скільки п’ятицифрових чисел можна утворити з дев’яти цифр 1, 2, 3, 4, 5,6,7, 8, 9?

7 Скільки слів можна отримати, якщо переставляти букви у слові “математика”?

8 Скільки наборів із 7 тістечок можна скласти, якщо у продажу є їх 4 сорти?

ВАРІАНТ 2

1 На одній з кафедр університету працює 13 чоловік, кожен з них знає хоча б одну іноземну мову. 10 чоловік знають англійську, 7 – німецьку, 6 – французьку, 5 - англійську та німецьку, 4 – англійську та французьку, 3 – німецьку та французьку. Скільки чоловік: а) знають всі три мови; б) знають тільки дві мови; в) знають лише англійську?

2 Команда з п'яти чоловік виступає на змаганнях, у яких бере участь ще 20 спортсменів. Скількома способами можуть бути розподілені місця, зайняті членами цієї команди, за умови, що жодне з них не може бути поділено?

3 Садівник протягом трьох днів має посадити 10 дерев десяти різних порід. Скількома способами він може розподілити за днями свою роботу, якщо буде висаджувати не менше одного дерева в день?

4 Ліфт, у якому знаходяться 9 пасажирів, може зупинятись на десяти поверхах. Пасажири виходять групами по два, три і чотири чоловіки. Скількома способами вони можуть вийти, якщо ліфт не повертається на поверх, де він уже був ?

5 Десятьох тенісистів мають розподілити на групи по 2,3 і 5 спортсменів для поїздки на три турніри, які обираються з 6 можливих. Скількома способами це можна зробити?

6 Скількома способами можна розділити 6 різних цукерок між трьома дітьми?

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

8 У поштовому відділенні продаються листівки 10 сортів. Скількома способами можна купити в ньому 12 листівок?

ВАРІАНТ 3

1 У класі навчається 35 чоловік. Усі вони у вільний час або плавають у басейні, або грають на скрипці, або працюють у ботанічному саду. 25 з них займаються плаванням та ботанікою, а 5 до того ж ще й музиканти. Чемпіон класу з плавання не грає на скрипці і не любить ботаніку, а два його товариша-ботаніки не вміють плавати, але добрі скрипалі. Серед скрипалів є 7 чоловік, які не плавають і не працюють у ботанічному саду. Скільки в класі скрипалів? Скільки чоловік відвідують басейн? Скільки ботаніків не цікавляться ні плаванням, ні музикою?

2 Скільки різних правильних дробів можна скласти з чисел 3, 5, 7, 11, 13, 17, 19, 23 так, щоб у кожний дріб входило два числа ?

3 У речовій лотереї розігрується 8 предметів. Усього в "урні" 50 квитків. Виймається 5 квитків. Скількома способами їх можна вийняти так, щоб: а) тільки два з них були виграшні; б) принаймні два з них були виграшні?

4 Із 8 тенісистів і 6 тенісисток формуюють три змішані пари (до пари входять по одному тенісисту і одній тенісистці). Скількома способами це можна зробити ?

5 У вищій лізі чемпіонату України з футболу грають 16 команд. Скільки існує способів розподілення І, II та III місця і двох команд, які перейдуть у першу лігу (дві останні команди) ?

6 Скількома способами можна розташувати 12 різних деталей у трьох ящиках?

7 У мами було 2 яблука, 3 груші та 2 апельсини. Кожен день вона давала дитині по одному фрукту. Скількома способами вона могла це зробити?

8 Скільки існує трикутників, довжини сторін яких мають одне з таких значень: 4, 5, 6, 7 см?

ВАРІАНТ 4

1 У класі навчається 40 чоловік. Із них мають трійки з англійської мови 19 учнів, з математики – 17, з фізики – 22, мають трійки лише з одного предмета: з фізики – 11, з англійської – 4, з математики – 4. 7 чоловік мають трійки і з математики, і з фізики, з них пятеро має трійки і з англійської мови. Скільки чоловік навчаються без трійок? Скільки чоловік мають лише по дві трійки?

2 Скільки можна скласти різних неправильних дробів, чисельниками і знаменниками яких є числа 3,5,7,13,17?

3 З лабораторії, у якій працює 25 чоловік, 5 співробітників мають поїхати у відрядження. Скільки може бути різних складів цієї групи, якщо начальник лабораторії, його замісник і головний інженер одночасно їхати не можуть ?

4 У турнірі беруть участь 12 шахістів. Визначити кількість різних розкладів першого туру (розклади вважаються різними, якщо вони відрізняються учасниками хоча б однієї партії; колір фігур та номер столу не враховуються).

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

6 У деякому казковому королівстві не було двох громадян з однаковим комплектом зубів. Якою могла б бути найбільша кількість мешканців цього королівства, якщо у людини 32 зуба?

7 Скількома способами можна переставити букви в слові “обороноздатність”, щоб дві букви “о” не стояли поряд?

8 Скільки можна побудувати різних прямокутних паралелепіпедів, довжини ребер яких виражаються натуральними числами від 1 до 10?

ВАРІАНТ 5

1 Підлога кімнати площею 12 м² вкрита 3 килимами: площа одного килима 5 м², другого - 4м², третього - 3м². Кожні 2 килими перекривають один одного на площі 1,5 м², до того ж 0,5м² з них припадає на ділянку підлоги, де перекриваються всі 3 килими. Яка площа підлоги, що не вкрита килимами? Яка площа ділянки, вкритої одним лише першим килимом?

2 На десяти картках записані цифри 0,1,2,3,. ..,9 (на кожній картці - по одній цифрі). Беруть чотири картки і складають із цифр, записаних на них, чотирицифрове число. Скільки різних чотирицифрових чисел можна отримати таким чином ?

3 Із групи, до складу якої входять 7 хлопчиків і 4 дівчини, треба сформувати команду з 6 чоловік так, щоб вона мала не менше двох дівчаток. Скільки існує способів сформувати таку команду ?

4 На футбольний турнір треба послати збірну команду в складі: тренер, його помічник, 2 асистенти, 20 футболістів, лікар і 2 масажисти. Тренерський склад може бути відібраний з 10 спеціалістів, футболісти - з 25 спортсменів, лікаря треба вибрати одного з трьох, а масажистів - двох з п'яти. Скількома способами може бути укомплектована така команда?

5 3 цифр 1,2,3,4,5,6,7,8,9 утворюють різні п'ятицифрові числа, що не мають однакових цифр. Визначити кількість чисел, у яких зустрічаються цифри 6 та 8 одночасно.

6 Скільки шестицифрових чисел можна утворити з дев’яти цифр 1, 2, 3, 4, 5, 6,7,8, 9?

7 Скільки слів можна утримати, якщо переставляти букви у слові “мисливство”?

8 Скільки наборів з 10 тістечок можна скласти, якщо у продажу є їх 6 сортів?

ВАРІАНТ 6

1 На базі відпочинку знаходиться 70 чоловік. З них 27 займаються в драматичному гуртку, 32 співають в хорі, 22 захоплюються спортом. Драмгурток уідвідують 10 чоловік з хора, а хор - 6 спортсменів, у драмгуртку 8 спортсменів, 3 спортсмени займаються і у драмгуртку і в хорі. Скільки чоловік не співають у хорі, не захоплюються спортом та не займаються у драмгуртку? Скільки чоловік зайняті лише спортом?

2 Скільки різних натуральних чисел можна скласти з цифр 0,1,2,3,4, щоб у кожному такому числі кожна з цих цифр зустрічалася не більше одного разу ?

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

4 Ліфт, у якому знаходяться 9 пасажирів, може зупинятись на десяти поверхах. Пасажири виходять групами по два, три і чотири чоловіки. Скількома способами вони можуть вийти, якщо ліфт не повертається на поверх, де він уже був ?

5 Десятьох тенісистів мають розподілити на групи по 2,3 і 5 спортсменів для поїздки на три турніри, які обираються з 7 можливих. Скількома способами це можна зробити ?

6 Скількома способами можна розділити 6 різних цукерок між трьома дітьми?

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

8 У поштовому відділенні продаються листівки 10 сортів. Скількома способами можна купити в ньому 12 листівок?

ВАРІАНТ 7

1 Якщо відомо, що кожний учень у школі вивчає хочаб одну із вказаних 3-х мов, знайдіть загальну кількість учнів у школі. Вивчають англійську - 28 учнів, французьку - 23 учні, німецьку - 23 учні, англійську та французьку - 12 учнів, англійську та німецьку - 11 учнів, французьку та німецьку - 8 учнів, всі 3 мови вивчають 5 учнів.

2 Скільки різних чотирицифрових чисел можна скласти з цифр 0,1,2,3,4,5,6,7 так, щоб у кожному з них була цифра 1 ? (Цифри в числі не повинні повторюватися).

3 Збори, на яких присутні 40 чоловік, обирають голову, секретаря і трьох членів комісії. Скількома способами це можна зробити ?

4 Із 9 тенісистів і 7 тенісисток формують три змішані пари (до пари входять по одному тенісисту і одній тенісистці). Скількома способами це можна зробити ?

5 У вищій лізі чемпіонату України з футболу грають 16 команд. Скільки є способів розподілення І, II та III місця і двох команд, які перейдуть у першу лігу (дві останні команди) ?

6 Скількома способами можна розташувати 12 різних деталей у трьох ящиках?

7 У мами було 2 яблука, 3 груші та 2 апельсини. Кожен день вона давала дитині по одному фрукту. Скількома способами вона могла це зробити?

8 Скільки існує трикутників, довжини сторін яких мають одне з таких значень: 4, 5, 6, 7 см?

ВАРІАНТ 8

1 У спортивному клубі займаються 38 чоловік. З них 16 грають у баскетбол, 17 – у хокей, 18 – у волейбол. Баскетболом і хокеєм захоплюються 4 чоловіки, баскетболом і волейболом – 3, волейболом і хокеєм – 5. Троє захоплюються фігурним ковзанням. Скільки чоловік захоплюються одночасно хокеєм, волейболом і баскетболом? Скільки чоловік захоплюються лише одним із цих видів спорту?

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

3 Скільки п'ятицифрових чисел можна утворити з цифр 2, 3, 6, 7, 8 (без повторення) так, щоб парні цифри не стояли поруч ?

4 У турнірі беруть участь 12 шахістів. Визначити кількість різних розкладів першого туру (розклади вважаються різними, якщо вони відрізняються часниками хоча б однієї партії; колір фігур та номер столу не враховуються).

5 Для привітання дівчат зі святом, яких у класі 12, хлопці вирішили купити 12 різних книг з 25, які запропонувало видавництво "Факт". Скільки є різних способів отримання подарунків дівчатами ?

6 У деякому казковому королівстві не було двох громадян з однаковим комплектом зубів. Якою могла б бути найбільша кількість мешканців цього королівства, якщо у людини 32 зуба?

7 Скількома способами можна переставити букви в слові “охорона”, аби дві букви “о” не йшли поряд?

8 Скільки можна побудувати різних прямокутних паралелепіпедів, довжини ребер яких виражаються натуральними числами від 1 до 10?

ВАРІАНТ 9

1 Знайти кількістьт цілих додатних чисел, що не більше 1000 і не діляться на жодне з чисел 3, 5 і 7.

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

3 Скількома способами можна вибрати трьох чергових із класу, у якому навчається 20 учнів ?

4 На футбольний турнір треба послати збірну команду в складі: тренер, його помічник, 2 асистенти, 22 футболісти, лікар і 3 масажисти. Тренерський склад може бути відібраний з 10 спеціалістів, футболісти - з 30 спортсменів, лікаря треба вибрати одного з трьох, а масажистів - трьох з п'яти. Скількома способами може бути укомплектована така команда?

5 3 цифр 1,2,3,4,5,6,7,8,9 утворюють різні п'ятицифрові числа, що не мають однакових цифр. Визначити кількість чисел, у яких зустрічаються цифри 5, 3, 4 одночасно.

6 Скільки трицифрових чисел можна утворити з дев’яти цифр 1, 2, 3, 4, 5, 6, 7, 8, 9?

7 Скільки слів можна отримати, якщо переставляти букви у слові “бібліотека”?

8 Скільки наборів з 15 тістечок можна скласти, якщо у продажу є їх 6 сортів?

ВАРІАНТ 10

1 Зайти кількість цілих додатних чисел, що не більше 1000 і не діляться на жодне з чисел 6, 7 і 15.

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

3 Скількома способами можна роздати 6 різних предметів трьом особам так, щоб кожна отримала по 2 предмети ?

4 Ліфт, у якому знаходяться 9 пасажирів, може зупинятись на десяти поверхах. Пасажири виходять групами по два, три і чотири чоловіки. Скількома способами вони можуть вийти, якщо ліфт не повертається на поверх, де він уже був ?

5 Десятьох тенісистів мають розподілити в групи по 2, 3 і 5 спортсменів для поїздки на три турніри, які обираються з 6 можливих. Скількома способами це можна зробити ?

6 Скількома способами можна розділити 6 різних цукерок між трьома дітьми?

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

8 У поштовому відділенні продаються листівки 10 сортів. Скількома способами можна купити в ньому 12 листівок?

Список літератури

1. Дискретная математика для программистов / Ф.А. Новиков. – СПб.: Питер, 2001. – 304 с.

2. Ю.М. Бардачев та ін. Дискретна математика. –К: Вища школа, 2002 – 287 с.

3. Р.М.Трохимчик. Збірник задач з теорії множин і відношень. - 2-е видання, перероб. і доповн.- К.: РВЦ “Київський університет ”, 2000. - 80 с.

4. Лихтарников Л.М., Сукачева Т.Г., Математическая логика, Москва, "Лань", 1999. - 283 с.

5. Н.К. Верещагин, А. Щень. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления.М.: МЦНМО, 2000 – 288 с.

6. Н.К. Верещагин, А. Щень. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств.М.: МЦНМО, 1999 – 128 с.

7. Гуц А.К. Математическая логика и теория алгоритмов: Учебное пособие. – Омск: Издательство Наследие, 2003. –108 с.

8. С.С. Шкільняк. Математична логіка і теорія алгоритмів: приклади і задачі. Навчальний посібник. К., 2000.-108 с.

9. И.А. Лавров, Л.Л. Максимова. Задачи по теории множеств, математической логике и теории алгоритмов. . — 4-е изд. М., 2001. – 256 с.

10. Р.М.Трохимчук. Теорія графів. Навчальний посібник для студентів факультету кібернетики - К.: РВЦ “Київський університет”, 1998. - 43 с.

11. Ю.В.Капіносов та ін. Основи дискретної математики, К.: Наукова думка. – 2002 , - 579 с.

12. О. Оре. Теория графов. М.: «Наука», 1980, 336 с

13. Бабенко Н.В. Дискретна математика. Збірник методичних вказівок до практичних робіт. Запорізький електротехнічний коледж, 2011

14. Бабенко Н.В. Дискретна математика. Методичні матеріали до самостійної роботи. Запорізький електротехнічний коледж, 2011

Додаткова література

1. Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. Введение в теорию автоматов, языков и вычислений, 2- е изд.. : Пер. с англ.-М.: Издательский дом “Вильямс”, 2002.-528 с.

2. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – 2-е изд., перераб. и доп. – М.: Энергоатомиздат, 1988. - 480 с.

3. И.А. Лавров, Л.Л. Максимова. Задачи по теории множеств, математической логике и теории алгоритмов, М., 1975. – 240 с.

4. В.А. Носов. Основы теории алгоритмов и сложности их вычисления. Курс лекций. М., 1992. – 139 с.

5. Столл Р. Множества, логика, аксиоматические теории. М.: Просвещение, 1968.

14