Совершенная дизъюнктивная нормальная форма

Материал из Циклопедии
Перейти к: навигация, поиск

Совершенная дизъюнктивная нормальная форма (СДНФ) для логической функции – это дизъюнкция различных элементарных конъюнкций всех аргументов (либо самих, либо их отрицаний) данной функции, причём в одинаковом порядке. При этом таблицы истинности для логической функции и её СДНФ совпадают.

Содержание

[править] Формула

Введём обозначения:

n – число аргументов функции;

(x1,x2,…,xn) – набор аргументов функции;

f(x1,x2,…,xn) – логическая функция;

fСДНФ(x1,x2,…,xn) – СДНФ логической функции;

arg[f(x1,x2,…,xn)=1] – фиксированный набор аргументов функции, обращающий функцию в 1;

argj[f(x1,x2,…,xn)=1] – значение аргумента xj в фиксированном наборе аргументов.

СДНФ01.JPG

СДНФ10.JPG – элементарная конъюнкция.

  • Для логической функции выбираются лишь те комбинации, которые приводят логическое выражение в состояние единицы.

В элементарную конъюнкцию записывается переменная без инверсии, если она в наборе равна 1, и с инверсией, если она равна 0.

[править] Пример

СДНФ11.JPG

[править] Другие формы:

[править] Ссылки

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты