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

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

Обозначения

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

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

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

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

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

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

Формула

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

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

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

Пример

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

• совершенная дизъюнктивная нормальная форма;
• совершенная конъюнктивная нормальная форма;
• минимальная дизъюнктивная нормальная форма;
• минимальная конъюнктивная нормальная форма);
• алгебраическая нормальная форма.

Ссылки

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