Спирина, М.С. Дискретная математика

6. Записать полученное упрощенное булево выражение в ДНФ. При заполнении карт Карно необходимо обратить внимание на порядок заполнения строк и столбцов значениями перемен­ ных. Последовательность значений переменных должна сохраняться неизменной. При таком заполнении каждые две соседние клетки отличаются лишь значением одной переменной. Нарушение по­ рядка заполнения строк или столбцов не запрещается, но может не дать ожидаемого результата. Рассмотрим примеры минимизации булевых функций с помо­ щью карт Карно. _ _ _ _ Пусть f{ABC ) = ABC v ABC v ABC v АВС. Нанесем единицы на карту (рис. 4.9) и обведем их сначала по­ парно двумя контурами. Такое действие соответствует заключе­ нию в скобки слагаемых ( ABC v АВС) и ( ABC v АВС). Вынося за скобки одинаковые конъюнкции согласно распределительному закону, в скобках получаем дизъюнкцию противоположных зна­ чений одной из переменных^ В данном примере этому шагу соот­ ветствуют конъюнкции АВ(С v С) и АВ(С v С). Поэтому объеди­ нение двух соседних единиц всегда приводит к закону инверсии, согласно которому дизъюнкция противоположных значений пе­ ременной равна 1. Поэтому при записи ответа после применения карты Карно переменные, заключенные в общий контур, связываются конъ­ юнкцией (как и общий множитель при вынесении за скобки), а такие отдельные конъюнкции, т.е. различные контуры, объеди­ няются между собой дизъюнкцией. Если записать полученный результат, то, очевидно, к нему вновь можно применить то же правило: /(А , В, С) = АВ v АВ = В. Однако в данном примере удобнее рассмотреть целиком весь квадрат из четырех единиц и сравнить переменные, записанные на горизонтальных и вертикальных клетках. Очевидно, общие мно­ жители сохранятся после упрощения (ведь их можно было вынес­ ти за скобки), а инвертируемые уйдут согласно закону инверсии. Поэтому целесообразнее опустить инвертируемые пары A v А и С v С, а в ответе сохранить общую для всех клеток переменную В. Синтактический способ минимизации дает тот же результат. Проверка: f(ABC ) = (ABC v ABC) v ABC v АВС - АВ v АВ - = В (A v А) - В. 182