задачка, компьютерное

[avva]

Убил на нее немало времени сегодня, но очень понравилась:

Придумайте схему, у которой есть три входа A, B, C и три выхода not-A, not-B, not-C. Можно пользоваться элементами AND, OR и NOT, но AND и OR сколько угодно, а NOT не более двух штук.

Я на время постараюсь скрывать правильные ответы. Но у меня есть предложение: если вы уже знаете решение, или нашли его компьютерным перебором, не пишите его в комментах - напишите просто, что нашли, например. Нет ничего плохого в компьютерном переборе, но не всем интересно. Мне хотелось именно найти решение самому аналитическим путем.

Comments

Re: Спойлер (выделить текст мышью для просмотра)

[adp.myopenid.com (from livejournal.com)]

Вот это сразу не вспомню. Помню только, что это сводится к немонотонной сложности суммы n переменных: если вы реализуете n отрицаний переменных, то вы реализуете сумму по модулю 2 x_1+...+x_n тем же числом инверторов. То есть L_neg(not x_1, ..., not x_n)>=L_neg(x_1+...+x_n), отсюда нижняя оценка для суммы влечёт нижнюю оценку для системы отрицаний.

Re: Спойлер (выделить текст мышью для просмотра)

[(Anonymous)]

Пошуровал в интернетах. Теорема доказана А. А. Марковым в 50-х годах, текст статьи paywalled, но зачем нам статья, нам и формулировки теоремы достаточно, а доказательство как-нибудь восстановим, хотя бы на уровне общей идеи.

Итак, пусть есть функция f из {0,1}^n в {0,1}^m, и пусть a_i — монотонно возрастающая последовательность векторов из {0,1}^n. Если f(a_i)>f(a_{i+1}), будем говорить, что имеет место падение f. Будем говорить, что f имеет класс немонотонности <=d, если на любой монотонно возрастающей последовательности f имеет не более d падений (и класс =d, если это число достигается). Теорема говорит, что для реализации f класса немонотонности d необходимо и достаточно ]log(d+1)[ инверторов.

Это все я нашел в интернетах, дальше мои домыслы.

Достаточно очевидно, что логическое отрицание имеет класс немонотонности 1, и что композиция немонотонной функции с монотонными не повышает класс немонотонности. Чуть менее очевидно, но все равно очевидно, что композиция функции класса d с функцией класса 1 дает функцию класса не более 2d+1 — инвертор добавляет не более одного падения на каждый монотонный интервал.

Сойдет за доказательство?

Re: Спойлер (выделить текст мышью для просмотра)

[adp.myopenid.com (from livejournal.com)]

Что-то типа того. Сумма по модулю 2 n переменных имеет класс немонотонности n.