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

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

Определение и формальное представление

Пусть даны булевы переменные \(x_1, x_2, \dots, x_n\). Литералом называется переменная \(x_i\) или её отрицание \(\neg x_i\) (также обозначаемое как \(\overline{x_i}\)). Дизъюнктом (или элементарной дизъюнкцией) называется дизъюнкция одного или нескольких литералов, например: \(x_1 \lor \neg x_2 \lor x_3\). Конъюнктивной нормальной формой называется конъюнкция одного или нескольких дизъюнктов:

\[ \bigwedge_{i=1}^{m} \left( \bigvee_{j=1}^{k_i} L_{ij} \right) \]

где \(L_{ij}\) — литералы, \(m\) — количество дизъюнктов, \(k_i\) — количество литералов в \(i\)-м дизъюнкте. Каждый дизъюнкт должен быть истинен (равен 1) для того, чтобы вся формула была истинна. Если хотя бы один дизъюнкт ложен, вся КНФ ложна.

Пример КНФ для трёх переменных: \[ (x_1 \lor x_2) \land (\neg x_1 \lor x_3) \land (x_2 \lor \neg x_3) \]

Свойства

• Универсальность: любая булева функция, за исключением тождественно истинной (константа 1), может быть представлена в КНФ. Тождественно истинная функция может быть представлена как пустая конъюнкция (считается равной 1).
• Неединственность: для одной и той же функции существует множество эквивалентных КНФ. Минимальная по числу литералов или дизъюнктов форма называется минимальной КНФ.
• Связь с ДНФ: КНФ является двойственной формой по отношению к ДНФ. Если в ДНФ функция представлена как дизъюнкция конъюнктов, то в КНФ — как конъюнкция дизъюнктов.
• Выполнимость: задача проверки выполнимости КНФ (SAT) является классической NP-полной задачей. Любая формула в общей форме может быть сведена к КНФ с линейным увеличением размера (преобразование Тарского — Кука).

Виды КНФ

Совершенная конъюнктивная нормальная форма (СКНФ)

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

Пример: для функции \(f(x_1, x_2, x_3)\), равной 0 на наборах (0,0,1), (1,0,0) и (1,1,1), СКНФ будет: \[ (x_1 \lor x_2 \lor \neg x_3) \land (\neg x_1 \lor x_2 \lor x_3) \land (\neg x_1 \lor \neg x_2 \lor \neg x_3) \]

СКНФ единственна для каждой функции (с точностью до перестановки дизъюнктов и литералов внутри них).

Минимальная КНФ

Минимальная КНФ — это КНФ, содержащая наименьшее возможное количество литералов среди всех эквивалентных КНФ. Поиск минимальной КНФ является задачей минимизации логических схем. Для её решения используются методы Квайна — Мак-Класки, карты Карно, а также эвристические алгоритмы (например, ESPRESSO).

КНФ специального вида

• 3-КНФ: каждый дизъюнкт содержит ровно три литерала. Задача выполнимости 3-КНФ (3-SAT) является классической NP-полной задачей, используемой для доказательства сложности других задач.
• Хорновская КНФ: каждый дизъюнкт содержит не более одного положительного литерала (без отрицания). Задача выполнимости хорновских формул решается за полиномиальное время.
• Двойственная хорновская КНФ: каждый дизъюнкт содержит не более одного отрицательного литерала.
• КНФ с ограниченной шириной: максимальное количество литералов в дизъюнкте ограничено константой (например, 2-КНФ). Задача 2-КНФ (каждый дизъюнкт содержит ровно два литерала) решается за полиномиальное время.

Способы приведения к КНФ

Любую формулу алгебры логики можно привести к КНФ с помощью эквивалентных преобразований:

1. Замена импликации и эквиваленции:

• \(A \rightarrow B \equiv \neg A \lor B\)
• \(A \leftrightarrow B \equiv (\neg A \lor B) \land (A \lor \neg B)\)

1. Продвижение отрицаний внутрь (законы де Моргана):

• \(\neg (A \land B) \equiv \neg A \lor \neg B\)
• \(\neg (A \lor B) \equiv \neg A \land \neg B\)

1. Дистрибутивность дизъюнкции относительно конъюнкции:

• \(A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)\)

1. Упрощение (удаление повторяющихся литералов и дизъюнктов, содержащих переменную и её отрицание).

Пример: привести формулу \((x_1 \rightarrow x_2) \land \neg (x_3 \lor x_1)\) к КНФ:

• Замена импликации: \((\neg x_1 \lor x_2) \land \neg (x_3 \lor x_1)\)
• Применение де Моргана: \((\neg x_1 \lor x_2) \land (\neg x_3 \land \neg x_1)\)
• Уже является КНФ (второй дизъюнкт — это литерал \(\neg x_3\), его можно рассматривать как дизъюнкт из одного литерала).

Применение

Теория вычислительной сложности

КНФ является стандартной формой для задач выполнимости булевых формул (SAT). Большинство современных решателей SAT (например, MiniSat, Glucose) работают с формулами, представленными в КНФ. Задача SAT лежит в основе многих задач искусственного интеллекта, верификации программ, автоматического планирования.

Синтез цифровых схем

В цифровой электронике КНФ используется для описания логических схем, особенно в контексте программируемых логических матриц (ПЛМ) и вентильных матриц. КНФ позволяет реализовать функцию в виде двухуровневой схемы: первый уровень — элементы ИЛИ (дизъюнкты), второй — элемент И (конъюнкция). Однако на практике чаще используется ДНФ, так как она более естественна для реализации на элементах И-НЕ.

Автоматическое доказательство теорем

Метод резолюций, используемый в логическом программировании (например, в языке Prolog), основан на работе с формулами в КНФ. Для доказательства утверждения формула приводится к КНФ, после чего применяется правило резолюции.

Криптография и анализ безопасности

Некоторые криптографические примитивы (например, хеш-функции, шифры) могут быть представлены в виде системы уравнений в КНФ. Атаки на такие системы сводятся к решению SAT-задач.

Связь с другими формами

• ДНФ: двойственная форма; функция истинна, если истинен хотя бы один конъюнкт.
• Полином Жегалкина: представление функции в виде суммы по модулю 2 (XOR) конъюнкций. Не является нормальной формой в классическом смысле.
• Базис Шеффера и стрелка Пирса: функционально полные наборы, не использующие конъюнкцию и дизъюнкцию напрямую.

Критика и ограничения

• Размер: для некоторых функций минимальная КНФ может быть экспоненциально большой по сравнению с исходной формулой. Например, функция чётности (XOR от n переменных) имеет КНФ размером \(O(2^{n-1})\).
• Сложность минимизации: задача поиска минимальной КНФ является NP-трудной. Для практических целей используются приближённые алгоритмы.
• Неинтуитивность: для человека КНФ часто менее наглядна, чем ДНФ или таблица истинности, особенно при большом количестве переменных.

Источники

• Яблонский С. В. «Введение в дискретную математику». — М.: Наука, 1986.
• Гаврилов Г. П., Сапоженко А. А. «Сборник задач по дискретной математике». — М.: Наука, 1977.
• Hopcroft J. E., Motwani R., Ullman J. D. «Introduction to Automata Theory, Languages, and Computation». — Pearson, 2006.
• Cook S. A. «The complexity of theorem-proving procedures». — Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971.
• Бибило П. Н. «Основы языка VHDL». — М.: Солон-Пресс, 2006.