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

Конъюнкт – конъюнкция некоторых переменных или их отрицаний.

Дизъюнкт – дизъюнкция некоторых переменных или их отрицаний.

Если конъюнкт (дизъюнкт) состоит из всех переменных функции или их отрицаний, где каждая переменная участвует лишь единожды, то такой конъюнкт (дизъюнкт) называется совершенным.

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

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

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