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

 

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

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

РЕСПУБЛИК (l% (1!) (5D 4 G 06 F 15 38

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ з zo

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21 ) 3891608/24-24 (22) 26.04.85 (46) 30.10.86. Бюл. У 40 (72) Б. С. Богумирский, В. Я. Яцук и В. А. Палагушин (53) 681.325(088.8) (56) Авторское свидетельство СССР

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

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

У 780011, кл. G 06 F 15/38, 1978. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ДОПОЛНЕНИЯ МНОЖЕСТВА (57) Изобретение относится к вычислительной технике. Целью изобретения является расширение функциональных возможностей за счет обеспечения операции сравнения элементов множеств. Устройство содержит блок 1 па" мяти, два счетчика 2 10, два элемента И 3, 4, элемент ИЛИ 5, две груп- . пы элементов И 6,7, два регистра 8,9>

pBb схемы 11, 12 сравнения, генератор ктовых импульсов, распределитель пульсов, триггеры 13,14. 1 ил.!! 1

Изобретение относится к вычислительной технике и может быть использовано в системах управления банками данных.

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

На чертеже приведена схема устройства, Устройство содержит блок 1 памяти, счетчик 2, элементы И 3, 4, элемент ИЛИ 5, группы 6, 7 элементов И, .регистры 8, 9, счетчик 10, схемы !I

12 сравнения, триггеры 13, 14, генератор 15 тактовых импульсов, распределитель 16 импульсов, адресный вход 17, информационный вход 18, вход 19 запуска, информационный выход 20, выход 21 признака окончания.

Схемы ll и 12 выдают сигнал при совпадении сравниваемых кодов, Группа 6 элементов И открывается при наличии сигналов одновременно на трех ев входах. При подаче адреса на адресный вход блока 1 этот блок выдает содержимое соответствующей ячейки памяти на свой выход и поддерживает его до тех пор, пока на его адресный вход не будет подан новый адрес.

Пусть P — универсальное множество, а А — множество, являющееся подмножеством множества P. Тогда дополнение множества А является множеством B=A элементов из множества

Р, не принадлежащих множеству А.

Множества, являющиеся подмножествами множества P хранятся в блоке 1 памяти, причем элементы этих множеств представлены кодами присел.

Элементы каждого множества находят,ся в последовательных ячейках памяти. Последний элемент каждого множества отмечается единицей в последнем разряде. Все остальные элементы отмечаются нулем. Элементы универсального множества закодированы целыми числами от I до N где N — число элементов в универсальном множестве. Во всех множествах один и тот же элемент представляется одинаковым кодом, Устройство работает следующим образом.

При включении питания распределитель 16 импульсов устанавливается в исходное состояние (при этом ни на одном из его выходов сигнал не появляется), генератор 15 устанавливает267436

5 !

О

f5

55 ся в запертое состояние, а регистр информации блока памяти и счетчик

I0 обнуляются (не показано). По вхо-. ду 18 в регистр 9 записывается код числа N+1, а по входу !7 в регистр 8 заносится адрес первого элемента множества А.устройство готово к рабоче, 3апуск устройства в работу осуществляется импульсом с входа 19, По этому импульсу триггер 13 устанавливается в единичное состояние, в результате чего открываются элементы И 3 и 4, и запускается генератор 15. Распределитель 16 начинает распределять импульсы по управляющим точкам устройства. По импульсу с первого выхода распределителя 16 триггер 14 устанавливается в единичное состояние, а содержимое счетчика 10 увеличивается на единицу, т.е. в нем формируется код первого (в дальнейшем очередного) элемента множества. На выходе блока 1 памяти присутствует нулевой код {в том числе и на выходе последнего разряда).

Поэтому схема 11 сигнала не выдает.

По импульсу с второго выхода распределителя !6 триггер 13 обнуляется, а в счетчик 2 из регистра 8 принимается адрес первого элемента множества А. По импульсу с третьего выхода распределителя 16 адрес первого (в дальнейшем очередного) элемента множества А из счетчика 2 подается в блок 1 памяти, в результате чего на его выходах появляется код первого элемента множества А.

Предположим, что множество А содержит не один, а несколько элементов. Поэтому сигнал на выходе последнего разряда блока 1 отсутствует.

Если код первого (в дальнейшем оче— редного) элементамножества А .равен коду первого {в дальнейшем очередного) элемента множества Р, то схема Il выдает сигнал, по которому триггер 14 обнуляется. По импульсу с четвертого выхода раслределителя

16 содержимое счетчика 2 увеличивается на единицу (т.е. формируется адрес следующего элемента множества А). Группа 6 элементов И не открывается, так как отсутствует сигнал с выхода последнего разряда блока 1 вследствие того, что еще не прочитаны все элементы множества А и не произведено их сравнение с первым (в дальнейшем очередным) элементом множества P.

12674!

f5

25

35

45

55

После этого снова появляется импульс на первом выходе распределителя 16, но так как элемент И 3 закрыт, то никаких действий по нему не производится. Импульс с второго выхода распределителя 16 также не проходит через закрытый элемент И 4.

По импульсу с третьего выхода распределителя 16 из блока 1 считывается код следующего элемента множества A после чего он сравнивается с кодом первого (в дальнейшем очередного) элемента множества P схемой 11.

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

Пусть из блока 1 считан последний элемент множества А. При этом появляется сигнал на выходе последнего разряда блока 1, что способствует открытию группы 6 элементов И. Этим же сигналом открываются элементы ИЗ и 4. Если первый (в дальнейшем очередной) элемент множества P совпал с одним из элементов множества А, то триггер 14 обнулен. Поэтому по импульсу с четвертого выхода распределителя 16 группа 6 элементов И не открывается. Если же триггер 14 остался в единичном состоянии, т.е. первый (в дальнейшем очередной) элемент множества P не принадлежит множеству А, то по этому импульсу группа 6 элементов И открывается и код первого (в дальнейшем очередного) элемента множества P из счетчика 10 поступает на выход 20 устройства в качестве кода первого (в дальнейшем очередного) элемента множества P.

Затем снова появляется импульс на первом выходе распределителя 16, по которому в счетчике 10 формируется код следующего элемента множества Р, а триггер 14 устанавливается в исходное (единичное) состояние.

По импульсу с второго выхода распределителя 16 подтверждается нулевое состояние триггера 13 и в счетчик 2 принимается адрес первого элемента множества А. В дальнейшем устройство работает аналогично описанному выше до тех пор, пока по очередному импульсу с первого выхода распределителя 16 содержимое счетчика 10 не совпадет с содержимым регистра 9.

При совпадении схема 12 выдает сигнал, по которому устройство устанавливается в исходное состояние (т.е. распределитель 16 переводится в исходное состояние, генератор 15 — в запертое, а счетчик 10 и регистр информации блока 1 обнуляются). Кроме того, он проходит на выход 21 устройства, сигнализируя об окончании формирования множества В.

После записи в регистр 8 адреса нового множества А устройство снова запускается в работу импульсом на входе 19 для определения множест ва В =A .

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

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

Редактор Н. Слободяник Техред А.Кравчук

Корректор М. Пожо

Заказ 5777/48 Тираж 67) ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

Подписное

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

$ l распределителя импульсов, второго счетчика и выход признака окончания устройства соединены с выходом второй схемы сравнения, счетный вход второго счетчика и единичный вход второго триггера соединены с выходом первого элемента И, первый: вход которого и первый вход второго элемента И соединены с выходом элемента ИЛИ, первый вход которого соединен с выходом первого триггера, нулевой вход которого соединен с выходом второго элемента И и с входом записи первого счетчика, первый и второй выходы распределителя импуль267436 Ь сов соединены соответственно с первыми входами первого и второго элемента И, третий выход подключен к вторым входам элементов И второй группы, четвертый выход распределителя импульсов соединен со счетным входом второго счетчика и с вторыми входами элементов И первой группы, третьи входы которых соединены с вы ð ходом второго триггера, нулевой вход которого соединен с выходом первой схемы. сравнения, выход последнего разряда блока памяти соединен с четвертыми входами элементов Ипервой груп1 пы ис вторымвходом элемента ИЛИ.