Задачи и упражнения

• 7.1. Приведите примеры биективных и небиективных функций из Р₂.
• 7.2. Вычислите весовые характеристики JVqJq, Х_хз, N_Xq, N_x$, N§ системы б.ф. Ф = {f= х_х Ф х₂ Ф х_хх₂ дг₃, /ч-х ₂ ® х_хх₃, /₃ = х_х ® х₂}.
• 7.3. <3 система [f_x(x_Xf …, х_п), …,/_m(xj,…, л,)} несбалансированна (алгебраически зависима) при т > я; при m < п, если содержит функцию-константу.
• 7.4. < если система (ЛО^,х_п), …,/_от(х,…, *")}:
• 1) сбалансирована (алгебраически независима), то сбалансирована (алгебраически независима) и любая ее подсистема;
• 2) несбалансированна (алгебраически зависима), то несбалансированна (алгебраически зависима) и любая система, ее содержащая.
• 7.5. Является ли система [f_x(x_Xt …, х_п)_у …, f_m(x_x,…, дг")> алгебраически независимой, если она линейно зависима; линейно независима?
• 7.6. Является ли система {f_x(x_x,…, х_п), …, f_n(x_x, .-, х")} функций из Р₂ алгебраически независимой, если каждая функция системы зависит от переменной х_п фиктивно?
• 7.7. <3 линейно независимая система линейных б.ф. алгебраически независима.
• 7.8. <] если функция ф: Р" —> Р^т сбалансирована, где Р — поле, то сбалансирована любая нетривиальная линейная комбинация ее координатных функций.
• 7.9. <3 преобразование множества V" линейно линейны все его координатные функции.
• 7.10. Биективно ли преобразование g= (g_Xt …, g") множества V" при координатных функцияхgj е Т₀(п) n (Р₂(п) Т_х(п)), i = 1,…, п?
• 7.11. Сбалансировано ли преобразование g.

a) g = {х_хх₂ Ф х₃, х^с₃ Ф x_Xix_xx₃ Ф х₂} б) g = {х_] Ф х₂, х₂ Ф л₃,…, х₁ Ф x₈, x_s Ф х_х}.

• 7.12. Имеет ли н.в.с. система из шести б.ф. {х_х, х_х Ф х₂, х₂ Ф х₃,…, х₅ Ф дг₆}?
• 7.13. Биективно ли преобразованиеg. Е₃—> Е₃, заданное системой координатных функций:

• 7.14. Биективно ли преобразованиеg = (g_t,…, g_Tl) множества V_n, если:
  • а) gi (x_v…,x_ri) = XjX_j+p i= 1,…, n — 1 , g_n(x_v …, x") =x_trx_l ®x_x ® 1;
  • б) g,+i (xi…x") = x, ©…(c)x" i = 1, я- 1, g,(Xi, x") ®…(c)g"Oi,…x") = x, © … Ф

(c)лг"?

• 7.15. Является ли алгебраически зависимой система б.ф.:
  • а) {х_хх₂ © % (х₂ © д^Хл^ © д:₄), х_хх₂ © © д:₄,х₂ © лг₄};
  • б) {х_хх₂х₃х₄ © х_3> х₂ © x₃, х, х₂ © дг₄ © 1, X2^₃ (c)х₄};
  • в) {х₁х₂х₄ © дг₃, х₂ © х₃, х_хх₂ © х₄, х_{®х₂® х₃ © дг₄}.
• 7.16. Имеются ли среди преобразованийg’i, g₂, g₃ множества V₄ взаимно обратные:

g_{ = {х_{1 х₂ © х₃, х₃ © х₄, х_{ © х₂}, g₂ = {х_ь х_{ © х₂, х₃ Ф дг₄, i₂®i₃© ддозЬ.

g₃ = {х_{ © Х^С₄у х₂ Ф х_{х₃, х₃ Ф Х2Х₄, х₄ © х_хх₂) ?

7.17. Определите, какие преобразования V₄ биективны:

a) g = {х₂,^xv^x3>^хг ®^хаЬ ^б) & = {*2″ X! (c)х₃Фх₄}; в) g = {х₄, д:₂ (c)х₃, х_2>х_{}?

• 7.18. <1 множество неподвижных точек линейного преобразования пространства Р" образует подпространство.
• 7.19. <1 для аффинного преобразования g пространства P^rl при любых х, у, z е Р^п

g (x — у + z) = g (x) — g (y) + g (z).

• 7.20. Определите, какие преобразования ЛКГ биективны:
  • а) g (x) = (6д* + 3) mod 16;
  • б) g*(x) = 9л: mod 16;
  • в) g (x) = (8л: + 1) mod35;

^г) g (^x) = 27л: mod 147?

• 7.21. При каких двоичных константах а, Ь_} с сбалансирована система б.ф.:
  • а) {ах_хх₂ Ф Ьх₂, ах₃ © Ьх_хх₃ © сд:₂, с (.г, Ф д:₃)};
  • б) {(а © Ь)х₂, ах₃ © Ьх_хх₃ © сх₂, с (х_х Ф лг^Гз)}?
• 7.22. При каких а, Ь_Усе {0,1} система б.ф. является:
  • а) сбалансированной;
  • б) преобразованием регистра левого сдвига;
  • в) биективным преобразованием регистра левого сдвига {(а Ф b)x_xx₂ Ф bx₂, abx₃ © © слг₂, Ьх_х © с (х_х © х₃)}?
• 7.23. <1 если g — подстановка регистра сдвига длины п над GF (2), Tog^¹ — также подстановка двоичного регистра длины п. Образуют ли группу подстановки всех регистров длины п?
• 7.24. <1 отображение неавтономного регистра левого (правого) сдвига над Хс любой обратной связью является сбалансированным.
• 7.25. <1 при любой б.ф. 1/(х₂,…, х") и любых двоичных константах а_{, а₂, а_п вес булевой функции (|f (x_2}…, х_п) (c)х_х © а_х)(х₂ © а₂)…(х_Т1 © а") равен 1.
• 7.26. <1 все обратимые треугольные преобразования множествах" образует группу.
• 7.27. Каков порядок моноида всех треугольных преобразований (группы всех треугольных подстановок) множества Х^п?
• 7.28. <1 граф Г" двоичного неавтономного регистра сдвига длины п, построенный по системе образующих {ygo>ygib ^не зависит от функции обратной связи. Постройте граф Г₃.

• 7.29. Получите условия на функции / и |/, при которых g — подстановка множества У₆:
  • а) g = {(х₂, х₃, х₄, х₅, х₆, х, /(х₄, х₅, х₆) Ф |/(х" х₂, х₃)};
  • б) g = {(х₂, х₃,/(х₄, х₅, х₆), х₅, х₆, |/(х" х₂, х₃)}.
• 7.30. Определите цикловую структуру и порядок подстановки регистра левого сдвига длины п с функцией/обратной связи:
  • а) «= 3,/(х_1гх₂, х₃) =x_t (c)Х2Х3© 1;
  • б) п = 4,/(х₁, х₂, х₃, х₄) =х_х ®х₂ ®ХзХ₄ Ф 1;
  • в) п = 4,/(Х|_Гг₂, х₃х₄) = х, © х^г'з © х₂х₄ Ф х₃х₄.