При доказательстве теорем 1 и 2 используется следующая теоВ следующей теореме устанавливается точное значение сложности функции ln вбазисеБ. <...> При любом натуральном n cложность реализации линейной функции ln = x1 ⊕ . ⊕ рема 3, доказанная в статье [6]. <...> Сложность реализации линейной функции ln = x1 ⊕x2 ⊕.⊕xn ⊕1, n 2,в базисе Б равна 4n − 4, а длясложности реализации этой функции в базисе Б выполняютсяследующие оценки: 4n−4 L(ln) 4n−3. <...> Всякую минимальную схему, реализующую линейную функцию от n переменных (n 2)вбазисе Б или Б со сложностью 4n − 4, будем называть правильной, если входы этой схемы не соединяются со входами инверторов. <...> Для доказательства теорем 1 и 2 потребуются следующие леммы. <...> Пусть Sn (n 2) — правильнаясхема, реализующая линейную функцию от n переменных, E1 — верхний элемент в ней. <...> Тогда в схеме Sn можно выделить правильно входящий в схему стандартный или специальный блок, главным элементом которого будет элемент E1. <...> Доказательство леммы 1, основанное на использовании метода забивающих констант, не приводится здесь из-за своего значительного объема. <...> Пусть Sn — правильнаясхема, реализующая линейную функцию от n переменных и содержащаяправильно входящий в схему специальный блок B, главные входы которого соединены со входами схемы. <...> Тогда в схеме Sn не существует входа, соединенного со входами более чем одного выходного элемента блока B. <...> Доказательство леммы 2 также проводится при помощи метода забивающих констант. <...> Отметим, что при доказательстве этой леммы, как и в работе [10], возникла необходимость подавать константы более чем на один вход схемы. <...> Пусть Sn — правильная схема в базисе Б, реализующая линейную функцию от n переменных. <...> Она содержит верхний элемент, а значит, согласно лемме 1, в ней можно выделить стандартный или специальный блок. <...> Если в Sn можно выделить стандартный блок, то его можно удалить, подав константу 0 на один из входов схемы, которые подаются на входы главного элемента блока, и получить <...>