О числе элементов схемы, реализующей обобщенную функцию голосования

Рассматривается один из важнейших разделов математической кибернетики – теория синтеза, надежности и сложности управляющих систем. Актуальность исследований в этой области обусловлена важностью многочисленных приложений, возникающих в различных разделах науки и техники. Все разнообразные средства цифровой техники: ЭВМ, микропроцессорные системы измерений и автоматизации технологических процессов, цифровая связь, телевидение и т.д., строятся на единой элементной базе, в состав которой входят чрезвычайно разные по сложности микросхемы – от логических элементов, выполняющих простейшие операции, до сложнейших программируемых кристаллов, содержащих миллионы логических элементов. Логические элементы цифровых устройств во многом определяют функциональные возможности последних, их конструктивное исполнение, технологичность, надежность. К числу основных модельных объектов математической теории синтеза, сложности и надежности управляющих систем относятся схемы из ненадежных функциональных элементов, реализующие булевы функции. В ряде результатов, относящихся к реализации булевых функций надежными схемами из ненадежных функциональных элементов, фигурирует параметр $N_{\hat{g}}$ – наименьшее число функциональных элементов, необходимых для реализации функции голосования $x`$ в рассматриваемом полном базисе. Оказалось, что еще и другие функции (обозначим их множество через $G$) обладают свойствами, аналогичными свойствам функции голосования. Эти функции имеют вид $x_1^{\sigma_1}x_2^{\sigma_2} \vee x_1^{\sigma_1}x_3^{\sigma_3} \vee x_2^{\sigma_2}x_3^{\sigma_3}$ ($\sigma_i \in \{0,1\}$, $i \in \{1,2,3\}$) и в статье называются обобщенными функциями голосования, т.е. $G$ – множество функций вида $x_1^{\sigma_1}x_2^{\sigma_2} \vee x_1^{\sigma_1}x_3^{\sigma_3} \vee x_2^{\sigma_2}x_3^{\sigma_3}$. Пусть $N_g$ – наименьшее число абсолютно надежных функциональных элементов, необходимых для реализации функции $g \in G$ в рассматриваемом полном базисе, а $N_g = min_{g \in G} N_g$, т.е. $N_g$ – наименьшее число абсолютно надежных функциональных элементов, достаточное для реализации хотя бы одной функции из множества $G$ в рассматриваемом полном базисе. Цель данной работы – получить верхнюю оценку величины $N_g$, которая была бы справедлива в произвольном полном базисе. Предполагается, что все функциональные элементы базиса абсолютно надежны. Для получения верхней оценки величины $N_g$ использованы те же методы и подходы, что и при доказательстве известной теоремы Поста о полноте систем булевых функций. Доказано, что в произвольном полном конечном базисе хотя бы одну функцию множества $G$ можно реализовать схемой, содержащей не более восьми функциональных элементов. Используя это свойство, можно в неравенствах заменить величину $N_g$ константой $8$. В ранее известных результатах по надежности схем, состоящих из ненадежных функциональных элементов и содержащих величину $N_g$ – зависящую от рассматриваемого базиса, можно улучшить ряд ранее известных оценок ненадежности асимптотически оптимальных по надежности схем.