Lectionc2 (1132951), страница 7
Текст из файла (страница 7)
. •$$ :: $$ ::: ∼ 1 $$ ::: ki$$ :: :$ ϕi • ki 1 :• ϕi•$ :z1z2a)x*1 . . . xki•*•**** ** ** *ϕi •x1 . . . xki••∼b)x1•∼ ∅c)Рис. 5.2: тождества ветвления, снятия ФЭ и снятия входадеств и положим bτБB = tBEi i=1 , bCτБC = tCEi i=1 ∪ tвх .Очевидно, что с помощью этих тождеств можно избавитьсяот всех висячих вершин и всех внутренних ветвлений, имеющихся в СФЭ. Следовательно, для любой СФЭ Σ, Σ ∈ UCБ,существует ЭП вида Σ |⇒ F, где F — формула (система{τ C ,τ B }UΦБ.формул) изb — однократное ЭП для формул изПусть, далее, F 7→ FtUΦБ , где тождество t имеет видt : F0 (x1 , .
. . , xn ) = F00 (x1 , . . . , xn ) ,b получается из формулы F заменой подфора формула F0мулы F (F1 , . . . , Fn ) формулой F00 (F1 , . . . , Fn ). Сопоставим§5. Преобразования на основе тождеств43888888 8888 8888Fn 88Fn 88 88F1 88 88F1 88 88 88 88 88 88 88 @@ . . .88 @@ . . .~~~~ 88 @@@88 @@@→−~~~~t88 88@88 88@~~~~~~88 88F0 88 88F00 88 88 88 88 88 88 88 88 88 88 bFΣРис. 5.3: моделирование ЭП формул с помощью ЭП СФЭэтому ЭП «моделирующее» его однократное ЭП СФЭ виb (см.
рис. 5.3). Заметим, что в том случае, когдада F 7→ Σtформулы F0 и F00 являются бесповторными формулами, аb совпадаБП x1 , . . . , xn — их существенными БП, СФЭ Σ00ет с СФЭ F . В остальных случаях из подформулы видаF0 (F1 , . . . , Fn ) формулы F необходимо с помощью тождествτБB сформировать сначала подсхему F0 (F1 , . . .
, Fn ), а затемb могут появитьсяприменить тождество t. При этом в СФЭ Σвисячие вершины или внутренние «ветвления», и тогда дляb необходимо провести ЭП вида Σbb кFb |⇒ F.перехода от Σ{τ C ,τ B }b где F, Fb ∈ UΦ ,Следовательно, для любого ЭП вида F |⇒ F,Бτсуществует моделирующее его ЭП видаF|⇒bF.{τ ,τБB ,τБC }На рис. 5.4 показано ЭП СФЭ из UC , которое моделируетЭП (3.1) для формул из UΦ .Из описанного выше способа «моделирования» ЭП формул с помощью ЭП СФЭ, а также способа перехода от формул к СФЭ и обратно на основе ЭП с помощью тождествτБB , τБC вытекает справедливость следующего утверждения.44Глава 2.
Основные классы управляющих системx1•x2x1x3•••¬ •#& •{x2•) && •u•¬•#∨ −→•••#{→¬ −tB&∨••{&∨z1z1••tM&&x1x3•x2x3••&•{#• ¬ −−→−→tΠK1,&tB&•&•{x1 x2• •z1x3•&•}!⇒τC•x1z1∨z1Рис. 5.4: пример моделирования ЭП формул с помощью ЭПСФЭ§5. Преобразования на основе тождеств45Теорема 5.1. Если τ — конечная полная систематожCBΦ— конечнаядеств для ЭП формул из UБ , то τ , τ , τполная система тождеств для ЭП СФЭ из UCБ. осн B C — КПСТСледствие. Система тождеств τ , τ , τCдля ЭП СФЭ из U .Рассмотрим далее вопросы структурного моделированияформул в различных базисах.
Пусть помимо базиса Б == {ϕ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 заменой каждой00ее подформулы вида ϕi (F1 , . . . , Fki ) формулой Φi F1 , . . . , Fki , xki +1 , . . . , xki ,то есть является результатом подстановки формулы Fj вместо БП xj в формулу Φ0i для всех j, j = 1, . . . , ki .
Переход отформулы F к формуле Π0 (F) будем называть структурныммоделированием формулы F в базисе Б0 на основе формулперехода Φ0 или, иначе, на основе тождеств перехода Π0 .Заметим, что этот переход является специальным ЭП видаF |⇒ Π0 (F)Π0для формул над базисом Б ∪ Б0 . Отсюда следует, в частности, что в результате указанного структурного моделирования обеих частей тождества t, являющихся формулами из46Глава 2. Основные классы управляющих систем0ΦUΦБ , получается тождество t для формул из UБ0 , котороемы будем обозначать через Π0 (t). Множество формул вида0Π0 (F), где F ∈ F ⊆ UΦБ , будем обозначать через Π (F), а0множество тождеств вида Π (t), где t ∈ τ — тождество над0UΦБ , — через Π (τ ).Рассмотрим теперь вопросы моделирования ЭП формулв базисе Б с помощью ЭП формул базиса Б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. Преобразования на основе тождеств47путем последовательного моделирования однократных ЭП,составляющих ЭП (5.1).Описанное выше моделирование позволяет выполнять ЭПдля тех эквивалентныхформул из UΦ, которые принадлеБ00Φжат множеству Π UБ , то есть являются «моделями» фор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Φ (см. §4) указанным в теореме способом можно получить КПСТ для ЭП формул в любом базисе Б.48Глава 2. Основные классы управляющих системАналогичным образом на основе теоремы 5.1 решаютсявопросы построения КПСТ для ЭП СФЭ в произвольномбазисе.§6Контактные схемы и π-схемы, оценка их числаРассмотрим класс контактных схем, в которых реализацияФАЛ осуществляется не с помощью преобразования входных значений в выходные, как это происходит, например, всхемах из функциональных элементов (см.
§7), а в результате передачи значений по ребрам графа, проводимостьюкоторого «управляют» входные БП. Ребро или дуга графа спометкой xi (xi ) называется замыкающим (соответственноразмыкающим) контактом БП xi (см. рис. 6.1).xivssuvsa)xisuvsb)xσisu-c)Рис. 6.1: типы контактовxq ivqqxq iqquvqq 6qqu?a)b)Рис. 6.2: физическая интерпретация контактовСчитается, что контакт вида xσi , σ ∈ {0, 1}, проводиттогда и только тогда, когда xi = σ, причем ориентирован-§6.
Контактные схемы и π-схемы, оценка их числа49ный контакт, то есть контакт, связанный с дугой, проводиттолько в соответствующем направлении.С точки зрения управления проводимостью неориентированный размыкающий (замыкающий) контакт БП xi функционирует как 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, или, иначе, реализуется50Глава 2. Основные классы управляющих системvs3sx1s v1v2 sa2a1x1x1x1s v1x2 v2x2a1x1x2v4sx3sa)C2C1sa2C3b)a1 svsx1x1sx2sx3s a3x1x2x3x1x2x3sx2sx3sa2c)Рис.
6.3: некоторые КС от БП x1 , x2 , x3между вершинами v и u. Из определения следует, что длянахождения ФАЛ gv,u (x1 , . . . , xn ) достаточно просмотретьвсе наборы α, α ∈ B n , и для каждого из них выяснить наличие или отсутствие в Σ цепи, состоящей из проводящихна наборе α контактов, которая идет из v в u. Так, просматривая все наборы значений БП x1 , x2 , можно убедиться втом, что ФАЛ проводимости gv1 ,v2 (x1 , x2 ) в КС Σ, показанной на рис. 6.3a, равна x1 ⊕ x2 , а ФАЛ проводимости gv3 ,v4равна 0.Будем считать, что в каждой вершине (1, m)-КС Σ(x1 , . . . , xn ; a1 ; a2 , . .
. , am+1 )§6. Контактные схемы и π-схемы, оценка их числа51реализуется ФАЛ проводимости от входа a1 к этой вершине и что Σ реализует систему ФАЛ F = (f1 , . . . , fm ), гдеfj — ФАЛ проводимости от a1 к выходу с пометкой aj+1 ,j ∈ [1, m]. При этом, очевидно, в вершине a1 реализуетсяФАЛ 1, которую в дальнейшем по умолчанию будем использовать в качестве пометки единственного входа (1, m)-КС.Так, КС, изображенные на рис. 6.3a, 6.3b и 6.3c, реализуютФАЛ x1 ⊕x2 , H (x1 , x2 , x3 ) и набор ФАЛ (x1 ⊕ x2 ⊕ x3 , x1 ⊕ x2 ⊕ x3 ⊕ 1)соответственно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
