Схемы из функциональных элементов

Доказать, что совершенная, сокращённая и минимальная ДНФ для функции $\operatorname {odd}\left(x_{1}, x_{2}, \ldots , x_{n}\right)$ совпадают и имеют $2^{n-1}$ элементарных конъюнкций длины $n$. $\square$

Доказать, что минимальная схема для сложения по модулю два имеет сложность $L(\oplus )=4$ в базисе $\mathcal{B}_{0}$. Указание. Доказать это утверждение для функций $x_{1} \oplus x_{2}$ и $x_{1} \leftrightarrow x_{2}$ одновременно.

Доказать предложение 85 на стр. 260.

Предложение 85: Пусть $\Pi$ — линейная программа с входными переменными $x_{1}, \ldots , x_{n}$, вычисляющая функцию $f$ в переменной $y$, и никакая невходная переменная не используется до присваивания ей значения. Тогда существует формула $\Phi_{\Pi }$ с переменными $x_{1}, \ldots , x_{n}$, реализующая эту же функцию.

Доказать, что в базисе $\mathcal{B}_{0}$ всякую булеву функцию $f$ можно вычислить с помощью линейной программы, где присваивание выполняется не более чем трём переменным. Можно ли уменьшить это количество до двух?

Доказать пункт 2) теоремы 86 на стр. 260.

Теорема 86, пункт 2): Пусть базис $\mathcal{B}$ позволяет получить константу 0, а программа $\Pi$ в базисе $\mathcal{B}$ кроме входных переменных $x_{1}, \ldots , x_{n}$ содержит $z_{1}, \ldots , z_{m}$, в каждой из которых вычисляется функция $f_{1}, \ldots , f_{m}$ соответственно. Тогда можно эффективно построить схему $\mathfrak {S}_{\Pi }$ в базисе $\mathcal{B}$, содержащую в том числе вершины $v_{1}, \ldots , v_{m}$ такие, что $f_{v_{i}}=f_{i}$ для $i=1, \ldots , m$.

Используя схему $\mathrm{SUM}_{n}$, построить схему, реализующую операцию вычитания двух $n$-разрядных двоичных чисел: $d=a-b$ (при условии, что $a \geqslant b$). Оценить сложность полученной схемы.

Определить глубину схем $\mathfrak {S}_{\oplus }, \mathfrak {S}_{\text{odd }}, \mathrm{SUM}_{1}$ и $\mathrm{SUM}_{n}$.

Два игрока независимо выбирают одно из четырёх чисел от 0 до 3. Первый игрок выигрывает, если их сумма является степенью двойки. Построить схему, определяющую выигрыш первого игрока. Её входы $u_{1}, u_{0}$ представляют в двоичной записи число $2 u_{1}+u_{0}$, выбранное первым игроком, а $v_{1}, v_{0}$ — число $2 v_{1}+v_{0}$, выбранное вторым игроком.

Построить схему $\mathfrak {C}_{n}$ для сравнения двух $n$-значных чисел, представленных в двоичном виде. Схема должна иметь входы $u_{n-1}, \ldots , u_{0}$ и $v_{n-1}, \ldots , v_{0}$ для исходных чисел и три выхода результата: больше, меньше или равно.

Построить схему для умножения двух двухзначных двоичных чисел. Схема должна иметь входы $a_{1}, a_{0}$ и $b_{1}, b_{0}$ для исходных чисел и четыре выхода для разрядов результата.

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

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