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

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

Определить, какую булеву функцию реализует схема $\mathfrak {S}$ на рис. 15 на следующей странице в вершине $v$? Можно ли для этой функции построить менее сложную схему? $\circledast$

Рис. 15: Схема \mathfrak {S} из задачи 387.

Определить, какую булеву функцию реализует схема $\mathfrak {S}$ на рис. 16 на следующей странице в вершине $v$? Можно ли для этой функции построить менее сложную схему? Построить линейную программу, вычисляющую ту же функцию. $\circledast$

Рис. 16: Схема \mathfrak {S} из задачи 388.

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

Доказать, что в предыдущей задаче количество изменяемых переменных нельзя уменьшить до одной. Указание. Рассмотреть функцию $x_{1} \oplus x_{2}$. $\circledast$

Задана схема $\mathfrak {S}$ из функциональных элементов (рис.17) и три линейных программы (рис. 18). Определить, какие из программ вычисляют в переменной $z$ ту же функцию $f(x, y, z, u)$, что и схема $\mathfrak {S}$ в вершине $v$? $\circledast$

Рис. 17: Схема \mathfrak {S} из задачи 391.

Рис. 19: Линейная программа из задачи 392.

Пусть задана линейная программа П с входными переменными $x_{1}, x_{2}, x_{3}$ (рис.19). Построить схему $\mathfrak {S}_{\Pi }$ из функциональных элементов со входами $x_{1}, x_{2}, x_{3}$ и функциональными вершинами, соответствующими присваиваниям П, вычисляющую ту же функцию, что и П в выходной переменной $z$. Чему равна её глубина? Можно ли для вычисления той же функции построить более короткие схему и линейную программу? $\circledast$

Пусть базис $\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$. $\circledast$

Допустим, что функция $f$ не является константой. Доказать, что сложность функции $f$ в базисе $\mathcal{B}_{0}$ не превосходит сложности $f$ в базисе $\mathcal{B}_{1}=\mathcal{B}_{0} \cup \left\{ 0,1\right\}$. $\circledast$

Пусть $\mathrm{SUM}_{n}$ — это схема $n$-разрядного сумматора, выполняющего сложение двух $n$-разрядных двоичных чисел, результатом которого является $(n+1)$-разрядное число (см. [3], § 13.3). Используя схему $\mathrm{SUM}_{n}$, построить схему, реализующую операцию вычитания двух $n$-разрядных двоичных чисел: $d=a-b$ (при условии, что $a \geqslant b$). Оценить сложность полученной схемы.

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

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

Показать, что схему для вычисления $n$-местной функции odd (задача 170 на стр.54) можно реализовать в базисе $\mathcal{B}_{0}$, используя не более $\lfloor n / 2\rfloor$ отрицаний. $\circledast$

Пусть $f$ - $n$-местная булева функция, которая реализуется схемой $\mathfrak {S}$ с $k$ отрицаниями в базисе $\mathcal{B}_{0}$,

Доказать, что для любых $j$ и $m$ в последовательности значений $s=\left(v_{j}, v_{j+1}, \ldots , v_{j+m}\right)$ функции $f$ существует не больше $2^{k}-1$ позиций, где значение 1 меняется на 0. Указание. Применить индукцию по $k$. $\circledast$

Показать, что оценка $2^{k}-1$ из предыдущей задачи реально достижима. Указание. Индукцией по $k$ построить соответствующую функцию $f_{k}$ с $2^{k+1}-1$ аргументами. $\circledast$

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

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

Построить логическую схему, определяющую результат голосования в комитете, состоящем из пяти членов, где у председателя и секретаря имеется по два голоса. То есть если $x_{1}, x_{2}, x_{3}, y, z-$ это голоса «за» трёх обычных членов, председателя и секретаря соответственно, то

Определить сложность и глубину построенной схемы. $\circledast$

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

Построить следующие логические схемы, определить их сложность и глубину:

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

Пусть ориентированный граф $\mathfrak {G}=(\left\{ 1,2,3\right\} , E)$ без петель задан матрицей смежности $A$ размера $3 \times 3$. Построить схему из функциональных элементов, которая по шести переменным $A_{i, j}, i \neq j$, определяет, является ли граф $\mathfrak {G}$ сильно связным. Определить сложность и глубину построенной схемы. $\circledast$

Пусть неориентированный граф $\mathfrak {G}=(\left\{ 1,2,3,4\right\} , E)$ без петель задан матрицей смежности $A$ размера $4 \times 4$. Построить схему из функциональных элементов, которая по шести переменным $A_{i, j}, i<j$, определяет, является ли граф $\mathfrak {G}$ двудольным. Определить сложность и глубину построенной схемы. $\circledast$

Пусть для слова $w$ из четырёх букв переменная $s_{i}$ означает, что $i$-я буква в $w$ является гласной. Построить схему из функциональных элементов, которая по четырём переменным $s_{i}, i=1, \ldots , 4$, определяет, что в слове $w$ нет подряд идущих ни двух гласных, ни трёх согласных. Определить сложность и глубину построенной схемы. $\circledast$

С помощью переменных $u_{3}, u_{2}, u_{1}, u_{0}$ закодировано четырёхразрядное двоичное число. Построить схему из функциональных элементов, которая по переменным $u_{3}, u_{2}, u_{1}, u_{0}$, определяет, является ли это число простым. $\circledast$