§ 6. Способ упрощения логической функции с помощью карт Карно

Определения и обозначения

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

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

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

Импликанта — конъюнкция переменных или их отрицаний, равная 1 на выбранной группе клеток. Для группы оставляют те переменные, значения которых во всех её наборах одинаковы. Каждая такая запись задаёт часть функции, а дизъюнкция импликант покрывает все наборы, на которых функция равна 1.

Как это устроено

Начинают с таблицы истинности: каждому её набору переменных должна соответствовать отдельная клетка карты. Значение функции из строки таблицы переносят в эту клетку, поэтому ни один набор нельзя пропустить или записать дважды. Расположение выбирают не произвольно: соседние клетки должны представлять наборы, отличающиеся значением одной переменной, иначе объединение не даст правильного сокращения.

Для двух переменных достаточно квадратной таблицы, а для большего числа переменных карту делят на строки и столбцы, подписанные наборами переменных. Подписи располагают в коде Грея — порядке, в котором соседние коды различаются одним битом. Например, порядок 00, 01, 11, 10 подходит лучше обычного двоичного 00, 01, 10, 11: в нём соседние подписи 01 и 10 отличаются сразу двумя битами. Код Грея сохраняет нужное соседство и при переходе от последней подписи к первой.

Чтобы получить упрощённую дизъюнктивную нормальную форму (ДНФ), на карте объединяют клетки со значением 1. Группа должна быть прямоугольной и содержать 1, 2, 4, 8 и далее клеток, то есть число клеток должно быть степенью двойки. Группы разрешается перекрывать, а также продолжать через край карты: эти правила позволяют захватить больше единиц. Нули в такие группы не включают.

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

Группы выбирают так, чтобы каждая единичная клетка была покрыта хотя бы один раз. Если единица входит в несколько групп, это допустимо: перекрытие может помочь обойтись меньшим числом слагаемых или использовать более крупную группу. Затем импликанты соединяют операцией ИЛИ и проверяют результат по карте: все единицы должны быть покрыты, а группы не должны захватывать нули. Такая проверка помогает заметить пропущенный набор или неверный знак отрицания.

Построение и чтение карты Карно

Сначала по подписи находят клетку каждого набора и переносят в неё значение функции. Затем отмечают соседние единицы и проверяют, можно ли объединить их в группы допустимого размера. При чтении группы оставляют только неизменные переменные, а результат проверяют по всем единичным клеткам.

Разбор задач

Задача 1. Для функции двух переменных задана таблица истинности: значение 1 функция принимает только при x = 0 и y = 1. Постройте карту Карно и запишите функцию.

1. Подпишем клетки наборами x и y: 00, 01, 11 и 10, расположенными по кругу в коде Грея.
2. Единица функции относится к набору x = 0, y = 1, то есть к клетке 01. В остальные клетки перенесём нули, так как других единичных наборов по условию нет.
3. Соседней единичной клетки для группы из двух нет, поэтому оставим одну клетку. В ней x равен 0, а y равен 1; оба значения неизменны.
4. Значению x = 0 соответствует отрицание ¬x, а значению y = 1 — переменная y без отрицания. Соединим их операцией И.

Ответ: f(x, y) = ¬x ∧ y. Запись равна 1 только при x = 0 и y = 1, как и требуется в условии.

Задача 2. Для функции трёх переменных единицы стоят в наборах 001, 011, 101 и 111. Постройте карту Карно и упростите функцию.

1. Обозначим переменные в порядке x, y, z. Разместим пары значений двух переменных по коду Грея, например 00, 01, 11, 10, а значения третьей переменной вынесем в две строки.
2. Перенесём единицы в клетки наборов 001, 011, 101 и 111. Во всех этих наборах последняя цифра равна 1, а первые две принимают все сочетания.
3. Эти четыре клетки образуют группу размера 4: при переходе между ними x и y меняются, а z остаётся равной 1. Поэтому x и y исключаем из импликанты.
4. Неизменное значение z = 1 записываем как z без отрицания. Других единичных клеток, которые нужно было бы покрыть отдельными группами, нет.

Ответ: f(x, y, z) = z. Проверка простая: функция равна 1 ровно на наборах, где z = 1, независимо от x и y.

Задача 3. Для функции четырёх переменных единицы заданы наборами 0000, 0001, 0011, 0010, 1100, 1101, 1111 и 1110. Постройте карту Карно, найдите минимальную ДНФ и проверьте результат по таблице истинности.

1. Назовём переменные x, y, z, w. Подпишем строки парами xy в порядке 00, 01, 11, 10, а столбцы парами zw в порядке 00, 01, 11, 10. Такое расположение сохраняет соседство по одному биту.
2. Первые четыре набора имеют xy = 00 и включают все варианты zw. Они образуют группу из четырёх клеток. В этой группе x = 0 и y = 0 неизменны, а z и w меняются, поэтому получаем импликанту ¬x ∧ ¬y.
3. Следующие четыре набора имеют xy = 11 и также включают все варианты zw. Они образуют вторую группу из четырёх клеток; x = 1 и y = 1 неизменны, значит импликанта этой группы — x ∧ y.
4. Группы уже покрывают все восемь единиц. Объединить их в одну группу нельзя: наборы с xy = 01 и xy = 10 между ними имеют значение 0, а включать нули в группы нельзя.
5. Запишем дизъюнкцию двух импликант и сопоставим её с условием. Она равна 1, когда xy равно 00 или 11; значения z и w на результат не влияют.

Ответ: f(x, y, z, w) = (¬x ∧ ¬y) ∨ (x ∧ y). Проверка по таблице подтверждает: все заданные наборы с xy = 00 или 11 дают 1, а наборы с xy = 01 или 10 дают 0.

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

Располагают наборы в обычном двоичном порядке и считают соседними клетки рядом на бумаге. Тогда некоторые соседние подписи отличаются сразу двумя битами, и сокращение получается неверным. Ошибка возникает из-за привычного порядка двоичных чисел; проверьте каждую пару соседних подписей: различаться должен ровно один бит.

Считают соседними только клетки, имеющие общую сторону внутри таблицы, и не замечают соседство через края. Из-за этого единицы могут остаться в маленьких группах, хотя их можно объединить крупнее. Представьте карту свёрнутой в кольцо и проверьте, не соединяются ли противоположные края строки или столбца.

Объединяют клетки по диагонали либо берут группу из трёх, шести или другого неподходящего числа клеток. Такие группы не соответствуют допустимому объединению наборов, потому что их размер не является степенью двойки или клетки не образуют прямоугольник. Перед записью импликанты проверьте форму группы, её размер и соседство клеток.

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

Связь с другими темами

Для работы с картой Карно нужно уметь читать таблицу истинности, записывать логические выражения и применять операции НЕ, И и ИЛИ. Например, переменная с нулевым значением в группе записывается через НЕ, а переменные одной импликанты соединяются через И.

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

Что запомнить

• Каждая клетка карты соответствует одному набору значений переменных.
• Соседние клетки отличаются значением ровно одной переменной.
• Группы клеток имеют размер, равный степени двойки.
• Для получения ДНФ группируют клетки со значением 1.
• В импликанте остаются только переменные, неизменные во всей группе.
• Крайние клетки карты могут быть соседними.
• После упрощения проверьте, что все единичные наборы покрыты.