• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Алгоритм приведення до ДДНФ і ДКНФ довільної логічної функції

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

Подання булевої функції у вигляді

,

де диз'юнкція береться по всім , на яких , називається досконалою диз'юнктивною нормальною формою (ДДНФ). Усяка булева функція (крім 0) має єдину СДНФ.

Щоб одержати досконалу диз'юнктивну нормальну форму, треба взяти всі набори, на яких значення функції дорівнює 1 і записати для кожного з них кон’юнкцію змінних й їхніх заперечень. Якщо в наборі значення змінної 0 - то змінну треба взяти із запереченням, якщо 1 - без заперечення. З наборів кон’юнкцій змінних треба побудувати диз'юнкцію.

Приклад 1 .(Досконала диз'юнктивна нормальна форма).

Побудуємо досконалу диз'юнктивну нормальну форму функції, заданою наступною таблицею.

Таблиця 2. Функція задана за допомогою таблиці.

Набори, на яких функція дорівнює 1 – це (0,1,1), (1,0,1), (1,1,0), (1,1,1). Перший набір дає кон’юнкцію x & y & z, другий – x & y & z, третій – x & y & четвертий – x & y & z.

У результаті одержуємо (x & y & z) √ (x & y & z) √ (x & y & z√ (x&y&z).

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

Переглядів: 1731