OK_metodichka_part_2 (1132797), страница 7
Текст из файла (страница 7)
Пусть помимо базиса Б == {ϕ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, являющихся формулами из§5. Преобразования на основе тождеств450Φ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) осуществляется46Глава 2. Основные классы управляющих системпутем последовательного моделирования однократных ЭП,составляющих ЭП (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) указанным в теореме способом можно получить КПСТ для ЭП формул в любом базисе Б.§6. Контактные схемы и π-схемы, оценка их числа47Аналогичным образом на основе теоремы 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 = σ, причем ориентирован-48Глава 2.
Основные классы управляющих системный контакт, то есть контакт, связанный с дугой, проводиттолько в соответствующем направлении.С точки зрения управления проводимостью неориентированный размыкающий (замыкающий) контакт БП xi функционирует как p-МОП (соответственно n-МОП) транзистор,на затвор которого поступает БП xi (см. рис. 6.2a и 6.2b), ааналогичный ориентированный контакт — как МОП-транзисторсоответствующего типа с диодом Шоттки [17, 23].
Кроме того, ориентированный контакт вида xσi , идущий из вершиныv в вершину u (см. рис. 6.1c), часто рассматривают как команду условного перехода из v в u, который выполняется,если xi = σ (см. также §10).Сеть Σ с входами 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, или, иначе, реализуется§6. Контактные схемы и π-схемы, оценка их числаvs3sx1x1x1s v1x2 v2x2s v1v2 sa2a1x149a1x1x2v4sx3sa)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 )50Глава 2. Основные классы управляющих системреализуется ФАЛ проводимости от входа 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)соответственно. На рис.
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 считаются, как обычно, изоморфными, если изоморфны соответствующие им графы, и эквивалентными, если они реализуют равные системы ФАЛ. Изоморфные КС, очевидно, эквивалентны.Для множества C, состоящего из контактов вида xσi11 , .
. . , xσirrв КС Σ, определим его функцию проводимости K (C) ифункцию отделимости J (C) как ФАЛ вида xσi11 · · · xσirr иxσi11 ∨. . .∨xσirr соответственно. При этом множество C называется проводящим (отделимым), если K (C) 6= 0 (J (C) 6= 1),и нулевым (соответственно единичным) в противном случае. Заметим, что в результате приведения подобных (см.§4) отличная от 0 ФАЛ K (C) и отличная от 1 ФАЛ J (C)могут быть преобразованы в ЭК и ЭД соответственно. Очевидно, также, чтоK C 0 > K (C)и J C 0 6 J (C) ,§6. Контактные схемы и π-схемы, оценка их числа51ss• a0sssKsK•sKKKxn KK•axnss•ssssOsx1 sss• OOOOsx2 OO•ss1 •sKKKKK xo2oooo•x1 KKo•KoKKKKx2 KKx2•1...ai•/ xσ1 .
. . xσnn1ss• a2n −2sssKsK•sKKKxn KK a n•xn2 −1a)a0 •KKK xnKKKKs•ssssa1 •ss xn•KKK xKK2KKo•KKK x1ooKKoox2oKKo•s• aOs• OO x2sOOO ssOs•ss x1ssssx2ss•a2n −2 •KKK xnKKKKs•ssssxnsa2n −1 •sb)Рис. 6.4: (1, 2n )- и (2n , 1)- контактные деревья порядка n52Глава 2. Основные классы управляющих системесли C 0 ⊆ C.Из введенных определений (см. также §1) следует, чтоФАЛ g, реализуемая КС Σ (x1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
