Контрольні питання до теми 4

1. Виберіть правильний варіант відповіді 1 - 4 для наступних питань:

а) Скільки існує різних булевих функцій n змінних? б) Скільки існує різних наборів змінних для булевої функції n змінних?

Варіанти відповіді: 1) 2 ⁿ; 2) 2² ; 3) n ²; 4) n!.

2. Яке з наступних тверджень вірно:

а) Змінні булевої функції і сама булева функція приймають значення 0 або 1;

б) Змінні булевої функції приймають значення 0 або 1, а значення самої булевої функції збігаються із множиною дійсних чисел;

в) Значення змінних булевої функції збігаються із множиною дійсних чисел, а сама булева функція приймає значення 0 або 1;

г) Значення змінних булевої функції й значення самої функції збігаються із множиною дійсних чисел;

3. Виберіть правильний варіант відповіді 1 - 4 для наступних питань:

а) Скільки може бути різних ДНФ у булевої функції?

б) Скільки може бути різних ДДНФ у булевої функції?

в) Скільки може бути різних КНФ у булевої функції?

г) Скільки може бути різних ДКНФ у булевої функції?

Варіанти відповіді:

1 - нуль або одна; 2 - нуль або нескінченно багато; 3 - нуль або одна; 4 - одна; 5 - одна або нескінченно багато.

4. У який з нормальних форм (ДНФ, ДДНФ, КНФ, ДКНФ) перебуває дана формула булевої функції трьох змінних f (x, y, z):

а) x V y & z; б) x & y & z; в) (x V y)&(x VØ z); г) x V y V z; д) Ø x & y & z V y &Ø z; е) x VØ y; ж) x & z.

5. Яка релейно-контактна схема відповідає функції провідності f (x) = (x V y)&(x VØ z)?

6. Побудувати досконалу диз’юнктивну нормальну форму

Ù)Ù(;

ÙC);

;

(AÙ.

7. Записати досконалу диз’юнктивну нормальну форму бульових функцій, які приймають значення 1 тільки при таких значеннях аргументів:

(0,0),(0,1),(1,0);

(0,1,0),(1,0,0),(0,0,1);

(1,1,1,0),(1,1,0,1),(1,0,1,1),(0,1,1,1),(1,0,0,0);

(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1),(1,1,1,1);

(1,1,0,0),(1,0,0,1),(1,0,1,0),(0,1,1,0),(0,1,0,1),(0,0,1,1),(1,1,1,1).

8. Записати досконалу диз’юнктивну нормальну форму бульових функцій f1(x1,x2,x3), f2(x1,x2,x3), f3(x1,x2,x3) та f4(x1,x2,x3) які задані таблично:

X1	X2	X3	f1(x1,x2,x3)	f2(x1,x2,x3)	f3(x1,x2,x3)	f4(x1,x2,x3)

ЛІТЕРАТУРА

1. Капітонова Ю.В., Кривий С.Л., Летичевський О.А., Луцькиц Г.М., Печорін М.К. Основи дискретної математики. – К.: Наукова думка, 2002. – С.6-15.

2. Кужель О.В. Елементи теорії множин і математичної логіки. – К.: Рад. школа, 1977. – С. 4-24.

3. Новиков Ф.А. Дискретная математика для програмистов. – СПб.: Питер, 2002. – С.19-32.

4. Федосеева Л.И. Дискретная математика: Учеб.-практич. пособие. – Пенза: Изд-во Пенз. технол. ин-та, 1998. – С. 3-30.

РОЗДІЛ 5. КОМБІНАТОРНИЙ АНАЛІЗ

Тема 5.1. ОСНОВНІ ПОНЯТТЯ КОМБІНАТОРНОГО АНАЛІЗУ

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

Комбінаторика виникла у XVI столітті, коли у житті верхніх прошарків суспільства важливе місце займали азартні ігри (карти, кості, пасьянси, лотереї). Це стало рушійною силою у розвитку комбінаторики та теорії ймовірностей. Ряд перших комбінаторних задач розв’язали такі відомі математики як Паскаль, Ферма, Ейлер, Бернуллі, Лейбніц.

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

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

Дата добавления: 2014-10-17