ОК_Часть_2_2015_(320-328)_v03-09 (1132806), страница 7
Текст из файла (страница 7)
Если τ — конечная полная систематожCBΦдеств для ЭП формул из UБ , то τ , τ , τ— конечнаяполная система тождеств для ЭП СФЭ из UCБ. осн B C Следствие. Система тождеств τ , τ , τ— КПСТдля ЭП СФЭ из UC .§5. Преобразования на основе тождествx1•x2x3•x1•¬ •#& •{••¬•#∨ −→x2&•& •u•) &•→¬ −tB&•{∨&•∨•z1•x3•tM&•{#x145z1x2x3••&•{#• ¬ −−→−→tB&tΠK1,&•{&x1 x2••z1x3•&•}!⇒τCx1•z1∨•z1Рис. 5.4: пример моделирования ЭП формул с помощью ЭПСФЭ46Глава 2. Основные классы управляющих системРассмотрим далее вопросы структурного моделированияформул в различных базисах. Пусть помимо базиса Б =конечный полныйбазис= {ϕi }bi=1 у нас имеется другой 0Б0 = {ϕ0i }bi=1 , и пусть формула Φ0i x1 , .
. . , xki0из UΦ, гдеБ0ki0 > ki , реализует ФАЛ ϕi , i = 1, . . . , b. Заметим, что вслучае ki0 > ki БП xki +1 , . . . , xki0 являются фиктивными БПформулы Φ0i . ПоложимΦ0 = Φ01 , . . . , Φ0b ,Π0 = Π01 , . . . , Π0b ,где Π0i — тождество вида ϕi = Φ0i , i = 1, . . . , b, и формулы изΦ0 (тождества из Π0 ) будем называть формулами (соответственно тождествами) перехода от базиса Б к базису Б0 .0Для формулы F, F ∈ UΦБ , обозначим через Π (F)0формулу над базисом Б , которая получается из F заменой каждой ее подформулывида ϕi (F1 , . . . , Fki ) формулойΦ0i F1 , .
. . , Fki , xki +1 , . . . , xki0 , то есть является результатомподстановки формулы Fj вместо БП xj в формулу Φ0i длявсех j, j = 1, . . . , ki . Переход от формулы F к формуле Π0 (F)будем называть структурным моделированием формулы Fв базисе Б0 на основе формул перехода Φ0 или, иначе, наоснове тождеств перехода Π0 . Заметим, что этот переходявляется специальным ЭП видаF |⇒ Π0 (F)Π0для формул над базисом Б ∪ Б0 . Отсюда следует, в частности, что в результате указанного структурного моделирования обеих частей тождества t, являющихся формулами из0ΦUΦБ , получается тождество t для формул из UБ0 , которое0мы будем обозначать через Π (t). Множество формул вида0Π0 (F), где F ∈ F ⊆ UΦБ , будем обозначать через Π (F), а0множество тождеств вида Π (t), где t ∈ τ — тождество над0UΦБ , — через Π (τ ).§5.
Преобразования на основе тождеств47Рассмотрим теперь вопросы моделирования ЭП формул в базисе Б с помощью ЭП формул базиса Б0 . ПустьΦ0 = (Φ01 , . . . , Φ0b ) — система формул перехода от базиса Б кбазису Б0 , а Π0 = (Π01 , . . . , Π0b ) — система тождеств перехода,связанная с Φ0 . Заметим, что любое ЭП для формул из UΦБ,имеющее видbF |⇒ F,(5.1)τможет быть «промоделировано» с помощью ЭП для формулвидаиз UΦБ0b 0,F0 |⇒ F(5.2)τ0b 0 = Π0 (F)b и τ 0 = Π0 (τ ).
Действительно,где F0 = Π0 (F), Fпусть ЭП (5.1) является однократным ЭП на основе тождества t, t ∈ τ , которое имеет видt : A (x1 , . . . , xq ) = B (x1 , . . . , xq ) ,b получается в результате замены подфори пусть формула Fмулы A (F1 , . . .
, Fq ) формулы F формулой B (F1 , . . . , Fq ). Тогда тождество t0 = Π0 (t) имеет видt0 : A0 (x1 , . . . , x1 ) = B (x1 , . . . , xq ) ,b 0 может бытьгде A0 = Π0 (A) и B0 = Π0 (B), а формула Fполучена из формулыF0 в результате замены ее подформу000лы A F1 , . . . , Fq , где Fj0 = Π0 (Fj ) для всех j, j ∈ [1, q],формулой B0 F10 , . . . , Fq0 . Моделирование кратного ЭП вида (5.1) с помощью кратного ЭП вида (5.2) осуществляетсяпутем последовательного моделирования однократных ЭП,составляющих ЭП (5.1).Описанное выше моделирование позволяет выполнятьЭП для тех эквивалентных формул из UΦ, которые приБ0,тоестьявляются«моделями»надлежат множеству Π0 UΦБ48Глава 2.
Основные классы управляющих систем0формул из UΦБ , на основе системы тождеств Π (τ ), являющихся «моделями» тождеств из τ . Для того чтобы проводить ЭП для произвольных формул из UΦс использованиБ0ем системы тождеств Π0 (τ ), выберем какую-либо системуформул перехода Φ = (Φ1 , . . . , Φb0 ) от базиса Б0 к базисуБ и рассмотрим связанную с ней систему тождеств перехода Π = (Π1 , . . . , Πb0 ). Пусть Π̌ — система тождеств видаΠ̌ = Π0 (Π) для ЭП формул из UΦ, которая получается в реБ0зультате структурного моделирования правых частей тождеств из Π на основе системы тождеств Π0 .
Для произволь, положимной формулы F0 , F0 ∈ UΦБ0Π̌ F0 = Π0 (Π (F))и заметим, чтоF0 |⇒ F̌0 = Π̌ F0 ,F̌0 ∈ Π0 UΦБ .Π̌В силу сказанного выше, отсюда вытекает справедливостьследующего утверждения.Теорема 5.2 (теорема перехода). Пусть τ — КПСТ для0ЭП формул из UΦБ , а Π и Π — системы тождеств дляперехода от базиса Б к базису Б0 и от базиса Б0 к базису Бсоответственно.
Тогда система тождеств {Π0 (τ ) , Π0 (Π)}является КПСТ для ЭП формул из UΦБ.Следствие. Из системы тождеств τ осн для ЭП формулиз UΦ (см. §3) указанным в теореме способом можно получить КПСТ для ЭП формул в любом базисе Б.Аналогичным образом на основе теоремы 5.1 решаютсявопросы построения КПСТ для ЭП СФЭ в произвольномбазисе.§6. Контактные схемы и π-схемы, оценка их числа§649Контактные схемы и π-схемы, оценка их числа. Особенности функционирования многополюсных схемРассмотрим класс контактных схем, в которых реализацияФАЛ осуществляется не с помощью преобразования входных значений в выходные, как это происходит, например, всхемах из функциональных элементов (см.
§4), а в результате передачи значений по ребрам графа, проводимостьюкоторого «управляют» входные БП. Ребро или дуга графа спометкой xi (xi ) называется замыкающим (соответственноразмыкающим) контактом БП xi (см. рис. 6.1).xivssuvsa)xisuvsb)xσisu-c)Рис. 6.1: типы контактовxq ivqqq?a)xq iquvqq 6qqub)Рис. 6.2: физическая интерпретация контактовСчитается, что контакт вида xσi , σ ∈ {0, 1}, проводиттогда и только тогда, когда xi = σ, причем ориентированный контакт, то есть контакт, связанный с дугой, проводиттолько в соответствующем направлении.С точки зрения управления проводимостью неориентированный размыкающий (замыкающий) контакт БП xi50Глава 2. Основные классы управляющих системфункционирует как p-МОП (соответственно n-МОП) транзистор, на затвор которого поступает БП xi (см.
рис. 6.2aи 6.2b), а аналогичный ориентированный контакт — какМОП-транзистор соответствующего типа с диодом Шоттки [17, 23]. Кроме того, ориентированный контакт вида xσi ,идущий из вершины v в вершину u (см. рис. 6.1c), часторассматривают как команду условного перехода из v в u,который выполняется, если xi = σ.Сеть Σ с входами a01 , . . . , a0p и выходами a001 , .
. . , a00q , в которой все ребра (дуги) помечены переменными x1 , . . . , xn илиих отрицаниями x1 , . . . , xn , называется (p, q)-контактнойсхемой (КС) от БП x1 , . . . , xn и обозначается Σ == Σ (x1 , . . . , xn ) или Σ = Σ x1 , . . . , xn ; a01 , . . . , a0p ; a001 , . . . , a00q .При этом число контактов называется сложностью КС Σи обозначается через L (Σ).
На рис. 6.3a–c показаны некоторые конкретные КС от БП x1 , x2 , x3 с входом a1 и выходамиa2 , a3 .Пусть Σ — КС от БП X (n) и α = (α1 , . . . , αn ) — набор из B n . Определим сеть Σ|α как сеть, получающуюсяиз Σ в результате удаления всех ребер (дуг) с пометкамиxα1 1 , . . . , xαnn , то есть ребер, которые не проводят на наборе α, и снятия пометок с остальных ребер Σ.
Для вершинv и u КС Σ введем функцию проводимости от вершины vк вершине u как ФАЛ gv,u (x1 , . . . , xn ), которая равна 1 нанаборе α = (α1 , . . . , αn ) ∈ B n тогда и только тогда, когдав сети Σ|α существует (v − u)-цепь, то есть тогда и только тогда, когда в Σ имеется цепь из проводящих на набореα контактов вида xα1 1 , . . . , xαnn , идущая из v в u. Будем говорить также, что ФАЛ gv,u является функцией достижимости вершины u из вершины v, или, иначе, реализуетсямежду вершинами v и u. Из определения следует, что длянахождения ФАЛ gv,u (x1 , . .
. , xn ) достаточно просмотретьвсе наборы α, α ∈ B n , и для каждого из них выяснить наличие или отсутствие в Σ цепи, состоящей из проводящих§6. Контактные схемы и π-схемы, оценка их числаvs3sx1x1x1s v1x2 v2x2s v1v2 sa2a1x151a1x1x2v4sx3sa)C2C1sa2C3b)a1 svsx1x1sx2sx3s a3x1x2x3x1x2x3sx2sx3sa2c)Рис. 6.3: некоторые КС от БП x1 , x2 , x3на наборе α контактов, которая идет из v в u.
Так, просматривая все наборы значений БП x1 , x2 , можно убедиться втом, что ФАЛ проводимости gv1 ,v2 (x1 , x2 ) в КС Σ, показанной на рис. 6.3a, равна x1 ⊕ x2 , а ФАЛ проводимости gv3 ,v4равна 0.Будем считать, что в каждой вершине (1, m)-КСΣ(x1 , . . .
, xn ; a1 ; a2 , . . . , am+1 ) реализуется ФАЛ проводимости от входа a1 к этой вершине и что Σ реализует систему ФАЛ F = (f1 , . . . , fm ), где fj — ФАЛ проводимости от a1 к выходу с пометкой aj+1 , j ∈ [1, m].52Глава 2. Основные классы управляющих системПри этом, очевидно, в вершине a1 реализуется ФАЛ 1,которую в дальнейшем по умолчанию будем использовать в качестве пометки единственного входа (1, m)-КС.Так, КС, изображенные на рис. 6.3a, 6.3b и 6.3c, реализуют ФАЛ x1 ⊕ x2 , H (x1 , x2 , x3 ) и набор ФАЛ(x1 ⊕ x2 ⊕ x3 , x1 ⊕ x2 ⊕ x3 ⊕ 1) соответственно. На рис.
6.4aпоказана (1, 2n )-КС D (x1 , . . . , xn ; 1; a0 , . . . , a2n −1 ), котораяназывается (1, 2n )-контактным деревом порядка n от БПX (n). Легко видеть, что в выходной вершине ai , i =0, . . . 2n − 1, этого контактного дерева (КД) реализуется ЭКвида xσ1 1 · · · xσnn , где ν (σ1 , . . . , σn ) = (i − 1), и что ФАЛ проводимости между любыми его выходами равна 0. Таким образом, (1, 2n )-КД порядка n является дешифратором порядка n, то есть схемой, реализующей систему Qn из всех ЭКранга n от БП X (n).Схемы Σ0 и Σ00 считаются, как обычно, изоморфными, если изоморфны соответствующие им графы, и эквивалентными, если они реализуют равные системы ФАЛ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
