Метричні властивості диз'юнктивної нормальної форми

Оцінки складності представлення форм булевих функцій можуть бути використані в таких напрямках:

1) оцінки складності алгоритмів перетворення форм булевих функцій;

2) оцінки складності дискретних пристроїв, складність схем яких пропорційна складності форм представлення булевих функцій;

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

Нижче наведені оцінки складності булевих функцій у ДНФ, що використовують найбільше.

33.2.1. Зроблена ДНФ

Максимальна складність – 2ⁿn, типова складність - 2^n-1n.

33.2.2. Скорочена ДНФ

Максимальна складність – 3ⁿ/Ön, таким чином, якщо в методі Квайна-МакКласки будувати таблицю покриттів, то вона може мати 3ⁿ/Ön рядків й
2^n-1 стовпців.

Типова складність – 2ⁿ n^{log log n}, таким чином, довжина скороченої ДНФ звичайно перевищує довжину зробленої ДНФ.

33.2.3. Найкоротша ДНФ

Максимальна складність – 2^n-1.

Типова складність – 2^n-1/log n log log n.

33.2.4. Зіставлення оцінок

Відношення складності мінімальної ДНФ і найкоротшої ДНФ майже для всіх функцій дорівнює одиниці. Пошук найкоротшої ДНФ - простіша задача.

Типове відношення V_n складності довільної безнадлишкової ДНФ і найкоротшої ДНФ визначається формулою:

Vn ³ log n,

тобто довільна безнадлишкова ДНФ може бути в кілька разів гірше, ніж найкоротша. Число t_n без надлишкових ДНФ для майже всіх булевих функцій оцінюється формулою

t_n = (2^2n-1)^{log n log log n},

тобто перебір без надлишкових ДНФ при більших n - безперспективний.

Число q_n найкоротших ДНФ можна оцініти формулою

q_n ³ (2^2n-1)^CnÖn,

дійсно, скорочення таблиці покриттів при пошуку всіх безнадлишкових ДНФ не відрізняється від відповідного її скорочення при пошуку всіх без надлишкових ДНФ.

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

Контрольні запитання

1. Як виконується перевірка покриття інтервалу об'єднанням інтервалів на основі операції віднімання?

2. У чому посягає процедура розширення інтервалу в заданому об'єднанні інтервалів до максимального?

3. Які кроки містить процедура розширення інтервалу в заданому об'єднанні інтервалів до максимального?

4. Що такє ядерність інтервалу?

5. У чому полягає перевірка інтервалу на ядерність?

6. Які кроки містить алгоритм перевірки інтервалу на ядерність?

7. Як повинна виконувитися перевірка надмірності інтервалу в об'єднанні інтервалів?

8. Як використовуються розглянуті оцінки складності представлення форм булевих функцій?

9. Як визначаються розглянуті максимальна й типова складність зробленої ДНФ?

10. Як визначаються розглянуті максимальна й типова складність скороченої ДНФ?

11. Як визначаються розглянути максимальна й типова складність найкоротшої ДНФ?

12. Яка формула відносини складності довільної безнадлишкової ДНФ і найкоротшої ДНФ?

13. Якою формулою оцінюється число безнадлишкових ДНФ для майже всіх булевих функцій?

14. Як оцінюється число найкоротших ДНФ?

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

Основна

1. Новоселов В.Г., Скатков А.В. Прикладная математика для инженеров-системотехников. Дискретная математика в задачах и примерах. – К.: Учебно-методический кабинет высшего образования, 1992. - С.190-196.

Додаткова

2. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986. – С.25-31.

Для практичних занять

3. Методичні вказівки і завдання до контрольних робіт з дисципліни «Основи дискретної математики» для студентів очної та заочної форм навчання фахів 6.0804, 6.0915 / О.М. Мартинюк. – Одеса: ОНПУ, 2004. - ч.2. – С.75-76.