дана система уравнений:

  1. (a11 & x) ^ (a12 & y) = b1
  2. (a21 & x) ^ (a22 & y) = b2

a11, a12, a21, a22, b1, b2, x, y - тридцати двухбитные числа. & - побитовое умножение, ^ - сложение битов по модулю 2. Гарантируется, что решение (x, y) у системы существует. Можно ли используя только логические битовые операции над этими числами получить какое нибудь( не важно какое ) решение системы?

задан 1 Мар '18 20:01

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

Над полем из двух элементов имеют место равенства $%a_{11}x+a_{12}y=b_1$%, $%a_{21}x+a_{22}y=b_2$%. Каждый разряд можно рассматривать по отдельности. Из общих соображений можно сделать вывод, что формулы всегда имеются. Действительно, у нас всегда есть решение, то есть получаются булевы функции от коэффициентов. Они представляются полиномами, у которых свободные члены можно считать нулевыми, а тогда всё выражается через сумму и произведение по модулю 2. Вопрос только в том, насколько сложными могут получиться эти формулы.

Пусть $%a_{11}=1$%. Из первого уравнения исключаем $%x=b_1+a_{12}y$%, подставляем во второе: $%a_{21}b_1+a_{12}a_{21}y+a_{22}y=b_2$%. В случае совместности подойдёт $%y=b_2+a_{21}b_1$%. Это очевидно, если коэффициент при $%y$% равен единице. Если же он равен нулю, то $%b_2$% тоже равно нулю по причине совместности, и тогда годится любое $%y$%. При этом $%x=b_1+a_{12}a_{21}b_1+a_{12}b_2$%.

Теперь пусть $%a_{11}=0$%. Аналогичным образом рассматриваем случай $%a_{12}=1$% . Выводим формулы для неизвестных. Остаётся случай $%a_{11}=a_{12}=0$%. Ввиду совместности, $%b_1=0$%, то есть первого уравнения как бы нет. Далее снова рассматриваем подслучай $%a_{21}=1$%, где $%y$% можно брать нулевым, и $%x=b_2$%. А если $%a_{21}=0$%, то $%x$% можно взять нулевым, и из $%a_{22}y=b_2$% в случае совместности годится $%y=b_2$%.

Несколько вариантов всегда можно объединить в один. Действительно, если при $%a_{11}$% для $%x$% получилась формула $%f$%, а для $%a_{11}=0$% -- формула $%g$%, то полагаем $%x=a_{11}f+(a_{11}+1)g$%. Тот же принцип действует при работе с подслучаями.

ссылка

отвечен 2 Мар '18 1:23

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

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

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

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

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

отмечен:

×890

задан
1 Мар '18 20:01

показан
596 раз

обновлен
2 Мар '18 12:50

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

по почте:

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

по RSS:

Ответы

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

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