2 (1132838), страница 7
Текст из файла (страница 7)
§2), асоответствующую ей формулу-граф, т. е. квазидерево (см. §2),будем обозначать через F. При этом тождеству t : F0 = F00 ,где F0 и F00 —формулы из UΦБ , будет соответствовать тождество t : F0 ∼ F00 , где F0 и F00 — соответствующие F0 и F00схемы из UCБ , являющееся «схемным» аналогом тождества t.Множество СФЭ вида F, где F ∈ F ⊆ UΦБ , будем обозначать1Под дублированием (снятием) выхода zi СФЭ понимается нанесение на вершину с пометкой zi еще одной выходной БП (соответственноудаление с неё пометки zi )42Введениеx1x2•1x1••2&x2••¬ •∼1¬ z•1x1x2••• ¬• ¬&2•z1 ∨•yz1a)•{∨x1∼ z•1b)ΠKРис.
5.1: тождества tM& и t1,&через F, а систему тождеств вида t, где t ∈ τ , а τ — систематождеств для UΦБ , — через τ . Так, на рис. 5.1a и 5.1b привеΠKдены тождества tM& и t1,& , являющиеся схемными аналогамиПKвведенных выше формульных тождеств tM& и t1,& .На рис. 5.2a и 5.2b показаны тождество ветвления tBEiи тождество снятия tCEi для функционального элемента Ei , i ∈[1, b], соответственно, а на рис.
5.2c — тождество снятиявхода tCвх . Заметим, что применение тождества снятия равносильно выполнению операции удаления висячей вершинысоответствующего типа (см. §7). Заметим также, что тожCCдества tBEi , tEi , tвх не являются аналогами формульных тождеств и положим bτБB = tBEi i=1 , bCτБC = tCEi i=1 ∪ tвх .Очевидно, что с помощью этих тождеств можно избавитьсяот всех висячих вершин и всех внутренних ветвлений, имеющихся в СФЭ.
Следовательно, для любой СФЭ Σ, Σ ∈ UCБ,существует ЭП вида Σ |⇒ F, где F — формула (система{τ C ,τ B }формул) изUΦБ.Введение43x1 . . . xki••ki1ϕi •x1•∼...1ϕi • kiz1z1 , z2xki•ki1 • ϕiz2a)x1 . . . xki••∼x1 . . . xk i••x1•∼ ∅ϕi •b)c)Рис. 5.2: тождества ветвления, снятия ФЭ и снятия входаb — однократное ЭП для формул изПусть, далее, F 7→ FtUΦБ , где тождество t имеет видt : F0 (x1 , . . . , xn ) = F00 (x1 , .
. . , xn ) ,b получается из формулы F заменой подфора формула Fмулы F0 (F1 , . . . , Fn ) формулой F00 (F1 , . . . , Fn ). Сопоставимэтому ЭП «моделирующее» его однократное ЭП СФЭ виb (см. рис. 5.3). Заметим, что в том случае, когдада F 7→ Σtформулы F0 и F00 являются бесповторными формулами, аb совпадаБП x1 , . . . , xn — их существенными БП, СФЭ Σ00ет с СФЭ F . В остальных случаях из подформулы видаF0 (F1 , . . . , Fn ) формулы F необходимо с помощью тождествτБB сформировать сначала подсхему F0 (F1 , . . . , Fn ), а затемb могут появитьсяприменить тождество t. При этом в СФЭ Σ44ВведениеF1FnF1...F0→−~Fn...tF00F~bΣРис. 5.3: моделирование ЭП формул с помощью ЭП СФЭвисячие вершины или внутренние «ветвления», и тогда дляb необходимо провести ЭП вида Σbb кFb |⇒ F.перехода от Σ{τ C ,τ B }b где F, Fb ∈ UΦ ,Следовательно, для любого ЭП вида F |⇒ F,Бτсуществует моделирующее его ЭП видаFbF.|⇒{B ,τ Cτ ,τББ}На рис.
5.4 показано ЭП СФЭ из UC , которое моделируетЭП (3.1) для формул из UΦ :x1 (x2 x3 ∨ x2 ∨ x3 ) 7→ x1 (x2 x3 ∨ x2 · x3 ) 7→ x1 .tM&tΠK1,&Из описанного выше способа «моделирования» ЭП формул с помощью ЭП СФЭ, а также способа перехода от формул к СФЭ и обратно на основе ЭП с помощью тождествτБB , τБC вытекает справедливость следующего утверждения.Теорема 5.1. Если τ — конечная полная систематожCBΦдеств для ЭП формул из UБ , то τ , τ , τ— конечнаяполная система тождеств для ЭП СФЭ из UCБ. осн B C Следствие.
Система тождеств τ , τ , τ— КПСТдля ЭП СФЭ из UC .Введение45x1•x2x3•x1•¬ •#& •{••¬•#∨ −→x2&& •u•) &•→¬ −tB&•{∨&•∨•z1••tM&•{#x1x3•z1x2x3••&•{#• ¬ −−→−→tB&tΠK1,&•{&x1 x2••z1x3•&•}!⇒τCx1•z1∨•z1Рис. 5.4: пример моделирования ЭП формул с помощью ЭПСФЭ46ВведениеРассмотрим далее вопросы структурного моделированияформул в различных базисах.
Пусть помимо базиса Б =конечный полныйбазис= {ϕ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ΦБ , — через Π (τ ).Введение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Введение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 решаютсявопросы построения КПСТ для ЭП СФЭ в произвольномбазисе.Введение§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Введениефункционирует как p-МОП (соответственно n-МОП) транзистор, на затвор которого поступает БП xi (см. рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
