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

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

Формула

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

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

(x₁,x₂,…,x_n) – набор аргументов функции;

f(x₁,x₂,…,x_n) – логическая функция;

f_СДНФ(x₁,x₂,…,x_n) – СДНФ логической функции;

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

arg_j[f(x₁,x₂,…,x_n)=1] – значение аргумента x_j в фиксированном наборе аргументов.

– элементарная конъюнкция.

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

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

Пример

Другие формы:

• совершенная дизъюнктивная нормальная форма (СДНФ);
• совершенная конъюнктивная нормальная форма (СКНФ);
• минимальная дизъюнктивная нормальная форма (МДНФ);
• минимальная конъюнктивная нормальная форма (МКНФ);
• алгебраическая нормальная форма (АНФ).

Ссылки

• Участник:Logic-samara