Схемы заданной длины и ширины

Было показано, что степени горизонтальности кривой в окрестностях точек связаны с длиной и шириной схемы. Ясно, что в практически важном случае интересующие нас значения будут находиться в этих окрестностях, т. е. реле будут с самого

начала достаточно надежными. В этом параграфе будут приведены некоторые результаты о связи степени горизонтальности с числом элементов в схеме.

Теорема 3. Если схема имеет длину и ширину то она содержит по крайней мере контактов. Другими словами, если функция ведет себя как вблизи и если ведет себя как вблизи то соответствующая схема содержит по крайней мере контактов.

Доказательство. Сопоставим каждому контакту в целое число следующим образом.

Рис. 13. Параллельно-последовательная схема длины и ширины

Контактам, непосредственно соединенным с левым полюсом схемы приписывается порядковый номер 1, контактам, непосредственно соединенным с контактами, обозначенными 1, приписывается 2 и т. д. Вообще контакту приписывается номер если существует цепь, идущая от него к левому полюсу и содержащая других контактов, но не имеется такой цепи, содержащей меньшее число контактов.

Множество контактов; которым приписано число для любого фиксированного от 1 до образует размыкающее множество в схеме. В самом деле, каждая цепь через схему начинается у левого полюса контактом, обозначенным 1, и кончается у правого полюса контактом, обозначенным I или большим числом (если бы какие-либо из контактов, примыкающие к правому полюсу, были обозначены числами, меньшими то длина схемы была бы меньше Вдоль каждой цепи при переходе от одного контакта к следующему номера изменяются на 0 или на Поэтому каждая цепь при переходе от контактов, занумерованных 1, к контактам, занумерованным числами, не превосходящими I, должна проходить через каждое промежуточное значение. Таким образом, если все контакты,

обозначенные будут исключены из то все цепи будут разорваны, и, следовательно, эти контакты образуют размыкающее множество.

Поскольку схема имеет ширину то каждое размыкающее множество будет содержать по крайней мере контактов. Таким образом, по крайней мере контактов будут обозначены 1, по крайней мере контактов будут обозначены и по крайней мере контактов будут обозначены I. Следовательно, схема будет содержать по крайней мере контактов.

Другая формулировка теоремы 3 вытекает из замечаний, относящихся к уравнениям (1) и (2).

Рис. 14. Другой вариант параллельнопоследовательной схемы длины и ширины

Можно самыми разнообразными способами получить «размеры» точно с контактами. Можно построить, например, последовательную схему с контактами и соединить параллельно таких схем (рис. 13). Можно поступить двойственным образом: контактов соединить параллельно, а таких схем — последовательно (рис. 14).

Теорема 4. Полная характеристика минимальных схем с размерами и состоит в следующем. Пусть и полюсы, -множество, состоящее только из и — множество, состоящее только из Кроме имеются еще подмножества узлов такие, что, во-первых, ровно контактов соединяют узлы из с узлами из и, во-вторых, если узел из имеет элементов, соединяющих его с узлами из то он имеет элементов, соединяющих его с узлами из

Это значит, что любую минимальную схему с размерами можно получить из схемы рис. 13 посредством соответствующих

соединений (отождествлений) между узлами на одной и той же вертикальной линии. Если, например, все узлы на каждой вертикальной линии соединяются вместе, то в результате получится схема рис. 14. Другая возможная схема показана на рис. 15.

Чтобы показать, что всякая минимальная -схема (т. е. схема с размерами и имеет вид, описанный в формулировке теоремы 4, заметим сначала, что в предыдущем рассуждении каждое из занумерованных размыкающих множеств должно содержать ровно элементов и эти элементы должны располагаться между элементами, имеющими меньшие номера, и элементами, имеющими большие номера.

Рис. 15. Гамакообразная схема длины и ширины

Так, узлы между элементами с номерами и будут относиться к подмножеству Предположим теперь, что какой-либо узел из имеет элементов, ведущих к узлам из элементов, ведущих к узлам из Элементы с номерами образуют размыкающее множество из элементов; легко видеть, что если эти элементов рассматриваемого размыкающего множества, исходящие из данного узла, заменить элементами, идущими к узлам то получится размыкающее множество, имеющее меньше элементов, что невозможно. Следовательно, всякая минимальная схема с размерами и есть схема рассматриваемого вида.

Чтобы доказать обратное, т. е. что всякая схема указанного вида имеет размеры и заметим, во-первых, что при переходе от одного полюса к другому нужно пройти через узлы, принадлежащие Поэтому всякая цепь будет иметь длину по меньшей мере и схема будет иметь длину Рассмотрим произвольное размыкающее множество с. Покажем, что с содержит по меньшей мере контактов. Рассмотрим контакты в с, имеющие минимальные номера. Предположим, что один из них соединяет узел А из с узлом В из Тогда или все элементы, идущие от В к узлам из принадлежат этому размыкающему множеству, или же какой-то из

них не принадлежит размыкающему множеству, и его можно устранить, получив при этом еще меньшее размыкающее множество. В первом случае эту группу элементов можно заменить таким же числом элементов, идущих от узла В к элементам из с сохранением свойства быть размыкающим множеством. Поступая таким образом, будем постепенно передвигать размыкающее множество по направлению к правому полюсу, причем число элементов в множестве будет или уменьшаться, или оставаться неизменным.

Рис. 16. (см. скан) Гамакообразные схемы различной длины и ширины.

Когда все элементы размыкающего множества окажутся рядом с правым полюсом, в этом множестве будет точно контактов. Следовательно, в первоначальном размыкающем множестве их было не меньше, что и требовалось доказать.

Интересный тип минимальных -схем получается при применении чередующихся соединений в схеме рис. 13, имеющих вид кирпичной кладки (рис. 15, а). «Стянув в точки» вертикальные соединения, получим схему, изображенную на рис. 15, б; схему такого типа будем называть гамакообраэной. На рис. 16 показаны простые случаи гамакообразных схем. Ясно, что если оба числа и четные, то для них возможны две гамакообразные схемы. Если

же или или или оба эти числа нечетные, то возможна только одна схема. Далее, двойственной схемой к гамакообразной схеме с длиной и шириной будет гамакообразная схема с длиной и шириной Такие гамакообразные схемы являются в некотором смысле промежуточными между крайними минимальными -схемами, изображенными на рис. 13 и 14, и имеют половину соединений, необходимых для перехода от схемы рис. 13 к схеме рис. 14. В случае когда I и равны и нечетны, гамакообразная (единственная) схема будет самодвойственной.

Основная задача

Теперь приступим к решению нашей основной задачи — построению сколь угодно надежных схем из ненадежных реле. Покажем, что может быть построена схема с функцией график которой изображен на рис. будет возрастать от значения, меньшего при до значения, большего при для любых Оценим также число контактов в такой схеме в зависимости от значений а и с.

Задача в общем случае разбивается на три этапа. Назовем их начальным, средним и последним.

Начальный этап состоит в нахождении схемы, которая, образно говоря, «передвигает» а и с так, чтобы они оказались по разные стороны от точки т. е. для которой -Эту схему можно себе представить как единичный контакт с более хорошими значениями а и с (по крайней мере более приемлемыми для применяемого нами метода).

Средний этап состоит в построении схемы, которая раздвигает значения а и с из окрестности точки 72, так чтобы а оказалось близким к — к 3/4.

Последний этап заключается в построении схемы, осуществляющей передвижение этих точек из окрестностей 74 и 3/4 соответственно к 0 и 1.

Решение задачи в общем случае основано на замещении копией первой (полученной на начальном этапе) схемы каждого контакта второй (полученной на среднем этапе) схемы. Копией получившейся схемы заменяется каждый контакт схемы, полученной на последнем этапе. Тогда общее число контактов равно произведению чисел контактов в указанных трех вспомогательных схемах.

Разделение задачи на три части сделано главным образом для удобства математического описания. По-видимому, наиболее эффективный метод синтеза часто не будет состоять из такой итерации трех схем.

Во многих случаях, конечно, первая часть или даже две первых части решения не являются необходимыми, если а и с уже

разделены точкой 1/2 и достаточно удалены друг от друга. Это всегда имеет место для реле, используемых на практике. Общий случай представляет главным образом теоретический интерес. Для практического случая, когда а и с уже близки к 0 и 1, будет показано, что схемы, предлагаемые на последнем этапе, достаточно экономны в смысле числа контактов. Они содержат не намного больше контактов, чем требует получаемая здесь нижняя оценка для всех схем.

Начальный этап

В первую очередь покажем, что можно построить схему, график функции которой пересекает прямую в произвольном интервале и имеет средний наклон в этом интервале не менее 1/2. Затем оценим число контактов в такой схеме. Точнее, докажем следующее.

Теорема 5. Пусть а и с таковы, что пусть далее Тогда существует схема имеющая не более чем контактов и такая, что .

Лемма 1. Существуют две последовательности схем такие, что для каждого i

1) имеет не более контактов;

2) М; имеет не более контактов;

5) либо может быть получена соединением накоротко некоторых двух узлов схемы либо может быть получена размыканием некоторого контакта схемы

Схемы этой леммы получаются из «лестничной» схемы, общий вид которой изображен на рис. 17 (однако с различными числами горизонтальных и вертикальных элементов в соответствии

Рис. 17. Лестничная схема, использованная для доказательства теоремы 5.

значением , возможно, начинающейся не горизонтальной, а вертикальной группой). Схемы М, и образуются при отрезании части схемы позади контакта (как показано для и соответственно замыкания или размыкания образовавшихся концов. Можно считать, что график функции бесконечной схемы пересекает точно при Схемы и являются конечными аппроксимациями, которым соответствуют точки пересечения, лежащие левее и правее

Доказательство. Пусть — тождественно замкнутая схема и — тождественно разомкнутая схема. Эти схемы удовлетворяют условиям леммы для случая так как Предположим теперь, что условия леммы выполнены для Если получается посредством соединения накоротко двух узлов схемы то пусть М — схема, получающаяся из введением одного контакта между этими узлами. Если получается путем размыкания одного из контактов в то пусть М—схема, получающаяся в результате введения нового контакта последовательно с этим контактом. Тогда М имеет не более контактов; если замкнуть (разомкнуть) добавленный контакт в схеме М, то получится Тогда на основании равенства (3)

и, следовательно Если полагаем Тогда

Если же то полагаем Тогда, точно так же Лемма доказана.

Лемма для всех таких, что

В самом деле, так как , то следовательно,

Для доказательства теоремы 5 положим тогда , следовательно,

Пусть — та из схем которая удовлетворяет условию (поскольку одна из них должна удовлетворять этому условию).

Тогда без ограничения общности достаточно показать, что

Допустим противное, т. е. допустим, что . Тогда, поскольку функция монотонна, то для всех заключенных между бис. Следовательно, по лемме 2 в этом интервале Поэтому

что противоречит предположению.

Средний этап

Второй этап решения нашей задачи состоит в нахождении схемы которая передвигает вероятности, немного меньшие и немного большие к значениям, меньшим и большим 3/4 соответственно. Иными словами, найдем схемы, для которых

и подсчитаем число используемых в них контактов в зависимости от значения .

Схемы, удовлетворяющие нашимусловиям, могут быть получены итерацией некоторой самодвойственной схемы с нею же самой достаточное число раз. Например, можно использовать гамакообразную схему три-на-три рис. 16. Нетрудно показать, что график функции этой схемы, как показано на рис. 18, расположен ниже прямой с наклоном 3/2, проходящей через точку в интервале и выше этой прямой в интервале -Отсюда видно, что итерация этой гамакообразной схемы с собой

достаточное число раз, обеспечивающая перемещение точки к точке требует меньшего числа подстановок, чем число шагов в ступенчатом процессе при соответствующем движении вдоль этой прямой линии. Далее, если перемещаться вдоль прямой от точки то очевидно, что после итерации точка дойдет до значения

Рис. 18. Функция, связанная с гамакообразной схемой три-на-три.

Если желательно дойти до «по прямой», то итераций будет достаточно в том случае, когда есть минимальное число, удовлетворяющее условию

Этого числа итераций будет заведомо достаточно для гамакообразной схемы, так как ее действие в ступенчатом процессе сильнее, чем в случае прямой линии. Число контактов в -кратной итерации этой гамакообразной схемы равно

Те же самые рассуждения применимы, конечно, для передвижения и это осуществляется той же самой схемой, поскольку она является самодвойственной.

Так как наше на начальном шаге определялось как то схема второго этапа требует самое большее 9 контактов. Общая схема (после первого и второго этапов) требует не более чем контактов.

Последний этап

Наша третья схема последнего этапа должна передвигать вероятности и 3/4, или лучшие, к точкам, близким к 0 и 1 соответственно. Этот тип схем также основан на итерации самодвойственной схемы, в частности гамакообразной схемы три-на-три или пятиэлементного мостика. Сначала будет удобно произвести подсчет контактов, с помощью которых возможно приблизиться к 0 и 1 в рассматриваемом случае.

В некоторых случаях возможно найти верхнюю и нижнюю оценки функции в зависимости от Например, пусть

Если составляется итерация соответствующей схемы, то мы получаем, используя тот факт, что монотонна,

Теперь предположим, что исходная схема содержит контактов. Тогда ее -кратная итерация с собой будет содержать контактов. Исключая из выражения (17), получаем

Если бы знак в неравенстве (16) был обращен в другую сторону, то результат получился бы также обратным. Следовательно, будет справедлив аналогичный результат, если заменить на

Гамакообразная схема три-на-три, рис. 16, имеет функцию вероятности

Так как выражение в квадратных скобках, очевидно, неотрицательно, то для Следовательно, для -кратной итерации в силу (17)

Так как каждая итерация умножает число контактов на 9, то общее их число равно и

Следует заметить, что данный результат справедлив только при Для больших значений верхняя оценка превосходит 1.

Обратим еще внимание на то, что в описанном процессе растет скачкообразно, увеличиваясь при каждом скачке в 9 раз. Если правая часть неравенства (19) дана, то может потребоваться число контактов, в 9 раз большее, чем определяемое неравенством, но этого количества будет заведомо достаточно.

Двойственная ситуация дает следующее неравенство для

Вернемся теперь к задаче последнего этапа. Пусть требуется улучшить вероятность от скажем, Это потребует, согласно неравенству (19), не более чем контактов. Так как используется гамакообразная схема, являющаяся самодвойственной, то те же самые построения применимы, чтобы улучшить вероятность от 3/4 до 1—6. Это делает та же самая схема.

Можно суммировать рассуждения, касающиеся итерации этих трех схем, следующим образом.

Теорема 6. Пусть даны и пусть Тогда существует такая схема, что содержащая не более контактов, где

Это выражение показывает, что эквивалент для сколь угодно надежного реле может быть получен из достаточного числа произвольно ненадежных реле, и дает оценку необходимого числа реле. Эта оценка безусловно не является вполне точной. В частности, множитель 81, который был введен («из соображений четности»), по-видимому, может быть уменьшен, если произвести более точный анализ. Для отдельных значений с, a и b этот множитель будет равен единице, а в случаях, где множитель больше, подстановка других схем в гамакообразную схему три-на-три часто уменьшает этот множитель до числа, близкого к единице без значительного изменения других членов правой части равенства.