§ 22. Синтез логических выражений
До этого момента мы считали, что логическое выражение уже задано, и нам надо что-то с ним сделать (построить таблицу истинности, упростить и т. п.). Такие задачи называются задачами анализа (от греческого avctXuau — разложение), в них требуется исследовать заданное выражение. При проектировании различных логических устройств, в том числе и устройств компьютеров, приходится решать обратную задачу — строить логическое выражение по готовой таблице истинности, которая описывает нужное правило обработки данных. Эта задача называется задачей синтеза (от греческого auveeaii — совмещение).
В качестве простейшего примера построим логическое выражение, тождественное операции импликации X = А —> В, по её таблице истинности (рис. 3.21).
Способ 1. В таблице истинности мы выделяем все строки, где логическое выражение равно единице. Тогда искомое выражение может быть записано как логическая сумма выражений, каждое из которых истинно только в одном случае.
Например, выражение ˥А*˥В истинно только при A=0 и В=О, т. е. только в первой строке таблицы. Выражение ˥А*В истинно только во второй строке, а А*В — только в последней.
Существует простое правило: если в некоторой строке переменная равна нулю, она входит в произведение с отрицанием, а если равна 1, то без отрицания.
Складывая выражения для всех отмеченных строк (кроме третьей, где функция равна нулю), получаем:
X=˥A*˥B+˥A*B+A*B
Упрощаем это выражение:
X=˥A*(˥B+B)+A*B=˥A+A*B=(˥A+A)*(˥A+B)=˥A+B.
Таким образом, мы вывели формулу, которая позволяет заменить импликацию через «НЕ» и «ИЛИ».
Способ 2. Если в столбце X таблицы истинности нулей меньше, чем единиц, удобнее сначала найти формулу для обратного выражения, ˥X, а потом применить операцию «НЕ». В данном случае выражение равно нулю в единственной строке, при А =1 и В =0, только в этой строке ˥Х =1, поэтому, используя предыдущий способ, получаем ˥X = А*˥В. Теперь остаётся применить операцию «НЕ» и закон де Моргана:
Х = ˥(А*˥В)=˥А+В.
Рассмотрим более сложный пример, когда выражение зависит от трёх переменных. В этом случае в таблице истинности будет 8 строк (рис. 3.22).
Отметим все строки, где X = 1, и для каждой из них построим выражение, истинное только для этой комбинации переменных (см. рис. 3.22). Теперь выполним логическое сложение:
Х = ˥А*˥В*˥С+˥А*˥В*С+˥А*В*˥С + ˥А*В*С + А*˥В*С + А* В* С.
Упрощение этого выражения даёт:
X=˥А*˥В*(˥С + С)+˥А*В*(˥С + С)+А*С*(˥В + В) =
=˥A*˥B+˥A*B+A*C=˥A*(˥B+B)+A*C=
=˥A+A*C=(˥A+A)*(˥A+C)=˥A+C.
Используя второй способ, получаем:
˥Х=А*˥В*˥С + А*В*˥С = А*˥С*(˥В + В) = А*˥С.
Тогда Х=˥(А*˥С) =˥А+С. В данном случае второй способ оказался проще, потому что в столбце X таблицы истинности меньше нулей, чем единиц.
Способ 3. При небольшом количестве нулей можно использовать ещё один метод. Попробуем применить операцию «НЕ» к исходному выражению для ˥X, без предварительного упрощения:
Х=˥(А*˥В*˥С +А*В*˥С).
Применяя закон де Моргана, получим:
Х=˥(А*˥В*˥С)*˥(А*В*˥С).
Используя закон де Моргана для обеих скобок, находим:
X =(˥А+В+С)*(˥А+˥В+С).
Заметим, что выражение в каждой скобке ложно только для одной комбинации исходных данных, при которых Х=0.
Таким образом, третий способ заключается в том, чтобы для каждой строки в таблице истинности, где выражение равно 0, построить логическую сумму, в которую переменные, равные в этой строке единице, входят с инверсией, а равные нулю — без инверсии. Выражение для X — это произведение полученных сумм.
В нашем примере выражение упрощается с помощью распределительного закона для «И» и закона исключённого третьего:
Х=(˥A+В+С)*(˥А+˥В+С)=(˥A+С)+В*˥В=˥А+С.
Неудивительно, что мы получили тот же ответ, что и раньше.
Иногда при упрощении выражений может потребоваться искусственный приём, который сначала вроде бы усложняет запись, но затем позволяет получить более простую форму. Например, рассмотрим выражение
X=˥A*B+˥A*C+˥B*C.
Учитывая, что В+˥В=1, можно представить второе слагаемое в виде:
˥А*С=˥А*(В+˥В)*С=˥А*В*С+˥А*˥В*С.
Тогда получаем:
X=˥A*B+˥A*B*C+˥A*˥B*C+˥B*C=˥A*B*(1+C)+(˥A+1)*˥B*C=˥A*B+˥B*C.