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

[avva]

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

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

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

Comments

[unsignedlong.livejournal.com]

сделать новый "my_not"

1)x xor 1 = not x

2)z or (not z ) = 1 (это для единички в xor)
3)xor = not(z) * y + not(y)+z

not(z) можно использовать из единички, которую получили в формуле 2

[avva.livejournal.com]

с третьим пунктом что-то не так, вам же надо вычислять не y xor z, а x xor 1, т.е. по формуле третьего пункта нужно будет еще отдельно not x.

[sleeping-death.livejournal.com]

xor=not(ZY)(Y+Z)

[unsignedlong.livejournal.com]

Я могу взять тот же not z, который я приготовил для 1
Тоесть я взял A , сделал из него not A, и разветвил - одной стороной в Or, другой в часть XOR-a

[avva.livejournal.com]

Все равно не понял. Вот у вас уже есть 1. И x. Для того, чтобы вычислить x xor 1, вам что not y, что not z, никак не помогают.

[(Anonymous)]

неинтересно, слишком много условий.

[unsignedlong.livejournal.com]

это не условия

[unsignedlong.livejournal.com]

секунду, я тут запутался :)

[unsignedlong.livejournal.com]

Да, я просто построил новый нот, которого так же надо 3 штуки :(
Все,задумался дальше :)

[burrru.livejournal.com]

На ум сразу приходят фамилии: Карацуба и Штрассен...

[avva.livejournal.com]

удачи :)

[avva.livejournal.com]

Я их кстати так и не изучил, все эти быстрые умножения :(

[burrru.livejournal.com]

А чего их учить?!... Посмотреть на формулы и все понятно. "Вот общая ее идея": избавляемся от одного умножения из нескольких. Если хочешь (мы на ты, да?) освоить, то у меня есть подходящая задачка - ее надо бы решить и даже статью написать, наверное, а мне лень...

[alexeybobkov]

О, я её лет десять назад решил аналитически.
Что интересно, вначале я доказал, что это невозможно :). Потом понял, что не учёл, что выход с одного инвертора можно завести на другой (через промежуточную логику, разумеется). Когда понял, задача сразу решилась.
Одно время схема у меня даже висела на стенке.
Могу восстановить, если надо.

В общем, в мире есть всего два инвертора. Не дай Бог один сгорит.

[avva.livejournal.com]

В общем, в мире есть всего два инвертора. Не дай Бог один сгорит.

О!

[alexeybobkov]

P.S. Слышал, что задача легко решается на Прологе. Было бы полезное упражнение, наверное. Сам я, однако, не настолько хороший знаток Пролога, чтобы её решить.

[renivid.livejournal.com]

Заводим A, B, C на AND, результ - на NOT, получаем !A+!B+!C дальше можно отделить A, B и С с помощью ИЛИ и пар B+C, A+C и A+B. Или я неправльно понял условия :).

[avva.livejournal.com]

попробуйте выписать точнее, и увидите, что это не так просто :)

[renivid.livejournal.com]

Что значит "выписать точнее"? Наверное, я все-таки неправильно понимаю условия.

[(Anonymous)]

Любую логическую схему можно реализовать на двух NOT.

[alexeybobkov]

Восстановил :)

[(Anonymous)]

Ну то есть да, конечно. Если три инвертора можно построить из двух, то и больше тоже можно. Duh.

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

Там дело не столько в избавлении от одного умножения (общее число арифметических операций сильно возрастает), сколько в возможности применять алгоритм рекурсивно. В этом случае число аддитивных операций, действительно, на порядок сложности не влияет. А так сравните сами: по определению умножать 2 линейных многочлена - нужно 4 умножения и 1 сложение, по Карацубе - 3 умножения и 5 сложений. По определению умножать матрицы 2х2 - нужно 8 умножений и 4 сложения, по Штрассену - 7 умножений и 18 сложений (алгоритм Винограда - 15 сложений).

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

Нет, не любую. Например, чтобы реализовать 4 функции NOT нужно уже минимум 3 инвертора (докажите).

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

Не буду портить удовольствия решения :-) Замечу только, что это - частный случай более общей задачи: как реализовать при неограниченном количестве AND и OR n отрицаний NOT x_1, ..., NOT x_n. Можно доказать, что для этого достаточно целой части сверху log_2 (n+1). Справедлива аналогичная нижняя оценка.