Устройство для минмизации логических функций

 

(11) 558275

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистинеских

Республик (61) Дополнительное к авт. свид-ву (22) Заявлено 31.05.74 (21) 2031236/24 с присоединением заявки № (23) Приоритет

Опубликовано 15.05.77. Бюллетень № 18

Дата опубликования описания 06.07.77 (51) М. Кл.2 G 06F 7/00

Государственный камитет

Савета Министрав СССР па делам изобретений и аткрытий (53) УДК 681.335(088.8) (72) Авторы изобретения

Ю. О. Чернышев и Н. Н. Садовой (71) Заявитель Ростовский-на-Дону институт сельскохозяйственного машиностроения (54) УСТРОЙСТВО ДЛЯ МИНИМИЗАЦИИ ЛОГИЧЕСКИХ

ФУНКЦИЙ

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

Известны устройства для минимизации логических функций, содержащие счетчики импульсов, дешифраторы, логические элементы и блоки, регистрации (1)..Однако у этих известных устройств сравнительно узкие функциональные возможности. Наиболее близким к изобретению техническим решением является устройство, содержащее пульт управления, счетчик импульсов с подключенным к его выходам дешифратором и последовательно соединенные блок элементов И; выходной блок и блок регистрации (2). Это известное устройство характеризуется большим количеством тумблеров, усложняющих пользование им и снижающих его быстродействие; кроме того, наличие релейных схем увеличивает объем аппаратуры и уменьшает надежность, а наличие световой индикации затрудняет считывание результата и снижает также быстродействие; характерным является и невозможность работы с дизьюнктивными нормальными формами логических выражений.

Цель изобретения — расширение области применения. В описываемом устройстве это достигается тем, что в него введены регистр памяти и преобразователь дизыонктивной нормальной формы логических функций в совершенную дизыонктивную нормальную форму, входы и выходы которого подключены к соответствующим выходам пульта управления и ко входам регистра памяти, выходы регистра памяти подсоединены к первой группе входов блока элементов И, вторая группа входов которого подключена к соответствую10 щим выходам дешифратора.

На фиг. 1 изображен граф для функции трех переменных; на фиг. 2 — структурная схема описываемого устройства.

Теоретическое обоснование заключается в

1 следующем. Для минимизации логического выражения используются графовые методы представления функции, например для функции трех переменных (х, хь х0). Граф представляет собой дерево, число концевых вер20 шин которого равно числу конституент единицы для данного числа переменных, т. е. 2", где и — число переменных. Ребра, удаленные на одинаковое расстояние от корня дерева р0, образуют поле одной и той же переменной.

25 Например, ребра (Po, 5) и (P 6) образуют поле переменной. Каждой вершине дерева инциндентно два ребра. Условимся, что левое ребро обозначает отрицание той переменной, в поле которой оно находится, а правое реб30 ро — саму переменную.

558275

Из рассмотрения путей в графе видно, что каждый путь из вершины k„. к вершине есть конституента Й,, Через каждую вершину графа, исключая концевые, проводим оси симметрии (в виде штрих-пунктирных линий), отмечаем концевые вершины (кружочками), конституенты единицы, которых есть в исходном задании логического выражения, и nipoизводим разметку ребер графа. Для этого сравниваем между собой все концевые вершины относительно всех осей симметрии. Для двух сравниваемых относительно какой-либо оси симметрии вершин могут иметь место следующие три случая: когда обе вершины отмечены, когда обе вершины не отмечены, когда отмечена одна из вершин. Если имеют место первые два случая, то ни одно ребро графа не отмечается. Если одна из вершин помечена, а другая — нет, то рассматриваются два ребра, инциндентные вершине, через которую проходит ось симметрии двух сравниваемых концевых вершин, Отмечается ребро (пунктирной линией),.которое входит в кратчайший путь от отмеченной концевой вершины до корня.

Например, рассмотрим логическое выражение, заданное в совершенной дизъюнктивной нормальной форме

F = х, х,х, Q х,х, х,, х,х,х, / / Х Х Хо \/ Хз Х ХО J Хзх х .

Для краткости заменим каждую конституенту единицы десятичным эквивалентом, а знак дизъюнкции — запятой: F= (1, 2, 3, 4, 5, 7).

На графе (см. фиг. 1) отметим (кружочками) следующие концевые вершины k;, соответствующие заданным конституентам единицы — (Йь 4, йз, kp, 4, Ь). Произведем разметку ребер, лежащих в поле переменной хо, для этого сравниваем концевые вершины относительно осей симметрии, проходящих через вершины (1, 2, 3, 4). Разметка выделяет ребра (k, 1) и (4, 4). Далее производим разметку ребер, лежащих в поле переменной хь сравнивая концевые вершины относительно осей симметрии, проходящих через вершины

5 и 6. Вершины 4, 4, kp, 4 сравниваются соответственно с вершинами k> Аз, 4, 4 и так далее до полной, разметки всех ребер дерева.

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

З0

55 жения,,которая в некоторых случаях совпадает с тупиковой или минимальной формой.

Для примера,,рассмотренного на фиг. 1, получается следующая сокращенная форма функции

F = х,х, /х,х, /х,х, /х,х,.

Структурная схема устройства реализующего рассмотренный алгоритм, состоит из преобразователя 1 дизъюнктивной нормальной формы логических выражений в совершенную дизъюнктивную нормальную форму, выход которого соединен с регистром памяти 2, связанным с блоком 3 элементов И, подключенным к выходному блоку 4 и управляемым счетчиком 5 через дешифратор 6. Кроме того, в состав устройства входят пульт управления

7, управляющий преобразователем 1, и блок регистрации 8, на который подаются сигналы от выходного блока 4. На пульте управления

7 тумблерами набираются интервалы функции, заданной в дизъюнктивной нормальной форме, которые с пульта управления поступают на регистр памяти 2. После набора тумблерами комбинации переменных на пульте управления 7 сигналом УП (управляющий импульс) открываются элементы И блока 3 и на их выходах появляются сигналы, соответствующие конституентам единицы функции для данного интервала, причем выход одного элемента И обозначает одну конституенту единицы функции.

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

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

Элементы И блока 3 разбиты на три группы. Первая группа сравнивает концевые вершины k; графа — дерева относительно осей симметрии, проходящих через вершины (1, 2, 3, 4), вторая группа — относительно осей симметрии, проходящих через вершины (5, 6), и т. д. Подключение элементов И к регистру памяти 2 происходит согласно графу — дереву (см. фиг. 1).

После окончания переходных процессов на счетчик 5 подаются тактирующие импульсы (ТИ), число состояний счетчика .равно числу путей от концевых вершин графа А; к вершине ро. Выходы счетчика 5 соединены со входом дешифратора 6, число выходов:.которого равно числу ребер дерева. Состояние этих выходов в зависимости от состояния счетчика приведено в таблице.

558275

Таблица

Входы

В ыходы

2 3

9 10 11

5 6 7

12 13

0

0

0

0

В соответствии с таблицей дешифратор 6 последовательно подает сигналы на элементы И блока 3, так что одновременно оказываются включенными элементы И, представляющие один путь от концевой вершины k„. до вершины Ра.

После просмотра всех путей и выдачи всех интервалов на блок регистрации 8, например алфавитно-цифровое печатающее устройство, процесс минимизации считается законченным.

Скорость подачи ТИ зависит от скорости работы блока регистрации 8.

Формула изобретения

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

Источники информации, принятые во вни15 мание при экспертизе.

1. Вычислительная техника. Справочник под ред. Г. Хаски и Г. Кориа, т П, М.-Л., Энергия, 1964.

2. Авторское свидетельство № 177692, М.

20 Кл.- G 06F 7/00, 16.11.64.

55S275

Фиг. 2

Составитель А. Маслов

Техред М, Семенов

Корректор Н. Аук

Редактор Л. Тюрина

Типография, пр. Сапунова, 2

За,каз 1258/10 Изд. J4 451 Тираж 815 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушокая наб., д. 4/5