Устройство для минимизации булевых функций Советский патент 1979 года по МПК G06F7/544 

и HapyjkHbiM выводам источника напряжения. i На фиг, 1 дана схема устройства для минимизации булевых функций; на фиг. 2 приведена таблица смежности для нахождения минимальной формы булевой функции, взятой в качестве примера. Устройство содёрз ит источник ШНряжения 1, двухполюсные Переключатели 2-9, индикаторные лампы конституент ЕДИНИЦЫ булевой функции lO-ll, индикаторные лампы несклеенных конституент п логическим переменным 18-41, индикаторные лампы склеиваемых конституенг единицы 42-53 и гасящие резисторы 54-65. Устройство работает следующим образом. В отключенном состоянии все двухполюсные переключатели 2-9 находятся в верхнем положении, а все индикаторны лампы 10-53 не горят. При включении какого-либо переключателя 2-9 выводы соответствующих индикаторных ламп 1053 подключаются к одному из выводов источника напряжения: 1, а поскольку дру гие выводы этих ламп подалючены к среднему выводу источника напрзяжения 1 непофедственнсэ или через отключенны переключатели 2-9, .о эти лампы загора ются и высвечивают заданную конституенту единицы булевой функции и несклеен ные переменные в соответствии с гравировкой в данной строке (столбце). При этом лампы 42-53, стоящие на пересечении строк и столбцов таблицы смежности (фиг. 2) оказываются подклю ченными к обоим выводам источника нап ряжения 1. Для ограничения величины тока последовательно последним лампам .,,. .-..-. поставлёны ГасяздИе сопротивления 5465. Таким образом при минимизации функ ции включаются соответствующие переключатели 2-9 и на индикаторных лампах , „ , . 10-17 высвечиваются заданные консти.. туенты, а на остальных лампах высвечивается таблица смежности (см. фиг. 2), минимальное покрытие которой столбцам и строками дает нам минимальную форму функции. Лампы 42-53 показывают места склеивания конституент в столбцах и строках таблицы смежности, т.е. минимальные покрытия булевой функции Например, при минимизации функции 3-х переменных X2 lXoVX2XiXoVX2 iXoVX2,X.XoV V,X2 lXoVX.,XiXo включаются переключатели 2,4,5,6,7,8, 9 и загораются 10,12,13,14,42, 21, 44,15,27,45,4-;. 30,32, 34,17,37, 52,53, в результате, чего происходит выполнение таблицы сь ежности в соответствии с фиг. 2. ;:; Найдя минимальное покрытие столбцаМи .и строками полученной таблицы, определим минимальные формы функции; ,Xo X XoVXixJvXgX . Для удобства нахождения минимального покрытия Ий дика горные лампы столбцов (строк), исклйШеМьш на очередном шаге, могут быть погашены соответствующими переключателями 2,4,5,6,7,9. Теоретическое обоснование работы предлагаемого устройства заключается л следующем. Разобьем совершенную дизъюнктивную нормальную форму (с.д.н.ф) функции от YI перемённ1,т1х на два подмножества: АЗ - содержащее конституенты единицы с четным числом неотрицательных переменных - с нечетным и составным таблицу смежности (см. фиг. 2), в строчках которой стоят все конституенты подмножества ГА , а в столбцах -Г&З причем заданные конституенты минимизиРУ функции отмечены, например, птичками , а на пересечении соответствующего столбца и строки ставится 1, если конституенты отмечены и. склеиваются, -если конституен.ты не могут склеиваться, переменная Xj ( Х ), по которой не произошло склеивание изза того, что отмеченный столбец (строка) пересекаются с неотмеченной строкой (столбцом). Затем найдем минимальное покрытие полученной таблицы строками, столбцами и их сочетаниями (сочетание столбца и строки входит в минимальное покрытие в том случае, если они пе- ресекаются и в месте пересечения стоит ,1), выпишем все переменные,входящие в состав,элементы минимального покрытия, объединив их.знаком конъюнкции, объединим знаком дизъюнкции полученные конъюнкции и после проведения операции поглощения получим минимальную форму функции. На фиг. 2 приведена таблица смежности, составленная для нахождения минимальной формы функции: X X X VXgXiX YXgX X YXgXiXoV YXgX.. Ее минимальное покрытие может быть образовано сочетаниями столбцов и строк О-1, 4-6, 3-7 или 1-3, О-4, 6-7, а минимальная форма будет X2XiVX2X VX X X XoVXjXoVX. Алгоритм может быть использован для нахождения минимальной формы фуйкции or|irl| переменных. Формула изобретения Устройство для минимизации булевых функций, содержащее ДЬухполюсные переключатели, источник напряжения и индикаторные лампы констлтуент единицы булевой функции, несклеенных конституент по логическим переменным и склеиваемых констигуент единицы, отличающе еся тем, что, с. целью упрощения устройства, в нем одни из выводов индикаторных ламп конституент единицы булево функции подсоединены к среднему выводу источника напряжения, а их другие выводы через соответствующие замыкающие контакты двух групп пвухполюсньгх переключателей, соответственно по числу строк и столбцов таблицы смежности минимизируемой функции, подключеР1Ы к наружным выводам того же источника напряжения, две группы индикаторных ламп несклеен- ных конституент по логическим переменным включены через соответствующие двухполюсные пфеключатели между средним выводом источника напряжения и его наружными выводами, а индикаторные пампы склеиваемых конституент единицы через дополнительные гасящие резисторы и замыкающие контакты соответствующих двухполюсных переключателей подключены к наружным выводам источника напряжения. Источники информации, принятые во внимание при экспертизе 1.Флорин Ж. Синтез логических устройств и его автоматизация, М.,Мир 1966, с. 257-370. 2.Авторское свидетельство СССР 177692. кл, Q 06 F 15/34, 1964,

.2