1) Мультиплексор порядка

Входами являются переменных , а выходами - переменные . На выходах реализуются всевозможные элементарные конъюнкции (“”). – произвольный набор.

Допустим, что на входе набор и этот набор соответствует двоичному представлению числа . Тогда i- выход мультиплексора будет равен , а все остальные выходы , то есть -ый выход мультиплексора реализует следующую логическое умножение: , где – двоичное представление числа :

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

Оценим сложность мультиплексора более точно, используя полученную оценку. Для этого рассмотрим мультиплексоры порядка от переменных и мультиплексор от оставшихся переменных . Примем , то есть разобьем все переменные на группы. К первой группе относим переменные первой половины , а ко второй группе – переменные второй половины. На выходах реализуются всевозможные элементарные конъюнкции от переменных , а на выходах мультиплексора реализуются всевозможные элементарные конъюнкции переменных . Каждую конъюнкцию от переменных можно получить логическим умножением двух конъюнкций: конъюнкции переменных и конъюнкции переменных . Поэтому общую схему мультиплексора можем представить следующим образом:

Как показано ранее,

Поэтому общая сложность мультиплексора порядка

2) Дешифратор порядка .

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

Дешифратор реализует следующую двоичную функцию:

(*)

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

, где

• – сложность мультиплексора;

• – умножение выходов мультиплексора на соответствующие входы дешифратора. Элементарные конъюнкции от переменных, т.е. таких умножений ;

• – всевозможные дизъюнкции слагаемых в формуле (*). Количество слагаемых равно числу двоичных наборов от переменных.

3) Универсальный многополюсник.

Входами этого многополюсника являются переменные , а выходами , где , и эти выходы соответствуют всевозможным функциям от n переменных.

Утверждение. Сложность многополюсника

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

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

Что и требовалось доказать.

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

Утвердение

Сложность любой двочной функции не более чем n перменных лежит в пределах:

при некоторых положительных константах и .

Доказательство:

Покажем справедливость верхней оценки. Рассмотрим любую двоичную функцию и разложим данную функцию по первым переменным. Справедлива формула :

(*)

.

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

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

( логарифм по основанию 2). Очевидны оценки:

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

Т.о. сложность построенной схемы:

Покажем, что каждое слагаемое есть

1)

т.к. , поэтому ограничена;

2) т.к.,, поэтому ограничена;

3) .

Требуемое доказано. Оценим сложность функции снизу, применяя мощностной метод.

Пусть число функциональных элементов в схеме . Обозначим символом число схем с входами, число элементов в которых . Покажем, что число таких схем удовлетворяет оценке: .

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

Поэтому общее число соединений 1-го элемента не больше , а т.к. элементов не превосходит , то общее число соединений элементов не больше чем .

Осталось назначить общий выход схемы, это можно сделать способами (в схеме элементов и выходов). Таким образом, общее число схем не превосходит , т.к. число переменных в схеме не менее 1.

Что и требовалось доказать.

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

Используя оценку получаем . Прологарифмируем данное неравенство: . Используя полученную ранее верхнюю оценку сложности для функции Шенона легко показать необходимую оценку.

Справедливы следующие элементарные арифметические выкладки:

по ранее полученной оценке Шеноновская сложность двоичных функций от переменных в асимптотике:

, поэтому , поэтому

,

тогда ;

при некоторой положительной константе

Утверждение. Известная точная асимптотика функции сложности:

, .