Таблицы истинности и канонические формы: Σm и ΠM

8 мин чтения · Команда bitGateLab

Почти любая задача цифрового проектирования начинается со словесного условия («сигнализация срабатывает, если...»), которое превращается в таблицу истинности. Следующий шаг — получить из этой таблицы уравнение, которое можно реализовать на логических элементах. Здесь вы освоите систематический способ это сделать: минтермы и макстермы, канонические формы «сумма произведений» и «произведение сумм», а также компактную запись Σm и ΠM, которая используется в учебниках, симуляторах и картах Карно.

Как упорядочена таблица истинности

При n переменных в таблице 2ⁿ строк. Их записывают в порядке возрастания двоичного числа, считая первую переменную старшим битом. Тогда каждой строке соответствует десятичный номер: в таблице для A, B и C строка A = 1, B = 0, C = 1 — это 101₂ = 5. Именно этот номер служит индексом минтерма или макстерма, поэтому порядок переменных важен: измените порядок — изменятся и номера.

Минтермы и сумма произведений

Назовём минтермом произведение (AND), в которое входят все переменные, каждая ровно один раз, с отрицанием или без. Составляется он так: переменная, равная 1 в данной строке, пишется без черты, а равная 0 — с чертой. Минтерм равен 1 только в своей строке и 0 во всех остальных. Обозначается он m_i, где i — номер строки.

Строка	A	B	C	Минтерм	Макстерм
0	0	0	0	m₀ = ABC	M₀ = A + B + C
1	0	0	1	m₁ = ABC	M₁ = A + B + C
2	0	1	0	m₂ = ABC	M₂ = A + B + C
3	0	1	1	m₃ = ABC	M₃ = A + B + C
4	1	0	0	m₄ = ABC	M₄ = A + B + C
5	1	0	1	m₅ = ABC	M₅ = A + B + C
6	1	1	0	m₆ = ABC	M₆ = A + B + C
7	1	1	1	m₇ = ABC	M₇ = A + B + C

Если сложить (OR) минтермы всех строк, в которых функция равна 1, получится уравнение, равное 1 именно в этих строках. Это каноническая сумма произведений (в русской литературе — СДНФ, по-английски SOP), или первая каноническая форма. В компактной записи: F = Σm(список строк с 1).

Макстермы и произведение сумм

А макстерм — это сумма (OR), в которую входят все переменные. Правило здесь обратное: переменная, равная 0 в данной строке, пишется без черты, а равная 1 — с чертой. Макстерм равен 0 только в своей строке. Обозначается он M_i (с заглавной M).

Если перемножить (AND) макстермы всех строк, в которых функция равна 0, получится уравнение, равное 0 именно там и 1 во всех остальных строках: каноническое произведение сумм (СКНФ, POS), или вторая каноническая форма. Записывается так: F = ΠM(список строк с 0).

Минтерм и макстерм одной и той же строки взаимно дополняют друг друга: m_i = M_i. Поэтому, если известен список Σm функции, список ΠM состоит из всех номеров, которых в нём нет.

Пример 1: от таблицы к обеим формам. Функция трёх переменных равна 1 в строках 1, 3, 6 и 7.

#	A	B	C	F
0	0	0	0	0
1	0	0	1	1
2	0	1	0	0
3	0	1	1	1
4	1	0	0	0
5	1	0	1	0
6	1	1	0	1
7	1	1	1	1

Компактная запись: F = Σm(1, 3, 6, 7) = ΠM(0, 2, 4, 5).
Каноническая сумма произведений: F = ABC + ABC + ABC + ABC.
Каноническое произведение сумм: F = (A + B + C)(A + B + C)(A + B + C)(A + B + C).
Упростите сумму произведений: ABC + ABC = AC и ABC + ABC = AB. Итак, F = AC + AB.

Проверка в строке 5 (A = 1, B = 0, C = 1): AC = 0 и AB = 0, значит, F = 0, как и в таблице.

Какую форму выбрать?

Обе формы описывают одну и ту же функцию, но размер у них разный. Берите ту, в которой меньше членов: если у функции мало единиц, короче Σm; если мало нулей, короче ΠM. При 8 строках у функции с 2 единицами каноническая сумма произведений состоит из 2 членов, а каноническое произведение сумм — из 6.

Важна и реализация. Сумма произведений собирается из элементов AND, выходы которых подаются на OR, и такая двухуровневая структура напрямую превращается в NAND-NAND. Произведение сумм собирается из элементов OR, выходы которых подаются на AND, и превращается в NOR-NOR.

Пример 2: от условия к уравнению. В баке установлены три датчика уровня: A (нижний), B (средний) и C (верхний). Каждый датчик выдаёт 1, когда вода до него доходит. Лампа «недопустимый уровень» должна загораться, когда комбинация физически невозможна: верхний датчик сработал, а какой-то из расположенных ниже — нет.

Допустимые комбинации (ABC): 000, 100, 110, 111. То есть строки 0, 4, 6 и 7.
Лампа загорается в остальных: F = Σm(1, 2, 3, 5).
Эквивалентная запись: F = ΠM(0, 4, 6, 7).
Упростите: m₁ + m₃ = AC, m₁ + m₅ = BC, m₂ + m₃ = AB. Используя m₁ и m₃ дважды (идемпотентность), получаем F = BC + AB.

Проверьте: строка 1 (001) даёт BC = 1; строка 2 (010) даёт AB = 1; строка 3 (011) даёт AB = 1; строка 5 (101) даёт BC = 1. В строках 000, 100, 110 и 111 оба члена равны 0. Читается это так: «C сработал без B» или «B сработал без A».

Дополнение функции

Если F = Σm(1, 3, 6, 7), то её дополнение равно 1 там, где F равна 0: F = Σm(0, 2, 4, 5). Это полезно, когда нужно упрощённое произведение сумм: вы упрощаете F как сумму произведений, а затем применяете теорему де Моргана. Например, F = AC + AB (проверьте по строкам 0, 2, 4 и 5), и после инвертирования получается F = (A + C)(A + B). Если раскрыть скобки, выйдет AB + AC + BC, а по теореме консенсуса это AB + AC — тот же результат, что и в примере 1.

Чтобы глубже разобраться в таких преобразованиях, повторите тему «булева алгебра»; чтобы упрощать графически, переходите к теме «карты Карно».

Типичные ошибки

Перепутать правило расстановки черты: в минтермах черта ставится над переменной, равной 0; в макстермах — над переменной, равной 1.
Включить в ΠM строки, в которых функция равна 1. В ΠM перечисляются нули, в Σm — единицы.
Изменить порядок переменных между таблицей и уравнением. При порядке C, B, A строка «5» — уже не та же самая строка.
Пропустить переменную в каноническом члене. В минтерме четырёх переменных всегда четыре литерала; если их меньше, член уже упрощён и не является каноническим.

Попробуйте в симуляторе

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

Создайте таблицу с тремя входами и одним выходом.
Отметьте значением 1 строки 1, 3, 6 и 7 из примера 1, а в остальных оставьте 0.
Посмотрите на получившиеся выражения Σm и ΠM и сравните их со своими.
Преобразуйте таблицу в схему и переключайте входы, чтобы убедиться, что выход соответствует таблице.
Повторите то же для задачи о баке и проверьте, что лампа загорается только при невозможных комбинациях.

Упражнения

Запишите минтерм m₉ и макстерм M₉ функции четырёх переменных A, B, C, D.
Ответ
9 = 1001. m₉ = ABCD и M₉ = A + B + C + D.
Пусть F(A, B, C) = Σm(0, 1, 5). Запишите F в виде ΠM.
Ответ
F = ΠM(2, 3, 4, 6, 7).
Найдите каноническую сумму произведений функции двух переменных, которая равна 1 только при одинаковых A и B, и упростите её, если это возможно.
Ответ
F = Σm(0, 3) = AB + AB. Она не упрощается: это XNOR.
Запишите каноническое произведение сумм для F(A, B, C) = Σm(1, 2, 3, 4, 5, 6, 7).
Ответ
Функция равна 0 только в строке 0, поэтому F = ΠM(0) = A + B + C. Всего один трёхвходовый элемент OR.