Три отрицания из двух.

[Sender]

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

SergeCpp в сообщении #1392174 писал(а):

Задачу получения трёх отрицаний из двух давали некогда (конец 80-х или чуть позже) в одном институте на экзамен-автомат (кто решит -- поставят). В Компьютерре в конце 90-х (или чуть позже) была статья про эту задачу и про то, что можно получить так сколько угодно отрицаний из двух.

SergeCpp в сообщении #1392289 писал(а):

Создать устройство (схему из логических элементов), имеющее три входа и три выхода. На выходах должно быть логическое отрицание входов: 000 >> 111, 001 >> 110, ..., 110 >> 001, 111 >> 000. Для создания устройства у нас есть любое количество элементов И и элементов ИЛИ (с любым количеством входов: 2И, 3И, ..., 2ИЛИ, 3ИЛИ, ...) и только два элемента НЕ.

Соответствующий номер Компьютерры мне найти не удалось, пришлось решать своими силами. В результате получилась такая схема:

f1 = x1 && x2;
f2 = x1 && x3;
f3 = x2 && x3;
f4 = f1 || f2 || f3;
f5 = ! f4;
f6 = x1 || x2 || x3;
f7 = x1 && x2 && x3;
f8 = f5 && f6;
f9 = f7 || f8;
f10 = ! f9;
f11 = f5 || f10;
f12 = f3 || f5;
f13 = x2 || x3 || f10;
f14 = f11 && f12 && f13;
f15 = f2 || f5;
f16 = x1 || x3 || f10;
f17 = f11 && f15 && f16;
f18 = f1 || f5;
f19 = x1 || x2 || f10;
f20 = f11 && f18 && f19;

Print[BooleanMinimize[f14, "anf"]];
Print[BooleanMinimize[f17, "anf"]];
Print[BooleanMinimize[f20, "anf"]];

На выходах f14, f17, f20 действительно получаются отрицания входных переменных при том, что в схеме использованы только два отрицания. Поскольку мы получили отрицания входных переменных, мы можем использовать два из них, чтобы получить три и т.д. вплоть до любого желаемого количества. Это означает, что мы можем вычислить произвольную булеву функцию, использовав не более двух отрицаний в дополнение к монотонному базису($\wedge,\vee$). В связи с этим возникают интересные вопросы относительно некоторых публикаций, в которых исследуется т.н. инверсионная сложность булевых функций. Вот, взять к примеру следующую работу, где чёрным по белому написано:

Цитата:

In this paper we consider Boolean circuits over an arbitrary basis that consists of all monotone functions (with zero weight) and finite nonempty set of non-monotone functions (with unit weight). It is shown that the minimal sufficient for a realization of the Boolean function f number of non-monotone gates is equal to $\lceil\log_2(d(f)+1)\rceil-O(1).$

Налицо явное противоречие с продемонстрированным выше результатом. Кто-нибудь может объяснить мне, что происходит?
Авторы ссылаются на работу Маркова: http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=22436&option_lang=rus, но в его доказательстве речь идёт, очевидно, не о схемной, а о формульной сложности.

[Sender]

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

[Xmas]

Sender, я бы хотел поучаствовать в обсуждении на студенческих правах Объяснить происходящее я едва ли смогу, но я вполне прилично владею некоторыми полезными языками программирования для этой задачи (вроде Пролог и VHDL), и задача интересная. Извиняюсь, что опубликовал своё сообщение без добавления конкретных результатов и схем. Их я добавлю.

[Sender]

Xmas, конечно, присоединяйтесь. Любые дельные мысли только приветствуются.

[mihaild]

Sender, вы собрали схему (из двух отрицаний и еще пачки элементов) с тремя входами и тремя выходами. Её выход подавать на её же вход нельзя, так что наивным способом (одну пару вход-выход отложить, над оставшимися повторить ту же операцию) получить четыре отрицания уже не получится.

[Sender]

mihaild, да, я уже сообразил.
А вам известно что-нибудь о теоретических нижних оценках инверсной сложности булевых схем? В трудах Маркова мне удалось найти только оценки инверсной сложности для булевых формул.

[SergeCpp]

1) У нас есть чёрный ящик с тремя входами и тремя выходами.
2) Внутри него у нас есть чёрный ящик с двумя входами и двумя выходами.
3) Добавляем ещё один ящик с одним входом и одним выходом.
4) Ящики 2 и 3 образуют ящик 1-штрих.
5) Goto 1.

Я не смог найти тот номер в сети, архивы-то есть, но я не помню названия. Бумажного номера, думаю, нет уже, увы (сил нет перебирать всё).

https://old.computerra.ru/offline/

[Sender]

SergeCpp, может, помните какое-нибудь характерное слово, которое точно есть в статье?
По поводу предлагаемого метода размножения:
допустим, мы построили схему, позволяющую получать отрицания трёх переменных: x1, x2 и x3. Мы хотим получить отрицания четырёх: x1, x2, x3, x4.
Тогда вместо x2 нам надо подать $(x2\wedge x3)\vee (x2\wedge x4) \vee (x3\wedge x4)$, а вместо x3 -- $x2\oplus x3 \oplus x4$. Если бы обе эти функции были монотонными, то всё получилось бы, а так нет.

[SergeCpp]

Я уже несколько дней вспоминаю.

Нарисуйте на бумажке с ящиками. Суть -- движемся внутрь, а не вне.

[12d3]

У меня вышло, что с $n$ инверторами можно использовать максимум $2^n - 1$ входов.
Если есть $2^n$ входов, то поступим так: сначала все входы выключены, потом последовательно включим первый, потом включим второй, и т.д. до $2^n$-ого, всего будет $2^n+1$ состояний, в которых каждое следующее отличается от предыдущего значением одного входа. Значение на выходе первого инвертора является монотонно убывающей функцией от входов, поэтому оно не может изменить значение с 0 на 1. Значит, сначала, для первых $m$ состояний там будет 1, а для следующих $2^n+1-m$ состояний будет 0. $max(m, 2^n+1-m) \ge 2^{n-1} + 1$, следовательно в ряду из $2^n+1$ состояний входов можно взять подпоследовательность из $2^{n-1} + 1$ подряд идущих состояний, в которой значение на выходе первого инвертора неизменно. Дальше, по индукции, можно доказать, что для любого $k$ существует $2^{n-k}+1$ последовательных состояний таких, что значения на выходе первых $k$ инверторов неизменно. То есть, и для $k=n$ получим два последовательных состояния, в которых значение на выходе всех инверторов неизменно, а значение одного из входов меняется с 0 на 1. Но тогда не получится построить схему, инвертирующую этот вход.

[Sender]

Браво, 12d3! Спасибо, очень элегантно. Полагаю, вопрос можно считать закрытым.

[12d3]

Хорошо бы еще построить схему, инвертирующую $2^n-1$ входов.
Для начала, построим схему, которая выдает 1, если для заданного $m$ включено не менее $m$ входов. Возьмем все возможные комбинации из $m$ входов, каждую комбинацию соединим в один элемент И, а выходы всех элементов И соединим в одно ИЛИ. Обозначим такую схему как $GE(m)$ (greater or equal).
Из рассуждения в предыдущем посте и из того, что мы могли включать входы в любом порядке, следует, что значения на выходах инверторов полностью определяются количеством включенных входов. А именно, на входе $k$-го инвертора должна быть единичка, если количество включенных входов в двоичном представлении имеет $k$-ый бит, равный единичке, считая от старшего бита к младшему. На выходе $k$-го инвертора должен быть, соответственно, инвертированный $k$-ый бит.
Теперь укажем схему, как должны быть эти инверторы соединены, чтобы они действительно вычисляли соответствующие биты двоичного представления количества включенных входов. Строить будем по индукции. Пусть у нас уже $k$ инверторов, которые вычисляют первые $k$ инвертированных бит. Эти инверторы позволяют построить схемы, выдающие 1 в случае, если первые $k$ бит числа включенных входов имеют произвольные заданные значения, а именно, берем элемент И с $k$ входами, на которые подаем сигналы либо со входов, либо с выходов этих инверторов. Построим $2^k$ таких схем для всех возможных значений $k$ бит, они нам все понадобятся. Обозначим эти схемы как $A_i$, где $0 \le i < 2^k$. $A_i$ выдает 1, если первые $k$ бит числа включенных входов образуют число $i$. Соединим каждую из $A_i$ со схемой $GE(i \cdot 2^{n-k} + 2^{n-k-1})$ элементом И, а потом все эти элементы И, в количестве $2^k$ штук, соединим элементом ИЛИ. На выходе ИЛИ будет 1, если $k+1$-ый бит равен 1, иначе 0. Выход ИЛИ воткнем в $k+1$-ый инвертор. Конец шага индукции.
Теперь мы можем вычислять каждый бит числа включенных входов, а это позволяет построить схемы, выдающие 1 в том случае, если количество включенных входов в точности равно заданному (в отличие от упоминавшихся в начале схем GE). Обозначим такие схемы как $EQ(m)$.
Всё, теперь можно инвертировать входы, например, первый вход. Делать будем так: рассмотрим все возможные наборы значений остальных $2^n-2$ входов. Таких наборов будет $2^{2^n-2}$ штук. Для каждого набора возьмем элемент И, на который подадим тех входы, значение которых равно 1 в этом наборе и схему, выдающую 1, если количество всех включенных входов равно количеству входов, принимающих значение 1 в этом наборе, а потом все эти элементы И соединим в одно ИЛИ. Например, для $n=2$ будет так: $(EQ(0)) \vee (EQ(1) \wedge x2) \vee (EQ(1) \wedge x3) \vee (EQ(2) \wedge x2 \wedge x3)$. На выходе будет инвертированный первый бит.

[Lia]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Computer Science»
Причина переноса: по просьбе ТС.