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

Произведение сумм (КНФ)

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

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

Содержание

Произведение сумм (product of sums, POS), или конъюнктивная нормальная форма (КНФ), — запись логической функции в виде логического И нескольких сумм, каждая из которых — логическое ИЛИ переменных или их инверсий. Например, (A' + B)(C' + D). Это двойственная форма к сумме произведений: если ДНФ строится по единицам функции, то КНФ — по нулям.

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

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

f=(A+B+C)(A+B+C‾)(A+B‾+C)(A‾+B+C)=ΠM(0,1,2,4)f = (A + B + C)(A + B + \overline{C})(A + \overline{B} + C)(\overline{A} + B + C) = \Pi M(0, 1, 2, 4)

Минимизация

На карте Карно группируют нули — наибольшими группами размером в степень двойки. Kuphaldt описывает порядок так: записать двоичный адрес группы, взять дополнение и превратить в сумму, отбросив переменные, которые внутри группы меняются. Для функции «два из трёх» группы нулей дают f = (A + B)(A + C)(B + C) — по-прежнему три сомножителя, как три слагаемых в ДНФ AB + BC + AC.

Иногда КНФ выигрывает заметно. В примере Kuphaldt функция с нулями ΠM(2, 6, 8, 9, 10, 11, 14) после склейки равна (A' + B)(C' + D): два элемента ИЛИ и один И против пяти элементов у минимальной суммы произведений. В другом примере, наоборот, SOP проще на один вход. Выбор формы зависит от функции и семейства: Kuphaldt замечает, что ТТЛ строится вокруг И-НЕ и лучше подходит для ДНФ, а в КМОП доступны элементы ИЛИ-НЕ на любое число входов.

Схема

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

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

Как по таблице истинности записать КНФ?

Взять строки, где функция равна нулю. Для каждой записать сумму всех переменных так, чтобы она обращалась в ноль именно на этих входах: переменная, равная в строке 0, входит прямо, равная 1 — с инверсией. Затем перемножить суммы. Это каноническая КНФ, или произведение макстермов.

Как минимизировать КНФ картой Карно?

Группировать не единицы, а нули — так же, наибольшими группами из 2, 4, 8 клеток. По Kuphaldt, для каждой группы записывают её двоичный адрес, берут дополнение и превращают в сумму, отбрасывая переменные, которые внутри группы меняются. Произведение этих сумм и есть минимальная КНФ.

Где на практике удобна форма произведения сумм?

Когда у функции мало нулей или когда сигнал должен сработать при «рассогласовании». У Kuphaldt сигнал о расхождении трёх датчиков записывается двумя сомножителями (A + B + C)(A' + B' + C'): он равен нулю, только если все датчики показывают одно и то же. Схема ИЛИ-И строится и целиком на элементах ИЛИ-НЕ.

Источники

  1. Kuphaldt T. R. Lessons In Electric Circuits, Vol. IV — Digital, ch. 8 «Karnaugh Mapping», разд. «Minterm vs maxterm solution» (CC BY) — для каждой SOP есть решение POS; порядок: наибольшие группы нулей размером в степень двойки, двоичное значение группы, дополнение, сумма; пример: группы дают три суммы, POS — 3 элемента ИЛИ и 1 И с 8 входами, SOP той же функции — 7 входов; функция ΠM(2, 6, 8, 9, 10, 11, 14) = (A' + B)(C' + D) — 3 элемента против 5 у SOP; POS удобна в КМОП, где есть элементы ИЛИ-НЕ всех размеров
  2. Kuphaldt T. R. Lessons In Electric Circuits, Vol. IV — Digital, ch. 7 «Boolean Algebra», разд. «Converting truth tables into Boolean expressions» (CC BY) — Product-Of-Sums из строк с нулевым выходом; пример — сигнал рассогласования трёх датчиков (A + B + C)(A' + B' + C'): ноль, когда все датчики согласны

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

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