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

Досконалі диз’юнктивна і кон’юнктивна нормальні форми

Як ми визначили вище, будь-яка формула має як ДНФ, так і КНФ.

Приклад. Знайдемо ДНФ і КНФ для формули .

– ДНФ

– КНФ.

Більше того, приведення деякої формули до ДНФ і КНФ не є однозначним. Для кожної формули існує нескінченне число рівносильних до неї ДНФ і КНФ. Дійсно, якщо приєднати до неповної ДНФ даної формули елементарні кон’юнкції вигляду і врахувати рівносильність , отримаємо нескінченну множину ДНФ, рівносильних до даної формули. Аналогічно, приєднуючи до деякої КНФ елементарні диз’юнкції вигляду і враховуючи рівносильність , отримаємо нескінченну множину КНФ, рівносильних до даної формули.

Серед множини ДНФ (КНФ), які має дана формула, існує унікальна форма, вона єдина для даної формули. Це – так звана досконала ДНФ (досконала КНФ).

Означення. Досконалою ДНФ (ДДНФ) називається диз’юнкція повних елементарних кон’юнкцій від змінних :

.

Приклад ДДНФ. ;

.

Означення. Досконалою КНФ (ДКНФ) називається кон’юнкція повних елементарних диз’юнкцій від змінних :

, .

Приклад ДКНФ. ;

.

Читайте також:

1. А/. Форми здійснення народовладдя та види виборчих систем.
2. Автоматизовані форми та системи обліку.
3. Аграрні реформи та розвиток сільського госпо- дарства в 60-х роках XIX ст. — на початку XX ст.
4. Акредитив та його форми
5. Активні форми участі територіальної громади у вирішенні питань ММС
6. Асимптотична нормальність й ЦПТ
7. Банківський контроль та нагляд: форми та мета здійснення. Пруденційний нагляд: поняття, органи та мета проведення.
8. Батьки мають право обирати форми та методи виховання, крім тих, які суперечать закону, моральним засадам суспільства.
9. Безособові дієслівні форми на –но, -то
10. Безробіття: суть, причини, форми та соціально-економічні наслідки
11. Білінійні і квадратичні форми в евклідовому просторі
12. Бланки, форми і штампи

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