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

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

¶Определение и основные понятия

В булевой алгебре переменные могут принимать значения 0 или 1. Элементарная конъюнкция — это конъюнкция (логическое умножение, операция И) нескольких переменных или их отрицаний, причём каждая переменная входит в конъюнкцию не более одного раза. Дизъюнктивная нормальная форма — это дизъюнкция (логическое сложение, операция ИЛИ) одной или нескольких таких элементарных конъюнкций.

Формально, если переменные \(x_1, x_2, \dots, x_n\), то ДНФ имеет вид: \[ \bigvee_{i=1}^{m} \bigwedge_{j=1}^{k_i} l_{ij} \] где \(l_{ij}\) — это либо переменная \(x_j\), либо её отрицание \(\neg x_j\), а \(m\) — количество элементарных конъюнкций.

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

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

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

Пример: для функции «исключающее ИЛИ» (XOR) от двух переменных таблица истинности даёт единицу на наборах (0,1) и (1,0). СДНФ этой функции: \[ (\neg x_1 \land x_2) \lor (x_1 \land \neg x_2) \]

¶История

Понятие нормальных форм в булевой алгебре восходит к работам английского математика Джорджа Буля (середина XIX века), который заложил основы алгебры логики. В 1854 году в книге «Исследование законов мысли» Буль ввёл операции логического умножения и сложения, хотя современная формализация ДНФ и КНФ была разработана позже. В начале XX века американский логик Эмиль Пост и другие исследователи систематизировали теорию булевых функций, включая канонические формы. ДНФ стала важным инструментом в 1930-х годах с развитием релейно-контактных схем (работы Клода Шеннона), а затем — в цифровой электронике и проектировании интегральных схем.

¶Свойства и характеристики

¶Универсальность

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

¶Минимизация

ДНФ не является единственной формой представления функции. Для упрощения логических схем часто применяют минимизацию ДНФ — получение кратчайшей (или минимальной) ДНФ, содержащей наименьшее число вхождений переменных. Основные методы минимизации:

• Метод Квайна — Мак-Класки — алгоритмический метод, основанный на склеивании конъюнкций.
• Карты Карно (диаграммы Вейча) — графический метод для функций с небольшим числом переменных (до 6).
• Метод Блейка — Порецкого — метод, основанный на законе поглощения и операции обобщённого склеивания.

Минимальная ДНФ может быть не единственной; существуют понятия тупиковой и сокращённой ДНФ.

¶Связь с КНФ

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

¶Применение

¶Цифровая схемотехника

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

¶Информатика и программирование

• Алгоритмы и структуры данных: ДНФ применяется в задачах проверки выполнимости булевых формул (SAT-решатели), хотя чаще используется КНФ. Однако ДНФ удобна для представления функций в системах автоматизированного проектирования.
• Базы данных: В реляционной алгебре ДНФ используется для представления сложных условий в запросах (например, в SQL-выражениях WHERE).
• Искусственный интеллект: В машинном обучении и логическом программировании ДНФ применяется для представления правил и знаний (например, в алгоритмах обучения булевых функций).

¶Криптография

В криптоанализе и теории кодирования ДНФ используется для представления булевых функций, используемых в шифрах (например, S-блоки). Минимизация ДНФ помогает анализировать сложность атак.

¶Примеры

¶Пример 1: Построение СДНФ по таблице истинности

Рассмотрим функцию трёх переменных \(f(x,y,z)\), заданную таблицей истинности:

Наборы, на которых \(f=1\): (0,0,1), (0,1,1), (1,0,0), (1,1,1). СДНФ: \[ (\neg x \land \neg y \land z) \lor (\neg x \land y \land z) \lor (x \land \neg y \land \neg z) \lor (x \land y \land z) \]

¶Пример 2: Минимизация ДНФ

Для функции \(f(x,y,z) = (\neg x \land \neg y \land z) \lor (\neg x \land y \land z) \lor (x \land \neg y \land \neg z) \lor (x \land y \land z)\) можно применить склеивание:

• Первые две конъюнкции склеиваются по переменной \(y\): \(\neg x \land z\).
• Последняя конъюнкция не склеивается ни с одной из оставшихся.
• Третья конъюнкция \(x \land \neg y \land \neg z\) остаётся без пары.

Минимальная ДНФ: \[ (\neg x \land z) \lor (x \land \neg y \land \neg z) \lor (x \land y \land z) \] (в данном случае полная минимизация может дать иной результат при использовании карт Карно).

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

Основной недостаток ДНФ — экспоненциальный рост размера при увеличении числа переменных. Для некоторых функций (например, «чётность» или «мультиплексор») СДНФ содержит \(2^{n-1}\) конъюнкций, что делает её непрактичной для больших \(n\). Минимизация ДНФ является NP-трудной задачей (задача нахождения минимальной ДНФ принадлежит классу NP-полных). На практике для больших схем используются более эффективные представления, такие как бинарные диаграммы решений (BDD) или AIG (And-Inverter Graphs).

¶Интересные факты

• В 1950-х годах советский математик Михаил Александрович Гаврилов разработал теорию минимизации булевых функций, включая методы, основанные на ДНФ, которые применялись в релейной автоматике.
• ДНФ лежит в основе языка программирования ПЛИС (программируемых логических интегральных схем) — VHDL и Verilog, где логические выражения часто записываются в виде суммы произведений.
• Понятие «дизъюнктивная нормальная форма» используется не только в булевой алгебре, но и в теории решёток и универсальной алгебре как частный случай представления элементов дистрибутивных решёток.

¶Источники

• Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986.
• Гаврилов М. А. Теория релейно-контактных схем. — М.: Изд-во АН СССР, 1950.
• Шеннон К. Работы по теории информации и кибернетике. — М.: Иностранная литература, 1963.
• Ковалёв М. М., Кравцов М. К. Дискретная математика. — Минск: БГУ, 2008.
• Электронный ресурс: «Булева алгебра» — Математическая энциклопедия, 1977.