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

Простая импликанта

Если склеивать минтермы, пока это возможно, останутся произведения, которые уже нельзя укоротить, не захватив ни одного нуля функции. Это простые импликанты — кирпичи, из которых собирается минимальная сумма произведений.

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

Простая импликанта (prime implicant) — произведение переменных, которое равно 1 только там, где равна 1 функция (то есть является её импликантой), и из которого нельзя убрать ни одну переменную, не нарушив этого условия. Мак-Класки в статье 1956 года определяет их через процедуру: склеивать члены по правилу x₁x₂ + x₁x₂' = x₁, пока это возможно, и отбросить всё, что участвовало в склейке, — оставшиеся члены и есть простые импликанты.

Пример

Функция Мак-Класки T = Σ(3, 7, 8, 9, 12, 13) от четырёх переменных:

ШагЧлены (двоичная запись, «-» — исключённая переменная)
Минтермы0011, 0111, 1000, 1001, 1100, 1101
Первая склейка0-11 (3, 7); 100- (8, 9); 1-00 (8, 12); 1-01 (9, 13); 110- (12, 13)
Вторая склейка1-0- (8, 9, 12, 13)
Простые импликанты0-11 и 1-0-

Член 0-11 ни с чем дальше не склеивается и остаётся простой импликантой; четыре члена первой склейки с единицей в старшем разряде собираются в 1-0-. Итог — x₁'x₃x₄ + x₁x₃': два произведения вместо шести минтермов. На карте Карно это две наибольшие группы — пара клеток и квадрат из четырёх.

Существенные импликанты и покрытие

Простых импликант бывает больше, чем нужно. Чтобы выбрать минимальный набор, Мак-Класки строит таблицу: столбцы — минтермы функции, строки — простые импликанты, крестик — импликанта покрывает минтерм. Если в столбце один крестик, его строка обязательна: такую импликанту называют существенной. После выбора существенных импликант оставшиеся непокрытые минтермы закрывают наименьшим числом дополнительных строк — и получается минимальная сумма произведений.

Для функции Kuphaldt Σm(0, 1, 3, 4, 5, 7, 12, 13, 15) все четыре простые импликанты — A'C', A'D, BC' и BD — существенны, и минимальная форма их сумма. Полный алгоритм описан в статье о методе Куайна — Мак-Класки, а импликанты для своей функции показывают карта Карно онлайн и симулятор логических схем.

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

Чем простая импликанта отличается от существенной?

Простая — любое произведение, которое нельзя укоротить без захвата нуля функции. Существенная — такая простая импликанта, которая единственная покрывает какой-то минтерм. В таблице покрытия Мак-Класки это строка, у которой есть столбец с единственным крестиком: она обязана войти в любую минимальную сумму.

Как простые импликанты выглядят на карте Карно?

Как наибольшие допустимые группы единиц: прямоугольники размером 1, 2, 4, 8 клеток, которые нельзя расширить, не захватив ноль. Каждая такая группа — простая импликанта. Минимальная сумма — наименьший набор этих групп, накрывающий все единицы.

Всегда ли минимальная сумма состоит из всех простых импликант?

Нет. Часто часть простых импликант лишняя: их минтермы уже покрыты другими. Например, у функции «два из трёх» Σm(3, 5, 6, 7) три простые импликанты — BC, AC и AB, и все три нужны. Но бывают функции, где без части простых импликант можно обойтись; выбор делают по таблице покрытия.

Источники

  1. E. J. McCluskey. Minimization of Boolean functions. The Bell System Technical Journal, 1956, vol. 35, no. 6, p. 1417 — разд. 3: теорема x1x2 + x1x2' = x1 применяется ко всем парам p-членов, затем к парам полученных членов, пока возможно; члены, участвовавшие в склейке, отбрасываются, оставшиеся называются простыми импликантами (prime implicants); минимальная сумма — сумма наименьшего числа простых импликант, равная 1 на всех нужных строках; пример 3.1: T = Σ(3, 7, 8, 9, 12, 13); разд. 4: таблица простых импликант — столбцы — номера строк, строки — импликанты, крестик, если импликанта равна 1 на строке; если в столбце один крестик, эта строка обязательно входит в решение
  2. Kuphaldt T. R. Lessons In Electric Circuits, Vol. IV — Digital, ch. 8 «Karnaugh Mapping» (CC BY) — на карте Карно группы единиц должны быть наибольшими и иметь размер степени двойки; каждая группа даёт произведение в сумме произведений; пример Σm(0, 1, 3, 4, 5, 7, 12, 13, 15) — A'C' + A'D + BC' + BD (по рисунку раздела)

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

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