СДНФ і СКНФ

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

Елементарної кон'юнкція називається кон'юнкція декількох змінних, взятих з запереченням або без заперечення, причому серед змінних можуть бути однакові: ¬ X X; X ¬ Z; ¬ X Y ¬ Z;
Елементарної диз'юнкція називається диз'юнкція кількох змінних, взятих з запереченням або без заперечення, причому серед змінних можуть бути однакові: ¬ XVX; XV ¬ Z; ¬ X V Y V ¬ Z;
Будь-яку диз'юнкцію елементарних кон'юнкція назвемо диз'юнктивній нормальною формою (ДНФ): (X X Ø Y) Ú(ØX Z)
Будь-яку кон'юнкцію елементарних диз'юнкцій назвемо кон'юнктівной нормальною формою (КНФ): (X VX V ¬ Y) (¬ XVZ)
C Цілком ДНФ називається ДНФ, в якій немає однакових елементарних кон'юнкція і всі кон'юнкції складаються з одного і того ж набору змінних, в який кожна змінна входить лише один раз (можливо з запереченням) X Y ¬ ZVX Y Z
C Цілком КНФ називається КНФ, в якій немає однакових елементарних диз'юнкцій і все диз'юнкції складаються з одного і того ж набору змінних, в який кожна змінна входить лише один раз (можливо з запереченням)
(¬ X VY V Z) (X V ¬ Y V Z.

Будь-яку функцію, крім констант 0 і 1, можна представити у вигляді як СДНФ, так і СКНФ

Алгоритм отримання СДНФ по таблиці істинності

1. Відзначити ті рядки ТИ, в останньому стовпці яких стоять 1:
2. Виписати для кожної зазначеної рядки кон'юнкцію всіх змінних наступним чином: якщо значення деякої змінної в цьому рядку = 1, то в кон'юнкцію включають саму цю змінну, якщо = 0, то її заперечення:
3. Всі отримані кон'юнкції зв'язати в диз'юнкцію:

Алгоритм отримання СКНФ по таблиці істинності

Відзначити ті рядки ТИ, в останньому стовпці яких стоять 0:

Виписати для кожної зазначеної рядки диз'юнкцію всіх змінних наступним чином: якщо значення деякої змінної в цьому рядку = 0, то в диз'юнкцію включають саму цю змінну, якщо = 1, то її заперечення:

Всі отримані диз'юнкції зв'язати в кон'юнкцію:

Завдання для самостійної роботи

Три викладачі відбирають завдання для олімпіади. На вибір пропонується кілька завдань. По кожній із завдань кожен з викладачів висловлює свою думку: легке завдання - (0) або важка (1). Завдання включається в олімпіадне завдання, якщо не менше двох викладачів відзначать її як важку, але якщо все три викладача вважають її важкою, то таке завдання не включається в олімпіадної завдання як занадто складне.

Складіть структурну формулу і функціональну схему пристрою, який на виході буде видавати 1, якщо завдання включена в олімпіадне завдання і 0, якщо не включена.