Устройство для определения дополнения множества

(51) ГОСУДАРСТВЕННЫЙ НОМИТЕТ ССС ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫ ОПИСАНИЕ ИЗОБРЕТЕНИЯН АВТОРСКОМУ С 8 ИДЕТЕЛЬСТВУ(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ДОПОЛНЕНИЯ МНОЖЕСТВА(57) Изобретение относится к вычислительной технике и может быть использовано в системах управления базамиданных. Цель изобретения - повышениебыстродействия и сокращение аппаратурных затрат, С этой целью в устройстве, содержащем блок 1 памяти, счетчики 2,3, элемент ИЛИ 4, элементыИ 5,6, группу 7 элементов И, регистры 8,9, схемы 10,11 сравнения, генератор 12 импульсов и распределитель13 импульсов, изменены связи, в результате чего реализован сокращенныйалгоритм поиска информации. 1 ил.Изобретение относится к вычислительной технике и может быть использовано в системах управления базамиданных.Цель изобретения - повышение быстродействия и сокращение аппаратурныхзатрат.На чертеже приведена схема устройства. 10Устройство содержит блок 1 памяти,счетчики 2 и 3, элемент ИЛИ 4, эле,менты И 5 и 6, группу 7 элементов И,регистры 8 и 9, схемы 10 и 11 сравнения, генератор 12 импульсов, распределитель 13 импульсов, группу 14адресных входов, группу 15 информационных входов, вход 16 запуска, груп пу 17 информационных выходов и выход 18 призйака окончания,20Пусть Р - универсальное множест ,во, А - множество, являющееся подмножеством множества Р. Тогда допол ненеием множества А являетоя множество В = А элементов из множества Р,не .25принадлежащих множеству А, Множества,являющиеся подмножествами множества Р, хранятся в блоке 1 памяти,причем их элементы представлены кодами чисел. Элементы кажпого множестванаходятся в последовательных ячейкахпамяти. Последний элемент каждогомножества отмечается единицей в последнем разряде. Все остальные элементы отмечаются нулем, Элементы универсального множества закодированыцелымичислами от 1 до И где И - числоэлементов в универсальном множестве,Устройство работает следующим образом.. 40При включении питания распределитель 13 импульсов устанавливается висходное состояние (при этом ни наодном из его выходов сигнал не появ;ляется), генератор 12 импульсов устанавливается в запертое состояние, счетчик 3 обнуляется, а последний разряд регистра информации блок 1 памяти устанавливается в единичное состояние (не показано). Потенциалом, прошедшим через элемент ИЛИ 4, подготавливается к срабатыванию элемент И 5. По группе 15 входов в регистр 9 записывается код числа Ы, а по группе 14 входов в регистр 8 заносит 55 ся адрес первого элемента множества А, Устройство готово к работе.Работа устройства инициализируется импульсом по входу.16, в результате чего запускается генератор 12.Распределитель 13 осуществляет рассылку импульсов с выхода генератора 12по управляющим точкам устройства.Импульс с первого выхода распределителя 13 проходит через элемент И 5,открывая информационные входы счетчика 2. Поэтому из регистра 8 в него заносится адрес первого элементамножества А. Кроме того, этот импульс поступает на счетный вход счетчика 3, формируя в нем код числа 1(код первого элемента множества Р),По импульсу на втором выходе распределителя 13 иэ блока 1 памяти осуществляется считывание кода первогоэлемента множества А, Он сохраняетсяна регистре информации блока 1 и выдается на его выходе. Предположим,что множество А содержит несколькоэлементов. Поэтому сигнал на выходепоследнего разряда блока 1 памятиотсутствует, Предположим также, чтосовпадение содержимого счетчика 3 и.регистра информации блока 1 не произошло. При этом выпадает сигнална правом выходе схемы 11 сравненияи отсутствует сигнал на его левомвыходе.По импульсу с третьего выхода распределителя 13 содержимое счетчика 2увеличивается на единицу, т.е. внем формируется адрес второго элемента множества А,Затем снова появляется импульс напервом выходе распределителя 13, однако никаких действий по нему не происходит, По импульсу с второго выхода распределителя 13 из блока 1 памяти считывается код второго элемента множества А, который сравниваетсяс кодом первого элемента множества Р.,Импульсом с третьего выхода распределителя 13 в счетчике 2 формируетсяадрес третьего элемента множества А.Устройство работает аналогично дотех пор, пока не возникнет одна изследующих ситуаций,Код очередного элемента множества А, считанный из блока 1 памяти,совпадает с кодом первого элементамножества Р В, этом случае появляется сигнал на левом выходе схемы 11сравнения, в результате чего подготав"ливается к срабатыванию элемент И 5.При этом по импульсу на первом выходе распределителя 13 в счетчик 2принимается адрес первого элемента3 14257множества А, а в счетчике 3 формируется кодвторого элемента множества Р, Выдача компаратором 11 сигнала совпадения означает, что первыйэлемент множества Р принадлежит множеству А, а поэтому нет необходимости в его дальнейшем просмотреНеобходимо пропустить первый элементмножества Р и перейти к проверке при надлежности второго элемента множества Р множеству А.Из блока 1 памяти прочитаны кодывсех элементов множества А, но совпадения схемой 11 сравнения не выявлены. При этом одновременно присутствуют сигналы на правом выходесхемы 11 сравнения и на выходе последнего разряда блока 1 памяти. Этоозначает, что первый элемент множест ва Р не принадлежит множеству А,а следовательно, его код необходимовыдать из устройства в качествекода первого элементамножества В.Поэтому подготавливаются к срабатыва нию элементы И 5 и б, По импульсу стретьего выхода распределителя 13через элемент И б открывается группа 7 элементов И и содержимое счетчика 3 проходит на группу 17 выходов.По импульсу на первом выходе распределителя 13 в счетчик 2 записываетсяадрес первого элемента множества А,а в счетчике 3 формируется кодвторого элемента множества Р,Проверка на принадлежность множе 35ству А второго и последующих элементов множества Р и выдача на группу 17выходов элементов множества В осуществляется аналогично описанному.Наступает такой момент, когда поимпульсу на первом выходе распределителя 13 в счетчике 3 сформирован кодчисла 3+1. При этом появляется сигнал на выходе схемы 10 сравнения, 45который проходит на выход 18 устройства, сигнализируя об окончании работы, и устанавливает устройство висходное состояние, т,е, останавливает генератор импульсов, обнуляет0счетчик 3, переводит распределитель 1 эв исходное состояние и устанавливаетпоследний разряд регистра информацииблока 1 памяти в единичное состояние.Формула изобретенияУстройство для определения дополнения множества, содержащее блок памя 174ти, два счетчика, элемент ИЛИ, дваэлемента И, группу элементов И, дварегистра, две схемы сравнения, генератор импульсов и распределитель импульсов, причем группа адресных выходов устройства соединена с входамипервого регистра, выходы которого соединены с информационными входами первого счетчика, выходы которого соединены с адресными входами блока памяти,выходы которого кроме последнего разряда, соединены с первой группой входов первой схемы сравнения, втораягруппа входов которой соединена с информациониыми входами группы элементов И, с выходами второго счетчикаи с первой группой входов второй схемы сравнения, вторая группа входов которой соединена с выходами второгорегистра, входы которого являютсягруппой информационных входов устройства, вход запуска которого соединенс входом запуска генератора импульсов, выход которого соединен с управляющим входом распределителя импульсов, первый вход которого соединен спервым входом первого элемента И, вы-,ход которого соединен с выходом признака окончания работы устройства, свыходом второй схемы сравнения, с установочными входами блока памяти,рас"пределителя импульсов и входом останова генератора импульсов, выходпо.леднего разряда блока памяти соединен с первым входом элемента ИЛИ,выход которого соединен с вторым входомпервого элемента И, выходы групп элементов И являются группой выходовустройства, второй и третий выходыраспределителя импульсов соединены суправляющим входом блока памяти и сосчетным входом первого счетчика соответственно, о т л и ч а ю щ е е с ятем, что, с целью повышения быстродействия и сокращения аппаратурныхзатрат, выход первого элемента Исоединен с управляющим входом первогосчетчика, третий выход распределителя импульсов соединен с первым входомвторого элемента И, второй вход которого соединен с выходом последнегоразряда блока памяти, второй входэлемента ИЛИ соединен с первым выходом первой схемы сравнения, второй выход которого соединен с третьим входом второго элемента И, выход которого соединен с управляющим входомгруппы элементов И,