Сконструировать пример схемы в базисе дизъюнкции, конъюнкции и отрицания, реализующей функцию $%f(x_1, ..., x_n, y_1, ..., y_n)$%, которая принимает значение 1 тогда и только тогда, когда $%|x'|⩽|y'|$% ($%|x'|$%-- число, двоичная запись которого задается набором $%x'$%).

задан 14 Апр '16 1:41

10|600 символов нужно символов осталось
0

Если $%x_1 < y_1$%, что выражается формулой $%\overline{x_1}\&y_1$%, то первое число меньше, и схема должна выдать $%1$%. Если $%x_1=y_1$%, то сравниваем числа, начиная со второго разряда, по рекурсии. Условие равенства записывается как $%x_1\&y_1\lor\overline{x_1}\&\overline{y_1}$%, но можно записать чуть проще, если учесть, что случай "меньше" уже учтён, и тогда достаточно взять отрицание случая "больше", то есть $%\overline{x_1\&\overline{y_1}}=\overline{x_1}\lor y_1$%.

Полагая $%f_0()=1$% (константа), далее для $%n\ge1$% задаём функцию по индукции: $%f_n(x_1,y_1,x_2,y_2,...,x_n,y_n)=\overline{x_1}\&y_1\lor(\overline{x_1}\lor y_1)\&f_{n-1}(x_2,y_2,...,x_n,y_n)$%. Эта схема имеет линейную сложность (порядка $%5n$%).

ссылка

отвечен 14 Апр '16 4:02

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,343
×26

задан
14 Апр '16 1:41

показан
315 раз

обновлен
14 Апр '16 4:02

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru