Устройство для минмизации логических функций Советский патент 1977 года по МПК G06F7/00 

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

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

г 2 V 0 V

/ 2 Хц Х Y .

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

7).

На графе (см. фиг. 1) отметим (кружочками) следуюшие концевые вершины ki, соответствующие заданным конституентам единицы- (ki, kz, kz, ki, kb, k). Нроизведем разметку ребер, лежаших в поле переменной XQ, для этого сравниваем концевые вершины относительно осей симметрии, проходяших через вершины (1, 2, 3, 4). Разметка выделяет ребра (ki, 1) и (К 4). Далее лроизводим разметку ребер, лежаших в поле переменной х, сравнивая концевые вершины относительно осей симметрии, проходяших через вершины 5 и 6. Вершины ko, ki, Й4, Й5 сравниваются соответственно с вершинами kz, kz, ke, k-j и так далее до полной разметки всех ребер дерева. ПОСле разметки проходим всевозможные пути от РО к концевым вершинам и понадаюшиеся отмеченные ребра записываем в виде буквы или ее отрицания, объединяя все буквы одного пути знаком конъюнкции, а каждую конъюнкцию одного пути соединяем с конъюнкцией другого пути знаком дизъюнкции. Носле рассмотрения всех путей, полученное выражение эквивалентно исходному и представляет собой .сокраш,енную дизъюнктивную нормальную форму логического выражения, которая в некоторых случаях совпадает с тупиковой или минимальной формой. Для примера, рассмотренного на фиг. 1, получается следующая сокращенная форма 5 функции

F х.Х V 2-«о V V .

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

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

5 элементы И блока 3, счетчик 5 и дешифратор 6.

Элементы И блока 3 разбиты на три группы. Перваягруппа сравнивает концевые вершины ki графа-дерева относительно осей

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

5 (см. фиг. 1).

После окончания переходных процессов на счетчик 5 подаются тактирующие импульсы (ТИ), число состояний счетчика равно числу

0 путей от концевых верщин графа ki к вершине РО. Выходы счетчика 5 соединены со входом дешифратора 6, число выходов которого равно числу ребер дерева. Состояние этих выходов в зависимости от состояния счетчика лриведено в таблице.

Таблица

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

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

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

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

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

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

ffr