9-3. МИНИМИЗАЦИЯ АНАЛИТИЧЕСКИХ ВЫРАЖЕНИЙ ТРЕХЗНАЧНЫХ ЛОГИЧЕСКИХ ФУНКЦИЙ

При переходе к троичным логическим элементам при синтезе схем вновь возникает вопрос об их минимизации.

Рассмотрим функцию, заданную следующей таблицей:

Запишем ее в сигма — нормальной форме:

Так как сложение по модулю является ассоциативной операцией, то вынесем из последних слагаемых общий множитель

Но, как легко видеть,

поэтому получим:

На рис. 9-14 показан куб рассматриваемой функции. В отличие от двухзначной логики здесь куб имеет ребра

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

Рис. 9-14.

Рис. 9-15.

Нормальная сигма — форма соответствует заданию суммы подмножеств Аналогичную задачу решает ТДСНФ, ТКСНФ задает сумму подмножеств

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

в двухзначном случае. Геометрическое изображение становится ненаглядным практически уже при

Пример 9-1. Написать аналитическое выражение для трехзначной логики функции, область определения которой показана на рис. 9-15.

Пусть необходимо написать данную функцию в ТДСНФ. Для этого мы должны учесть подмножества (на рисунке точки, относящиеся к этому подмножеству, обведены двойным кружком) и (точки этого подмножества на рисунке зачерчелы). С целью возможного сокращения аналитической записи постараемся покрыть точки соответствующих подмножеств интервалами возможно большего ранга. Мы видим, что все точки кроме точки с координатами (1,1,0), покрываются гранью куба, на которой постоянно, принимают всевозможные значения. С этой гранью, естественно, сопоставляется конъюнкция Кроме того, точки множества могут быть покрыты прямыми, которые на рисунке выделены жирными линиями. Сопоставляя с этими прямыми соответствующие конъюнкции, мы окончательно можем написать ТДОНФ данной функции:

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

Рис. 9-16.

Можно попытаться свести задачу минимизации -значных логических функций к минимизации двухзначных логических функций. Для этого необходимо ввести специальное разбиение множества значений -значной логики на пересекающиеся подмножества, содержащие по два значения. Один из возможных способов такого разбиения рассмотрен в работе 3. Л. Рабиновича и Ю. Л. Иваськива. На рис. 9-16,а показано разбиение множества значений -значной логики на пересекающиеся подмножества, использованное в этой работе. Элемент, входящий в общее пересечение всех подмножеств, играет роль нуля. Для трехзначной логики разбиение на подмножества показано на рис. 9-16, б.

Введем теперь характеристические функции определяемые соотношениями:

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

где — означает конъюнкцию либо характеристических функций , либо характеристических функций

Выражение (9-12) распадается на две части, представляющие собой ДНФ в двухзначной логике со значениями (0,1) и (0,2) соответственно. Отличие этих ДНФ от ДСНФ двухзначной логики в том, что вместо аргументов в элементарные конъюнкции входят характеристические функции или Минимальное выражение для функции из (9-12) совпадает с дизъюнкцией двух минимальных форм для двухзначных логических функций из и , полученных обычным образом.

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

то в (9-12) вместо импликант можно использовать импликанты получающиеся из заменой операции конъюнкции операцией, определяемой функцией В этом случае возможно дальнейшее упрощение представления для функции заключающееся в замене функций аргументами в виде или V. Возможность такой замены вытекает из следующей теоремы, доказанной в работе 3. Л. Рабиновича и Ю. Л. Иваськива.

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

Решение проблем построения схем на троичных мажоритарных или пороговых элементах проводится теми же методами, что и для двоичного случая (см. § 4-7). Интересующиеся этими проблемами могут ознакомиться с работами, указанными в списке литературы к гл. 9.

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

1) тристабил со счетным входом

2) тристабил типа А

3) тристабил типа В

4) тристабил типа С

Используя элементы такого типа, можно строить различные троичные схемы с цепями обратной связи.