Математическая логика. Шапорев С.Д, страница 12

Очевидно, что язык схем из функциоиальнык элементов в целом эквивалентен языку суперпозицин функций алгебры лопгкн. Однако при построении схем возниюют некоторые ограничения: 1. Не могут соединяться выкоды. 2. У схемы должен быть лишь один выход. 3. Нельзя соединять «акай-то вход элемента схемы с выходом, т. е. ие допускаются циклы. Рнс. 1.6 Совокуиггость элементов Л, Ут,...,/, называетса Пнкэом (Рис.

1.6В если выкол элемента /, соединен с каким-то входом элема~пи Гз, выход элемента Ут с «аким-то вхолом 1з и т.д., выход г»ч — с каким-то вхадоы /ы а выход ~~ с каким-то входом /,. В таком случае говорит, что в соединении элементов суигествует обрамная сеять. Работа схем из функциональных элементов моягет происходить двумя способами.

Первый отстоит в предположении, что элементы схемы срабатывают мгновенно. Другое предположение заключается в том, что для получения выходного сигнала каждого функционального элемента требуется некоторое время. Тогда на входы внутренних элементоь схемы сигналы иогут приходить не одновременно, т. к. им необходимо пройти разное число элементов, да и время, требующееся различным функциональным элементам для обработки сигналов, может быть различным. Однако можно предположить, что сигналы подаются ча входы схемы сколь дона ( Ллгеб логияи (алгебр в яазыввн й( тз угодно долго цо тех пор, пока на выходе не появится сигнал.

соатаагагвую. щцй тем сигналя>>. чта пода>отса на акад екемы Второе предположение бодсе соо>встщ вует реальной ситуации, однако оно требует введения иремени задерягки функционалыюго эломента. — прея>сни Г, которое проходит между пода юй входных сигналов и ппявланнем выходного. Кроме того, вводится понязис так>а Время рабаны функциоцаяьных элементов изменяется дискретно и принимает натуральныс значения (,2,....д,... Единица времени называется >впалом. Сасюяния входов и выходов элементов последу>отса лишь в момен> ы времени, кратныс такту. Обычно при рассмотрении схеч из функпнанальньш элементов вволят уира.

щщощис предпало>кения, например, все схемм рассматрнвмотсл как аднотаьтные, т. е, между аигналами на входе н резулюирующим сигналом на выходе происходит олин такт, сигналы также можно подавать ~срез одна такт. Скема из функционазьнь>х элементов реализует некоторую функшно алгебры логики / с задержкой (. сслн ее входы можно отождествить с аргументамн ( так, по при подаче в любой момент времени на вхолы схемы некоторого набора сигналов на вь>халс через г тактов возникает сигнал, соответствующий значению функции ( при значениях аргументов, отвечающих подан>ым сигнгшам Схема, Рсыи>>ующая какую-либо ф) икцию алгебры логики, называется лдоаияы>ай.

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

Оказывае>ся, во многих случаях можно непротиворечивым образам описать раба~у СФЭ с обратнь>ми связямн. Дальнейшее исследование агата вопроса приладит к поня щю каис ща>.о авюмата. Рассмотрим еще один способ реализации функций алгебры логики — рг >елла«оллююлчые с.хмы (РКС), широко испо>шзуемые в электро>щавычислитсльной технике Описание н конструирование заких схем в силу их громозлкосю> весьма затрулнительно.

Однако оказалось, что црн конструировании РКС можно использовать аппарат булевых функций Исхолное замечание сащоит в том, что если логической переменной х поатавить в соответствие проводник. па которому идет или нег ток в зависимости оттого, х = ! нли х = О, то паследоввтсльпому соелинснию проводников отвечает коныонкция переменных, а параллельному — дизыон>гция Часто проводники на схемах заменя>от обозначением специальных устРойств — переключателей, которые ма~уг быть механическим>т и элекгрон- Че ш 1.

Магемапмеслвл лапше ными. Многократно используя параллельно-последоватцчьиые соединения, мохгно строить сложные схемы. Очевидно, что при этом ьгожно реализовать лишь монотонные функции. Для реализации произвольных функций необходимо уметь реализовать отрицание. Это молгно сделать при помощи устройства, называемого реле с ргггмыкаюшци «олглакмом (рис. 1.7). Боян по обмотке «атушки А ток не идет(х= О), то пружина оттягивает контакт В вверх, и цепь замыкаетсв. В результате на «лемме С будет ток ( х = 1). Вели эке по обмотке А идет ток ( х = 1), то контакт В притягивается вниз и на выходе С нет тока (х = О ).

,— ай ° -е ° -Е:Л Рис. 1.8 Рис. 1,7 Для РКС также существует проблема залерэкки сигналов на элементах схемы. Мы не будем рассматривать эту проблему, а ограничимся только схемами, а «оторых соединжотся лишь контакты. Контакт или перекюачатель будем изображать отрезком или прямоугольником, концы контакта называть полюсами. Конструкция, изобршкенная на рис. 1.8, называется деухлолгосггихам. Двухпалюсник будем снабжать символом переменной х, если контакт замыкающий, и х, если рюмыкаюший.

Двухполюсиики соединяются полюсами. В результате схема будет представлять из себя граф Граф Г с lг полюсами, в иотором каждое ребро помечено буквой из алфавита Х = уц,х„...,х„,х„х„.,х„~, называсия /с-лотгюснсй ксвюакмнсд схемой, реализующей булевы функции переменных х,,х,...,х„, или (гс,п)- схемой. Контактная схема называется се«злое (сильно селзнои, нарпогеэгьооносгедоеоглктьггой), если таковым «вляетс» ее граф. Параилельнопоследовательная схема называете» л-схемой. Две схемы называются «замор((эггымн, если их графы июморфны и при этом соответствующие ребра и полюса помечены одинаково.

В графе выделяются две вершины: вход и выход. Часто вход изображает полюс в в«де светлого «ружка, остальные полюса изображаются темными кружками. Релейно-контактные схемы отличаются от схем из функциональных элементов теи, что в СФЭ каждмц имеющийся енгнам чожно было размножить без дополнительных устройств (выход элемента можно соединять с любым числом Глава! Л гйрвлелкв)алгеар еисяааив яй) гв входов), в зо время как лля размпоэкения снпмла в РКС сга нулгно падать нв обмотку катушки с пужщлм числом пололгитсльныт контактов.

Второе разшь чие закчючастся в гом, по в РКС днзыонкция реазизусюя путем пвраллслыюга сасдгзнсн~гя провали иков, в СФ ) для этого необходим спсшгвлыгый элеьгеиз Калуга же функцию алгебры лопп и реализует контактная схема! Этгг функция равна единице при тех знаыпию, аргументов, при которых в схеме сеть проводимость. и нулю, сеян провалнмаати нет Пусть а и Ь вЂ” двв полюса контактной схемы к, [гг,!э) — искоюрая цепь, соединяющая а н Ь н К! ! — коиыонкция букв, приписанных ребрам цепи [а,Ь). Функция у", [х ), определяемая формулой ),ь[э")= а А')„ь), П )9!) в которой дизъюпкция бсрешя по веси простым цепям схемы.

соединяющим полюса а и Ь, называетая г)г! югяелл)юсат агин чемлуполюсамн а н Ь схемы а. На самсьг деле для пшзучения функции проводимости досппачно брать дизъ|онкцию це по всем цепям а лишь по пекозорыч. Цепь Г, называстсл сгл)есглегллоя. если она ни через какую вершину графа не проходит два.клы. Оказывается, по дизыонкцнв конъюнкций, соотвегсгвующих сущещвеннмм цепям, равиосю~ьпа функции проводимости Действитель ю, пусть и сезс» неко~арак цепь, в оюрой некоторая вершина всзрс- чается давиды Отбросим все ко~пактьл которые встречаются между двумя прокоэкдениями через эту вершину. Ясно. по при этан мы вновь получим цепь, причем если все контакты исходной цепи были замкнуты, иэ б)луг юмкнуты в все контакты вновь полученной цепи 1аким образоч.

последовательна сокращая цепь, мо,к о получить существеннуго ц пь. в ксп эрой будет проволимостгь если была проволимость в неладной пепи. Посмотрим теперь, каь або~опт дело с обрапгой задачей построением цо функции реализующей сс схемы Продешеви функцию в вилс дПФ Каждой входящей в ДНФ элементарной конъюнкции з лар л...лл,' поставим в соответствие скому !рис ! 9), состоящую нз последовательна сослинешшп Это схема элементарной конъюнкции. На рнс. !.9 и ! !й вели пзн|я г,' обозначены через у, После щахгдесгвления мелгду собои с одной стороны входов всех этих схем, с другой с~арапы —. ьыходов, получим функцию, соответствующую заданной схеме Есшствснно, моэкпо реализовать функцию по схемам таклге исходя из КНФ Каждой элемегпарной дизъюнкции часы 1. Маюьг гнчесюя яогияа уп хч ч х," о.„о х," поставим в оютветсгвие схему, июбрагкснную на рнс.

1.1О. Затем последоватечьно соединим все эти схемы для всех элементарных дизыонкций, входящих в КНФ, так, чтобы вход последую~цедя схемы совпадал с аьподам предыдущей г, у и г. Рис. 1.10 Рис. 1.9 Схему, состоящую из одного контакта, называют элеыеятариой. Ясно, что любая х-скема может быть получена из элементарных за некоторое число шагов при помощи парзллельных и последовательных соединений. Каждому способу построения я-схемы из элементарных схем отвечает представление функции проводимости в виде формулы, содержащей только лизъюнкции, конъюнкции и отрицания. Если коитактнал схема является я -схемой, то ес можно разбить на нескочько схем, соединенных либо последовательно, либо параллельно. Обратное тоже верно, Если схема не допускает разбиения на две схемы, соединенные либо последовательно, либо параллельно, она не явявется г -схемой. Для примера рассмотрим схему "мостик" 1рис.

1.11), которая не является элементарной Если две схемы соединены последовательно, то у полученной общей схемы все поаюсы, кроме соелннжощего, либо не имеют общих контактов нн с входоьг, ни с выходом всей схемы, либо имеют общий контакт или толька с вхо. доы, юи только с выходом. Очевидно, что какой бы из внутренних попиков на рис.