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

Союз Советскит Соцмалнстм ческит Республик(51) М, КлС 06 Р 15/34 Государотаенный комктет СССР ло делам кзобретенкй и откроткй(71) Заявитель 54) УСТРОЙСТВО ЛЛЯ МИНИМИЗЛЦИ БУЛЕВЫХ ФУНКЦИЙние устройства.Указанная цель достигается тем, что в устройстве одни из выводов индикаторных ламп конституент единицы булевой функции подсоединены к среднему выводу исгочника напряжения, а их другие выводы через соответствующие замыкающие контакты двух групп двухполюсных переключателей, соответственно по числу строк и столбцов таблицы смежности минимизируемой функции, подключены к наружным выводам того же источника напряжения две группы индикаторных ламп нескдеендоги ескм переменветствующиеели между средапряжения и его индикаторные титуент единицы сяшие резисторы соответствующих елей подключены ных конституент по ч ным включены через соот двухполюсные переключаг ним выводом источникан наружными выводами, а лампы склеиваемых конс через дополнительные га и замыкающие контакты двухполюсных переключа Изобретение относится к области вычислительной техники и может найти при- менение при автоматизации процесса проектирования и диагностики дискретных устройств.Известно устройство для минимизации 5 булевых функций, содержащее блоки нахождения максимальных импликанг и блоки нахождения минимального поиможества простых импликант 111, Однако это устройство весьма громоздко и имеет ма- то лое быстродействие.Наиболее близким техническим решением к предложенному изобретению является устройство для минимизации булевых функций, которое, как и данное устройство, содержит двухполюсные переключате ли, источник напряжения и индикаторные лампы конституент единицы булевой функции несклеенных конституент по погибче920 ским переменным и склеиваемых, консгитуент единицы 12 .Однако это устройство требует большого количества оборудования. ного изобретения - упро3 643886 включаются переключатели 2,4,5,6,7,8,9 и загораются лампы 10, 12, 13, 14,42,21 441 153 271 45 ф 47 30 321 34 1 7 ф 3752,53,в результате чего происходит выполнение таблицы смежности в соответствии с фиг, 2.Найдя минимальное покрытие столбцами и строками полувоенной таблицы, определим минимальные формы функции:ХХ 1 Ч ХХаЧ Х 1 Хох Х ЧХ Х ЧХ МДля удобства нахож ения минимальногопокрытия индикатор ые лампы столбцов(строк), искльчаем 1 е на очередном шаге, могут быть погашены соответствующими переключателями 2,4,5,6,7,9.Теоретическое обоснование работы0 предлагаемого устройства заключается кследующем. Разобъем совершенную дизъюнктивную нормальнук форму (с.д,н.ф) функции от т 1 переменньх на два подмножества:Я - содержащее конституенты еди 5 ницы с, четным числом неотрицательныхпеременных и,3 - с нечетным и составным таблицу смежности (см. фиг. 2), встрочках которой стоят все конотитуентыподмножества А, а в столбцах -Ъ 10 причем заданные конституенты минимизируемой функции отмечены, например,"птичками, а на пересечении соответствующего столбца и строки ставится " 1 ",если конституенты отмечены и склеиваются,"-если конституенты не могутсклеиваться, переменная Х 1 ( 71 ),по которой не произошло склеиваниеизза того, что отмеченный столбец (строка) пересекаются с неотмеченной строО кой (столбцом). Затем найдем минимальное покрытие полученной таблицы строками, столбцами и их сочетаниями (сочетание столбца и строки входит в минимальное покрытие в том случае, если они пе 45 ресекаются и в месте пересечения стоит1), выпишем все переменные, входюциев состав, элементы минимального покрытия, объединив их знаком конъюнкции,объединим знаком дизъюнкции полученныеконъюнкции и после проведения операциипоглощения получим минимальную формуфункции,На фиг. 2 приведена таблица смежности, составленная для нахождения минимальной формы функции:Х Х Х ЧХ Х 1 Х Ч Х х Х ЧХХ ХоЧУХХХЧХХХ 15 35 к наружным выводам йсточника напряжения,На фиг, 1 дана схема устройства дляминимизации булевых функций; на фиг. 2оприведена таблица смежности для нахожденни минимальной формы булевой функции, взятой в качестве примера.Устройство содержит источйик" напряжения 1, двухполюсные переключателиЪ, индикаторные лампы конституент 10"диницы булевой функции 10-1 Ф, индикаторные лампы. несклеенных конституент щлогическим переменным 18-41, индикаторные лампы склеиваемых конституентединицы 42-53 и гасящие резисторы5465,Устройство работает следующим образом. В отключенном состоянии все двухполюсные переключатели 2-9 находятся2в верхнем положении, а все индикаторныелампы 10-53 не горят. При включениикакого-либо переключателя 2-9 выводысоответствующих индикаторных ламп 1053 подключаются к одному из выводов7источника напряжения. 1, а поскольку дру гие выводы этих ламп подключены ксреднему выводу источника напряжения1 непосредственно или через отключенныепереключатели 2-9, .о эти лампы загораются и высвечивают заданную конституенту единицы булевой функции и несклеенные переменные в соответствии с гравировкой в данной строке (столбце),При этом лампы 42-53, стоящие напересечении строк и столбцов таблицысмежности (фиг. 2) оказываются подключенными к обоим выводам источника напряжения 1.,Пля ограничения величинытока последовательно последним лампам" йаставлены гасюцие сопротивления 5465.Таким образом при минимизации функции включаются соответствующие переключатели 2-9 и на индикаторных лампах10-17 высвечиваются заданные конституенты, а на остальных лампах высвечивается таблица смежности (см, фиг. 2),минимальное покрытие которой столбцамии строками дает нам минимальную формуфункции. Лампы 42-53 показывают места склеивания конституент в столбцах истроках таблицы смежности, т.е, минимальные покрытия булевой функции,Например, при минимизации функции3-х переменныхХ Х Х ЧХ Х ХаЧХ Х ХоЧХХ ХаЧЧ Х,Х,Х,ЧХ Х,Х,Ее минимальное покрытие может. бытьобразовано сочетаниями столбцов и строк0-1, 4-6, 3-7 или 1-3, 0-4, 6-7,а минимальная форма будетХ Х УХХоХ 1 Хо/)(Алгоритм может быть использован для 10нахождения минимальной формы фуйкцииофЧ переменных.формула изобретения15Устройство для минимизации булевых функций, содержащее двухполюсные переключатели, источник напряжения и индикаторные лампы конституент единицы булевой функции, несклеенных конституент по 20 логическим переменным и склеиваемых конституент единицы, о т л и ч а ю ш е - е с я тем, что, с целью упрощения устройства, в нем одни из выводов индикаторных ламп конституент единицы булевой функции подсоединены к среднему выводу источника напряжения, а их другие выводы через соогвегсгвующие замыкающиеконтакты двух групп пвухполюсных переключателей, соответственно по числу строки столбцов таблицы смежности минимизируемой функции, подключены к наружнымвыводам того же источника напряжения,две группы индикаторных ламп песклеенных конституент по логическим переменным включены через соответствующиедвухполюсные переключатели между средним выводом источника напряжения кего наружными выводами, а индикаторныелампы склеиваемых констигуенг единицычерез дополнительные гасящие резисторыи замыкающие контакты соответствующи-хих двухполюсных переключателей подключены к наружным выводам источниканапряженияИсточники информации, принятые вовнимание при экспертизе1. флорин Ж. Синтез логических устройств и его автоматизация. М Мир1966, с. 257-370,2. Авторское свидетельство СССР177692, кл. Ц 06 Р 15/34, 1964,643886 к тавитель Г. Соред И, Астал ректор А. Власен Редакто аказ 11303 атент", г. Ужгород, ул. Проектная, 4 П СоА. Садомов Те/49 ТирЦНИИПИ Госупо дел5, Москва ж 779 рственного ком изобретени Ж, Раущс