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

ОПИСАНИЕ бб 8275ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистицеских Республик(22) Заявлено 31.05.74 (21) 2031236/24 1, Кл.2 б 06 Г инением заявкиприс асударствеииый камитеСавета Мииистрав СССРаа делам изабретеиийи аткрытий) УСТРОЙСТВО ДЛЯ МИНИМИЗАЦИИ ЛОГИЧЕС ФУНКЦИЙИзобретение относитси процесса проектированиякретных устройств и можно при разработке систечислительной техники.Известны устройства для минимизации логических функций, содержащие счетчики импульсов, дешифраторы, логические элементы и блоки, регистрации 1. Однако у этих известных устройств сравнительно узкие функциональные возможности. Наиболее близким к изобретению техническим решением является устройство, содержащее пульт управления, счетчик импульсов с подключенным к его выходам дешифратором и последовательно соединенные блок элементов И; выходной блок и блок регистрации 12, Это известное устройство характеризуется большим количеством тумблеров, усложняющих пользование им и снижающих его быстродействие; кроме того, наличие релейных схем увеличивает объем аппаратуры и уменьшает надежность, а наличие световой индикации затрудняет считывание результата и снижает также быстродействие; характерным является и невозможность работы с дизьюнктивными нормальными формами логических выражений.Цель изобретения - расширение области применения. В описываемом устройстве это достигается тем, что в него введены регистр памяти и преобразователь дизыонктивнои нормальнои формы логических функций в совершенную дизыонктивную нормальную форму, входы и выходы которого подключены к 5 соответствующим выходам пульта управления и ко входам регистра памяти, выходы регистра памяти подсоединены к первой группе входов блока элементов И, вторая группа входов которого подключена к соответствую щим выходам дешифратора.На фиг, 1 изображен граф для функциитрех переменных; на фиг. 2 - структурная схема описываемого устройства.Теоретическое обоснование заключается в 15 следующем. Для минимизации логическоговыражения используются графовые методы представления функции, например для функции трех переменных (х, хь хо). Граф представляет собой дерево, число концевых вер шин которого равно числу конституент единицы для данного числа переменных, т. е, 2", где и - число переменных. Ребра, удаленные на одинаковое расстояние от корня дерева ро, образуют поле одной и той же переменной,пример, ребра (ро, 5) и (ро, 6) образуют ле переменной. Каждой вершине дерева циндентно два ребра. Условимся, что левоеребро обозначает отрицание той переменной, в поле которой оно находится, а правое реб ро - саму переменную.Из рассмотрения путей в графе видно, чтокаждый путь из вершины Й; к вершине есть конституента Й Через каждую вершину графа, исключая концевые, проводим оси симметрии (в виде штрих-пунктирных линий), отмечаем концевые вершины (кружочками), конституенты единицы, которых есть в исходном задании логического выражения, и производим разметку ребер графа. Для этого сравниваем между собой все концевые вершины относительно всех осей симметрии. Для двух сравниваемых относительно какой-либо оси симметрии вершин могут иметь место следующие три случая: когда обе вершины отмечены, когда обе вершины не отмечены, когда отмечена одна из вершин. Если имеют место первые два случая, то ни одно ребро графа не отмечается. Если одна из вершин помечена, а другая - нет, то рассматриваются два ребра, инциндентные вершине, через которую проходит ось симметрии двух сравниваемых концевых вершин, Отмечается ребро (пунктирной линией), которое входит в кратчайший путь от отмеченной концевой вершины до корня.Например, рассмотрим логическое выражение, заданное в совершенной дизъюнктивной нормальной формеР = х, х,х, / х,х, х, ,х,х,х, //х,х, хх,хх, /х,х,хДля краткости заменим каждую конституенту единицы десятичным эквивалентом, а знак дизъюнкции - запятой: Р= (1, 2, 3, 4, 5, 7),На графе (см. фиг. 1) отметим (кружочками) следующие концевые вершины Й;, соответствующие заданным конституентам единицы - (Йь йь йз, йь, йз, Ь). Произведем разметку ребер, лежащих в поле переменной хо, для этого сравниваем концевые вершины относительно осей симметрии, проходящих через вершины (1, 2, 3, 4). Разметка выделяет ребра (йь 1) и (Ь, 4). Далее производим разметку ребер, лежащих в поле переменной хь сравнивая концевые вершины относительно осей симметрии, проходящих через вершины 5 и 6. Вершины Йо, йь Йь Йз сравниваются соответственно с вершинами Йз, 7 з, е, Ь и так далее до полной, разметки всех ребер дерева. После разметки проходим всевозможные пути от ро к концевым вершинам и попадающиеся отмеченные ребра записываем в виде буквы или ее отрицания, объединяя все буквы одного пути знаком коныонкции, а каждую конъюнкцию одного пути соединяем с конъюнкцией другого пути знаком дизыонкции. После рассмотрения всех путей, полученное выражение эквивалентно исходному и представляет собой сокращенную дизъюнктивную нормальную форму логического выра После окончания переходных процессов на счетчик 5 подаются тактирующие импульсы (ТИ), число состояний счетчика равно числу путей от концевых вершин графа А; к вершине Ро, Выходы счетчика 5 соединены со входом дешифратора 6, число выходов которого равно числу ребер дерева. Состояние этих выходов в зависимости от состояния счетчика приведено в таблице. 60 65 1 О 15 2 О 25 зо 35 40 45 50 55 жениякоторая в некоторых случаях совпадает с тупиковой или минимальной формой. Для примерарассмотренного на фиг. 1, получается следующая сокращенная форма функции Р= х,х, /х,х, /х,х, /х,х,. Структурная схема устройства реализующего рассмотренный алгоритм, состоит из преобразователя 1 дизъюнктивной нормальной формы логических выражений в совершенную дизъюнктивную нормальную форму, выход которого соединен с регистром памяти 2, связанным с блоком 3 элементов И, подключенным к выходному блоку 4 и управляемым счетчиком 5 через дешифратор 6. Кроме того, в состав устройства входят пульт управления 7, управляющий преобразователем 1, и блок регистрации 8, на который подаются сигналы от выходного блока 4. На пульте управления 7 тумблерами набираются интервалы функции, заданной в дизъюнктивной нормальной форме, которые с пульта управления поступают на регистр памяти 2. После набора тумблерами комбинации переменных на пульте управления 7 сигналом УП (управляющий импульс) открываются элементы И блока 3 и на их выходах появляются сигналы, соответствующие конституентам единицы функции для данного интервала, причем выход одного элемента И обозначает одну конституенту единицы функции.Перед началом работы все разряды регистра 2 переводятся в нулевое состояние, и единица в данном разряде свидетельствует о наличии конституенты единицы логического выр ажения, соответствующей этому р азр яду. После расширения всего логического выражения до совершенной дизъюнктивной нормальной формы и запоминания всех конституент единиц в регистре 2 начинается следующий этап - этап разметки и получения сокращенной формы функции, для чего используются элементы И блока 3, счетчик 5 и дешифратор 6.Элементы И блока 3 разбиты на три группы. Первая группа сравнивает концевые вершины Й; графа - дерева относительно осей симметрии, проходящих через вершины (1, 2, 3, 4), вторая группа - относительно осей симметрии, проходящих через вершины (5, 6), и т. д. Подключение элементов И к регистру памяти 2 происходит согласно графу - дереву (см. фиг. 1).558275 Таблица Входы В ыходы 1 2 3 5 6 7 9 10 12 13 14 0 1 0 0 0 0 0 0 В соответствии с таблицей дешифратор 6 последовательно подает сигналы на элементы И блока 3, так что одновременно оказываются включенными элементы И, представляющие один путь от концевой вершины А; до вершины ро.После просмотра всех путей и выдачи всех интервалов на блок регистрации 8, например алфавитно-цифровое печатающее устройство, процесс минимизации считается законченным.Скорость подачи ТИ зависит от скорости работы блока регистрации 8. Формула изобретенияУстройство для минимизации логических функций, содержащее пульт управления, счетчик импульсов с подключенным к его выходам дешифратором и последовательно соединенные блок элементов И, выходной блок и блок регистрации, отличающееся тем,что, с целью расширения области применения устройства, оно содержит регистр памяти и преобразователь дизъюнктивной нормальной формы логических функций в совершенную дизъюнктивную нормальную форму, входы и выходы которого подключены к соответствующим выходам пульта управления и ко входам регистра памяти, выходы регистра памяти подсоединены к первой группе входов бло ка элементов И, вторая группа входов которого подключена к соответствующим выходам дешифратор а. Источники информации, принятые во вни 15 мание при экспертизе. 1. Вычислительная техника, Справочник под ред. Г. Хаски и Г. Кориа, т 11, М.-Л., Энергия, 1964, 2. Авторское свидетельство177692, М.20 Кл.- 6 06 Р 7/00, 16.11.64.тавитель А. МасловТехред М, Семенов на Тираж 815омитета Совета Министров Сетений и открытий5, Раушокая наб д. 4/5 ПодписР Редактор Л. Тюр За,каз 1258/10 ЦНИИИзд.451 Государственног по делам из 3035, Москва, Ж