русс | укр

Мови програмуванняВідео уроки php mysqlПаскальСіАсемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование


Linux Unix Алгоритмічні мови Архітектура мікроконтролерів Введення в розробку розподілених інформаційних систем Дискретна математика Інформаційне обслуговування користувачів Інформація та моделювання в управлінні виробництвом Комп'ютерна графіка Лекції


Нормальні і досконалі нормальні форми логічних функцій


Дата додавання: 2014-11-27; переглядів: 2376.


Будь-яка логічна функція може бути представлена у вигляді диз’юнктивної нормальної форми (ДНФ – диз’юнкція елементарних кон’юнкцій) та кон’юнктивної нормальної форми (КНФ – кон’юнкція елементарних диз’юнкцій).

Елементарними кон’юнкціями називаються кон’юнкції будь-якого числа різних змінних, узятих з інверсіями або без них.

Аналогічно елементарними диз’юнкціями називаються диз’юнкції будь-якого числа змінних, узятих з інверсіями або без них.

Для усякої логічної функції можуть існувати декілька рівносильних ДНФ і КНФ.

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

- елементарні диз’юнкції;

- елементарні кон’юнкції.

ДНФ: ;

КНФ: .

Існує вид ДНФ та КНФ, у якому логічна функція може бути записана єдиним чином. Це досконала нормальна форма.

Досконалою диз’юнктивною нормальною формою (ДДНФ) э диз’юнкція елементарних кон’юнкцій, які містять всі змінні з інверсіями або без них.

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

ДДНФ записується по одиницям за допомогою таблиць істинності:

a b c x

 

.

ДКНФ записується по нулям. До тієї ж таблиці:

.

КНФ ті ДНФ можна привести до ДДНФ та ДКНФ.

 


<== попередня лекція | наступна лекція ==>
Закони алгебри Буля | Приклад.


Онлайн система числення Калькулятор онлайн звичайний Науковий калькулятор онлайн