Простые импликант

Cтраница 4

Как уже указывалось, первоначально в теории релейных устройств рассматривались главным образом вопросы синтеза структуры логического блока ( структурный синтез), в задачи которого входит в основном построение минимальной структуры по заданной таблице состояний релейного устройства. Методы, предложенные в первом периоде развития теории релейных устройств, не носили алгоритмического характера: при их применении получаемые результаты в смысле минимизации структур в основном зависели от опыта и интуиции проектировщика. Основным в них является получение так называемых минимальных членов ( простых импликантов), представляющих собой неизбыточные конъюнкции, из которых состоят все минимальные формы булевых функций, характеризующие минимальные структуры логических блоков. Из множества минимальных членов ( общая минимальная форма) выделяются неизбыточные подмножества ( частные минимальные формы), на основе которых строятся минимальные структуры. [46]

Всякой релейной структуре ( за исключением мостовых структур) взаимно однозначно соответствует логич. Алгебра логики), а именно: для контактных схем буквам выражения соответствуют контакты, а знакам операций - паралл. Именно в этом заключается большая роль ма-тематич. В них, как правило, входят: 1) отыскание всех импли-кантов простых заданной функции ц 2) построение ( или выделение) таких дизъюнкций простых имшшкантов, к-рые эквивалентны исходной ф-ции п содержат наименьшее ( по сравнению с др. такими дизъюнкциями) число логич. К таким методам относятся методы Квайна - Маккласки, Нельсона, Блэка - Порецкого, Гаврилова и др. Поскольку число шагов в этих алгоритмах чрезвычайно быстро растет с ростом числа перем. ЭВМ, были созданы практические методы упрощения ф-ций. К ним относятся карточные методы и методы, основанные на отыскании не всех простых импликантов заданной ф-ции, а лишь тех, из к-рых можно построить одну из тупиковых ( неизбыточных) форм. [47]

Всякой релейной структуре ( за исключением мостовых структур) взаимно однозначно соответствует логич. Алгебра логики), а именно: для контактных схем буквам выражения соответствуют контакты, а знакам операций - паралл. Именно в этом заключается большая роль ма-тематич. В них, как правило, входят: 1) отыскание всех импли-кантов простых заданной функции и 2) построение ( или выделение) таких дизъюнкции простых нмпликантов, к-рые эквивалентны исходной ф-ции и содержат наименьшее ( по сравнению с др. такими дизъюнкциями) число логич. К таким методам относятся методы Квайна - Маккласки, Нельсона, Блэка - Порецкого, Гаврилова и др. Поскольку число шагов в этих алгоритмах чрезвычайно быстро растет с ростом числа порем, в ф-цнн и уже при 8 - 10 перем. ЭВМ, были созданы практические методы упрощения ф-ций. К ним относятся карточные методы и методы, основанные на отыска-тш не всех простых импликантов заданной ф-цин, а лишь тех, из к-рых можно построить одну из тупиковых ( неизбыточных) форм. [48]

Комбинационная схема из примера 1 в § 3 - 6. [49]

Такие переключательные функции принято называть неполностью определенными. Задача реализации неполностью определенных функций возникает в тех случаях, когда по тем или иным причинам некоторые сочетания входных сигналов никогда не могут появиться на входах цифровой схемы. Например, в ЦВМ, работающей в десятичной системе счисления, для представления одной десятичной цифры используют четыре двоичных цифры. Но из четырех двоичных цифр можно составить 16 комбинаций, только 10 из которых используются. Остальные 6 комбинаций не используются, и, следовательно, при правильной работе ЦВМ никогда возникать не могут. Поэтому на тех наборах, на которых функция не определена, ее можно доопределять произвольно. Естественно при этом так доопределить функцию, чтобы соответствующая ей схема была наиболее простой, то есть так, чтобы МДНФ доопределенной функции содержала наименьшее число букв. Один из них основан на методе Квайна и состоит в следующем. Неполностью определенную функцию приравнивают 1 на всех тех наборах, на которых она не определена. Полученную таким путем функцию обозначим / t ( xn) и найдем все ее простые импликанты. Затем с помощью импликантной матрицы найдем наименьшее число наиболее коротких простых импликант, которые накрывают все конституенты функции, полученной из исходной путем приравнивания ее 0 на всех наборах, на которых исходная функция не определена. [50]

Страницы: 1 2 3 4