Теормин (все билеты, кроме 12-14) (Мадорский) (1133375), страница 6
Текст из файла (страница 6)
Переход от формулы F к формуле Π′ (F)будем называть структурным моделированием формулы Fв базисе Б′ на основе формул перехода Φ′ или, иначе, наоснове тождеств перехода Π′.Теорема 2.2 (теорема перехода). Пусть τ — КПСТ для′ЭП формул из UΦБ , а Π и Π — системы тождеств дляперехода от базиса Б к базису Б′ и от базиса Б′ к базису Бсоответственно. Тогда система тождеств {Π′ (τ ) , Π′ (Π)}является КПСТ для ЭП формул из UΦБ.Следствие.
Из системы тождеств τ осн для ЭП формулиз UΦ (см. §3) указанным в теореме способом можно получить КПСТ для ЭП формул в любом базисе Б.2526Эквивалентные преобразования контактныхсхем. Основные тождества, выводвспомогательных и обобщенных тождествВ соответствии с ?? эк-вивалентность КС Σ′ = Σ′ (x1, . .
. ,xn; a1, . . . , am) и Σ′′ = Σ′′ (x1, . . . , xn; a1, . . . , am), то естьсправедливость тождества t : Σ′ ∼ Σ′′ означает, что длялюбых i и j из отрезка [1, m] ФАЛ проводимости от ai к aj вКС Σ′ равна ФАЛ проводи-мости от ai к aj в КС Σ′′.Определим подстановку для КС как переименование (свозможным отождествлением и инвертированием) БП, атакже переименование (с возможным отождествлением иснятием) полюсов.Это означает подсхемы Σ′ КС Σ имеет ме-сто включениеV (Σ′) ⊂ V (Σ) и E(Σ′) ∈ E(Σ), а полюсами Σ′ являются всепринадлежащие ей полюса КС Σи все те ее вершины,которые инцидентны в Σ ребрам из E(Σ) \ E(Σ′),и, возможно, некоторые другие вершины.(1)(2)Лемма 3.1. Имеет место выводимость {t1 − t5 , t6 , t6 } |⇒{t7 − −t11 }.27Теорема 4.1. Для любых двух эквивалентных КС Σ′ и Σ′′от БП x1 , .
. . , xn существует ЭП вида Σ′ ⇒ Σ′′ .τnСледствие 1. Система τn является КПСТ для ЭП КС изUK от БП x1 , . . . , xn .Следствие 2. Система τ∞ является ПСТ для ЭП КС изUK .Лемма 4.2. Если Σ′ (x1 , . . . , xn )⇒{t1 −t5 }Σ′′ (x1 , . . . , xn ), тоΘ (Σ′ ) = Θ (Σ′′ ), а если Σ′ ⇒ Σ′′ , где k < n, то Θ (Σ′ )−Θ (Σ′′ )делится на 2n−k .τkТеорема 4.2.
В классе UK не существует конечной полнойсистемы тождеств.no(n)(n)(n)(n)Систему тождеств τ (n) = t1 , . . . , t11 , где t1 = t1 , t6 —(n)соответствующее основное тождество (см. рис. 3.1f), t2 —система, состоящая из тождеств, показанных на рис. 3.8a,где Ie — произвольная перестановка цепочки I, а остальныетождества приведены на рис. 3.8b—3.8i, будем называть системойn обобщенных тождествo порядка n. При этом система(1)(n)τn = t1 , .
. . , t5 , t6 , . . . , t6считается системой основныхтождеств порядка n, а система всех основных тождеств обоIIeзначается через τ∞ .(n)∼a) t :12•I 2nI1212I2b)(n)t3:1∼2n21•I1′xnc)(n)t4:xn•1∼21xnI2′xn•d)26I1:2I ′ n−12I(n)t52n22∼12II33Ie)f)g)(n)t7(n)t8(n)t9::I1I1•12I2xn′∼xnI:∼213•I′•(n)t10 :xn∼1I12∼12II3321i)Im13IIII:31I(n)t112•Ih)xnI′0∼m2III03IЛемма 3.2. При n>2 имеет место выводимость τn⇒τ(n).Докажем сначала полноту системы основных тождеств τ∞Полнота системы основных тождествиля ЭП КС. Для этого, как обычно, достаточн одоказать,отсутствие конечной полной системычто с помощью ЭП на основе системы τ∞ произвольную КСтождествв классе контактных схемKиз U можно привести к каноническому виду. Напомнимb 1 , . .
. , xn ; a1 , . . . , am ), или,(см. ??), что каноническая КС Σ(xиначе, каноническая КС порядка n, представляет собой объединение канонических (1, 1)-КС вида b ij (x1 , . . . , xn ; ai , aj ),Σ ФАЛ проводимопостроенных на основе совершенных ДНФсти от ai к aj для всех i и j таких, что 1 6 i < j 6 m.27(n)Любую цепь Ii (см.
§3), где i ∈ [1, 2n ], а также любую(n)цепь, которая получается из Ii перестановкой контактов,будем называть канонической цепью порядка n. Заметим,b (x1 , . . . , xn ; a1 , . . . , am ) является канонической КСчто КС Σпорядка n тогда и только тогда, когда она обладает следующими свойствами:b принадлежит некоторой канониче1. любой контакт Σb,ской цепи порядка n, являющейся подсхемой схемы Σпричем полюсами этой подсхемы служат только концевые вершины данной цепи;b является внутренней2. любая внутренняя вершина Σвершиной некоторой цепи из пункта 1;b отсутствуют «висячие циклы» (см. тождество3. в КС Σ(n)t6 ) и «параллельные» цепи, то есть канонические цепи порядка n из пункта 1, которые соединяют одни ите же полюса и реализуют равные ЭК;b нет существенных транзитных проводимостей,4.
в КС Σ(n)то есть наличие цепей вида Ii , соединяющих полюсaj с полюсом ak и полюс ak с полюсом at (см. рис. 4.1a),влечет наличие цепи такого же вида, соединяющей полюс aj с полюсом at (см. рис. 4.1b).Лемма 4.1. Для любой КС Σ, где Σ ∈ UK и Σ == Σ (x1 , . . . , xn ; a1 , . . . , am ), и любой эквивалентной Σ КСb (x1 , . . . , xn ; a1 , . . . , am ) канонического вида существуетΣb.ЭП Σ ⇒ ΣτnЗадача контроля схем и тесты для таблиц. Построение всех тупиковых28 тестов,оценки длины диагностического тестаПусть (Σ, И) — указанная выше модель ненадежной схемыΣ с возможными состояниями Σ = Σ1, Σ2, .
. . , Σs, в которых реализуются ФАЛ f= f1, f2, . . . , fs соответственно от БП X (n), определенные на множестве наборов A= = {α1, . . . , αp} ⊆ Bn. Рассмотрим матрицу M, M ∈ Bp,s, где M hi, ji = fj (αi ) ,считая, что i-й строке (j-му столбцу) этой таблицы соот-ветствует набор αi(соответственно функция fj и состоя-ние Σj ). Матрица, состоящая из различныхстолбцов (строк) называется отделимой по столбцам (соответственно стро-кам)матрицей.
Заметим, что каждому классу неотличимых состояний модели (Σ, И)соответствует группа одинаковых столбцов матрицы M и рассмотрим отделимуюпо столбцам матрицу Mc, состоящую из всех различных столбцов матри-цы M.При этом будем считать, что каждый столбец матри-цы Mc связан ссоответствующим классом неотличимости со-стояний модели (Σ, И), и будемназывать Mc таблицей кон-троля данной модели. Для простоты будем, какправило, предполагать, что все состояния модели (Σ, И) попарно от-личимы, тоесть, M = Mc. Это предположение, очевидно, не ограничивает общностирассуждений.В частности, если N состоит из всех пар указанного вида, то целью контроляявляется диагностика схемы, а если N = {(1, 2) , . .
. , (1, t)}, то — проверкаисправности схемы. Множество строк мат-рицы M с номерами из T, T ⊆[1, p], называется тестом для матрицы M относительно множества N,или, иначе, тестом для (M, N), если для любой пары (i, j) из N существует t, t ∈ T , такое, что M ht, ii 6= M ht, ji. Мощность теста называется такжеего длиной.Заметим, что множество, состоящее из всех строк табли-цы контроля, всегдаобразует тест. Тест, который перестает быть тестом при удалении любойсвоей строки, назы-вается тупиковым, а тест, который имеет минимальнуюмощность, — минимальным. В том случае, когда целью кон-троля являетсядиагностика схемы (проверка исправности схемы), тест называетсядиагностическим (соответственно проверяющим).Будем говорить, что множество наборов τ, τ ⊆ A, обра-зует тест для модели(Σ, И) относительно цели контро-ля N, или, иначе, тест для (Σ, И, N), еслисоответствую-щие наборам из τ строки матрицы M образуют тест для (M, N).
Всевведенные выше понятия, которые касаются те-стов для таблиц, без измененийпереносятся на случай те-стов для ненадежных схем.Рассмотрим ФАЛ F (y), для которой F (β) = 1 тогда и только тогда, когдасистема строк матрицы M с номерами из I (β) образует тест для (M, N), ибудем называть эту ФАЛ функцией теста для (M, N).Лемма 1.1. Функция теста f (y1, . . . , yp) для отделимой по столбцам матрицыM, M ∈ Bp,s, и цели контроля N может быть заданас помощью КНФ^_f (y1 , .
. . , yp ) =yt ,(1.1)(i,j)∈N16t6pM ht,ii6=M ht,jiСледствие. Каждая элементарная конъюнкция вида yt1 · · · ytrсокращенной ДНФ функции f (y1, . . . , yp), получающаяся из КНФ в результатераскрытия скобок и приведения подобных, соответствует тупиковому тесту,связанному с множеством T = {t1 , . . . , tr } и обратно.Алгоритм построения всех тупиковых тестов для матрицы M относительноцели контроля N:1. выписываем для функции теста КНФ вида (1.1);2. раскрывая в ней скобки и приводя подобные, получаем сокращеннуюДНФ функции теста;3. сопоставляем каждой элементарной конъюнкции этойсокращенной ДНФ тупиковый тест.Лемма 1.2. Длина любого тупикового диагностического теста для отделимойпо столбцам матрицы из множе-ства Bp,s заключена в пределах от dlog se до(s − 1).Замечание. Указанные в лемме границы достигаются: ниж-няя — на любойотделимой по столбцам матрице из Bp,s, где p = dlog se, а верхняя — на матрицеиз Bs−1,s, все столбцы которой различны и содержат не более одной единицы (обематрицы имеют единственный диагностический тест, состо-ящий из всех строк).Лемма 1.3.
Пусть ϕ (s) , t (s) и p (s) — целочисленные неотрицательныефункции натурального аргумента s, для которыхt (s) = d2 log se + ϕ (s) , p (s) > t (s) , ϕ (s) −−−→ ∞.s→∞Тогда у почти всех отделимых по столбцам матриц из Bp(s),s первые t (s) строкобразуют диагностический тест.Доказательство. Заметим, что все матрицы из Bp,s, где p = p (s), у которыхпервые t = t (s) строк образуют диагностический тест, отделимы по столбцам.Легко видеть также, что число таких матриц равно (p−t)s1(s − 1)tttps2 2 − 1 ··· 2 − s + 1 · 2=21 − t ··· 1 −,22tа их доля среди всех отделимых по столбцам матриц из Bp,s не меньше, чем 1(s − 1)s21 − t ··· 1 −>1−> 1 − 2−2ϕ(s) ,22t2tи, следовательно, стремится к 1 при s стремящемся к беско-нечности.Следствие.
Для любой неотрицательной и неограниченно возрастающейфункции ϕ (s) у почти всех отделимых по столбцам матриц из Bp,s длинаминимального диагности- ческого теста не больше, чем 2 log s + ϕ (s).29Самокорректирующиеся контактные схемыи методы их постороения. Асимптотическинаилучший метод синтеза контактных схем,корректирующих один обрыв (одно замыкание)Рассмотрим вопрос повышения надежности схем на примерет. н. самокорректирующихся КС. Будем считать, что контакты рассматриваемых КС могут выходить из строя, переходя в одно из двух возможных неисправных состояний:состояние обрыва, когда контакт не проводит, и состояниезамыкания, когда контакт проводит при любых значенияхуправляющей им БП.Будем говорить, что КС Σ является (p, q) - самокорректирующейся КС или, иначе, корректирует p обрывов и qзамыканий, где p > 0 и q > 0, если любая КС Σ′ , котораяможет быть получена из КС Σ в результате обрыва не болеечем p, и замыкания не более, чем q, контактов, эквивалентнаΣ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
