Устройство для определения дополнения множества Советский патент 1986 года по МПК G06F17/27 

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

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

На чертеже приведена схема устройства.

Устройство содержит блок 1 памяти, счетчик 2, элементы ИЗ, 4, элемент ИЛИ 5, группы 6, 7 элементов И .регистры 8, 9, счетчик 10, схемы 11, 12 сравнения, триггеры 13, 14, генератор 15 тактовых импульсов, распределитель 16 импульсов, адресный вход 17, информационный вход 18, вход 19 запуска, информационный выход 20, выход 21 признака окончания Схемы 11 и 12 выдают сигнал при совпадении сравниваемых кодов. Группа 6 элементов И открывается при наличии сигналов одновременно на трех ее входах. При подаче адреса на адресный вход блока 1 этот блок выдает содержимое соответствующей ячейки памяти на свой выход и поддерживает его до тех пор, пока на его адресный вход не будет подан новый а,црес

Пусть Р - универсальное множество, а А - множество, являющееся подмножеством множества Р. Тогда дополнение множества А является множеством элементов из множества Р, не принадлежащих множеству А. Множества, являющиеся подмножествами множества Р, хранятся в блоке 1 памяти, причем элементы этих множеств представлены кодами исел. Элементы каждого множества ,ся в последовательных ячейках памяти. Последний элемент каждого множества отмечается единицей в последнем разряде. Все остальные элементы отмечаются нулем. Элементы универсального множества закодированы целыми числами от 1 до N, где N - число элементов в универсальном множестве. Во всех множествах один и тот же элемент представляется одинаковым кодом.

Устройство работает следующим образом.

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

ся в запертое состояние, а регистр информации блока памяти и счетчик 10 обнуляются (не показано). По вхо-. ду 18 в регистр 9 загшсывается код

5 числа N+I, а по входу 7 в регистр 8 заносится ад,рес первого элемента множества А.Устройство готово кработе.

Запуск устройства в работу осуществляется импульсом с входа 19,

10 По этому импульсу триггер 13 устанавливается в единичное состояние, в результате чего открываются элементы И 3 и 4, и запускается генератор 15. Распределитель 16 начинает

t5 распределять импульсы по управляющим точкам устройства. По импульсу с перво.го выхода распределителя 16 триггер 14 устанавливается в единичное состояние, а содержимое счетчи20 ка 10 увеличивается на единицу, т.е. в нем формируется код первого (в дальнейшем очередного) элемента множества. На выходе блока 1 памяти присутствует нулевой код (в том чис25 ле и на выходе последнего разряда). Поэтому схема 11 сигнала не выдает. По импульсу с второго выхода распределителя 16 триггер 13 обнуляется, а в счетчик 2 из регистра 8 принима30 ется адрес первого элемента множества А. По импульсу с третьего выхода распределителя 16 адрес первого (в дальнейшем очередного) элемента мно жества А из счетчика 2 подается в блок 1 памяти, в результате чего на его выходах появляется код первого элемента множества А,

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

3

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

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

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

674364

совпадет с содержимым регистра 9, При совпадении схема 12 выдает сигнал, по которому устройство устанавливается в исходное состояние (т.е.

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

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

., на входе 19 для определения множества в А .

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

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

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

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

распределителя импульсов, второго счетчика и выход признака окончания устройства соединены с выходом второй схемы сравнения, счетный вход второго счетчика и единичный вход второго триггера соединены с выходом первого элемента И, первый вход которого и первый вход второго элемента И соединены с выходом элемента ИЛИ, первый вход которого соединен с выходом первого триггера, нулевой вход которого соединен с выходом второго элемента И и с входом записи первого счетчика, первый и второй выходы распределителя имлуль

67436ft

сов соединены соответственно с первыми входами первого и второго элемента И, третий выход подключен к вторым входам элементов И второй

J группы, четвертый выход распределителя импульсов соединен со счетным входом второго счетчика и с вторыми входами элементов И первой группы, третьи входы которых соединены с вы10 ходом второго триггера, нулевой вход которого соединен с выходом первой схемы; сравнения, выход последнего разряда блока памяти соединен с четвертыми входами элементов Ипервой груп15 пыис вторым-входом элемента ИЛИ.