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

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

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

Булева функция \( f(x_1, x_2, \dots, x_n) \) от \( n \) переменных задаёт отображение \( \{0,1\}^n \to \{0,1\} \). Элементарная конъюнкция (конъюнкт) — это логическое произведение (конъюнкция) переменных или их отрицаний, причём каждая переменная встречается не более одного раза. Если конъюнкция содержит все \( n \) переменных (каждую либо в прямом, либо в инверсном виде), она называется минтермом (или конституентой единицы). Минтерм принимает значение 1 ровно на одном наборе значений переменных — том, на котором каждая переменная совпадает со своим значением в минтерме (без отрицания — 1, с отрицанием — 0).

СДНФ функции \( f \) — это дизъюнкция всех минтермов, соответствующих тем наборам переменных, на которых \( f \) равна 1. Если функция тождественно равна 0, её СДНФ не существует (или считается пустой).

Свойства СДНФ

• Единственность: Для каждой булевой функции, не равной тождественному нулю, существует ровно одна СДНФ (если не учитывать перестановку слагаемых). Это следует из того, что каждый минтерм однозначно соответствует одному набору переменных.
• Совершенство: Каждый минтерм содержит все переменные, что отличает СДНФ от других дизъюнктивных нормальных форм (ДНФ), где конъюнкции могут быть неполными.
• Полнота: Любая булева функция может быть представлена в СДНФ, за исключением константы 0.
• Связь с таблицей истинности: СДНФ строится непосредственно по таблице истинности: для каждой строки, где значение функции равно 1, записывается минтерм, и все такие минтермы соединяются знаком дизъюнкции.

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

Алгоритм построения СДНФ включает следующие шаги:

1. Составить таблицу истинности заданной булевой функции.
2. Выбрать все строки, в которых значение функции равно 1.
3. Для каждой такой строки записать минтерм: если переменная в строке равна 1, она входит в минтерм без отрицания; если равна 0 — с отрицанием.
4. Соединить все полученные минтермы знаком дизъюнкции (\(\lor\) или \(+\)).

Пример: Дана функция \( f(x, y, z) \), заданная таблицей:

Строки, где \( f = 1 \): (0,0,1), (0,1,1), (1,0,1), (1,1,1). Соответствующие минтермы:

• Для (0,0,1): \(\overline{x} \land \overline{y} \land z\)
• Для (0,1,1): \(\overline{x} \land y \land z\)
• Для (1,0,1): \(x \land \overline{y} \land z\)
• Для (1,1,1): \(x \land y \land z\)

СДНФ: \( f = \overline{x}\,\overline{y}\,z \lor \overline{x}\,y\,z \lor x\,\overline{y}\,z \lor x\,y\,z \). Упрощение (склеивание) даёт \( f = z \), но это уже не СДНФ, а сокращённая форма.

Связь с другими формами представления

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

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

Минимизация ДНФ

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

Карты Карно

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

Применение

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

Примеры

1. Конъюнкция: \( f(x,y) = x \land y \). Таблица: \( f=1 \) только на наборе (1,1). СДНФ: \( x\,y \).
2. Дизъюнкция: \( f(x,y) = x \lor y \). Наборы (0,1), (1,0), (1,1). СДНФ: \( \overline{x}\,y \lor x\,\overline{y} \lor x\,y \). После упрощения: \( x \lor y \).
3. Исключающее ИЛИ (XOR): \( f(x,y) = x \oplus y \). Наборы (0,1), (1,0). СДНФ: \( \overline{x}\,y \lor x\,\overline{y} \).
4. Функция трёх переменных, равная 1 на всех наборах: СДНФ содержит 8 минтермов, каждый из которых — конъюнкция всех трёх переменных с отрицаниями.

Ограничения и недостатки

• Размер: Для функции от \( n \) переменных СДНФ может содержать до \( 2^n \) минтермов, что делает её громоздкой при больших \( n \). Например, для \( n=10 \) максимальное число слагаемых — 1024.
• Неэффективность: СДНФ не является минимальной формой, поэтому для практической реализации схем требуется минимизация.
• Неприменимость к константе 0: Для функции, тождественно равной 0, СДНФ не существует.

История

Понятие нормальных форм в алгебре логики восходит к работам Джорджа Буля (середина XIX века), который ввёл алгебраические методы для логических высказываний. Систематическое изучение дизъюнктивных и конъюнктивных нормальных форм, включая совершенные, было развито в XX веке в рамках математической логики и теории автоматов. Важный вклад внесли такие учёные, как Эмиль Пост (теорема о полноте), Клод Шеннон (применение булевой алгебры в релейно-контактных схемах) и Морис Карно (карты Карно). В СССР и России теория нормальных форм разрабатывалась в работах А. Н. Колмогорова, П. С. Новикова, С. В. Яблонского и других.

Источники

1. Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986.
2. Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. — М.: Наука, 1977.
3. Шеннон К. Работы по теории информации и кибернетике. — М.: ИЛ, 1963.
4. Карно М. Карты Карно и минимизация логических функций // Труды IEEE, 1953.
5. Пост Э. Введение в общую теорию элементарных пропозиций // American Journal of Mathematics, 1921.