Перейти к содержанию

Сумма произведений (ДНФ)

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

Обновлено Редакция GAW

Содержание

Сумма произведений (sum of products, SOP), или дизъюнктивная нормальная форма (ДНФ), — запись логической функции в виде логического ИЛИ нескольких произведений, каждое из которых — логическое И переменных или их инверсий. Например, AB + BC + AC. Kuphaldt называет SOP основной формой, в которой функцию получают из таблицы истинности.

Каноническая ДНФ

Для каждой строки таблицы с единицей на выходе записывают произведение всех переменных — минтерм — и складывают их. Функция «два из трёх» из примера Kuphaldt с датчиками пламени:

f=A‾BC+AB‾C+ABC‾+ABC=Σm(3,5,6,7)f = \overline{A}BC + A\overline{B}C + AB\overline{C} + ABC = \Sigma m(3, 5, 6, 7)

Такая форма единственна для функции, но избыточна: каждое произведение покрывает одну строку.

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

Упрощение склеивает произведения, отличающиеся одной переменной: ABC' + ABC = AB. После всех склеек остаются простые импликанты, и из них выбирают наименьший набор, покрывающий все единицы. Для датчиков получается f = AB + BC + AC. Мак-Класки в статье 1956 года определяет минимальную сумму строго: наименьшее число членов, а при равенстве — наименьшее число литералов; в его примере одна запись функции содержит 12 литералов, другая — 11, и минимальна только вторая.

Минимальную ДНФ находят картой Карно — группами единиц размером в степень двойки — или табличным методом Куайна — Мак-Класки.

Схема

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

Частые вопросы

Чем каноническая ДНФ отличается от минимальной?

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

Как реализовать ДНФ схемой?

Двумя уровнями: каждое произведение — элемент И, их сумма — один элемент ИЛИ. По Kuphaldt, ту же схему можно собрать целиком на элементах И-НЕ, заменив ими все И и ИЛИ: функция не изменится..

Что выбрать: ДНФ или КНФ?

Ту форму, которая проще для конкретной функции и семейства. Kuphaldt сравнивает их по числу элементов и входов: в одном примере сумма произведений требует семь входов против восьми, в другом произведение сумм обходится тремя элементами вместо пяти. Проще всего получить обе формы и сравнить.

Источники

  1. Kuphaldt T. R. Lessons In Electric Circuits, Vol. IV — Digital, ch. 7 «Boolean Algebra», разд. «Converting truth tables into Boolean expressions» (CC BY) — Sum-Of-Products: для каждой строки с выходом 1 — произведение, равное 1 при этих входах, затем сумма; пример с тремя датчиками: A'BC + AB'C + ABC' + ABC, после упрощения AB + BC + AC; SOP соответствует схеме И-ИЛИ
  2. Kuphaldt T. R. Lessons In Electric Circuits, Vol. IV — Digital, ch. 8 «Karnaugh Mapping», разд. «Minterm vs maxterm solution» (CC BY) — минимальная SOP по карте Карно: наибольшие группы единиц размером в степень двойки, каждая группа — произведение; сравнение с POS по числу элементов и входов; переход И-ИЛИ → И-НЕ-И-НЕ; ТТЛ на И-НЕ хорошо подходит для SOP
  3. E. J. McCluskey. Minimization of Boolean functions. The Bell System Technical Journal, 1956, vol. 35, no. 6, p. 1417 — каноническое разложение — сумма элементарных произведений по единичным строкам; минимальная сумма — с наименьшим числом членов, а при равенстве — с наименьшим числом литералов; пример Σ(7, 9, 10, 12, 13, 14, 15): 11 литералов против 12

Нашли ошибку?

Смотрите также