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

(57) Изобретение отн ной технике и может системах управлен Целью изобретения .области применения работки множеств с и жением элементов, два блока памяти, дв нения, три группы элемент И, элемент ронизации, 2 ил,жЯ ГОСУДАРСТВЕННОЕ ПАТЕНТНОВЕДОМСТВО СССР(71) Московский институт инженеров грданской авиации(56) Авторское свидетельство СССРМ 1176346, кл, 6 06 Р 15/38, 1984.Авторское свидетельство СССРМ 1267436, кл, 6 06 Г 15/38, 1985,(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНРАЗНОСТИ МНОЖЕСТВ Изобретение относится к вычислительной технике и может быть использовано всистемах управления банками данных.Цель изобретения - расширение области применения за обработки множеств спроизвольным расположением элементов,На фиг, 1 приведена структурная схемаустройства для определения разности множеств; на фиг, 2 - структурная схема блокасинхронизации,Устройство для определения разностимножеств (фиг, 1) содержит блоки 1 и 2 памяти, первый и второй счетчики 3, 4, группы5-7 элементов И с первой по третью соответственно, блок 8 синхронизации, схему 9сравнения, триггер 10, элемент 11 И, элемент 12 задержки, первую группу 13 адресных входов, вторую 14 группу адресныхвходов, вход 15 пуска, группу 16 информационных выходов, управляющий выход 17,пятый выход 18 блока синхронизации, выходи19-22 блока синхронизации с первого почетвертый соответственно, второй и третийвходы 23 и 24 блока синхронизации,501817106 А 1 осится к вычислительбыть использовано в ия банками данных. является расширение устройства за счет оброизвольным располоУстройство содержит а счетчика, схему сравэлементов И триггер задержки и блок синхБлок синхронизации (фиг, 2) содержит элемент 25 ИЛИ, первый и второй элементы 26 и 27 И, распределитель 28, триггер 29 и генератор 30 тактовых импульсов.Пусть существует универсальное множество Р; остальные множества, элементы которых являются элементами множества Р, называются подмножествами множеств Р. Все используемые подмножества в виде совокупностей своих элементов записаны в блоках памяти 1 и 2, содержимое которых идентично. Элементы некоторого множества записаны в смежных ячейках каждого блока памяти. Пользователю известны начальные адреса каждого множества (среди них может находиться и универсальное), Тогда разностью подмножеств А и В является множество С, в которое входят элементы множества А, не входящие в множество В, В частности, если множеством А является множество Р, то разность (А - В) является дополнением множества В. (Следует заметить, что операция вычитания множеств некоммутативна). Последний элемент каждого10 20 25 30 40 45 50 множества в устройстве помечается "единицей" в стэршем разряде памяти (на фиг, 1 помечен пунктиром); остальные элементы в данном разряде содержат нули. Элементы множеств закодированы числами (в двоичной форме) от 1 до К, где К - мощность множества Р,Устройство работает следующим образом,При включении питания распределитель 28 блока 8 устанавливается в исходное состояние; нэ всех его выходах - нули. Генератор 30 зэкрыт; счетчики 3 и 4 обнулены (соответствующие цепи не показаны на фиг, 1, 2).Подготовка устройства к работе осуществляется подачей на входы 13 начального адреса "уменьшаемого" множества А, э на входы 14 - начального адреса "вычитэемого" множества В, После этого устройство готово к работе.Запуск работы устройства осуществляется подачей импульса на вход 15 пуска устройства, который устэнавливает в единичное состояние триггер 29 и запускает генератор 30. Распределитель 28 нэчинает циклически формировать импульсы на своих выходах (последовательно, с первого по четвертый 19 - 22), Устанавливаясь в единичное состояние, триггер 29 открывает через элемент ИЛИ 25 элементы И 26 и 27, э также переписывает с входов 13 код в счетчик 4, По сигналу с выхода первого распределителя 28 формируется сигнал на выходе элемента И 26, который инкрементирует содержимое счетчика 4 (таким образом, для более корректной работы устройства и обслуживания им полного "уменьшэемого" множествэ следует нэ входах 13 устанэвливать код адреса на единицу меньше начального). Сигналом с второго выхода распределителя 28 формируется сигнал на выходе элемента И 27, устанавливающий в единичное состояние триггер 10 и записывающий в счетчик 3 код с входов 14; триггер 29 возвращается в исходное состояние; открываются элементы группы И 7 и начальный адрес "уменьшаемого" множества (А) поступает нэ адресные входы блока памяти 2. Сигналом с выхода 21 блока 8 открывается группа 5 элементов И и выдает на адресные входы блока памяти 1 начальный эдрес "вычитаемого" множества (В), Первые элементы множеств А и В поступают на входы схемы сравнения 9. При их совпадении нэ вход сброса триггера 10 поступает сигнал, устанавливающий его в нуль, В противном случае ничего не происходит.Сигналом с выхода 22 блока 8 счетчик 3 инкрементируется. Далее процесс продолжэется аналогично, за исключением того, что элементы И 26 и 27 закрыты в следующих циклах, На схеме сравнения 9 последовательно сравниваются элементы множества В с первым элементом множества А. При совпадения любого элемента множества В с элементом множествэ А триггер 10 устанавливается в нуль,После достижения последнего элемента множества В с последнего разряда блока памяти 1 формируется сигнал, подготавливающий к срабатыванию элементы И 26 и 27; формируется рэзрешэющий сигнал на блок 6, который, если триггер 10 не сброшен в нуль, в момент формирования сигнэла нэ выходе 22 блока 8 выдает первый элемент множества А на выход 16 устройства, что означает, что первый элемент множества А не содержится в множестве В. В противном случае элемент нэ выход 16 не выдается,Зэтем, с началом нового цикла распределителя сигналом с выхода 19 блока 8 содержимое счетчика 4 инкрементируется, и далее процесс перебора всех элементов множества В повторяется для следующего элемента множества А,Когда перебор элементов множества А достигает его последнего элемента, в последнем разряде блока 2 формируется сигнал, подготавливэющий к срабатыванию элемент 11, После перебора для последнего элемента множества А всех элементов множества В сигналом с выхода последнего разряда блока 1 через элемент задержки 12 формируется сигнал нэ выходе элемента 11, который подэется пользователю, сигнализируя об окончании операции определения разности множеств; обнуляет регистры информации блоков памяти 1 и 2; устэнавливэетв исходное состояние распределитель 28 и генератор 30. Операция закончена.Следует отметить, что после каждого цикла работы сигналом с элемента И 26 триггер 10 устанавливается в единичное состояние.Таким образом, в результате работы ус-тройства на выходе 16 формируется последовательность элементов множества А, не входящих в множество В, т.е. разность А - В,При подаче нэ вход "уменьшэемого" множествэ начального адреса универсального множества нэ выходе возможно формирование дополнения для некоторого выбранного подмножества В. Следовательно, данное устройство реализует операцию рэзности множеств и, кэк дополнение, операцию получения дополнения заданного множества до универсального (последняя операция реализуется прототипом).Формула изобретения Устройство для определения разности множеств, содержащее блок синхронизации, первый вход которого соединен с входом пуска устройства, первый счетчик, информационный вход которого соединен с входом начального адреса первоо множества устройства, а выход - с первыми входами элементов И первой группы, выходы которых соединены с адресными входами первого блока памяти, выходы разрядов которого, кроме последнего, соединены с первым входом схемы сравнения, выход которой соединен с нулевым входом триггера, выход которого соединен с первыми входами элементов И второй группы, вторые входы которых соединены с выходом последнего разрядов первого блока памяти и с вторым входом блока синхронизации, первый, второй, третий и четвертый выходы которого соединены соответственно со счетным входом второго счетчика, с входом записи первого счетчика, с втОрыми входами элементов И первой группы, со счетным входом первого счетчика, выходы элементов И второй группы являются информационным выходом устройства, четвертый выход блока синхронизации соединен с третьими входами элементов И второй группы, вход начального адреса второго множества устройства соединен с информационным входом второго счетчика, 5 отличающеесятем,что,сцельюрасширения области применения путем обработки множеств с произвольным расположением элементов, в него введены элемент И, второй блок памяти, третья группа эле ментов И, элемент задержки, причем входзаписи второго счетчика и его выход соединены соответственно с пятым выходом блока синхронизации и с первыми входами элементов И третьей группы, выходы кото рых соединены с адресными входами второго блока памяти, выходы разрядов которого, кроме последнего, соединены с четвертыми входами элементов И второй группы и с вторым входом схемы сравнения, выход по следнего разряда первого блока памяти через элемент задержки соединен с первым входом элемента И, второй вход которого соединен с выходом последнего разряда второго блока памяти, а выход - с выходом 25 окончания работы устройства, с третьимвходом блока синхронизации и с установочными входами первого и второго блоков памяти,1817106 Составитель С.Кишенскииактор Г.Бельская Техред М,Моргентал Корректо К ине роиэводственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 10 акаэ 1724 Тираж ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС113035, Москва, Ж, Раушская наб., 4/5