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

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

Обозначения

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