От таблицы истинности к выражению: минтермы, макстермы, SOP и POS

Выделение одной строки таблицы истинности

Зафиксируем порядок входов $A,B,C$, считая A старшим битом. Строка 5 соответствует ABC=101. Произведение, равное 1 только в этой строке, — $m_5=A\overline B C$. Такой член, содержащий каждую переменную ровно один раз, называется минтермом (minterm). Это не означает минимального числа элементов.

Если функция $F$ равна 1 в строках 1, 3, 5, 6, 7, объединим их минтермы^{iМинтерм — AND-терм, содержащий каждую входную переменную ровно один раз и равный 1 только для одной комбинации входов. Минтермы строк с выходом 1 можно объединить через OR.} через OR.

Это сумма произведений (SOP). В канонической SOP каждый член содержит все переменные. В общей SOP некоторые переменные в членах могут отсутствовать.

Та же функция из строк с нулём

Сумма, равная 0 только в строке 2, ABC=010, — $M_2=A+\overline B+C$. Литералы выбраны так, чтобы каждый был нулём в этой строке. Макстерм (maxterm)^{iМакстерм — OR-терм, содержащий каждую входную переменную ровно один раз и равный 0 только для одной комбинации входов. Макстермы строк с выходом 0 объединяют через AND.} — OR-член, равный 0 только для одной конкретной строки.

F равна 0 в строках 0, 2, 4, поэтому получаем произведение сумм (POS):

Σ и Π — сокращённая запись наборов номеров строк таблицы истинности^{iТаблица истинности перечисляет все возможные комбинации входов и выход для каждой из них. Изменения во времени проверяют отдельно по временным диаграммам. Подробнее}. В Σm перечисляют строки с 1, в ΠM — строки с 0.

Каноническая форма — начало, упрощение — следующий шаг

Эта функция сокращается до $F=C+AB$. Четыре строки с C=1 образуют группу, а оставшуюся при C=0 строку 110 покрывает AB. Член AB не содержит C, поэтому это SOP, но не каноническая SOP.

Следующая лекция о картах Карно показывает, как находить такие группы визуально. Думайте о том, какая переменная исчезает при изменении входов: тогда правила не придётся просто заучивать.

Практикум · свяжите три представления одной функции

Кнопки A, B, C сверху меняют только наблюдаемый вход. Кнопки 0, 1, X внутри карты меняют саму спецификацию функции. Различайте эти действия. Пунктир отмечает текущий вход, синяя рамка — ячейки, покрытые выбранным произведением.

В исходной функции задайте ABC=110: F=1, потому что даже при C=0 член AB равен 1. Поочерёдно выбирайте группы C и A·B и убедитесь, что m7 входит в обе. Повторное включение ячейки не меняет результат OR.

Теперь дважды нажмите выход m6, изменив 1 → X → 0. Конечная функция выражается одним C. Номер 6 должен исчезнуть из Σm и добавиться в ΠM. Промежуточное X означает, что спецификация не требует определённого выхода в этой строке. Если вход возможен, а выход задан, нельзя произвольно заменить его на X ради снижения стоимости.

Σm показывает обязательные 1, ΠM — обязательные 0, d — строки без требования. Если d непусто, одна запись Σm или ΠM не задаёт полную таблицу истинности. «Минимальная SOP» в упражнении — одна из форм, сначала минимизирующих число произведений, затем число литералов; это не гарантия минимальной площади реальных элементов.