2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Три отрицания из двух.
Сообщение12.05.2019, 01:42 


14/01/11
2916
В теме, созданной достопочтенным 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).$

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

 Профиль  
                  
 
 Re: Три отрицания из двух.
Сообщение12.05.2019, 17:05 


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

 Профиль  
                  
 
 Re: Три отрицания из двух.
Сообщение12.05.2019, 17:43 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Три отрицания из двух.
Сообщение12.05.2019, 18:52 


14/01/11
2916
Xmas, конечно, присоединяйтесь. Любые дельные мысли только приветствуются. :-)

 Профиль  
                  
 
 Re: Три отрицания из двух.
Сообщение12.05.2019, 19:52 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Три отрицания из двух.
Сообщение12.05.2019, 20:11 


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

 Профиль  
                  
 
 
Сообщение12.05.2019, 20:13 
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Три отрицания из двух.
Сообщение12.05.2019, 20:30 


14/01/11
2916
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$. Если бы обе эти функции были монотонными, то всё получилось бы, а так нет.

 Профиль  
                  
 
 
Сообщение12.05.2019, 20:32 
Аватара пользователя


10/10/18
739
At Home
Я уже несколько дней вспоминаю.

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

 Профиль  
                  
 
 Re: Три отрицания из двух.
Сообщение12.05.2019, 21:00 
Заслуженный участник


04/03/09
906
У меня вышло, что с $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. Но тогда не получится построить схему, инвертирующую этот вход.

 Профиль  
                  
 
 Re: Три отрицания из двух.
Сообщение12.05.2019, 21:32 


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

 Профиль  
                  
 
 Re: Три отрицания из двух.
Сообщение12.05.2019, 23:16 
Заслуженный участник


04/03/09
906
Хорошо бы еще построить схему, инвертирующую $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)$. На выходе будет инвертированный первый бит.

 Профиль  
                  
 
 Posted automatically
Сообщение13.05.2019, 01:38 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group