Задание № 23 · ЕГЭ

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

Представление булевой функции через набор минтермов

2 мин чтенияСложность: Обновлено 29 сентября 2026

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

Совершенная дизъюнктивная нормальная форма (СДНФ)«Дизъюнктивная» означает использование операции ИЛИ, а «совершенная» — наличие всех переменных в каждом слагаемом.

Представление булевой функции как дизъюнкции минтермов, соответствующих наборам значений переменных, на которых функция равна 1. В каждом минтерме все переменные функции встречаются ровно один раз — с отрицанием или без него.

СДНФ является одним из видов нормальных форм. Её слагаемые соединяются операцией дизъюнкции, а внутри каждого слагаемого используется конъюнкция. СДНФ строят по строкам таблицы истинности, в которых значение функции равно 1.

\[F(x_1,x_2,\ldots,x_n)=\bigvee_{F(a_1,\ldots,a_n)=1}(l_1\land l_2\land\ldots\land l_n),\quad l_i=\begin{cases}x_i,&a_i=1\\\neg x_i,&a_i=0\end{cases}\]

№

Пример

Пусть функция \(F(A,B)\) равна 1 на наборах \((0,1)\) и \((1,1)\). Для набора \((0,1)\) получаем минтерм \(\neg A\land B\), а для набора \((1,1)\) — \(A\land B\). Поэтому СДНФ функции имеет вид \(F=(\neg A\land B)\lor(A\land B)\). Каждый минтерм содержит обе переменные.

Не путайте с обычной ДНФ

В обычной ДНФ не обязательно присутствуют все переменные в каждом слагаемом. Например, \(A\lor(B\land C)\) — это ДНФ, но не СДНФ для трёх переменных: в первом слагаемом отсутствуют \(B\) и \(C\).

Проверьте себя

Какой вид имеет минтерм для набора \((A,B,C)=(1,0,1)\)?

Для функции, которая нигде не принимает значение 1, СДНФ обычно записывают как константу лжи \(0\): подходящих минтермов нет. Практическое построение формы подробно рассматривается на странице построение СДНФ.

Главное за минуту

Главное

СДНФ — дизъюнкция минтермов, соответствующих единичным строкам таблицы истинности.
Каждый минтерм содержит все переменные ровно по одному разу.
Для нулевого значения переменной берут её отрицание, для единичного — саму переменную.