Глава 3

§ 22. Синтез логических выражений

До этого момента мы считали, что логическое выражение уже задано, и нам надо что-то с ним сделать (построить таблицу истин­ности, упростить и т. п.). Такие задачи называются задачами ана­лиза (от греческого avctXuau — разложение), в них требуется ис­следовать заданное выражение. При проектировании различных логических устройств, в том числе и устройств компьютеров, при­ходится решать обратную задачу — строить логическое выраже­ние по готовой таблице истинности, которая описывает нужное правило обработки данных. Эта задача называется задачей синтеза (от греческого auveeaii — совмещение).

В качестве простейшего примера построим логическое выра­жение, тождественное операции импликации X = А —>  В, по её таб­лице истинности (рис. 3.21).

 

Способ 1. В таблице истинности мы выделяем все строки, где логическое выражение равно единице. Тогда искомое выражение может быть записано как логическая сумма выражений, каждое из которых истинно только в одном случае.

Например, выражение ˥А*˥В истинно только при A=0 и В=О, т. е. только в первой строке таблицы. Выражение ˥А*В истинно только во второй строке, а  А*В — только в последней.

Существует простое правило: если в некоторой строке пере­менная равна нулю, она входит в произведение с отрицанием, а если равна 1, то без отрицания.

Складывая выражения для всех отмеченных строк (кроме третьей, где функция равна нулю), получаем:

X=˥A*˥B+˥A*B+A*B

Х = ˥(А*˥В)=˥А+В.

Рассмотрим более сложный пример, когда выражение зависит от трёх переменных. В этом случае в таблице истинности будет 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.