Тапсырма № 23 · ЕГЭ

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

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

2 мин чтенияҚиындық: Обновлено 29 қыркүйек 2026

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

Конъюнктивная нормальная формаНазвание отражает порядок операций: внешней операцией является конъюнкция, а внутри её частей используются дизъюнкции.

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

Общий вид

\[(l_{11} \lor l_{12} \lor \dots \lor l_{1k_1}) \land (l_{21} \lor l_{22} \lor \dots \lor l_{2k_2}) \land \dots \land (l_{m1} \lor l_{m2} \lor \dots \lor l_{mk_m})\]

Здесь каждый \(l_{ij}\) — литерал, то есть переменная или её отрицание. Внутри скобок используется дизъюнкция (\(\lor\)), а между скобками — конъюнкция (\(\land\)). Скобки иногда опускают, если порядок действий понятен.

№

Пример КНФ

Формула \((A \lor \neg B) \land (C \lor D \lor \neg A)\) записана в КНФ. В ней два дизъюнктивных члена: \((A \lor \neg B)\) и \((C \lor D \lor \neg A)\), соединённые конъюнкцией.

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

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

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

Какая формула записана в конъюнктивной нормальной форме?

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

Главное

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