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

[avva]

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

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

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

Comments

[alexeybobkov]

Неправильно (или я не понял, о чём вы пишете).
Есть два инвертора.
Строим из них три.
Потом выбираем из получившихся трёх любые два и опять строим из них три.
Итого становится четыре :)
Процесс продолжаем до бесконечности.

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

Попробуйте нарисовать схему для 4 отрицаний с двумя инверторами, и вы обнаружите в ней комбинационный цикл, недопустимый в схеме функциональных элементов. В теории они просто запрещены, а на практике могут привести к незатухающим периодическим колебаниям.

[alexeybobkov]

Хм. Да, вы правы, будет цикл.
Интересно бы промоделировать.

P.S.Вообще надо переходить на Haskell. Сейчас написал бы уравнения 4 инверторов, построенных на двух, а потом бы написал монаду с задержкой сигнала, вот и всё моделирование :)

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

:-)

Вообще, проработав 4 года в индустрии, из них 2 в исследовательском подразделении, могу с уверенностью утверждать, что схемы с комбинационными циклами между гейтами, реализующими полноценные булевы функции, избегаются практически во всех промышленных мэйнстримных методологиях (по разговорам со старшими товарищами), сам я ни разу с такими не сталкивался.

С современной высокой частотой работы железа это принесло бы невероятные трудности. Уже сейчас время переключения вполне легального гейта уже одного порядка с временем одного периода клок-цикла. Приходится долго сводить дизайн, чтобы схема корректно работала. Если же ещё допустить большие циклы из гейтов, в которых будут такие колебания, то работать с таким дизайном будет уже невозможно. Каждый гейт в цикле имеет собственную задержку + задержки в проводах, да ещё это всё должно будет несколько раз прокрутиться до тех пор, пока не установятся стабильные сигналы. Чем это всё рассчитывать, просто запрещают комбинационные циклы в дизайне. И совсем уж сумасшедший дом получится при переходе с одной библиотеки реализаций гейтов на другую, с новыми задержками. Там вообще всё пересчитывать заново, потому что легальные циклы могут стать нелегальными. (Пересчитывать заново и кучу всего переписывать приходится и так, но это уже другая тема :-)