Устройство для минимизации булевых функций

 

Союз Советскик

Соцмалмстм чески тт

Респубттнк (1 643886 (6)) Дополнительное к авт, свил-ву— (22) Заявлено 07.07.76 (21) 2379713/18-24 с присоединением заявки №(23) При оритет—

Опубликовано 25.01.79Бюллетень № 3

Дата опубликования описания 28.01 79

2 (51) M. Кл

Cj 06 F 15/34

Государотеенный комктет

СССР ло делам кзобретенкй и открыткй (53} УДК 681.325 (088. 8) (72) Авторы изобретения

10. О. Чернышев и Н. H. Садовой

Ростовский-на-Лону институт сельскохозяй машиностроения (71) Заявитель (54) УСТРОЙСТВО ЛЛЯ МИНИМИЗАЦИИ

БУЛЕВЫХ ФУНКЦИЙ

Цель данного изобретения — упрощение устройства.

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

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

Известно устройство для минимизации булевых функций, содер ж ащее блоки нахождения максимальных импликанг и блоки нахождения минимального подмножества простых импликант (1) . Однако это устройство весьма громоздко и имеет ма- 10 ло е бы стродейсг ви е.

Наиболее близким техническим решением к предпоженному изобретению является устройство для минимизации булевых функций, которое, как и данное устройство, содержит двухполюсные переключате ли, источник напряжения и индикаторные лампы конституент единицы булевой функции несклеенных конституент по погибче«

20 ским переменным и склеиваемых, консгитуент единицы $2) .

Однако это устройство требует большого количества оборудования.

) т

/ Рт..l|.. Р,,1 4 т: ";.

643886 А к йаружным выводам йсточника напряжения.

На фиг. 1 дана схема устройства для минимизации булевых функций; на фиг. 2 о приведена таблица смежности для нахож- з денни минимальной формы булевой функции, взятой в качестве примера.

Устройство содержит источйик" напряжения 1, двухполюсные переключатели

Ъ-9, индикаторные лампы конституент 10

"диницы булевой функции 10-1Ф, индикаторные лампы. несклеенных конституент щ логическим переменным 18-41, индикаторные лампы склеиваемых конституент единицы 42-53 и гасящие резисторы

54»65, Устройство работает следующим образом. В отключенном состоянии все двухполюсные переключатели 2-9 находятся

20 в верхнем положении, а все индикаторные лампы 10-53 не горят. При включении какого-либо переключателя 2-9 выводы соответствующих индикаторных ламп 1053 подключаются к одному из выводов

7$ источника напряжения. 1, а поскольку дру-гие выводы этих. ламп подключены к среднему выводу источника напряжения

1 непосредственно или через отключенные переключатели 2-9 .о эти лампы загораЭ *

30 ются и высвечивают заданную конституенту единиды булевой функции и несклеенные переменные в соответствии с гравировкой в данной строке (столбце).

При этом лампы 42-53, стоящие на пересечении строк и столбцов таблицы смежности (фиг. 2) оказываются подключенными к обоим выводам источника напряжения 1.,Пля ограничения величины тока последовательно последним лампам.

" " йбставлены гасящие сопротивления 5465.

Таким образом при минимизации функции включаются соответствующие переключатели 2-9 и на индикаторных лампах

10-17 высвечиваются заданные конституенты, а на остальных лампах высвечивается таблица смежности (см. фиг. 2), минимальное покрытие которой столбцами и строками дает нам минимальную форму функции. Лампы 42-53 показывают места склеивания конституент в столбцах и строках таблицы смежности, т.е. минимальные покрытия булевой функции.

Например, при минимизации функции

3-х переменных

Х2Х Х Ч Х2Х1ХоЧ Х Х1ХоЧ Х2Х1Х оЧ

Ч Х Х1Х ЧХ2Х1ХО включаются переключатели 2,4,5,6,7,8, 9 и загораются лампы 10, 12, 13, 14,42, 21, 44, 15,27,45,47,30,32,34,17,37, 52,53,в результате чего происходит вы-! полнение таблицы смежности в соответствии с фиг, 2.

Найдя минимальное покрытие столбцами и строками полувоенной таблицы, определим минимальные формы функции: !

Х Х 1Ч Х2ХоЧ Х 1Хо

Х КОЧХ Х ЧХ2М

Для удобства нахож ения минимального покрытия индикатор ые лампы столбцов (строк), искльчаем 1е на очередном шаге, могут быть погашены соответствующими переключателями 2,4,5,6,7,9.

Теоретическое обоснование работы ! предлагаемого устройства заключается следующем. Разобъем совершенную дизъюн1 ктивную нормальнук форму (с.д.н.ф) функции от т1 переменнь х на два подмножества:(Д вЂ” содержащее конституенты единицы с четным числом неотрицательных переменных s)3) — с нечетным и составным таблицу смежности (см. фиг. 2), в строчках которой стоят все конотитуенты подмножества (A$, а в столбцах -$5$ > причем заданные конституенты минимизируемой функции отмечены, например, "птичками, а на пересечении соответствующего столбца и строки ставится " 1 ", если конституенты отмечены и склеиваются, "-если конституенты не могут склеиваться, переменная Х 1 (X j ), по которой не произошло склеивание изза того, что отмеченный столбец (строка) пересекаются с неотмеченной строкой (столбцом). Затем найдем минимальное покрытие полученной таблицы строками, столбцами и их сочетаниями (сочетание столбца и строки входит в минимальное покрытие в том случае, если они пересекаются и в месте пересечения стоит

1), выпишем все переменные, входящие в состав, элементы минимального покрытия, объединив их знаком конъюнкции, объединим знаком дизъюнкции полученные конъюнкции и после проведения операции поглощения получим минимальную форму функции.

На фиг. 2 приведена таблица смежности, составленная для нахождения минимальной формы функции:

Х Х Х VX XÕXОЧ Х Х Х УХ2X ХОЧ

ТХХХ ЧХХ1Х .

643886

Ее минимальное покрытие может. быть образовано сочетаниями столбцов и строк

0-1, 4-6, 3-7 или 1-3, 0-4, 6-7, а минимальная форма будет

Х х VX2XoVX Х

Х2хочх1ХОV Х х !

Алгоритм может быть использован для 10 нахождения минимальной формы фуйкции оф1 переменных.

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

Устройство для минимизации булевых функций, содержащее двухполюсные переключатели, источник напряжения и индикаторные лампы конституент единицы булевой функции, несклеенных конституент по 20 логическим переменным и склеиваемых конституент единицы, о т л и ч а ю ш e— е с я тем, что, с целью упрощения устройства, в нем одни из выводов индикаторных ламп конституент единицы булевой функции подсоединены к среднему выводу источника напряжения, а их другие выводы через соответствующие замыкающие контакты двух групп пвухполюсных переключателей, соответственно по числу строк и столбцов таблицы смежности минимизируемой функции, подключены к наружным выводам того же источника напряжения, две группы индикаторных ламп песклеен ных конституент по логическим переменным включены через соответствующие двухполюсные переключатели между средним выводом источника напряжения к его наружными выводами, а индикаторные лампы склеиваемых конституент единицы через дополнительные гасящие резисторы и замыкающие контакты соответствую- щих двухполюсных переключателей подключены к наружным выводам источника напряжения.

Источники информации, принятые во внимание при экспертизе

1. Флорин Ж. Синтез логических усгройств и его автоматизация. M., Мир, 1966, с. 257-370.

2. Ав торское сви де тел ьст во С CCP

177692, кл. Cj 06 Р 15/34, 1964.

643886

Составитель Г. Сорокин

Редактор A. Садомов Техред И. Асталош Корректор А. Власенко юМ йю;й йай ъь

Заказ 159/49 Тираж 779 .Подписное

ЦНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5 филиал ППП Патент, r. Ужгород, ул. Проектная, 4