Алгоритм одержання мінімальної КНФ

1. Записують диз'юнкцію всіх конституент одиниці, які не входять до

ДДНФ функції F, тобто знаходять F.

2. Знаходять мінімальну ДНФ за відомим алгоритмом для функції F.

3. Беруть заперечення від функції F і перетворюють її за правилами

де Моргана в КНФ. Одержана КНФ буде мінімальною КНФ функції F.

Приклад 1. Знайти мінімальну КНФ логічної функції F=F(А, В, С) =

Розв'язування.

1. Знайдемо ДДНФ функції F: F =

2. Одержимо ДДНФ функції

3. Знайдемо скорочену ДНФ функції F, виконавши всі операції неповного склеювання і поглинання:

4. Складемо імплікантну матрицю для функції

5. Знайдемо мінімальні форми функції у ДНФ:

6. Взявши заперечення від обох частин останніх рівностей і застосо-

вуючи формули де Моргана, одержимо дві мінімальні кон'юнктивні нормальні форми:

 

41. Комбінаторика як розділ дискретної математики. Об'єкт дослідження комбінаторики. Комбінаторні задачі.

 

Під комбінаторикою звичайно розуміють розділ дискретної математики, присвячений розв'язанню задач про вибір та розміщення елементів скінченної множини згідно із заданими правилами. У результаті створюються необхідні комбінаторні об'єкти чи конфігурації. Характерними властивостями цих об'єктів є те, що вони відповідають деяким обмеженням щодо них, і тому завжди можна розпізнати дозволений комбінаторний об'єкт, який відповідає правилам його побудови, і недозволений, який не відповідає цим правилам.

Комбінаторні задачі

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

Після розв'язання першої задачі комбінаторики розв'язується не менш важлива друга - задача переліку комбінаторних об'єктів, які відповідають вихідним правилам їх побудови. Саме на розв'язання цієї задачі спрямовані сьогодні зусилля багатьох учених. Є досить багато задач, які так чи інакше стосуються цієї загальної задачі. Наприклад, до неї належить питання про кількість різних способів, якими можна розмістити групу студентів з 30 чоловік на 30 чи більше місцях, або про кількість способів проведення матчів з футболу між 10 різними командами?

Далі на основі отриманих розв'язків конкретних задач з переліку комбінаторних об'єктів розв'язується третя задача комбінаторики - це її побудова. Наприклад, потрібно не лише підрахувати кількість можливих варіантів розподілу ЗО студентів на ЗО місцях, а й побудувати всі ці розподіли або деякі з них у вигляді їх комбінаторних конфігурацій. Також може виникнути потреба побудувати таблицю матчів між 10 футбольними командами, а не тільки знати їх кількість.

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

42. Основне правило комбінаторики. Приклади.

Правило Добутку використовується тоді, коли кожний елемент множини А може бути вибраний разом з елементом множини В. Відповідно до кожного способу вибору елемента множини А буде зіставлятися к способів вибору елемента множини В. Тоді загальна кількість способів сумісного вибору елементів множини А з елементами множини В, очевидно, дорівнюватиме т* k.

Модель урн можна застосувати і для ілюстрації правила Добутку. У цьому випадку розглядаються дві урни, у першій з яких знаходиться т куль, а в другій k. Будемо вважати, що будь-якій кулі першої урни може відповідати будь-яка куля з другої урни. А оскільки в першій урні знаходиться т куль, то й кількість способів вибору куль з першої урни разом з різними кулями з другої урни буде дорівнювати т-k.

У загальному вигляді правило Добутку буде мати такий вигляд.

Якщо треба виконати якусь дію, що може бути виконана к сумісними діями, перша з яких може бути виконана n₁ способами, друга – п₂і т.д. до k - ої дії, яку можна виконати п_k способами, то основна дія може бути виконана М способами, де

У цьому правилі важливу роль відіграє сполучник і, який об'єднує різні дії в одну.

Приклад 2. На денне чергування в студентському гуртожитку вибирається два студента - один студент з трьох, що проживають у кімнаті 1, і один студент з чотирьох, які проживають у кімнаті 2. Скільки існує можливих способів формування різних пар з двохстудентів для чергування?

Розв'язання. Кількість способів чергувань двох студентів з різних кімнат відповідно до правила Добутку буде дорівнювати 12.

43. Невпорядковані множини. Сполучення. Приклади.

Сполученнями називаються різні неупорядковані підмножини,що мають k елементів та побудовані з множинами М число елементів якої дорівнює n.

Порядок елементів в довільній kелементній підмножині не має значення.

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

Загальна кількість таких сполучень визначається як

=

де символом n позначаються добуток натуральних чисел від 1 до заданого натурального числаn включно.

Зручно вважати,що 0!=1

Для сполучення має місце формула яку називається формулою симетрії і використовується коли

k> = -формула симетрії

= =1 =

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

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

 

44. Впорядковані множини. Перестановки. Приклади.

Впорядковані множини – це скінчені множини, для яких є істотнім порядок елементів. У відповідність кожному елементу множини можна поставити натуральне число. Наприклад, числові послідовності – впорядковані множини, А множина яблук на дереві – не є впорядкована множина. Для позначення впорядкованих множин використовують круглі дужки, а невпорядкованих - фігурні. Перестановка – це будь-яка впорядкована множина з n елементів. Перестановки відрізняють між собою порядком елементів. Наприклад, з множини А={0,1,2} можна утворити шість перестановок: (0,1,2), (1,2,0), (2,0,1), (0,2,1), (1,0,2), (2,1,0).
Кількість перестановок з n елементів позначається Р_n:

Задача 1.
Скільки трицифрових чисел можна утворити з допомогою трьох різних цифр, відмінних від 0.
Розв'язання.

Задача 2.
Скількома способами можна розмістити 6 учнів за 6 партами по одному за партою?
Розв'язання.

45. Впорядковані підмножини. Розміщення. Приклади.

Розміщення. Будь-яка впорядкована підмножина з m елементів даної множини М, яка містить n елементів, де , називається розміщенням з n елементів по m.

Задача 3.
Скільки різних послідовностей із 3 букв можна скласти?
Розв'язання.
Послідовності букв відрізняються між собою або буквами, або порядком їх розміщення. Отже слід знайти число розміщень з 33 елементів по 3 (вважаємо, що в алфавіті 33 букви).

46. Перестановки з повторенням. Приклади.

Розглянемо мультимножину M, а саме множину, яка може вміщувати однакові елементи. Наприклад, . Повторення елементів мультимножини можна задати і іншим способом .
Сформулюємо задачу. Нехай задано предмети типів. Скільки існує перестановок елементів першого типу, - другого типу і т.д., - -го типу?

Такі перестановки називають перестановками з повторенням. Практично, це перестановки елементів деякої мультимножини. Нехай, наприклад, . Розглядаючи елементи M як різні, тобто отримаємо перестановок. Без індексів багато з перестановок будуть однакові. Фактично кожна з перестановки множини M зустрілась би рівно раз, оскільки для елементу 1 індекси можна поставити способами, елементу - способами,елемента - способами. Тому число перестановок множини М дорівнює

У загальному випадку число перестановок мультимножини (перестановок з повторенням) буде рівне

,де

- загальна кількість елементів множини. Встановимо зв'язок між перестановками з повторенням і комбінаціями. Визначимо кількість перестановок з повторенням наступним чином. Із усіх місць перестановки першого типу займають -місце. Вибір місць для них можна зробити способами. Залишилось місць, на яких можна розмістити елементів другого типу способами і т.д. елементи -го типу - способами. За правилом прямого добутку

Приклад 9. Скільки існує різних перестановок букв в слові "математика"?
Розв'язання.
.

 

 

47. Сполучення з повторенням. Приклади.

Приклад. Якщо у продажу є квіти чотирьох сортів, то різних букетів, що складаються з 7 квіток, можна скласти

48. Біном Ньютона. Біноміальні коефіцієнти. Біноміальна теорема. Трикутник Паскаля.

ТрикутникПаскаля

Формула бінома Ньютона

Двочлен а+b називають біномом.
Коефіцієнти розкладу (а+b)ⁿ збігаються з n-м рядком трикутника Паскаля, тому:

Приклад
Знайти восьмий член розкладу (х-а)¹².
Розв'язування
(х-а)¹²=(х+(-а))¹².
За формулою бінома Ньютона маємо: