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

Дизъюнктивная нормальная форма

Представление логической функции как дизъюнкции конъюнкций литералов

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

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

Формула имеет дизъюнктивную нормальную форму, если она является дизъюнкцией одного или нескольких выражений, каждое из которых представляет собой конъюнкцию литералов. Литералом называют переменную или её отрицание, например \(A\), \(\neg A\), \(B\).

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

Общий вид

\[(L_{11} \cdot L_{12} \cdot \ldots) \lor (L_{21} \cdot L_{22} \cdot \ldots) \lor \ldots \lor (L_{k1} \cdot L_{k2} \cdot \ldots)\]

Здесь \(L_{ij}\) — литералы, символ \(\cdot\) обозначает конъюнкцию («И»), а \(\lor\) — дизъюнкцию («ИЛИ»). Конъюнкция может состоять даже из одного литерала: например, \(A \lor (\neg B \cdot C)\) уже является ДНФ.

№

Пример

Формула \((A \cdot \neg B) \lor (C \cdot D) \lor \neg E\) записана в ДНФ. Она состоит из трёх конъюнкций: \(A \cdot \neg B\), \(C \cdot D\) и отдельного литерала \(\neg E\), соединённых дизъюнкцией.

Не путайте с КНФ

В ДНФ внешняя операция — «ИЛИ», а внутри скобок — «И». В конъюнктивной нормальной форме наоборот: внешняя операция — «И», а внутри скобок — «ИЛИ». Например, \((A \lor B) \cdot (\neg C \lor D)\) — это КНФ, а не ДНФ.

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

Какая формула записана в ДНФ?

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

Главное

ДНФ — это дизъюнкция конъюнкций литералов.
Внутри ДНФ используются переменные и их отрицания, соединённые операциями «И» и «ИЛИ».
В ДНФ внешняя операция — «ИЛИ»; это отличает её от КНФ.