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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСГ1УБЛИК (st)s G 06 F 15/38

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕН1 СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4784841/24 (22) 18.12.89 (46) 23.05.93. Бюл. ¹ 19 (71) Московский институт инженеров гражданской авиации (72) С.Ж,Кишенский, А.Л.Кузьмин, Е,Н.Надобных и О.Ю.Христенко (56) Авторское свидетельство СССР

N 1176346, кл, G 06 F 15/38, 1984.

Авторское свидетельство СССР

¹ 1267436, кл. G 06 F 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 блока синхронизации.

„„5U „„1817106 А1 (57) Изобретение относится к вычислительной технике и может быть использовано в системах управления банками данных.

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

Блок синхронизации (фиг. 2) содержит З элемент 25 ИЛИ, первый и второй элементы

26 и 27 И, распределитель 28, триггер 29 и генератор 30 тактовых импульсов.

Пусть существует универсальное множество Р; остальные множества, элементы которых являются элементами множества Р, называются подмножествами множеств P.

Все используемые подмножества в виде со- р вокупностей своих элементов записаны в блоках памяти 1 и 2, содержимое которых идентично. Элементы некоторого множества записаны в смежных ячейках каждого блока памяти. Пользователю известны на- О чальные адреса каждого множества (среди О них может находиться и универсальное).

Тогда разностью подмножеств А и В является множество С, в которое входят элементы множества А, не входящие в множество В.

В частности, если множеством А является множество Р, то разность (А - В) является дополнением множества В. (Следует заметить, что операция вычитания множеств некоммутативна). Последний элемент каждого

1817106

20

30

50 множества в устройстве помечается "единицей" в старшем разряде памяти (на фиг, 1 помечен пунктиром); остальные элементы в данном разряде содержат нули. Элементы множеств закодированы числами (в двоичной форме) от 1 до К, где К вЂ” мощность множества Р, Устройство работает следующим образом, При включении питания распределитель 28 блока 8 устанавливается в исходное состояние: на всех его выходах — нули. Генератор 30 закрыт; счетчики 3 и 4 обнулены (соответствующие цепи не показаны на фиг.

1, 2).

Подготовка устройства к работе осуществляется подачей на входы 13 начального адреса "уменьшаемого" множества А, à wa входы 14 — начального адреса "вычитаемого" множества В, После этого устройство готово к работе.

Запуск работы устройства осуществляется подачей импульса на вход i5 пуска устройства, который устанавливает в единичное состояние триггер 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 блока S выдает первый элемент множества А на выход 16 устройства, что означает, что первый элемент множества А не содержится в множестве

В. В противном случае элемент на выход

16 не выдается.

Затем, с началом нового цикла распределителя сигналом с выхода 19 блока 8 содержимое счетчика 4 инкрементируется, и далее процесс перебора всех элементов множества В повторяется для следующего элемента множества А.

Когда перебор элементов множества А достигает его последнего элемента, в последнем разряде блока 2 формируется сигнал, подготавливающий к срабатыванию элемент 11, После перебора для последнего элемента множества А всех элементов множества В сигналом с выхода последнего разряда блока 1 через элемент задержки 12 формируется сигнал на выходе элемента 11, который подается пользователю, сигнализируя об окончании операции определения разности множеств; обнуляет регистры информации блоков памяти 1 и 2; устэнавливаетв исходное состояние распределитель 28 и генератор 30. Операция закончена.

Следует отметить, что после каждого цикла работы сигналом с элемента И 26 триггер 10 устанавливается в единичное состояние.

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

1817106

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

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

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

И, второй блок памяти, третья группа эле10 ментов И, элемент задержки, причем вход записи второго счетчика и его выход соединены соответственно с пятым выходом блока синхронизации и с первыми входами элементов И третьей группы, выходы кото15 рых соединены с адресными входами второго блока памяти, выходы разрядов которого, кроме последнего, соединены с четвертыми входами элементов И второй группы и с вторым входом схемы сравнения, выход по20 следнего разряда первого блока памяти через элемент задержки соединен с первым входом элемента И, второй вход которого соединен с выходом последнего разряда второго блока памяти, а выход — с выходом

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

Составитель С.Кишенский

Техред M.Moðråíòàë Корректор M,Mýêñèìèøèíåö

Редактор Г.Бельская

Производственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101

Закаэ 1724 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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