Оценки функции h'(p)

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

Теорема 1. Если то справедливо неравенство

при условии, что не равна тождественно нулю, единице или

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

Очевидно, что если то

так как каждый из членов положителен. Раскрывая скобки, получаем

После некоторых преобразований имеем

Добавляя к обеим частям неравенства, находим

Поскольку по индуктивному предположению или или является одной из трех исключительных функций, в каждом случае и точно так же Из этих выражений и неравенства (11) получаем

Разделив на находим

или

что и доказывает теорему.

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

Графики функций этого семейства для , 1/2, 1, 2, 3, 4 изображены на рис. 11. График всякой возможной функции пересекает кривые этого семейства, так что в точке пересечения наклон графика функции больше наклона кривой семейства. Следовательно, в открытом интервале график всякой функции может пересечь каждую из кривых семейства самое большее один раз. Поскольку прямая линия с угловым

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

Рис. 11. Семейство кривых, удовлетворяющих уравнению

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

где абсцисса точки (обязательно единственной) пересечения кривой графика функций с диагональю.

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

Для достаточно малых функция может быть разложена в ряд Тейлора

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

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

Рис. 12. Двоичный канал, используемый для получения верхней оценки для

Таким образом, при близком к нулю, пропускная способность С (асимптотически) равна

Рассмотрим теперь ненадежное реле, которое имеет вероятность замыкания когда обмотка возбуждена, и вероятность замыкания когда обмотка не возбуждена. Это реле можно рассматривать как канал, для которого обмотка является входом, а контакт — выходом. Если достаточно мало, то пропускная способность реле равна Если имеется реле с одинаковыми то общая пропускная способность системы, имеющей обмоток в качестве входа и контактов в качестве выхода, равна поскольку пропускная способность совокупности независимых каналов равна сумме их пропускных способностей.

Докажем, исходя из этих соображений о пропускной способности, что функция вероятности для наших контактных схем удовлетворяет соотношению

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

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

Если это неравенство заменить равенством, то получим дифференциальное уравнение

Решение этого уравнения имеет вид

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

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

Булеву функцию переменных назовем функцией кворума, если существует такое что если в ней менее переменных равно 1, то функция равна 0, а если более чем переменных равно 1, то функция равна 1.

Теорема 2. Если график функции вероятности для произвольной функции кворума переменных пересекает график

функции вероятности некоторой другой булевой функции переменных, то в точке пересечения справедливо неравенство

т. е. функция кворума имеет максимальную производную. Кроме того,

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

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

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

где Пусть где а — наименьшее из чисел и А. Тогда

где — неотрицательные целые числа, а равно или в зависимости от того, что меньше, или А.

Заметим, что для выражения вида и имеет место равенство

Таким образом, есть монотонно возрастающая функция Далее, все члены в сумме равенства (15) для соответствуют большим значениям , чем значения в сумме для Если — произвольный член в сумме для — произвольный член в сумме для то

следорательно, существует такая постоянная К, что

и

Суммируя первое неравенство по всем членам а второе — по всем членам и, получим

Но при имеем следовательно,

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