О.Б. Лупанов - Элементы математической кибернетики (1161667), страница 8
Текст из файла (страница 8)
Используем тот же подход, что был применен в случае формул и системы правил ∆. Введем определение. Пусть дана контактная схема S с переменными из {x1 , . . . , xn } и полюсами α1 , . . . , αs .Построим контактную схему S ′ следующим образом. Полюсы схемыS ′ есть полюсы схемы S. Для любых двух полюсов αi и αj схемы Sпредставим их проводимость fij в виде совершенной ДНФ по всем переменным x1 , .
. . , xn , и в схеме S ′ соединим полюсы αi и αj цепями, соответствующими всем конъюнкциям совершенной ДНФ. Полученнаясхема S ′ называтся канонической контактной схемой для схемы S.Понятно, что у эквивалентных контактных схем канонические схемысовпадают. В этом смысле осталось показать, что любую контактнуюсхему S можно преобразовать в каноническую с помощью системы правил γn (системы правил I – VI для цепей контактов).Заменим каждый контакт схемы S системой параллельно соединенных цепей по правилу IV. Полученная контактная схема будет содержать вершины трех типов: полюсы, бывшие внутренние вершины ивершины между контактами внутри цепей.
Будем уничтожать бывшиевнутренние вершины. Рассмотрим бывшую вершину β. Предположим,что из нее выходит t цепей Ii к вершинам δ1 , . . . , δt . Выберем одну изδj и применим правило V (см. рис. 33).rβIiIiIirδ1Ii rδ2rδ3···rδtРис. 33Таким же образом поступим с цепями других сортов произвольнойфиксированной вершины β. Используем правило 7◦ и добавим к β всенедостающие цепи в одном экземпляре.
Теперь у вершины β будут цепипо одной каждого сорта. Воспользовавшись правилом III, удалим внутреннюю вершину β, а также все ей подобные вершины. В результатев схеме соединятся цепями будут только полюсы. Однако, возможныциклы. Пусть, например, полюсы αi и αj соединены цепью I, проходящей, возможно, и через другие полюсы. Добавим еще одну прямуюцепь I, соединяющую полюсы αi и αj . Одинаковые цепи между некоторыми полюсами переведем в циклы по правилу V, а сами циклы44r❅ xx1❅2x3 ❅rr❅x❅x21❅rr❅❅❅rr❅❅❅rа)б)Рис. 34устраним в соответствии с правилом VI. В итоге схема примет видканонической.
Теорема доказана.Рассмотрим контактную схему S с проводимостью f (x1 , . . . , xn ).Пусть σ̃ — произвольный набор из En2 . Построим на основе S графG, соответствующий значению f (σ̃). Введем для графа G функцииMϕn (S, σ̃) = p + q + r (mod 2), ϕn (S) =ϕn (S, σ̃),σ̃где p — число вершин, q — число ребер, r — число гранейграфа G. Например, схеме S, изображенной на рис. 34, а, приσ̃ = (0, 1, 1) соответствует граф G (см.
рис. 34, б), и в этом случаеϕn (S, σ̃) = 4 + 3 + 1 (mod 2) = 0.Лемма 6. Правила 1◦ — 5◦ не изменяют значение функции ϕn (S).Доказательство. 1◦ . Пусть схема S ′′ получена из схемы S ′ путем удаления изолированной вершины. Соответствующие схемам графы обозначим через G′′ и G′ . Если (p, q, r) — параметры графа G′ , то параметрами графа G′′ станут (p − 1, q, r − 1). Их сумма по модулю 2, каквидно, останется прежней.2◦ . Рассмотрим теперь цепь схемы S ′ , соединяющую вершины αи β и состоящую, например, из контактов x1 и x2 .
В схеме S ′′ этиконтакты следуют в обратном порядке. Тогда при подстановке наборов (0, 0, σ3 , . . . , σn ) и (1, 1, σ3 , . . . , σn ) соответствующие графы будутидентичны. А при подстановке набора (0, 1, σ3 , . . . , σn ) (или, скажем,(1, 0, σ3 , . . . , σn )) графы хотя и могут измениться, но их параметры(p, q, r) сохранятся.3◦ . Допустим, что правило применяется по переменной x1 . При подстановке в схемы S ′ и S ′′ набора (0, σ2 , . . . , σn ) (или (1, σ2 , .
. . , σn )) соответствующие графы G′ и G′′ имеют параметры (p, q, r) и (p − 1, q − 1, r),как видно, одинаковой суммы.454◦ . Аналогично, подставив в схемы S ′ и S ′′ набор (0, σ2 , . . . , σn ), получим графы G′ и G′′ параметров (p, q, r) и (p + 2, q + 1, r + 1), а подставив набор (1, σ2 , . . . , σn ) — графы параметров (p, q, r) и (p + 2, q + 2, r).Сумма снова будет одинаковой.5◦ . В данном случае, подставив набор (1, σ2 , . .
. , σn ), получим графы, имеющие одни и те же параметры (p, q, r), а при подстановке набора (0, σ2 , . . . , σn ) графы будут и вовсе одинаковыми. Лемма доказана.Покажем, что подобное утверждение для правила 6◦n не имеет места.Если подставить в схемы S ′ и S ′′ набор (1, 1, .
. . , 1), соответствующиеграфы G′ и G′′ будут иметь параметры (p, q, r) и (p − (n − 1), q − n, r)неодинаковой суммы по модулю 2. Если это набор (1, . . . , 1, 0, 1, . . . , 1),графы будут иметь параметры (p, q, r) и (p − (n − 1), q − (n − 1), r) одинаковой суммы. Сумма также будет одинаковой и при подстановке набора (1, . .
. , 1, 0, 1, . . . , 1, 0, 1, . . . , 1), хотя при этом граф G′′ будет иметьдве компоненты связности (одна из которых, возможно, не содержитребер).Таким образом, можно сделать вывод, что ϕn (S ′ , σ̃) 6= ϕn (S ′′ , σ̃)только для набора σ̃ = (1, 1, . . . , 1), следовательноϕn (S ′ ) = ϕn (S ′′ ) + 1 (mod 2)для правила 6◦n . Вместе с тем, если добавить несущественную переменную xn+1 для функции ϕn+1 в правиле 6◦n , то на наборах (1, . .
. , 1, 1) и(1, . . . , 1, 0) произойдет удвоение значений, т. е. ϕn+1 (S ′ ) = ϕn+1 (S ′′ ).Теорема 9. Не существует полной конечной системы правил в случае произвольного числа переменных.Докажем методом от противного“. Допустим, что Γ — полная конеч”ная система преобразований такая, что каждое ее правило содержитпроизвольное конечное число переменных. Пусть число переменных Γесть N.
Рассмотрим правило 6◦N +1 . По предположению оно выводимоиз системы Γ. Но в силу полноты системы γN , правило 6◦N +1 выводимои из γN . Правила системы γN (и в том числе правило 6◦N ) не изменяютзначение функции ϕN +1 . Следовательно, каждое правило, выводимоеиз системы γN , должно сохранять значение функции ϕN +1 . Однако,это не так: выводимое из γN правило 6◦N +1 не сохраняет значение ϕN +1 .Теорема доказана.46Глава 5Контроль работы схем§ 5.1. Самокорректирующиеся контактныесхемыРассмотрим произвольный контакт xσi контактной схемы. Напомним, что разомкнуть этот контакт — значит удалить ребро с нагрузкой xσi , замкнуть контакт — отождествить концы того же ребра.
Можно построить такую схему, которая самокорректировалась бы относительно замыкания/размыкания контакта xσi . В самом деле, если заменить этот контакт на ромб“, изображенный на рис. 35, то замыка”ние/размыкание контакта xσi уже не повлияет на работу схемы. Аналогично, если в произвольной контактной схеме каждый контакт заменить на соответствующий ромб“, получим самокорректировку отно”сительно одного замыкания/размыкания.
Если теперь требуется защитить схему от a замыканий и b размыканий, то согласно той же логике,каждый контакт xσi придется заменять многомерным ромбом“ с a + 1”параллельно соединенными цепями длины b + 1.Рассмотрим процесс построения самокорректирующейся контактной схемы асимптотически наилучшим способом.
Вспомним, что ис❡α❆ xσi✁❆❆r✁r❆✁σ✁xσixi❆❆ ❡✁xσi ✁βРис. 3547b1 rb2 rrbt···❜✧❜✧❏❜❏✧αh❜✧❜ ❏ xh✧❜ ❏✧hh❜✧xαxαh❜❏r✧hdhxαh❡cРис. 36пользовалось табличное задание функции f (см. табл. 1) и затем разложение_f (x1 , . . . , xn ) =fij (x1 , . . . , xn )(i,j)для i–й горизонтальной и j–й вертикальной полос. Схема представляла собой следующее: характеристическая функция по переменным x1 , . . . , xr , разделительное контактное дерево по переменнымxr+1 , . . . , xn−k и, наконец, пучки контактов xn−k+1 , . .
. , xn . Причем,именно на пучки контактов пришлась главная часть асимптотики.В пучках для каждого номера h собрали в полюс–выход c все контактыxαh h , выходящие из некоторых полюсов b1 , . . . , bt .1. Случай одного замыкания. Вне пучков будем дублировать контакты последовательно. На асимптотике сложности всей схемы это никак не отразится. С каждым из пучков поступим так: вставим еще одинпромежуточный контакт xαh h перед полюсом c (см. рис. 36). Проводимость останется той же, зато схема станет устойчивой к замыканию одного контакта. Сложность схемы асимптотически не увеличится: всегодобавится1r = 2⌈ 2 log2 n⌉контактов на каждый полюс c, что есть o(2n /n).2.
Случай одного размыкания. Вне пучков дублируем контакты параллельно. В пучках заменим сходящиеся к полюсу c контакты xαh h нацикл (см. рис. 37). Такая схема устойчива к размыканию одного контакта. Аналогично, сложность схемы асимптотически не увеличится.Рассмотрим другой подход. Пусть неисправность (любого рода) вконтактной схеме появляется с вероятностью p = const. Требуется построить схему, которая работала бы правильно почти всегда. Возьмем,к примеру, простейшую схему, изображенную на рис.
35.48b1hxαh bxαhxαbhr❜ h 2 r hr t···✧❜✧❜✧❜✧❜✧ α❜✧hxh h❜✧xα❡hcРис. 371) Если xσi = 1, то неисправность — размыкание. Следовательно,корректно работать контакт будет с вероятностью 1 − p. Цепь замкнута, когда замкнуты оба контакта, поэтому цепь будет разомкнутой свероятностью 1 − (1 − p)2 . Вся схема окажется разомкнутой с вероятностью (1 − (1 − p)2 )2 . Итак, вероятность некорректной работы схемыпри xσi = 1 меньше 4p2 .2) Если xσi = 0, неисправность — замыкание.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
