Викиучебник ruwikibooks https://ru.wikibooks.org/wiki/%D0%97%D0%B0%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0 MediaWiki 1.39.0-wmf.21 first-letter Медиа Служебная Обсуждение Участник Обсуждение участника Викиучебник Обсуждение Викиучебника Файл Обсуждение файла MediaWiki Обсуждение MediaWiki Шаблон Обсуждение шаблона Справка Обсуждение справки Категория Обсуждение категории Полка Обсуждение полки Импортировано Обсуждение импортированного Рецепт Обсуждение рецепта Задача Обсуждение задачи TimedText TimedText talk Модуль Обсуждение модуля Гаджет Обсуждение гаджета Определение гаджета Обсуждение определения гаджета 0 18839 220993 129681 2022-07-20T06:08:38Z CommonsDelinker 933 Replacing Ca2fa97388fd.jpg with [[File:Oriflame_logo.jpg]] (by [[:c:User:CommonsDelinker|CommonsDelinker]] because: [[:c:COM:FR|File renamed]]: [[:c:COM:FR#FR2|Criterion 2]] (meaningless or ambiguous name)). wikitext text/x-wiki [[Файл:Lapiz labial.jpg|right|thumb|200px| [[w:Губная помада|Губная помада]] ]] [[Файл:Oriflame logo.jpg|right|thumb|200px|[[Oriflame|Oriflame]] ]] [[Файл:Prestige Cosmetics.jpg|right|thumb|200px| Девушка наносит блеск для губ с помощью кисточки-аппликатора]] [[Файл:Lipstick production at Colgate-Palmolive.jpg|right|thumb|200px|]] [[Файл:DifferentColorsOfLipsticks.JPG|right|thumb|200px|]] == Расположение == Завод [[w:Oriflame|Oriflame]] — ногинском район, московская область.<ref>[http://www.the-village.ru/village/business/process/227475-pomady Как делают помады и блески для губ]</ref>. == Необходимые вещества == '''Губная помада''' на 80 процентов состоит из воды. # [[w:Ланолин|Ланолин]] (жир с шерсти овец), # [[w:Касторовое Масло|Касторовое Масло]] # [[w:Воски|Воски]] (оригинальные— канделильский и карнаубский), # [[w:Красители|Красители]] # [[w:Перламутр|Перламутр]] == Этапы завершения материала == # Владимир Мигулин, руководитель производства губных помад Oriflame отмечает, то что получилось в специальной нагревательной камере. # Оператор загружает нужные ингредиенты в котле, затем варит их там же. # При температуре 80 градусов все ингредиенты сливаются, варятся не более 6 часов. # Затем из котла аккуратно берется проба. Она сравнивается с эталоном. # Нужно чтобы цвет помады ни чем не отличался, тогда его смешивают с красителем. # Помаду берут из миксера, делается проба на белом листке бумаги, дальше на губах. # Огненную жидкость в котле переливают в особой прочности контейнер, дно обязательно из пищевого [[w:Полиэтилен|полиэтилена]] # Масса должна остыть 8 часов. # Каждая партия весит в сумме 20 килограмм, затем идёт фасовка товара. # Потом еще раз плавят, выкладывают на формовочную машину. # Вещество заливают в специальные формы. Состав: силиконовый или медный # Охлаждение всей порции # Помада насаживается на тюбик == Оборудование == # Рядом всегда должна находиться лампа, которая меняет свет в комнате. == Интересные факты == # Операторы отметили, что популярностью пользовались розовые и клеверные оттенки == Википедия == === Состав === Основные компоненты помады: основа, добавки, красящая смесь, отдушки. В основу помады «Основу» входят воски и масла Воск определяет форму помады, обеспечивают её прочность и пластичность. Изначально для производства губной помады использовался натуральный пчелиный воск, но он является сильным аллергеном, как мёд и другие продукты пчеловодства. Сегодня высококачественную помаду чаще всего изготавливают на основе натуральных восков растительного происхождения. Масла. Основное масло для производства губной помады — касторовое. Главным его достоинством является устойчивость к окислению. В значительно меньших количествах производители помады используют масла кокоса и ши. Также масла используются в качестве добавок. Красители. Исторически первым красителем, применённым в производстве губных помад, был кармин. Цвет этого пигмента может изменяться от серого до пурпурно-фиолетового. Добавки. Среди добавок, входящих в состав губной помады, наиболее часто встречаются витамины А и Е. Они обладают противовоспалительным действием, содержат растительные масла, экстракты и солнцезащитные фильтры. Чтобы продлить срок службы помады, в её жировую основу обязательно вводят антиокислители и консерванты. Также в современную помаду добавляют пленкообразующие компоненты (полимеры и силикатные производные, обеспечивающие помаде блеск и стойкость). Полимеры, образующие тончайшие покрытия на коже губ. Это покрытие-плёнка обеспечивает устойчивость и предохраняет губы от потери влаги. Отдушка скрывает запах сырья губной помады и придает ей свой запах.<ref name=ReferenceA>{{cite web|url=http://www.livemaster.ru/topic/64945-istoriya-vozniknoveniya-gubnoj-pomady|title=История возникновения губной помады - Ярмарка Мастеров - ручная работа, handmade|accessdate=2013-03-13|archiveurl=http://www.webcitation.org/6F9Pj0sCR|archivedate=2013-03-16}}</ref> == Примечания == {{примечания}} [[Категория:Oriflame]] [[Категория:Производство]] [[Категория:Промышленность]] [[Категория:Косметика]] [[Категория:Пищевые добавки]] [[Категория:Воски]] [[Категория:Продукты животного происхождения]] [[Категория:Пчеловодство]] [[Категория:Красители]] [[Категория:Драгоценные минералы органического происхождения]] [[Категория:Поделочные камни]] [[Категория:Композиты]] [[Категория:Анатомия моллюсков]] [[Категория:Мёд]] 7r4q6m7z6kh0iixuz3goerzzzeifn7s 0 30038 220983 220981 2022-07-19T20:30:09Z Va musinov 69698 /* Лирическое отступление */ wikitext text/x-wiki '''Инволю́ция''' (от {{lang-la|involutio}} — свёртывание, завиток) — нетождественное преобразование, которое является [[w:обратная функция|обратным]] самому себе, то есть своей собственной [[w:обратная функция|инверсией]]. Это [[w:унарная операция|унарная операция]]. Формально, функция <math>f</math> называется инволюцией, если <math>f(f(x)) = x</math> для всякого <math>x</math> из [[w:Область определения функции|области определения функции]] <math>f</math>. Иногда пишут: <math>f\circ f= {f}^{2}=id</math>, где <math>id</math> обозначает тождественное преобразование. Вместо <math>id(x)</math> используют запись: <math>e(x)=x</math>. Таким образом, двойное применение функции <math>f</math> даёт исходное значение. == Свойства == Любая инволюция — это [[w:биекция|биекция]]. Если преобразование <math>f</math> инволютивное, то для любого выражения <math>A</math> и его образа <math>B=f(A)</math> имеем <math>f(B)=A</math>. В самом деле, <math>f(B)= f(f(A))=id(A)={id}_{A}=A</math>. '''''Критерий инволюции'''''. Функция <math>f</math> является инволюцией тогда и только тогда, когда для всякого выражения <math>A</math> существует такое выражение <math>B</math>, что <math>f(A)=B\neq A</math> и <math>f(B)=A</math>. Другими словами, преобразование является инволюцией в том и только в том случае, когда оно меняет местами какие-либо два выражения. ---- Если <math>f</math> — инволюция, то имеют место следующие соотношения: * <math>\forall a \in D_{f}: f^{-1}(a) = f(a)</math> [основное свойство] * <math>D_{f} = E_{f}</math> * <math>\forall a : f(f(a)) = a</math> * <math>\forall a, \exists b : f(a) = b \land f(b) = a</math> [критерий] == Примеры == Примеры инволюций: * <math>f(x) = -x</math>, заданная на множестве [[w:целое число|целых]] <math>\mathbb{Z}</math>, [[w:рациональное число|рациональных]] <math>\mathbb{Q}</math> или [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>; * простейшие инволюции на множестве [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>: *: <math>\dfrac{a}{x}</math>, <math>a-x</math>, <math>\dfrac{x}{x-1}</math>, <math>\dfrac{x+1}{x-1}</math>, <math>\dfrac{x-1}{x+1}</math>, <math>\dfrac{ax+b}{cx-a}</math>; * инволюция <math>f(x) = \dfrac{b}{x-a} + a</math> при <math>x\in \mathbb{R} \setminus \left\{a\right\}</math> и <math>b\neq 0</math>; * <math>f(x)= \bar{x}</math> — [[w:дополнение множества|дополнение множества]], заданная для подмножеств некоторого универсального множества <math>U</math>; * <math>f(x)= \neg x</math> — [[w:логическое отрицание|логическое отрицание]] [[w:булева алгебра|булевой алгебры]]; * [[w:Симметрия|симметрии]]: [[w:Центральная симметрия|центральная]], [[w:Осевая симметрия|осевая]], [[w:Зеркальная симметрия|зеркальная]]; * [[w:инверсия (геометрия)|инверсия]]; * [[w:комплексное сопряжение|комплексное сопряжение]]; * [[w:преобразование Лежандра|преобразование Лежандра]] * при факторизации обычного тора (точнее, одномерного комплексного тора, ещё точнее, эллиптической кривой) <math>E</math> по инволюции вида <math>x\mapsto -x</math> получается сфера; * Если представить, что <math>f</math> — нажатие на клавишу [[w:выключатель бытовой| бытового накладного выключателя]] (т. е. включить либо выключить свет), то <math>f</math> будет инволюцией. == Важнейшие факты == ;'''Теорема 1'''. : Композиция <math>{f}\circ{g}</math> двух инволюций <math>f</math> и <math>g</math> является инволюцией тогда и только тогда, когда они коммутируют: <math>{f}\circ{g} =g\circ f</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Пусть дана композиция <math>{f}\circ{g}</math>, в которой <math>f</math>, <math>g</math> — инволюции. Это означает, что <math>f=f^{-1}</math> и <math>g=g^{-1}</math>, а также <math>{f}\circ{g}={\left({f}\circ{g}\right)}^{-1}</math>. Имеем: <math>{f}\circ{g}= {\left({f}\circ{g}\right)}^{-1}={g^{-1}}\circ {f^{-1}}={g}\circ{f}</math>. Если <math>{f}\circ{g}</math> — инволюция, то двигаемся слева направо. Обратно, если выполняется равенство <math>{f}\circ{g} =g\circ f</math>, то справа налево. |} <code>Пример 1</code>. Такая композиция <math>\left(f_{1} \circ f_{2}\right) (x) = \left(f_{2} \circ f_{1} \right) (x) = {f_{3}} (x) = -{\dfrac{1}{x}}</math> есть инволюция. Аналогично, если <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math> и <math>g</math>, <math>h</math>, <math>k</math> — инволюции, то и <math>f</math> — инволюция. <code>Пример 2</code>. <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. ; '''Теорема 2'''. : Если <math>{f}</math> — монотонно возрастающая функция, то уравнения <math>{f}(x)=x</math> и <math>f(f(x))=x</math>, или <math>{f}(x)={f^{-1}}(x)</math>, равносильны. Рассмотрим следующую задачу. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>\sqrt{1+\sqrt{x}}=x-1</math>. |- | Перепишем данное уравнение в виде: <math>1+\sqrt{1+\sqrt{x}}=x</math>. Рассмотрим теперь функцию <math>f(x)=1+\sqrt{x}</math>. Тогда полученное уравнение примет вид: <math>f(f(x))=x</math>. Для решений уравнений такого вида применим '''теорему 2'''. Но сначала следует убедиться, что введённая функция <math>f</math> действительно монотонно возрастает. Для того чтобы <math>f(x)</math> была строго возрастающей, достаточно (но не является необходимым условием), чтобы <math>f'(x)>0</math>. В нашем случае получается <math>f'(x)=\dfrac{1}{2\sqrt{x}}>0</math>. В соответствии с приведённой '''теоремой 2''' приходим к равносильному уравнению <math>{f}(x)=x</math>, или <math>1+\sqrt{x}=x</math>, решение которого уже не сложно. Ответ: <math>x = \dfrac{3+\sqrt{5}}{2}.</math> |} ; '''Теорема 3'''. : Функция вида <math>f={h}\circ{g}\circ{h^{-1}}</math> (где <math>h</math> — некоторое биективное отображение) будет инволюцией в том и только в том случае, если функция <math>g</math> — инволюция. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Имеем следующее: <math>f=f^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {\left({h}\circ{g}\circ{h^{-1}}\right)}^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {{h}\circ{g^{-1}}\circ{h^{-1}}} \mid { \circ h} \Longleftrightarrow {h}\circ{g}={h}\circ{g^{-1}} \Longleftrightarrow {h^{-1} \circ } \mid {{h}\circ{g}={h}\circ{g^{-1}}} \Longleftrightarrow g = g^{-1}.</math> Если <math>{f}</math> является инволюцией, то двигаемся слева направо. Обратно, если <math>{g}</math> — инволюция, то справа налево. Теорема доказана. |} ''Замечание''. Ясно, что '''теорема 3''' сохраняет свою силу, если <math>f={h^{-1}}\circ{g}\circ{h}</math>, где <math>h</math> — биекция. <code>Пример 3</code>. В положительных числах такая функция будет как раз инволюцией по доказанной выше теореме: : <math>ln\left(\dfrac{e^x+1}{e^x-1}\right).</math> ; '''Следствие'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Тогда если <math>h</math> — взаимно-однозначное отображение [биекция] множества <math>E</math> на <math>F</math> с обратной биекцией <math>h^{-1}</math>, то композиция <math>h\circ f\circ h^{-1}</math> — инволюция на множестве <math>F</math>. [[File:Involution4.png|Involution4]] {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Утверждение очевидно по предыдущему. ''Указание''. Воспользоваться '''теоремой 3'''. |} ; '''Теорема 4'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Если <math>h</math> — такое отображение из <math>E</math> в <math>E</math>, что <math>h\circ f\circ h = f</math>, то <math>h\circ f</math> и <math>f\circ h</math> — инволюции на <math>E</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Покажем, что из исходного равенства <math>h\circ f\circ h = f</math> и условия <math>f=f^{-1}</math> получается инволютивная функция <math>h\circ f</math>. Итак, : <math>h\circ f\circ h = f \mid { \circ h^{-1}} \Longrightarrow h\circ f = f \circ h^{-1} \Longrightarrow h \circ f = {\left(h \circ f^{-1}\right)}^{-1} \Longrightarrow h \circ f = {\left(h \circ f \right)}^{-1} \mid {\circ {\left(h \circ f \right)}} \Longrightarrow {\left(h \circ f \right)}^{2} = e.</math> Таким образом, композиция <math>h\circ f</math> по определению является инволюцией. Аналогично проводится доказательство для <math>f\circ h</math>. |} {| class="wikitable collapsible collapsed" width="100%" ! Пусть дана функция <math>f=h\circ g\circ h\circ g^{-1}</math>, где <math>g</math> — биекция, а <math>h=h^{-1}</math>. Выяснить, при каком условии <math>f</math> будет инволютивной. |- | <u>''Решение''</u>. Во-первых, функция <math>f</math> будет инволюцией, если выполняется равенство: <math>f=f^{-1}</math>. Во-вторых, стоит заметить, что <math>h \circ f = g\circ h\circ g^{-1} = f^{-1} \circ h </math>. Поэтому <math>f=f^{-1} \Longleftrightarrow f = h \circ f \circ h</math>. Но по '''следствию''' композиция <math>g \circ h \circ g^{-1}</math> является инволюцией, а значит, и <math>h \circ f</math> — тоже инволюция. Наконец, <math> h\circ \mid f = h \circ f \circ h \Longleftrightarrow h\circ f = f \circ h</math>, то есть <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}</math>. ''Ответ'': <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}.</math> |} <code>Пример 4</code>. Функция <math>f(x)= -ln\left(-e^{x}\right)</math>. <u>'''Упражнение'''</u>. Убедитесь, что представленная функция действительно обладает таким свойством. ''Схемой'', или ''строением'', функции <math>f</math> назовём последовательность функций <math>f_{1}, f_{2}, ... , f_{n-1}, f_{n}</math> так, что каждая из них является либо элементарной, либо инволюцией и <math>f=f_{n} \circ f_{n-1} \circ ... \circ f_{2} \circ f_{1}</math>. <code>Пример 5</code>. Пусть <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. Тогда схемой функции <math>f</math> будет <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math>. == Фокус == {| class="wikitable collapsible collapsed" width=100% ! Целое общество гостей, непосвящённых в арифметические тайны, вы можете поразить следующим фокусом. |- | Фокусник просит одного человека написать на бумажке, секретно от него, трёхзначное число, какое этот человек хочет, и затем просит приписать к нему ещё раз то же самое число. Получится шестизначное число, состоящее из трёх повторяющихся цифр. Фокусник предлагает тому же товарищу или его соседу разделить — секретно от него — это число на 7; при этом фокусник заранее предсказывает, что остатка не получится. Результат деления передаётся соседу, который, по предложению ведущего, делит его на 11; и хотя фокусник не знает делимого, он всё же смело утверждает, что и оно разделится без остатка. Полученный результат фокусник направляет следующему соседу, которого просит разделить это число на 13 — деление снова выполняется без остатка, о чём он заранее предупреждает. Результат третьего деления фокусник, не глядя на полученное число, вручает первому товарищу со словами: — Вот число, которое вы задумали! — Так и есть: вы угадали. |} <code>Какова разгадка этого фокуса?</code> ''Указание''. Возьмите за функцию <math>f</math> алгоритм приписывания к числу <math>x\rightleftharpoons \overline{abc}</math>, то есть <math>f(x)= \overline{abcabc}</math>. Так как результат совпадает с исходным числом <math>x\rightleftharpoons \overline{abc}</math>, то <math>f^{-1}</math> над числом — это умножение его на 7, 11 и 13. Осталось найти связь <math>f</math> и <math>f^{-1}</math>. == Лирическое отступление == Приведём пример композиции двух инволюций, которая не будет уже инволюцией. <code>Пример</code>. Функция <math>\tau(x)=\dfrac{1}{1-x}</math> не является инволюцией; её строение таково: <math>\tau=\alpha \circ \beta</math>, где <math>\alpha (x) = \dfrac{1}{x}</math> и <math>\beta (x) = 1-x</math> у нас — обе инволюции. '''''Упражнение'''''. Докажите: для <math>\tau(x)=\dfrac{1}{1-x}</math> верно, что <math>\tau \neq {\tau}^{-1}</math>. ''Замечание''. Функция <math>{{\tau}^{-1}}{\left(x\right)}=1-{\dfrac{1}{x}}=\dfrac{x-1}{x}</math> со схемой <math>{\tau}^{-1}=\beta \circ \alpha</math> также не есть инволюция. Легко видеть, что <math>\alpha \circ {{\tau}^{-1}}</math> — инволюция. Делаем вывод, что композиция инволюции и неинволютивной функции может давать инволюцию в результате. Вопрос: ''в каком случае это происходит?'' Перед тем, как ответить на этот вопрос, сперва-наперво выясним, а каким свойством, в принципе, обладает введённая функция <math>\tau(x)=\dfrac{1}{1-x}</math>. Вычислим <math>{\tau}^{2}(x)</math>. У нас получится: : <math>{\tau}^{2}(x)=\dfrac{1}{1-\dfrac{1}{1-x}} = \dfrac{1-x}{1-x-1}=\dfrac{x-1}{x}={\tau}^{-1}(x).</math> Значит, <math>{\tau}^{3}=e</math>. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>f{\left(x\right)}\cdot {f{\left(\dfrac{1}{1-x}\right)}}=\dfrac{1-x}{x}</math>. |- | <code>Шаг 1</code> Напишем схему данного уравнения: <math>f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}}=-{\tau}^{-1}(x)</math>. <code>Шаг 2</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}^{-1}(x)</math>. Получим: : <center><math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(\tau({\tau}^{-1}(x))\right)}}=-{\tau}^{-1}({\tau}^{-1}(x)) \Longrightarrow f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}^{-2}(x).</math></center> Но так как <math>{\tau}^{2}(x)={\tau}^{-1}(x)</math>, то <math>{\tau}^{-2}(x)={\tau}(x)</math>. Поэтому <math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}(x)</math>. <code>Шаг 3</code> Теперь из результатов <code>Шага 1</code> и <code>Шага 2</code> делаем простой вывод: : <center><math>f(x)=\dfrac{-{\tau(x)}}{f{\left({\tau}^{-1}(x)\right)}} = \dfrac{{-{\tau}}^{-1}(x)}{f{\left({\tau}(x)\right)}}.</math></center> <code>Шаг 4</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}(x)</math>. Имеем: : <center><math>f{\left({\tau}^{-1}(x)\right)}=\dfrac{-x}{f{\left({\tau}(x)\right)}}=\dfrac{{-{\tau}}(x)}{f{\left(x\right)}}.</math></center> <code>Шаг 5</code> Наконец-то, мы <br><br><math> \begin{cases} \begin{array} {rcrcc} \dfrac{-x}{f{\left({\tau}(x)\right)}} = \dfrac{{-{\tau}}(x)}{f{\left(x\right)}}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases} \Longrightarrow \begin{cases} \begin{array} {rcrcc} {f{\left({\tau}(x)\right)}} = \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases}</math> Ответ: <math>x = \dfrac{3+\sqrt{5}}{2}.</math> |} == Инволюция в алгебре == [[w:Перестановка|Перестановка]] <math>\tau</math> является инволюцией, если <math>\tau\circ\tau=id</math>, каждая инволюция является произведением непересекающихся транспозиций, например: : <math>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 5 & 7 & 4 & 3 & 1 & 8 & 2 & 6\end{pmatrix} = (1,5)(2,7)(3,4)(6,8)</math>. Число инволюций в [[w:Группа перестановок|группе перестановок]] порядка <math>n</math> определяется по формулам: * <math> a(0) = 1,\ a(1) = 1,\ a(n) = a(n-1) + (n-1)a(n-2),\ n>1</math> (рекуррентная формула), * <math>a(n) = \sum_{k=0}^{[ n/2 ]}{\frac{n!}{2^k\cdot (n-2k)!\cdot k!}}</math>, (первые значения <math>a(n)</math>: 1, {{w:nums|link=nrl|1|2|4|10|26|76|232|764|2620|9496|35696|140152}}<ref>{{OEIS long|A000085|lc=1}}</ref>). Свойства инволюции обеспечивают ей широкое применение в различных приложения, например, инволютивные преобразования над пространством булевых векторов используются в различных схемах построения симметричных [[w:криптоалгоритм|криптоалгоритм]]ов, таких как [[w:Сеть Фейстеля|сети Фейстеля]] и [[w:SP-сеть|подстановочно-перестановочные сети]]. == Примечания == 1nitdl56zu5i09kju9ax146n5lk1hh5 220984 220983 2022-07-19T20:33:08Z Va musinov 69698 wikitext text/x-wiki '''Инволю́ция''' (от {{lang-la|involutio}} — свёртывание, завиток) — нетождественное преобразование, которое является [[w:обратная функция|обратным]] самому себе, то есть своей собственной [[w:обратная функция|инверсией]]. Это [[w:унарная операция|унарная операция]]. Формально, функция <math>f</math> называется инволюцией, если <math>f(f(x)) = x</math> для всякого <math>x</math> из [[w:Область определения функции|области определения функции]] <math>f</math>. Иногда пишут: <math>f\circ f= {f}^{2}=id</math>, где <math>id</math> обозначает тождественное преобразование. Вместо <math>id(x)</math> используют запись: <math>e(x)=x</math>. Таким образом, двойное применение функции <math>f</math> даёт исходное значение. == Свойства == Любая инволюция — это [[w:биекция|биекция]]. Если преобразование <math>f</math> инволютивное, то для любого выражения <math>A</math> и его образа <math>B=f(A)</math> имеем <math>f(B)=A</math>. В самом деле, <math>f(B)= f(f(A))=id(A)={id}_{A}=A</math>. '''''Критерий инволюции'''''. Функция <math>f</math> является инволюцией тогда и только тогда, когда для всякого выражения <math>A</math> существует такое выражение <math>B</math>, что <math>f(A)=B\neq A</math> и <math>f(B)=A</math>. Другими словами, преобразование является инволюцией в том и только в том случае, когда оно меняет местами какие-либо два выражения. ---- Если <math>f</math> — инволюция, то имеют место следующие соотношения: * <math>\forall a \in D_{f}: f^{-1}(a) = f(a)</math> [основное свойство] * <math>D_{f} = E_{f}</math> * <math>\forall a : f(f(a)) = a</math> * <math>\forall a, \exists b : f(a) = b \land f(b) = a</math> [критерий] == Примеры == Примеры инволюций: * <math>f(x) = -x</math>, заданная на множестве [[w:целое число|целых]] <math>\mathbb{Z}</math>, [[w:рациональное число|рациональных]] <math>\mathbb{Q}</math> или [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>; * простейшие инволюции на множестве [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>: *: <math>\dfrac{a}{x}</math>, <math>a-x</math>, <math>\dfrac{x}{x-1}</math>, <math>\dfrac{x+1}{x-1}</math>, <math>\dfrac{x-1}{x+1}</math>, <math>\dfrac{ax+b}{cx-a}</math>; * инволюция <math>f(x) = \dfrac{b}{x-a} + a</math> при <math>x\in \mathbb{R} \setminus \left\{a\right\}</math> и <math>b\neq 0</math>; * <math>f(x)= \bar{x}</math> — [[w:дополнение множества|дополнение множества]], заданная для подмножеств некоторого универсального множества <math>U</math>; * <math>f(x)= \neg x</math> — [[w:логическое отрицание|логическое отрицание]] [[w:булева алгебра|булевой алгебры]]; * [[w:Симметрия|симметрии]]: [[w:Центральная симметрия|центральная]], [[w:Осевая симметрия|осевая]], [[w:Зеркальная симметрия|зеркальная]]; * [[w:инверсия (геометрия)|инверсия]]; * [[w:комплексное сопряжение|комплексное сопряжение]]; * [[w:преобразование Лежандра|преобразование Лежандра]] * при факторизации обычного тора (точнее, одномерного комплексного тора, ещё точнее, эллиптической кривой) <math>E</math> по инволюции вида <math>x\mapsto -x</math> получается сфера; * Если представить, что <math>f</math> — нажатие на клавишу [[w:выключатель бытовой| бытового накладного выключателя]] (т. е. включить либо выключить свет), то <math>f</math> будет инволюцией. == Важнейшие факты == ;'''Теорема 1'''. : Композиция <math>{f}\circ{g}</math> двух инволюций <math>f</math> и <math>g</math> является инволюцией тогда и только тогда, когда они коммутируют: <math>{f}\circ{g} =g\circ f</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Пусть дана композиция <math>{f}\circ{g}</math>, в которой <math>f</math>, <math>g</math> — инволюции. Это означает, что <math>f=f^{-1}</math> и <math>g=g^{-1}</math>, а также <math>{f}\circ{g}={\left({f}\circ{g}\right)}^{-1}</math>. Имеем: <math>{f}\circ{g}= {\left({f}\circ{g}\right)}^{-1}={g^{-1}}\circ {f^{-1}}={g}\circ{f}</math>. Если <math>{f}\circ{g}</math> — инволюция, то двигаемся слева направо. Обратно, если выполняется равенство <math>{f}\circ{g} =g\circ f</math>, то справа налево. |} <code>Пример 1</code>. Такая композиция <math>\left(f_{1} \circ f_{2}\right) (x) = \left(f_{2} \circ f_{1} \right) (x) = {f_{3}} (x) = -{\dfrac{1}{x}}</math> есть инволюция. Аналогично, если <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math> и <math>g</math>, <math>h</math>, <math>k</math> — инволюции, то и <math>f</math> — инволюция. <code>Пример 2</code>. <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. ; '''Теорема 2'''. : Если <math>{f}</math> — монотонно возрастающая функция, то уравнения <math>{f}(x)=x</math> и <math>f(f(x))=x</math>, или <math>{f}(x)={f^{-1}}(x)</math>, равносильны. Рассмотрим следующую задачу. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>\sqrt{1+\sqrt{x}}=x-1</math>. |- | Перепишем данное уравнение в виде: <math>1+\sqrt{1+\sqrt{x}}=x</math>. Рассмотрим теперь функцию <math>f(x)=1+\sqrt{x}</math>. Тогда полученное уравнение примет вид: <math>f(f(x))=x</math>. Для решений уравнений такого вида применим '''теорему 2'''. Но сначала следует убедиться, что введённая функция <math>f</math> действительно монотонно возрастает. Для того чтобы <math>f(x)</math> была строго возрастающей, достаточно (но не является необходимым условием), чтобы <math>f'(x)>0</math>. В нашем случае получается <math>f'(x)=\dfrac{1}{2\sqrt{x}}>0</math>. В соответствии с приведённой '''теоремой 2''' приходим к равносильному уравнению <math>{f}(x)=x</math>, или <math>1+\sqrt{x}=x</math>, решение которого уже не сложно. Ответ: <math>x = \dfrac{3+\sqrt{5}}{2}.</math> |} ; '''Теорема 3'''. : Функция вида <math>f={h}\circ{g}\circ{h^{-1}}</math> (где <math>h</math> — некоторое биективное отображение) будет инволюцией в том и только в том случае, если функция <math>g</math> — инволюция. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Имеем следующее: <math>f=f^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {\left({h}\circ{g}\circ{h^{-1}}\right)}^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {{h}\circ{g^{-1}}\circ{h^{-1}}} \mid { \circ h} \Longleftrightarrow {h}\circ{g}={h}\circ{g^{-1}} \Longleftrightarrow {h^{-1} \circ } \mid {{h}\circ{g}={h}\circ{g^{-1}}} \Longleftrightarrow g = g^{-1}.</math> Если <math>{f}</math> является инволюцией, то двигаемся слева направо. Обратно, если <math>{g}</math> — инволюция, то справа налево. Теорема доказана. |} ''Замечание''. Ясно, что '''теорема 3''' сохраняет свою силу, если <math>f={h^{-1}}\circ{g}\circ{h}</math>, где <math>h</math> — биекция. <code>Пример 3</code>. В положительных числах такая функция будет как раз инволюцией по доказанной выше теореме: : <math>ln\left(\dfrac{e^x+1}{e^x-1}\right).</math> ; '''Следствие'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Тогда если <math>h</math> — взаимно-однозначное отображение [биекция] множества <math>E</math> на <math>F</math> с обратной биекцией <math>h^{-1}</math>, то композиция <math>h\circ f\circ h^{-1}</math> — инволюция на множестве <math>F</math>. [[File:Involution4.png|Involution4]] {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Утверждение очевидно по предыдущему. ''Указание''. Воспользоваться '''теоремой 3'''. |} ; '''Теорема 4'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Если <math>h</math> — такое отображение из <math>E</math> в <math>E</math>, что <math>h\circ f\circ h = f</math>, то <math>h\circ f</math> и <math>f\circ h</math> — инволюции на <math>E</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Покажем, что из исходного равенства <math>h\circ f\circ h = f</math> и условия <math>f=f^{-1}</math> получается инволютивная функция <math>h\circ f</math>. Итак, : <math>h\circ f\circ h = f \mid { \circ h^{-1}} \Longrightarrow h\circ f = f \circ h^{-1} \Longrightarrow h \circ f = {\left(h \circ f^{-1}\right)}^{-1} \Longrightarrow h \circ f = {\left(h \circ f \right)}^{-1} \mid {\circ {\left(h \circ f \right)}} \Longrightarrow {\left(h \circ f \right)}^{2} = e.</math> Таким образом, композиция <math>h\circ f</math> по определению является инволюцией. Аналогично проводится доказательство для <math>f\circ h</math>. |} {| class="wikitable collapsible collapsed" width="100%" ! Пусть дана функция <math>f=h\circ g\circ h\circ g^{-1}</math>, где <math>g</math> — биекция, а <math>h=h^{-1}</math>. Выяснить, при каком условии <math>f</math> будет инволютивной. |- | <u>''Решение''</u>. Во-первых, функция <math>f</math> будет инволюцией, если выполняется равенство: <math>f=f^{-1}</math>. Во-вторых, стоит заметить, что <math>h \circ f = g\circ h\circ g^{-1} = f^{-1} \circ h </math>. Поэтому <math>f=f^{-1} \Longleftrightarrow f = h \circ f \circ h</math>. Но по '''следствию''' композиция <math>g \circ h \circ g^{-1}</math> является инволюцией, а значит, и <math>h \circ f</math> — тоже инволюция. Наконец, <math> h\circ \mid f = h \circ f \circ h \Longleftrightarrow h\circ f = f \circ h</math>, то есть <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}</math>. ''Ответ'': <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}.</math> |} <code>Пример 4</code>. Функция <math>f(x)= -ln\left(-e^{x}\right)</math>. <u>'''Упражнение'''</u>. Убедитесь, что представленная функция действительно обладает таким свойством. ''Схемой'', или ''строением'', функции <math>f</math> назовём последовательность функций <math>f_{1}, f_{2}, ... , f_{n-1}, f_{n}</math> так, что каждая из них является либо элементарной, либо инволюцией и <math>f=f_{n} \circ f_{n-1} \circ ... \circ f_{2} \circ f_{1}</math>. <code>Пример 5</code>. Пусть <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. Тогда схемой функции <math>f</math> будет <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math>. == Фокус == {| class="wikitable collapsible collapsed" width=100% ! Целое общество гостей, непосвящённых в арифметические тайны, вы можете поразить следующим фокусом. |- | Фокусник просит одного человека написать на бумажке, секретно от него, трёхзначное число, какое этот человек хочет, и затем просит приписать к нему ещё раз то же самое число. Получится шестизначное число, состоящее из трёх повторяющихся цифр. Фокусник предлагает тому же товарищу или его соседу разделить — секретно от него — это число на 7; при этом фокусник заранее предсказывает, что остатка не получится. Результат деления передаётся соседу, который, по предложению ведущего, делит его на 11; и хотя фокусник не знает делимого, он всё же смело утверждает, что и оно разделится без остатка. Полученный результат фокусник направляет следующему соседу, которого просит разделить это число на 13 — деление снова выполняется без остатка, о чём он заранее предупреждает. Результат третьего деления фокусник, не глядя на полученное число, вручает первому товарищу со словами: — Вот число, которое вы задумали! — Так и есть: вы угадали. |} <code>Какова разгадка этого фокуса?</code> ''Указание''. Возьмите за функцию <math>f</math> алгоритм приписывания к числу <math>x\rightleftharpoons \overline{abc}</math>, то есть <math>f(x)= \overline{abcabc}</math>. Так как результат совпадает с исходным числом <math>x\rightleftharpoons \overline{abc}</math>, то <math>f^{-1}</math> над числом — это умножение его на 7, 11 и 13. Осталось найти связь <math>f</math> и <math>f^{-1}</math>. == Лирическое отступление == Приведём пример композиции двух инволюций, которая не будет уже инволюцией. <code>Пример</code>. Функция <math>\tau(x)=\dfrac{1}{1-x}</math> не является инволюцией; её строение таково: <math>\tau=\alpha \circ \beta</math>, где <math>\alpha (x) = \dfrac{1}{x}</math> и <math>\beta (x) = 1-x</math> у нас — обе инволюции. '''''Упражнение'''''. Докажите: для <math>\tau(x)=\dfrac{1}{1-x}</math> верно, что <math>\tau \neq {\tau}^{-1}</math>. ''Замечание''. Функция <math>{{\tau}^{-1}}{\left(x\right)}=1-{\dfrac{1}{x}}=\dfrac{x-1}{x}</math> со схемой <math>{\tau}^{-1}=\beta \circ \alpha</math> также не есть инволюция. Легко видеть, что <math>\alpha \circ {{\tau}^{-1}}</math> — инволюция. Делаем вывод, что композиция инволюции и неинволютивной функции может давать инволюцию в результате. Вопрос: ''в каком случае это происходит?'' Перед тем, как ответить на этот вопрос, сперва-наперво выясним, а каким свойством, в принципе, обладает введённая функция <math>\tau(x)=\dfrac{1}{1-x}</math>. Вычислим <math>{\tau}^{2}(x)</math>. У нас получится: : <math>{\tau}^{2}(x)=\dfrac{1}{1-\dfrac{1}{1-x}} = \dfrac{1-x}{1-x-1}=\dfrac{x-1}{x}={\tau}^{-1}(x).</math> Значит, <math>{\tau}^{3}=e</math>. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>f{\left(x\right)}\cdot {f{\left(\dfrac{1}{1-x}\right)}}=\dfrac{1-x}{x}</math>. |- | <code>Шаг 1</code> Напишем схему данного уравнения: <math>f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}}=-{\tau}^{-1}(x)</math>. <code>Шаг 2</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}^{-1}(x)</math>. Получим: : <center><math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(\tau({\tau}^{-1}(x))\right)}}=-{\tau}^{-1}({\tau}^{-1}(x)) \Longrightarrow f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}^{-2}(x).</math></center> Но так как <math>{\tau}^{2}(x)={\tau}^{-1}(x)</math>, то <math>{\tau}^{-2}(x)={\tau}(x)</math>. Поэтому <math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}(x)</math>. <code>Шаг 3</code> Теперь из результатов <code>Шага 1</code> и <code>Шага 2</code> делаем простой вывод: : <center><math>f(x)=\dfrac{-{\tau(x)}}{f{\left({\tau}^{-1}(x)\right)}} = \dfrac{{-{\tau}}^{-1}(x)}{f{\left({\tau}(x)\right)}}.</math></center> <code>Шаг 4</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}(x)</math>. Имеем: : <center><math>f{\left({\tau}^{-1}(x)\right)}=\dfrac{-x}{f{\left({\tau}(x)\right)}}=\dfrac{{-{\tau}}(x)}{f{\left(x\right)}}.</math></center> <code>Шаг 5</code> Наконец-то, мы <br><br><math> \begin{cases} \begin{array} {rcrcc} \dfrac{-x}{f{\left({\tau}(x)\right)}} = \dfrac{{-{\tau}}(x)}{f{\left(x\right)}}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases} \Longrightarrow \begin{cases} \begin{array} {rcrcc} {f{\left({\tau}(x)\right)}} = \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases}.</math> <code>Шаг 6</code> Подставим выражение <math>{f{\left({\tau}(x)\right)}}</math> во вторую строчку системы. Итак, Ответ: <math>x = \dfrac{3+\sqrt{5}}{2}.</math> |} == Инволюция в алгебре == [[w:Перестановка|Перестановка]] <math>\tau</math> является инволюцией, если <math>\tau\circ\tau=id</math>, каждая инволюция является произведением непересекающихся транспозиций, например: : <math>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 5 & 7 & 4 & 3 & 1 & 8 & 2 & 6\end{pmatrix} = (1,5)(2,7)(3,4)(6,8)</math>. Число инволюций в [[w:Группа перестановок|группе перестановок]] порядка <math>n</math> определяется по формулам: * <math> a(0) = 1,\ a(1) = 1,\ a(n) = a(n-1) + (n-1)a(n-2),\ n>1</math> (рекуррентная формула), * <math>a(n) = \sum_{k=0}^{[ n/2 ]}{\frac{n!}{2^k\cdot (n-2k)!\cdot k!}}</math>, (первые значения <math>a(n)</math>: 1, {{w:nums|link=nrl|1|2|4|10|26|76|232|764|2620|9496|35696|140152}}<ref>{{OEIS long|A000085|lc=1}}</ref>). Свойства инволюции обеспечивают ей широкое применение в различных приложения, например, инволютивные преобразования над пространством булевых векторов используются в различных схемах построения симметричных [[w:криптоалгоритм|криптоалгоритм]]ов, таких как [[w:Сеть Фейстеля|сети Фейстеля]] и [[w:SP-сеть|подстановочно-перестановочные сети]]. == Примечания == 6qcbakm83sszzvzdmxtuk6hdnti2wjz 220985 220984 2022-07-19T20:43:41Z Va musinov 69698 /* Лирическое отступление */ wikitext text/x-wiki '''Инволю́ция''' (от {{lang-la|involutio}} — свёртывание, завиток) — нетождественное преобразование, которое является [[w:обратная функция|обратным]] самому себе, то есть своей собственной [[w:обратная функция|инверсией]]. Это [[w:унарная операция|унарная операция]]. Формально, функция <math>f</math> называется инволюцией, если <math>f(f(x)) = x</math> для всякого <math>x</math> из [[w:Область определения функции|области определения функции]] <math>f</math>. Иногда пишут: <math>f\circ f= {f}^{2}=id</math>, где <math>id</math> обозначает тождественное преобразование. Вместо <math>id(x)</math> используют запись: <math>e(x)=x</math>. Таким образом, двойное применение функции <math>f</math> даёт исходное значение. == Свойства == Любая инволюция — это [[w:биекция|биекция]]. Если преобразование <math>f</math> инволютивное, то для любого выражения <math>A</math> и его образа <math>B=f(A)</math> имеем <math>f(B)=A</math>. В самом деле, <math>f(B)= f(f(A))=id(A)={id}_{A}=A</math>. '''''Критерий инволюции'''''. Функция <math>f</math> является инволюцией тогда и только тогда, когда для всякого выражения <math>A</math> существует такое выражение <math>B</math>, что <math>f(A)=B\neq A</math> и <math>f(B)=A</math>. Другими словами, преобразование является инволюцией в том и только в том случае, когда оно меняет местами какие-либо два выражения. ---- Если <math>f</math> — инволюция, то имеют место следующие соотношения: * <math>\forall a \in D_{f}: f^{-1}(a) = f(a)</math> [основное свойство] * <math>D_{f} = E_{f}</math> * <math>\forall a : f(f(a)) = a</math> * <math>\forall a, \exists b : f(a) = b \land f(b) = a</math> [критерий] == Примеры == Примеры инволюций: * <math>f(x) = -x</math>, заданная на множестве [[w:целое число|целых]] <math>\mathbb{Z}</math>, [[w:рациональное число|рациональных]] <math>\mathbb{Q}</math> или [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>; * простейшие инволюции на множестве [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>: *: <math>\dfrac{a}{x}</math>, <math>a-x</math>, <math>\dfrac{x}{x-1}</math>, <math>\dfrac{x+1}{x-1}</math>, <math>\dfrac{x-1}{x+1}</math>, <math>\dfrac{ax+b}{cx-a}</math>; * инволюция <math>f(x) = \dfrac{b}{x-a} + a</math> при <math>x\in \mathbb{R} \setminus \left\{a\right\}</math> и <math>b\neq 0</math>; * <math>f(x)= \bar{x}</math> — [[w:дополнение множества|дополнение множества]], заданная для подмножеств некоторого универсального множества <math>U</math>; * <math>f(x)= \neg x</math> — [[w:логическое отрицание|логическое отрицание]] [[w:булева алгебра|булевой алгебры]]; * [[w:Симметрия|симметрии]]: [[w:Центральная симметрия|центральная]], [[w:Осевая симметрия|осевая]], [[w:Зеркальная симметрия|зеркальная]]; * [[w:инверсия (геометрия)|инверсия]]; * [[w:комплексное сопряжение|комплексное сопряжение]]; * [[w:преобразование Лежандра|преобразование Лежандра]] * при факторизации обычного тора (точнее, одномерного комплексного тора, ещё точнее, эллиптической кривой) <math>E</math> по инволюции вида <math>x\mapsto -x</math> получается сфера; * Если представить, что <math>f</math> — нажатие на клавишу [[w:выключатель бытовой| бытового накладного выключателя]] (т. е. включить либо выключить свет), то <math>f</math> будет инволюцией. == Важнейшие факты == ;'''Теорема 1'''. : Композиция <math>{f}\circ{g}</math> двух инволюций <math>f</math> и <math>g</math> является инволюцией тогда и только тогда, когда они коммутируют: <math>{f}\circ{g} =g\circ f</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Пусть дана композиция <math>{f}\circ{g}</math>, в которой <math>f</math>, <math>g</math> — инволюции. Это означает, что <math>f=f^{-1}</math> и <math>g=g^{-1}</math>, а также <math>{f}\circ{g}={\left({f}\circ{g}\right)}^{-1}</math>. Имеем: <math>{f}\circ{g}= {\left({f}\circ{g}\right)}^{-1}={g^{-1}}\circ {f^{-1}}={g}\circ{f}</math>. Если <math>{f}\circ{g}</math> — инволюция, то двигаемся слева направо. Обратно, если выполняется равенство <math>{f}\circ{g} =g\circ f</math>, то справа налево. |} <code>Пример 1</code>. Такая композиция <math>\left(f_{1} \circ f_{2}\right) (x) = \left(f_{2} \circ f_{1} \right) (x) = {f_{3}} (x) = -{\dfrac{1}{x}}</math> есть инволюция. Аналогично, если <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math> и <math>g</math>, <math>h</math>, <math>k</math> — инволюции, то и <math>f</math> — инволюция. <code>Пример 2</code>. <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. ; '''Теорема 2'''. : Если <math>{f}</math> — монотонно возрастающая функция, то уравнения <math>{f}(x)=x</math> и <math>f(f(x))=x</math>, или <math>{f}(x)={f^{-1}}(x)</math>, равносильны. Рассмотрим следующую задачу. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>\sqrt{1+\sqrt{x}}=x-1</math>. |- | Перепишем данное уравнение в виде: <math>1+\sqrt{1+\sqrt{x}}=x</math>. Рассмотрим теперь функцию <math>f(x)=1+\sqrt{x}</math>. Тогда полученное уравнение примет вид: <math>f(f(x))=x</math>. Для решений уравнений такого вида применим '''теорему 2'''. Но сначала следует убедиться, что введённая функция <math>f</math> действительно монотонно возрастает. Для того чтобы <math>f(x)</math> была строго возрастающей, достаточно (но не является необходимым условием), чтобы <math>f'(x)>0</math>. В нашем случае получается <math>f'(x)=\dfrac{1}{2\sqrt{x}}>0</math>. В соответствии с приведённой '''теоремой 2''' приходим к равносильному уравнению <math>{f}(x)=x</math>, или <math>1+\sqrt{x}=x</math>, решение которого уже не сложно. Ответ: <math>x = \dfrac{3+\sqrt{5}}{2}.</math> |} ; '''Теорема 3'''. : Функция вида <math>f={h}\circ{g}\circ{h^{-1}}</math> (где <math>h</math> — некоторое биективное отображение) будет инволюцией в том и только в том случае, если функция <math>g</math> — инволюция. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Имеем следующее: <math>f=f^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {\left({h}\circ{g}\circ{h^{-1}}\right)}^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {{h}\circ{g^{-1}}\circ{h^{-1}}} \mid { \circ h} \Longleftrightarrow {h}\circ{g}={h}\circ{g^{-1}} \Longleftrightarrow {h^{-1} \circ } \mid {{h}\circ{g}={h}\circ{g^{-1}}} \Longleftrightarrow g = g^{-1}.</math> Если <math>{f}</math> является инволюцией, то двигаемся слева направо. Обратно, если <math>{g}</math> — инволюция, то справа налево. Теорема доказана. |} ''Замечание''. Ясно, что '''теорема 3''' сохраняет свою силу, если <math>f={h^{-1}}\circ{g}\circ{h}</math>, где <math>h</math> — биекция. <code>Пример 3</code>. В положительных числах такая функция будет как раз инволюцией по доказанной выше теореме: : <math>ln\left(\dfrac{e^x+1}{e^x-1}\right).</math> ; '''Следствие'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Тогда если <math>h</math> — взаимно-однозначное отображение [биекция] множества <math>E</math> на <math>F</math> с обратной биекцией <math>h^{-1}</math>, то композиция <math>h\circ f\circ h^{-1}</math> — инволюция на множестве <math>F</math>. [[File:Involution4.png|Involution4]] {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Утверждение очевидно по предыдущему. ''Указание''. Воспользоваться '''теоремой 3'''. |} ; '''Теорема 4'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Если <math>h</math> — такое отображение из <math>E</math> в <math>E</math>, что <math>h\circ f\circ h = f</math>, то <math>h\circ f</math> и <math>f\circ h</math> — инволюции на <math>E</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Покажем, что из исходного равенства <math>h\circ f\circ h = f</math> и условия <math>f=f^{-1}</math> получается инволютивная функция <math>h\circ f</math>. Итак, : <math>h\circ f\circ h = f \mid { \circ h^{-1}} \Longrightarrow h\circ f = f \circ h^{-1} \Longrightarrow h \circ f = {\left(h \circ f^{-1}\right)}^{-1} \Longrightarrow h \circ f = {\left(h \circ f \right)}^{-1} \mid {\circ {\left(h \circ f \right)}} \Longrightarrow {\left(h \circ f \right)}^{2} = e.</math> Таким образом, композиция <math>h\circ f</math> по определению является инволюцией. Аналогично проводится доказательство для <math>f\circ h</math>. |} {| class="wikitable collapsible collapsed" width="100%" ! Пусть дана функция <math>f=h\circ g\circ h\circ g^{-1}</math>, где <math>g</math> — биекция, а <math>h=h^{-1}</math>. Выяснить, при каком условии <math>f</math> будет инволютивной. |- | <u>''Решение''</u>. Во-первых, функция <math>f</math> будет инволюцией, если выполняется равенство: <math>f=f^{-1}</math>. Во-вторых, стоит заметить, что <math>h \circ f = g\circ h\circ g^{-1} = f^{-1} \circ h </math>. Поэтому <math>f=f^{-1} \Longleftrightarrow f = h \circ f \circ h</math>. Но по '''следствию''' композиция <math>g \circ h \circ g^{-1}</math> является инволюцией, а значит, и <math>h \circ f</math> — тоже инволюция. Наконец, <math> h\circ \mid f = h \circ f \circ h \Longleftrightarrow h\circ f = f \circ h</math>, то есть <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}</math>. ''Ответ'': <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}.</math> |} <code>Пример 4</code>. Функция <math>f(x)= -ln\left(-e^{x}\right)</math>. <u>'''Упражнение'''</u>. Убедитесь, что представленная функция действительно обладает таким свойством. ''Схемой'', или ''строением'', функции <math>f</math> назовём последовательность функций <math>f_{1}, f_{2}, ... , f_{n-1}, f_{n}</math> так, что каждая из них является либо элементарной, либо инволюцией и <math>f=f_{n} \circ f_{n-1} \circ ... \circ f_{2} \circ f_{1}</math>. <code>Пример 5</code>. Пусть <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. Тогда схемой функции <math>f</math> будет <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math>. == Фокус == {| class="wikitable collapsible collapsed" width=100% ! Целое общество гостей, непосвящённых в арифметические тайны, вы можете поразить следующим фокусом. |- | Фокусник просит одного человека написать на бумажке, секретно от него, трёхзначное число, какое этот человек хочет, и затем просит приписать к нему ещё раз то же самое число. Получится шестизначное число, состоящее из трёх повторяющихся цифр. Фокусник предлагает тому же товарищу или его соседу разделить — секретно от него — это число на 7; при этом фокусник заранее предсказывает, что остатка не получится. Результат деления передаётся соседу, который, по предложению ведущего, делит его на 11; и хотя фокусник не знает делимого, он всё же смело утверждает, что и оно разделится без остатка. Полученный результат фокусник направляет следующему соседу, которого просит разделить это число на 13 — деление снова выполняется без остатка, о чём он заранее предупреждает. Результат третьего деления фокусник, не глядя на полученное число, вручает первому товарищу со словами: — Вот число, которое вы задумали! — Так и есть: вы угадали. |} <code>Какова разгадка этого фокуса?</code> ''Указание''. Возьмите за функцию <math>f</math> алгоритм приписывания к числу <math>x\rightleftharpoons \overline{abc}</math>, то есть <math>f(x)= \overline{abcabc}</math>. Так как результат совпадает с исходным числом <math>x\rightleftharpoons \overline{abc}</math>, то <math>f^{-1}</math> над числом — это умножение его на 7, 11 и 13. Осталось найти связь <math>f</math> и <math>f^{-1}</math>. == Лирическое отступление == Приведём пример композиции двух инволюций, которая не будет уже инволюцией. <code>Пример</code>. Функция <math>\tau(x)=\dfrac{1}{1-x}</math> не является инволюцией; её строение таково: <math>\tau=\alpha \circ \beta</math>, где <math>\alpha (x) = \dfrac{1}{x}</math> и <math>\beta (x) = 1-x</math> у нас — обе инволюции. '''''Упражнение'''''. Докажите: для <math>\tau(x)=\dfrac{1}{1-x}</math> верно, что <math>\tau \neq {\tau}^{-1}</math>. ''Замечание''. Функция <math>{{\tau}^{-1}}{\left(x\right)}=1-{\dfrac{1}{x}}=\dfrac{x-1}{x}</math> со схемой <math>{\tau}^{-1}=\beta \circ \alpha</math> также не есть инволюция. Легко видеть, что <math>\alpha \circ {{\tau}^{-1}}</math> — инволюция. Делаем вывод, что композиция инволюции и неинволютивной функции может давать инволюцию в результате. Вопрос: ''в каком случае это происходит?'' Перед тем, как ответить на этот вопрос, сперва-наперво выясним, а каким свойством, в принципе, обладает введённая функция <math>\tau(x)=\dfrac{1}{1-x}</math>. Вычислим <math>{\tau}^{2}(x)</math>. У нас получится: : <math>{\tau}^{2}(x)=\dfrac{1}{1-\dfrac{1}{1-x}} = \dfrac{1-x}{1-x-1}=\dfrac{x-1}{x}={\tau}^{-1}(x).</math> Значит, <math>{\tau}^{3}=e</math>. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>f{\left(x\right)}\cdot {f{\left(\dfrac{1}{1-x}\right)}}=\dfrac{1-x}{x}</math>. |- | <code>Шаг 1</code> Напишем схему данного уравнения: <math>f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}}=-{\tau}^{-1}(x)</math>. <code>Шаг 2</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}^{-1}(x)</math>. Получим: : <center><math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(\tau({\tau}^{-1}(x))\right)}}=-{\tau}^{-1}({\tau}^{-1}(x)) \Longrightarrow f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}^{-2}(x).</math></center> Но так как <math>{\tau}^{2}(x)={\tau}^{-1}(x)</math>, то <math>{\tau}^{-2}(x)={\tau}(x)</math>. Поэтому <math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}(x)</math>. <code>Шаг 3</code> Теперь из результатов <code>Шага 1</code> и <code>Шага 2</code> делаем простой вывод: : <center><math>f(x)=\dfrac{-{\tau(x)}}{f{\left({\tau}^{-1}(x)\right)}} = \dfrac{{-{\tau}}^{-1}(x)}{f{\left({\tau}(x)\right)}}.</math></center> <code>Шаг 4</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}(x)</math>. Имеем: : <center><math>f{\left({\tau}^{-1}(x)\right)}=\dfrac{-x}{f{\left({\tau}(x)\right)}}=\dfrac{{-{\tau}}(x)}{f{\left(x\right)}}.</math></center> <code>Шаг 5</code> Наконец-то, мы <br><br><math> \begin{cases} \begin{array} {rcrcc} \dfrac{-x}{f{\left({\tau}(x)\right)}} = \dfrac{{-{\tau}}(x)}{f{\left(x\right)}}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases} \Longrightarrow \begin{cases} \begin{array} {rcrcc} {f{\left({\tau}(x)\right)}} = \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases}.</math> <code>Шаг 6</code> Подставим выражение <math>{f{\left({\tau}(x)\right)}}</math> во вторую строчку системы. Итак, : <math>f{\left(x\right)}\cdot \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)} = -{\tau}^{-1}(x) \Longleftrightarrow f{\left(x\right)}\cdot f{\left(x\right)} = \dfrac{{-{\tau}}(x)}\cdot {{\tau}^{-1}{\left(x\right)}}{x}</math> Ответ: <math>x = \dfrac{3+\sqrt{5}}{2}.</math> |} == Инволюция в алгебре == [[w:Перестановка|Перестановка]] <math>\tau</math> является инволюцией, если <math>\tau\circ\tau=id</math>, каждая инволюция является произведением непересекающихся транспозиций, например: : <math>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 5 & 7 & 4 & 3 & 1 & 8 & 2 & 6\end{pmatrix} = (1,5)(2,7)(3,4)(6,8)</math>. Число инволюций в [[w:Группа перестановок|группе перестановок]] порядка <math>n</math> определяется по формулам: * <math> a(0) = 1,\ a(1) = 1,\ a(n) = a(n-1) + (n-1)a(n-2),\ n>1</math> (рекуррентная формула), * <math>a(n) = \sum_{k=0}^{[ n/2 ]}{\frac{n!}{2^k\cdot (n-2k)!\cdot k!}}</math>, (первые значения <math>a(n)</math>: 1, {{w:nums|link=nrl|1|2|4|10|26|76|232|764|2620|9496|35696|140152}}<ref>{{OEIS long|A000085|lc=1}}</ref>). Свойства инволюции обеспечивают ей широкое применение в различных приложения, например, инволютивные преобразования над пространством булевых векторов используются в различных схемах построения симметричных [[w:криптоалгоритм|криптоалгоритм]]ов, таких как [[w:Сеть Фейстеля|сети Фейстеля]] и [[w:SP-сеть|подстановочно-перестановочные сети]]. == Примечания == eyqa50fy1a2h8f7c6jykoqhfzzxa5t1 220986 220985 2022-07-19T20:47:39Z Va musinov 69698 /* Лирическое отступление */ wikitext text/x-wiki '''Инволю́ция''' (от {{lang-la|involutio}} — свёртывание, завиток) — нетождественное преобразование, которое является [[w:обратная функция|обратным]] самому себе, то есть своей собственной [[w:обратная функция|инверсией]]. Это [[w:унарная операция|унарная операция]]. Формально, функция <math>f</math> называется инволюцией, если <math>f(f(x)) = x</math> для всякого <math>x</math> из [[w:Область определения функции|области определения функции]] <math>f</math>. Иногда пишут: <math>f\circ f= {f}^{2}=id</math>, где <math>id</math> обозначает тождественное преобразование. Вместо <math>id(x)</math> используют запись: <math>e(x)=x</math>. Таким образом, двойное применение функции <math>f</math> даёт исходное значение. == Свойства == Любая инволюция — это [[w:биекция|биекция]]. Если преобразование <math>f</math> инволютивное, то для любого выражения <math>A</math> и его образа <math>B=f(A)</math> имеем <math>f(B)=A</math>. В самом деле, <math>f(B)= f(f(A))=id(A)={id}_{A}=A</math>. '''''Критерий инволюции'''''. Функция <math>f</math> является инволюцией тогда и только тогда, когда для всякого выражения <math>A</math> существует такое выражение <math>B</math>, что <math>f(A)=B\neq A</math> и <math>f(B)=A</math>. Другими словами, преобразование является инволюцией в том и только в том случае, когда оно меняет местами какие-либо два выражения. ---- Если <math>f</math> — инволюция, то имеют место следующие соотношения: * <math>\forall a \in D_{f}: f^{-1}(a) = f(a)</math> [основное свойство] * <math>D_{f} = E_{f}</math> * <math>\forall a : f(f(a)) = a</math> * <math>\forall a, \exists b : f(a) = b \land f(b) = a</math> [критерий] == Примеры == Примеры инволюций: * <math>f(x) = -x</math>, заданная на множестве [[w:целое число|целых]] <math>\mathbb{Z}</math>, [[w:рациональное число|рациональных]] <math>\mathbb{Q}</math> или [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>; * простейшие инволюции на множестве [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>: *: <math>\dfrac{a}{x}</math>, <math>a-x</math>, <math>\dfrac{x}{x-1}</math>, <math>\dfrac{x+1}{x-1}</math>, <math>\dfrac{x-1}{x+1}</math>, <math>\dfrac{ax+b}{cx-a}</math>; * инволюция <math>f(x) = \dfrac{b}{x-a} + a</math> при <math>x\in \mathbb{R} \setminus \left\{a\right\}</math> и <math>b\neq 0</math>; * <math>f(x)= \bar{x}</math> — [[w:дополнение множества|дополнение множества]], заданная для подмножеств некоторого универсального множества <math>U</math>; * <math>f(x)= \neg x</math> — [[w:логическое отрицание|логическое отрицание]] [[w:булева алгебра|булевой алгебры]]; * [[w:Симметрия|симметрии]]: [[w:Центральная симметрия|центральная]], [[w:Осевая симметрия|осевая]], [[w:Зеркальная симметрия|зеркальная]]; * [[w:инверсия (геометрия)|инверсия]]; * [[w:комплексное сопряжение|комплексное сопряжение]]; * [[w:преобразование Лежандра|преобразование Лежандра]] * при факторизации обычного тора (точнее, одномерного комплексного тора, ещё точнее, эллиптической кривой) <math>E</math> по инволюции вида <math>x\mapsto -x</math> получается сфера; * Если представить, что <math>f</math> — нажатие на клавишу [[w:выключатель бытовой| бытового накладного выключателя]] (т. е. включить либо выключить свет), то <math>f</math> будет инволюцией. == Важнейшие факты == ;'''Теорема 1'''. : Композиция <math>{f}\circ{g}</math> двух инволюций <math>f</math> и <math>g</math> является инволюцией тогда и только тогда, когда они коммутируют: <math>{f}\circ{g} =g\circ f</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Пусть дана композиция <math>{f}\circ{g}</math>, в которой <math>f</math>, <math>g</math> — инволюции. Это означает, что <math>f=f^{-1}</math> и <math>g=g^{-1}</math>, а также <math>{f}\circ{g}={\left({f}\circ{g}\right)}^{-1}</math>. Имеем: <math>{f}\circ{g}= {\left({f}\circ{g}\right)}^{-1}={g^{-1}}\circ {f^{-1}}={g}\circ{f}</math>. Если <math>{f}\circ{g}</math> — инволюция, то двигаемся слева направо. Обратно, если выполняется равенство <math>{f}\circ{g} =g\circ f</math>, то справа налево. |} <code>Пример 1</code>. Такая композиция <math>\left(f_{1} \circ f_{2}\right) (x) = \left(f_{2} \circ f_{1} \right) (x) = {f_{3}} (x) = -{\dfrac{1}{x}}</math> есть инволюция. Аналогично, если <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math> и <math>g</math>, <math>h</math>, <math>k</math> — инволюции, то и <math>f</math> — инволюция. <code>Пример 2</code>. <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. ; '''Теорема 2'''. : Если <math>{f}</math> — монотонно возрастающая функция, то уравнения <math>{f}(x)=x</math> и <math>f(f(x))=x</math>, или <math>{f}(x)={f^{-1}}(x)</math>, равносильны. Рассмотрим следующую задачу. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>\sqrt{1+\sqrt{x}}=x-1</math>. |- | Перепишем данное уравнение в виде: <math>1+\sqrt{1+\sqrt{x}}=x</math>. Рассмотрим теперь функцию <math>f(x)=1+\sqrt{x}</math>. Тогда полученное уравнение примет вид: <math>f(f(x))=x</math>. Для решений уравнений такого вида применим '''теорему 2'''. Но сначала следует убедиться, что введённая функция <math>f</math> действительно монотонно возрастает. Для того чтобы <math>f(x)</math> была строго возрастающей, достаточно (но не является необходимым условием), чтобы <math>f'(x)>0</math>. В нашем случае получается <math>f'(x)=\dfrac{1}{2\sqrt{x}}>0</math>. В соответствии с приведённой '''теоремой 2''' приходим к равносильному уравнению <math>{f}(x)=x</math>, или <math>1+\sqrt{x}=x</math>, решение которого уже не сложно. Ответ: <math>x = \dfrac{3+\sqrt{5}}{2}.</math> |} ; '''Теорема 3'''. : Функция вида <math>f={h}\circ{g}\circ{h^{-1}}</math> (где <math>h</math> — некоторое биективное отображение) будет инволюцией в том и только в том случае, если функция <math>g</math> — инволюция. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Имеем следующее: <math>f=f^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {\left({h}\circ{g}\circ{h^{-1}}\right)}^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {{h}\circ{g^{-1}}\circ{h^{-1}}} \mid { \circ h} \Longleftrightarrow {h}\circ{g}={h}\circ{g^{-1}} \Longleftrightarrow {h^{-1} \circ } \mid {{h}\circ{g}={h}\circ{g^{-1}}} \Longleftrightarrow g = g^{-1}.</math> Если <math>{f}</math> является инволюцией, то двигаемся слева направо. Обратно, если <math>{g}</math> — инволюция, то справа налево. Теорема доказана. |} ''Замечание''. Ясно, что '''теорема 3''' сохраняет свою силу, если <math>f={h^{-1}}\circ{g}\circ{h}</math>, где <math>h</math> — биекция. <code>Пример 3</code>. В положительных числах такая функция будет как раз инволюцией по доказанной выше теореме: : <math>ln\left(\dfrac{e^x+1}{e^x-1}\right).</math> ; '''Следствие'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Тогда если <math>h</math> — взаимно-однозначное отображение [биекция] множества <math>E</math> на <math>F</math> с обратной биекцией <math>h^{-1}</math>, то композиция <math>h\circ f\circ h^{-1}</math> — инволюция на множестве <math>F</math>. [[File:Involution4.png|Involution4]] {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Утверждение очевидно по предыдущему. ''Указание''. Воспользоваться '''теоремой 3'''. |} ; '''Теорема 4'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Если <math>h</math> — такое отображение из <math>E</math> в <math>E</math>, что <math>h\circ f\circ h = f</math>, то <math>h\circ f</math> и <math>f\circ h</math> — инволюции на <math>E</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Покажем, что из исходного равенства <math>h\circ f\circ h = f</math> и условия <math>f=f^{-1}</math> получается инволютивная функция <math>h\circ f</math>. Итак, : <math>h\circ f\circ h = f \mid { \circ h^{-1}} \Longrightarrow h\circ f = f \circ h^{-1} \Longrightarrow h \circ f = {\left(h \circ f^{-1}\right)}^{-1} \Longrightarrow h \circ f = {\left(h \circ f \right)}^{-1} \mid {\circ {\left(h \circ f \right)}} \Longrightarrow {\left(h \circ f \right)}^{2} = e.</math> Таким образом, композиция <math>h\circ f</math> по определению является инволюцией. Аналогично проводится доказательство для <math>f\circ h</math>. |} {| class="wikitable collapsible collapsed" width="100%" ! Пусть дана функция <math>f=h\circ g\circ h\circ g^{-1}</math>, где <math>g</math> — биекция, а <math>h=h^{-1}</math>. Выяснить, при каком условии <math>f</math> будет инволютивной. |- | <u>''Решение''</u>. Во-первых, функция <math>f</math> будет инволюцией, если выполняется равенство: <math>f=f^{-1}</math>. Во-вторых, стоит заметить, что <math>h \circ f = g\circ h\circ g^{-1} = f^{-1} \circ h </math>. Поэтому <math>f=f^{-1} \Longleftrightarrow f = h \circ f \circ h</math>. Но по '''следствию''' композиция <math>g \circ h \circ g^{-1}</math> является инволюцией, а значит, и <math>h \circ f</math> — тоже инволюция. Наконец, <math> h\circ \mid f = h \circ f \circ h \Longleftrightarrow h\circ f = f \circ h</math>, то есть <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}</math>. ''Ответ'': <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}.</math> |} <code>Пример 4</code>. Функция <math>f(x)= -ln\left(-e^{x}\right)</math>. <u>'''Упражнение'''</u>. Убедитесь, что представленная функция действительно обладает таким свойством. ''Схемой'', или ''строением'', функции <math>f</math> назовём последовательность функций <math>f_{1}, f_{2}, ... , f_{n-1}, f_{n}</math> так, что каждая из них является либо элементарной, либо инволюцией и <math>f=f_{n} \circ f_{n-1} \circ ... \circ f_{2} \circ f_{1}</math>. <code>Пример 5</code>. Пусть <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. Тогда схемой функции <math>f</math> будет <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math>. == Фокус == {| class="wikitable collapsible collapsed" width=100% ! Целое общество гостей, непосвящённых в арифметические тайны, вы можете поразить следующим фокусом. |- | Фокусник просит одного человека написать на бумажке, секретно от него, трёхзначное число, какое этот человек хочет, и затем просит приписать к нему ещё раз то же самое число. Получится шестизначное число, состоящее из трёх повторяющихся цифр. Фокусник предлагает тому же товарищу или его соседу разделить — секретно от него — это число на 7; при этом фокусник заранее предсказывает, что остатка не получится. Результат деления передаётся соседу, который, по предложению ведущего, делит его на 11; и хотя фокусник не знает делимого, он всё же смело утверждает, что и оно разделится без остатка. Полученный результат фокусник направляет следующему соседу, которого просит разделить это число на 13 — деление снова выполняется без остатка, о чём он заранее предупреждает. Результат третьего деления фокусник, не глядя на полученное число, вручает первому товарищу со словами: — Вот число, которое вы задумали! — Так и есть: вы угадали. |} <code>Какова разгадка этого фокуса?</code> ''Указание''. Возьмите за функцию <math>f</math> алгоритм приписывания к числу <math>x\rightleftharpoons \overline{abc}</math>, то есть <math>f(x)= \overline{abcabc}</math>. Так как результат совпадает с исходным числом <math>x\rightleftharpoons \overline{abc}</math>, то <math>f^{-1}</math> над числом — это умножение его на 7, 11 и 13. Осталось найти связь <math>f</math> и <math>f^{-1}</math>. == Лирическое отступление == Приведём пример композиции двух инволюций, которая не будет уже инволюцией. <code>Пример</code>. Функция <math>\tau(x)=\dfrac{1}{1-x}</math> не является инволюцией; её строение таково: <math>\tau=\alpha \circ \beta</math>, где <math>\alpha (x) = \dfrac{1}{x}</math> и <math>\beta (x) = 1-x</math> у нас — обе инволюции. '''''Упражнение'''''. Докажите: для <math>\tau(x)=\dfrac{1}{1-x}</math> верно, что <math>\tau \neq {\tau}^{-1}</math>. ''Замечание''. Функция <math>{{\tau}^{-1}}{\left(x\right)}=1-{\dfrac{1}{x}}=\dfrac{x-1}{x}</math> со схемой <math>{\tau}^{-1}=\beta \circ \alpha</math> также не есть инволюция. Легко видеть, что <math>\alpha \circ {{\tau}^{-1}}</math> — инволюция. Делаем вывод, что композиция инволюции и неинволютивной функции может давать инволюцию в результате. Вопрос: ''в каком случае это происходит?'' Перед тем, как ответить на этот вопрос, сперва-наперво выясним, а каким свойством, в принципе, обладает введённая функция <math>\tau(x)=\dfrac{1}{1-x}</math>. Вычислим <math>{\tau}^{2}(x)</math>. У нас получится: : <math>{\tau}^{2}(x)=\dfrac{1}{1-\dfrac{1}{1-x}} = \dfrac{1-x}{1-x-1}=\dfrac{x-1}{x}={\tau}^{-1}(x).</math> Значит, <math>{\tau}^{3}=e</math>. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>f{\left(x\right)}\cdot {f{\left(\dfrac{1}{1-x}\right)}}=\dfrac{1-x}{x}</math>. |- | <code>Шаг 1</code> Напишем схему данного уравнения: <math>f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}}=-{\tau}^{-1}(x)</math>. <code>Шаг 2</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}^{-1}(x)</math>. Получим: : <center><math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(\tau({\tau}^{-1}(x))\right)}}=-{\tau}^{-1}({\tau}^{-1}(x)) \Longrightarrow f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}^{-2}(x).</math></center> Но так как <math>{\tau}^{2}(x)={\tau}^{-1}(x)</math>, то <math>{\tau}^{-2}(x)={\tau}(x)</math>. Поэтому <math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}(x)</math>. <code>Шаг 3</code> Теперь из результатов <code>Шага 1</code> и <code>Шага 2</code> делаем простой вывод: : <center><math>f(x)=\dfrac{-{\tau(x)}}{f{\left({\tau}^{-1}(x)\right)}} = \dfrac{{-{\tau}}^{-1}(x)}{f{\left({\tau}(x)\right)}}.</math></center> <code>Шаг 4</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}(x)</math>. Имеем: : <center><math>f{\left({\tau}^{-1}(x)\right)}=\dfrac{-x}{f{\left({\tau}(x)\right)}}=\dfrac{{-{\tau}}(x)}{f{\left(x\right)}}.</math></center> <code>Шаг 5</code> Наконец-то, мы <br><br><math> \begin{cases} \begin{array} {rcrcc} \dfrac{-x}{f{\left({\tau}(x)\right)}} = \dfrac{{-{\tau}}(x)}{f{\left(x\right)}}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases} \Longrightarrow \begin{cases} \begin{array} {rcrcc} {f{\left({\tau}(x)\right)}} = \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases}.</math> <code>Шаг 6</code> Подставим выражение <math>{f{\left({\tau}(x)\right)}}</math> во вторую строчку системы. Итак, : <math>f{\left(x\right)}\cdot \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)} = -{\tau}^{-1}(x) \Longleftrightarrow f{\left(x\right)}\cdot f{\left(x\right)} = \dfrac{{-{\tau}}(x) \cdot {{\tau}^{-1}{\left(x\right)}}}{x}.</math> <u>'''Ответ в общем виде'''</u>: <math>f{\left(x\right)} = \pm{\sqrt{\dfrac{{-{\tau}}(x) \cdot {{\tau}^{-1}{\left(x\right)}}}{x}}}.</math> |} == Инволюция в алгебре == [[w:Перестановка|Перестановка]] <math>\tau</math> является инволюцией, если <math>\tau\circ\tau=id</math>, каждая инволюция является произведением непересекающихся транспозиций, например: : <math>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 5 & 7 & 4 & 3 & 1 & 8 & 2 & 6\end{pmatrix} = (1,5)(2,7)(3,4)(6,8)</math>. Число инволюций в [[w:Группа перестановок|группе перестановок]] порядка <math>n</math> определяется по формулам: * <math> a(0) = 1,\ a(1) = 1,\ a(n) = a(n-1) + (n-1)a(n-2),\ n>1</math> (рекуррентная формула), * <math>a(n) = \sum_{k=0}^{[ n/2 ]}{\frac{n!}{2^k\cdot (n-2k)!\cdot k!}}</math>, (первые значения <math>a(n)</math>: 1, {{w:nums|link=nrl|1|2|4|10|26|76|232|764|2620|9496|35696|140152}}<ref>{{OEIS long|A000085|lc=1}}</ref>). Свойства инволюции обеспечивают ей широкое применение в различных приложения, например, инволютивные преобразования над пространством булевых векторов используются в различных схемах построения симметричных [[w:криптоалгоритм|криптоалгоритм]]ов, таких как [[w:Сеть Фейстеля|сети Фейстеля]] и [[w:SP-сеть|подстановочно-перестановочные сети]]. == Примечания == o3gc2r9b0wtm1wvx77tt0c3g2g2t1b7 220987 220986 2022-07-19T20:50:42Z Va musinov 69698 wikitext text/x-wiki '''Инволю́ция''' (от {{lang-la|involutio}} — свёртывание, завиток) — нетождественное преобразование, которое является [[w:обратная функция|обратным]] самому себе, то есть своей собственной [[w:обратная функция|инверсией]]. Это [[w:унарная операция|унарная операция]]. Формально, функция <math>f</math> называется инволюцией, если <math>f(f(x)) = x</math> для всякого <math>x</math> из [[w:Область определения функции|области определения функции]] <math>f</math>. Иногда пишут: <math>f\circ f= {f}^{2}=id</math>, где <math>id</math> обозначает тождественное преобразование. Вместо <math>id(x)</math> используют запись: <math>e(x)=x</math>. Таким образом, двойное применение функции <math>f</math> даёт исходное значение. == Свойства == Любая инволюция — это [[w:биекция|биекция]]. Если преобразование <math>f</math> инволютивное, то для любого выражения <math>A</math> и его образа <math>B=f(A)</math> имеем <math>f(B)=A</math>. В самом деле, <math>f(B)= f(f(A))=id(A)={id}_{A}=A</math>. '''''Критерий инволюции'''''. Функция <math>f</math> является инволюцией тогда и только тогда, когда для всякого выражения <math>A</math> существует такое выражение <math>B</math>, что <math>f(A)=B\neq A</math> и <math>f(B)=A</math>. Другими словами, преобразование является инволюцией в том и только в том случае, когда оно меняет местами какие-либо два выражения. ---- Если <math>f</math> — инволюция, то имеют место следующие соотношения: * <math>\forall a \in D_{f}: f^{-1}(a) = f(a)</math> [основное свойство] * <math>D_{f} = E_{f}</math> * <math>\forall a : f(f(a)) = a</math> * <math>\forall a, \exists b : f(a) = b \land f(b) = a</math> [критерий] == Примеры == Примеры инволюций: * <math>f(x) = -x</math>, заданная на множестве [[w:целое число|целых]] <math>\mathbb{Z}</math>, [[w:рациональное число|рациональных]] <math>\mathbb{Q}</math> или [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>; * простейшие инволюции на множестве [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>: *: <math>\dfrac{a}{x}</math>, <math>a-x</math>, <math>\dfrac{x}{x-1}</math>, <math>\dfrac{x+1}{x-1}</math>, <math>\dfrac{x-1}{x+1}</math>, <math>\dfrac{ax+b}{cx-a}</math>; * инволюция <math>f(x) = \dfrac{b}{x-a} + a</math> при <math>x\in \mathbb{R} \setminus \left\{a\right\}</math> и <math>b\neq 0</math>; * <math>f(x)= \bar{x}</math> — [[w:дополнение множества|дополнение множества]], заданная для подмножеств некоторого универсального множества <math>U</math>; * <math>f(x)= \neg x</math> — [[w:логическое отрицание|логическое отрицание]] [[w:булева алгебра|булевой алгебры]]; * [[w:Симметрия|симметрии]]: [[w:Центральная симметрия|центральная]], [[w:Осевая симметрия|осевая]], [[w:Зеркальная симметрия|зеркальная]]; * [[w:инверсия (геометрия)|инверсия]]; * [[w:комплексное сопряжение|комплексное сопряжение]]; * [[w:преобразование Лежандра|преобразование Лежандра]] * при факторизации обычного тора (точнее, одномерного комплексного тора, ещё точнее, эллиптической кривой) <math>E</math> по инволюции вида <math>x\mapsto -x</math> получается сфера; * Если представить, что <math>f</math> — нажатие на клавишу [[w:выключатель бытовой| бытового накладного выключателя]] (т. е. включить либо выключить свет), то <math>f</math> будет инволюцией. == Важнейшие факты == ;'''Теорема 1'''. : Композиция <math>{f}\circ{g}</math> двух инволюций <math>f</math> и <math>g</math> является инволюцией тогда и только тогда, когда они коммутируют: <math>{f}\circ{g} =g\circ f</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Пусть дана композиция <math>{f}\circ{g}</math>, в которой <math>f</math>, <math>g</math> — инволюции. Это означает, что <math>f=f^{-1}</math> и <math>g=g^{-1}</math>, а также <math>{f}\circ{g}={\left({f}\circ{g}\right)}^{-1}</math>. Имеем: <math>{f}\circ{g}= {\left({f}\circ{g}\right)}^{-1}={g^{-1}}\circ {f^{-1}}={g}\circ{f}</math>. Если <math>{f}\circ{g}</math> — инволюция, то двигаемся слева направо. Обратно, если выполняется равенство <math>{f}\circ{g} =g\circ f</math>, то справа налево. |} <code>Пример 1</code>. Такая композиция <math>\left(f_{1} \circ f_{2}\right) (x) = \left(f_{2} \circ f_{1} \right) (x) = {f_{3}} (x) = -{\dfrac{1}{x}}</math> есть инволюция. Аналогично, если <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math> и <math>g</math>, <math>h</math>, <math>k</math> — инволюции, то и <math>f</math> — инволюция. <code>Пример 2</code>. <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. ; '''Теорема 2'''. : Если <math>{f}</math> — монотонно возрастающая функция, то уравнения <math>{f}(x)=x</math> и <math>f(f(x))=x</math>, или <math>{f}(x)={f^{-1}}(x)</math>, равносильны. Рассмотрим следующую задачу. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>\sqrt{1+\sqrt{x}}=x-1</math>. |- | Перепишем данное уравнение в виде: <math>1+\sqrt{1+\sqrt{x}}=x</math>. Рассмотрим теперь функцию <math>f(x)=1+\sqrt{x}</math>. Тогда полученное уравнение примет вид: <math>f(f(x))=x</math>. Для решений уравнений такого вида применим '''теорему 2'''. Но сначала следует убедиться, что введённая функция <math>f</math> действительно монотонно возрастает. Для того чтобы <math>f(x)</math> была строго возрастающей, достаточно (но не является необходимым условием), чтобы <math>f'(x)>0</math>. В нашем случае получается <math>f'(x)=\dfrac{1}{2\sqrt{x}}>0</math>. В соответствии с приведённой '''теоремой 2''' приходим к равносильному уравнению <math>{f}(x)=x</math>, или <math>1+\sqrt{x}=x</math>, решение которого уже не сложно. Ответ: <math>x = \dfrac{3+\sqrt{5}}{2}.</math> |} ; '''Теорема 3'''. : Функция вида <math>f={h}\circ{g}\circ{h^{-1}}</math> (где <math>h</math> — некоторое биективное отображение) будет инволюцией в том и только в том случае, если функция <math>g</math> — инволюция. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Имеем следующее: <math>f=f^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {\left({h}\circ{g}\circ{h^{-1}}\right)}^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {{h}\circ{g^{-1}}\circ{h^{-1}}} \mid { \circ h} \Longleftrightarrow {h}\circ{g}={h}\circ{g^{-1}} \Longleftrightarrow {h^{-1} \circ } \mid {{h}\circ{g}={h}\circ{g^{-1}}} \Longleftrightarrow g = g^{-1}.</math> Если <math>{f}</math> является инволюцией, то двигаемся слева направо. Обратно, если <math>{g}</math> — инволюция, то справа налево. Теорема доказана. |} ''Замечание''. Ясно, что '''теорема 3''' сохраняет свою силу, если <math>f={h^{-1}}\circ{g}\circ{h}</math>, где <math>h</math> — биекция. <code>Пример 3</code>. В положительных числах такая функция будет как раз инволюцией по доказанной выше теореме: : <math>ln\left(\dfrac{e^x+1}{e^x-1}\right).</math> ; '''Следствие'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Тогда если <math>h</math> — взаимно-однозначное отображение [биекция] множества <math>E</math> на <math>F</math> с обратной биекцией <math>h^{-1}</math>, то композиция <math>h\circ f\circ h^{-1}</math> — инволюция на множестве <math>F</math>. [[File:Involution4.png|Involution4]] {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Утверждение очевидно по предыдущему. ''Указание''. Воспользоваться '''теоремой 3'''. |} ; '''Теорема 4'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Если <math>h</math> — такое отображение из <math>E</math> в <math>E</math>, что <math>h\circ f\circ h = f</math>, то <math>h\circ f</math> и <math>f\circ h</math> — инволюции на <math>E</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Покажем, что из исходного равенства <math>h\circ f\circ h = f</math> и условия <math>f=f^{-1}</math> получается инволютивная функция <math>h\circ f</math>. Итак, : <math>h\circ f\circ h = f \mid { \circ h^{-1}} \Longrightarrow h\circ f = f \circ h^{-1} \Longrightarrow h \circ f = {\left(h \circ f^{-1}\right)}^{-1} \Longrightarrow h \circ f = {\left(h \circ f \right)}^{-1} \mid {\circ {\left(h \circ f \right)}} \Longrightarrow {\left(h \circ f \right)}^{2} = e.</math> Таким образом, композиция <math>h\circ f</math> по определению является инволюцией. Аналогично проводится доказательство для <math>f\circ h</math>. |} {| class="wikitable collapsible collapsed" width="100%" ! Пусть дана функция <math>f=h\circ g\circ h\circ g^{-1}</math>, где <math>g</math> — биекция, а <math>h=h^{-1}</math>. Выяснить, при каком условии <math>f</math> будет инволютивной. |- | <u>''Решение''</u>. Во-первых, функция <math>f</math> будет инволюцией, если выполняется равенство: <math>f=f^{-1}</math>. Во-вторых, стоит заметить, что <math>h \circ f = g\circ h\circ g^{-1} = f^{-1} \circ h </math>. Поэтому <math>f=f^{-1} \Longleftrightarrow f = h \circ f \circ h</math>. Но по '''следствию''' композиция <math>g \circ h \circ g^{-1}</math> является инволюцией, а значит, и <math>h \circ f</math> — тоже инволюция. Наконец, <math> h\circ \mid f = h \circ f \circ h \Longleftrightarrow h\circ f = f \circ h</math>, то есть <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}</math>. ''Ответ'': <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}.</math> |} <code>Пример 4</code>. Функция <math>f(x)= -ln\left(-e^{x}\right)</math>. <u>'''Упражнение'''</u>. Убедитесь, что представленная функция действительно обладает таким свойством. ''Схемой'', или ''строением'', функции <math>f</math> назовём последовательность функций <math>f_{1}, f_{2}, ... , f_{n-1}, f_{n}</math> так, что каждая из них является либо элементарной, либо инволюцией и <math>f=f_{n} \circ f_{n-1} \circ ... \circ f_{2} \circ f_{1}</math>. <code>Пример 5</code>. Пусть <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. Тогда схемой функции <math>f</math> будет <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math>. == Фокус == {| class="wikitable collapsible collapsed" width=100% ! Целое общество гостей, непосвящённых в арифметические тайны, вы можете поразить следующим фокусом. |- | Фокусник просит одного человека написать на бумажке, секретно от него, трёхзначное число, какое этот человек хочет, и затем просит приписать к нему ещё раз то же самое число. Получится шестизначное число, состоящее из трёх повторяющихся цифр. Фокусник предлагает тому же товарищу или его соседу разделить — секретно от него — это число на 7; при этом фокусник заранее предсказывает, что остатка не получится. Результат деления передаётся соседу, который, по предложению ведущего, делит его на 11; и хотя фокусник не знает делимого, он всё же смело утверждает, что и оно разделится без остатка. Полученный результат фокусник направляет следующему соседу, которого просит разделить это число на 13 — деление снова выполняется без остатка, о чём он заранее предупреждает. Результат третьего деления фокусник, не глядя на полученное число, вручает первому товарищу со словами: — Вот число, которое вы задумали! — Так и есть: вы угадали. |} <code>Какова разгадка этого фокуса?</code> ''Указание''. Возьмите за функцию <math>f</math> алгоритм приписывания к числу <math>x\rightleftharpoons \overline{abc}</math>, то есть <math>f(x)= \overline{abcabc}</math>. Так как результат совпадает с исходным числом <math>x\rightleftharpoons \overline{abc}</math>, то <math>f^{-1}</math> над числом — это умножение его на 7, 11 и 13. Осталось найти связь <math>f</math> и <math>f^{-1}</math>. == Лирическое отступление == Приведём пример композиции двух инволюций, которая не будет уже инволюцией. <code>Пример</code>. Функция <math>\tau(x)=\dfrac{1}{1-x}</math> не является инволюцией; её строение таково: <math>\tau=\alpha \circ \beta</math>, где <math>\alpha (x) = \dfrac{1}{x}</math> и <math>\beta (x) = 1-x</math> у нас — обе инволюции. '''''Упражнение'''''. Докажите: для <math>\tau(x)=\dfrac{1}{1-x}</math> верно, что <math>\tau \neq {\tau}^{-1}</math>. ''Замечание''. Функция <math>{{\tau}^{-1}}{\left(x\right)}=1-{\dfrac{1}{x}}=\dfrac{x-1}{x}</math> со схемой <math>{\tau}^{-1}=\beta \circ \alpha</math> также не есть инволюция. Легко видеть, что <math>\alpha \circ {{\tau}^{-1}}</math> — инволюция. Делаем вывод, что композиция инволюции и неинволютивной функции может давать инволюцию в результате. Вопрос: ''в каком случае это происходит?'' Перед тем, как ответить на этот вопрос, сперва-наперво выясним, а каким свойством, в принципе, обладает введённая функция <math>\tau(x)=\dfrac{1}{1-x}</math>. Вычислим <math>{\tau}^{2}(x)</math>. У нас получится: : <math>{\tau}^{2}(x)=\dfrac{1}{1-\dfrac{1}{1-x}} = \dfrac{1-x}{1-x-1}=\dfrac{x-1}{x}={\tau}^{-1}(x).</math> Значит, <math>{\tau}^{3}=e</math>. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>f{\left(x\right)}\cdot {f{\left(\dfrac{1}{1-x}\right)}}=\dfrac{1-x}{x}</math>. |- | <code>Шаг 1</code> Напишем схему данного уравнения: <math>f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}}=-{\tau}^{-1}(x)</math>. <code>Шаг 2</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}^{-1}(x)</math>. Получим: : <center><math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(\tau({\tau}^{-1}(x))\right)}}=-{\tau}^{-1}({\tau}^{-1}(x)) \Longrightarrow f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}^{-2}(x).</math></center> Но так как <math>{\tau}^{2}(x)={\tau}^{-1}(x)</math>, то <math>{\tau}^{-2}(x)={\tau}(x)</math>. Поэтому <math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}(x)</math>. <code>Шаг 3</code> Теперь из результатов <code>Шага 1</code> и <code>Шага 2</code> делаем простой вывод: : <center><math>f(x)=\dfrac{-{\tau(x)}}{f{\left({\tau}^{-1}(x)\right)}} = \dfrac{{-{\tau}}^{-1}(x)}{f{\left({\tau}(x)\right)}}.</math></center> <code>Шаг 4</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}(x)</math>. Имеем: : <center><math>f{\left({\tau}^{-1}(x)\right)}=\dfrac{-x}{f{\left({\tau}(x)\right)}}=\dfrac{{-{\tau}}(x)}{f{\left(x\right)}}.</math></center> <code>Шаг 5</code> Наконец-то, мы <br><br><math> \begin{cases} \begin{array} {rcrcc} \dfrac{-x}{f{\left({\tau}(x)\right)}} = \dfrac{{-{\tau}}(x)}{f{\left(x\right)}}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases} \Longrightarrow \begin{cases} \begin{array} {rcrcc} {f{\left({\tau}(x)\right)}} = \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases}.</math> <code>Шаг 6</code> Подставим выражение <math>{f{\left({\tau}(x)\right)}}</math> во вторую строчку системы. Итак, : <math>f{\left(x\right)}\cdot \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)} = -{\tau}^{-1}(x) \Longleftrightarrow f{\left(x\right)}\cdot f{\left(x\right)} = \dfrac{{-{\tau}}(x) \cdot {{\tau}^{-1}{\left(x\right)}}}{x}.</math> <u>'''Ответ'''</u>: <math>f{\left(x\right)} = \pm{\sqrt{\dfrac{{-{\tau}}(x) \cdot {{\tau}^{-1}{\left(x\right)}}}{x}}} = \pm{\dfrac{1}{x}}.</math> |} == Инволюция в алгебре == [[w:Перестановка|Перестановка]] <math>\tau</math> является инволюцией, если <math>\tau\circ\tau=id</math>, каждая инволюция является произведением непересекающихся транспозиций, например: : <math>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 5 & 7 & 4 & 3 & 1 & 8 & 2 & 6\end{pmatrix} = (1,5)(2,7)(3,4)(6,8)</math>. Число инволюций в [[w:Группа перестановок|группе перестановок]] порядка <math>n</math> определяется по формулам: * <math> a(0) = 1,\ a(1) = 1,\ a(n) = a(n-1) + (n-1)a(n-2),\ n>1</math> (рекуррентная формула), * <math>a(n) = \sum_{k=0}^{[ n/2 ]}{\frac{n!}{2^k\cdot (n-2k)!\cdot k!}}</math>, (первые значения <math>a(n)</math>: 1, {{w:nums|link=nrl|1|2|4|10|26|76|232|764|2620|9496|35696|140152}}<ref>{{OEIS long|A000085|lc=1}}</ref>). Свойства инволюции обеспечивают ей широкое применение в различных приложения, например, инволютивные преобразования над пространством булевых векторов используются в различных схемах построения симметричных [[w:криптоалгоритм|криптоалгоритм]]ов, таких как [[w:Сеть Фейстеля|сети Фейстеля]] и [[w:SP-сеть|подстановочно-перестановочные сети]]. == Примечания == n1lgupiwnjyvhgp3h0qx3bvw8a9ymj0 220988 220987 2022-07-19T20:52:50Z Va musinov 69698 wikitext text/x-wiki '''Инволю́ция''' (от {{lang-la|involutio}} — свёртывание, завиток) — нетождественное преобразование, которое является [[w:обратная функция|обратным]] самому себе, то есть своей собственной [[w:обратная функция|инверсией]]. Это [[w:унарная операция|унарная операция]]. Формально, функция <math>f</math> называется инволюцией, если <math>f(f(x)) = x</math> для всякого <math>x</math> из [[w:Область определения функции|области определения функции]] <math>f</math>. Иногда пишут: <math>f\circ f= {f}^{2}=id</math>, где <math>id</math> обозначает тождественное преобразование. Вместо <math>id(x)</math> используют запись: <math>e(x)=x</math>. Таким образом, двойное применение функции <math>f</math> даёт исходное значение. == Свойства == Любая инволюция — это [[w:биекция|биекция]]. Если преобразование <math>f</math> инволютивное, то для любого выражения <math>A</math> и его образа <math>B=f(A)</math> имеем <math>f(B)=A</math>. В самом деле, <math>f(B)= f(f(A))=id(A)={id}_{A}=A</math>. '''''Критерий инволюции'''''. Функция <math>f</math> является инволюцией тогда и только тогда, когда для всякого выражения <math>A</math> существует такое выражение <math>B</math>, что <math>f(A)=B\neq A</math> и <math>f(B)=A</math>. Другими словами, преобразование является инволюцией в том и только в том случае, когда оно меняет местами какие-либо два выражения. ---- Если <math>f</math> — инволюция, то имеют место следующие соотношения: * <math>\forall a \in D_{f}: f^{-1}(a) = f(a)</math> [основное свойство] * <math>D_{f} = E_{f}</math> * <math>\forall a : f(f(a)) = a</math> * <math>\forall a, \exists b : f(a) = b \land f(b) = a</math> [критерий] == Примеры == Примеры инволюций: * <math>f(x) = -x</math>, заданная на множестве [[w:целое число|целых]] <math>\mathbb{Z}</math>, [[w:рациональное число|рациональных]] <math>\mathbb{Q}</math> или [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>; * простейшие инволюции на множестве [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>: *: <math>\dfrac{a}{x}</math>, <math>a-x</math>, <math>\dfrac{x}{x-1}</math>, <math>\dfrac{x+1}{x-1}</math>, <math>\dfrac{x-1}{x+1}</math>, <math>\dfrac{ax+b}{cx-a}</math>; * инволюция <math>f(x) = \dfrac{b}{x-a} + a</math> при <math>x\in \mathbb{R} \setminus \left\{a\right\}</math> и <math>b\neq 0</math>; * <math>f(x)= \bar{x}</math> — [[w:дополнение множества|дополнение множества]], заданная для подмножеств некоторого универсального множества <math>U</math>; * <math>f(x)= \neg x</math> — [[w:логическое отрицание|логическое отрицание]] [[w:булева алгебра|булевой алгебры]]; * [[w:Симметрия|симметрии]]: [[w:Центральная симметрия|центральная]], [[w:Осевая симметрия|осевая]], [[w:Зеркальная симметрия|зеркальная]]; * [[w:инверсия (геометрия)|инверсия]]; * [[w:комплексное сопряжение|комплексное сопряжение]]; * [[w:преобразование Лежандра|преобразование Лежандра]] * при факторизации обычного тора (точнее, одномерного комплексного тора, ещё точнее, эллиптической кривой) <math>E</math> по инволюции вида <math>x\mapsto -x</math> получается сфера; * Если представить, что <math>f</math> — нажатие на клавишу [[w:выключатель бытовой| бытового накладного выключателя]] (т. е. включить либо выключить свет), то <math>f</math> будет инволюцией. == Важнейшие факты == ;'''Теорема 1'''. : Композиция <math>{f}\circ{g}</math> двух инволюций <math>f</math> и <math>g</math> является инволюцией тогда и только тогда, когда они коммутируют: <math>{f}\circ{g} =g\circ f</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Пусть дана композиция <math>{f}\circ{g}</math>, в которой <math>f</math>, <math>g</math> — инволюции. Это означает, что <math>f=f^{-1}</math> и <math>g=g^{-1}</math>, а также <math>{f}\circ{g}={\left({f}\circ{g}\right)}^{-1}</math>. Имеем: <math>{f}\circ{g}= {\left({f}\circ{g}\right)}^{-1}={g^{-1}}\circ {f^{-1}}={g}\circ{f}</math>. Если <math>{f}\circ{g}</math> — инволюция, то двигаемся слева направо. Обратно, если выполняется равенство <math>{f}\circ{g} =g\circ f</math>, то справа налево. |} <code>Пример 1</code>. Такая композиция <math>\left(f_{1} \circ f_{2}\right) (x) = \left(f_{2} \circ f_{1} \right) (x) = {f_{3}} (x) = -{\dfrac{1}{x}}</math> есть инволюция. Аналогично, если <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math> и <math>g</math>, <math>h</math>, <math>k</math> — инволюции, то и <math>f</math> — инволюция. <code>Пример 2</code>. <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. ; '''Теорема 2'''. : Если <math>{f}</math> — монотонно возрастающая функция, то уравнения <math>{f}(x)=x</math> и <math>f(f(x))=x</math>, или <math>{f}(x)={f^{-1}}(x)</math>, равносильны. Рассмотрим следующую задачу. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>\sqrt{1+\sqrt{x}}=x-1</math>. |- | Перепишем данное уравнение в виде: <math>1+\sqrt{1+\sqrt{x}}=x</math>. Рассмотрим теперь функцию <math>f(x)=1+\sqrt{x}</math>. Тогда полученное уравнение примет вид: <math>f(f(x))=x</math>. Для решений уравнений такого вида применим '''теорему 2'''. Но сначала следует убедиться, что введённая функция <math>f</math> действительно монотонно возрастает. Для того чтобы <math>f(x)</math> была строго возрастающей, достаточно (но не является необходимым условием), чтобы <math>f'(x)>0</math>. В нашем случае получается <math>f'(x)=\dfrac{1}{2\sqrt{x}}>0</math>. В соответствии с приведённой '''теоремой 2''' приходим к равносильному уравнению <math>{f}(x)=x</math>, или <math>1+\sqrt{x}=x</math>, решение которого уже не сложно. Ответ: <math>x = \dfrac{3+\sqrt{5}}{2}.</math> |} ; '''Теорема 3'''. : Функция вида <math>f={h}\circ{g}\circ{h^{-1}}</math> (где <math>h</math> — некоторое биективное отображение) будет инволюцией в том и только в том случае, если функция <math>g</math> — инволюция. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Имеем следующее: <math>f=f^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {\left({h}\circ{g}\circ{h^{-1}}\right)}^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {{h}\circ{g^{-1}}\circ{h^{-1}}} \mid { \circ h} \Longleftrightarrow {h}\circ{g}={h}\circ{g^{-1}} \Longleftrightarrow {h^{-1} \circ } \mid {{h}\circ{g}={h}\circ{g^{-1}}} \Longleftrightarrow g = g^{-1}.</math> Если <math>{f}</math> является инволюцией, то двигаемся слева направо. Обратно, если <math>{g}</math> — инволюция, то справа налево. Теорема доказана. |} ''Замечание''. Ясно, что '''теорема 3''' сохраняет свою силу, если <math>f={h^{-1}}\circ{g}\circ{h}</math>, где <math>h</math> — биекция. <code>Пример 3</code>. В положительных числах такая функция будет как раз инволюцией по доказанной выше теореме: : <math>ln\left(\dfrac{e^x+1}{e^x-1}\right).</math> ; '''Следствие'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Тогда если <math>h</math> — взаимно-однозначное отображение [биекция] множества <math>E</math> на <math>F</math> с обратной биекцией <math>h^{-1}</math>, то композиция <math>h\circ f\circ h^{-1}</math> — инволюция на множестве <math>F</math>. [[File:Involution4.png|Involution4]] {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Утверждение очевидно по предыдущему. ''Указание''. Воспользоваться '''теоремой 3'''. |} ; '''Теорема 4'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Если <math>h</math> — такое отображение из <math>E</math> в <math>E</math>, что <math>h\circ f\circ h = f</math>, то <math>h\circ f</math> и <math>f\circ h</math> — инволюции на <math>E</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Покажем, что из исходного равенства <math>h\circ f\circ h = f</math> и условия <math>f=f^{-1}</math> получается инволютивная функция <math>h\circ f</math>. Итак, : <math>h\circ f\circ h = f \mid { \circ h^{-1}} \Longrightarrow h\circ f = f \circ h^{-1} \Longrightarrow h \circ f = {\left(h \circ f^{-1}\right)}^{-1} \Longrightarrow h \circ f = {\left(h \circ f \right)}^{-1} \mid {\circ {\left(h \circ f \right)}} \Longrightarrow {\left(h \circ f \right)}^{2} = e.</math> Таким образом, композиция <math>h\circ f</math> по определению является инволюцией. Аналогично проводится доказательство для <math>f\circ h</math>. |} {| class="wikitable collapsible collapsed" width="100%" ! Пусть дана функция <math>f=h\circ g\circ h\circ g^{-1}</math>, где <math>g</math> — биекция, а <math>h=h^{-1}</math>. Выяснить, при каком условии <math>f</math> будет инволютивной. |- | <u>''Решение''</u>. Во-первых, функция <math>f</math> будет инволюцией, если выполняется равенство: <math>f=f^{-1}</math>. Во-вторых, стоит заметить, что <math>h \circ f = g\circ h\circ g^{-1} = f^{-1} \circ h </math>. Поэтому <math>f=f^{-1} \Longleftrightarrow f = h \circ f \circ h</math>. Но по '''следствию''' композиция <math>g \circ h \circ g^{-1}</math> является инволюцией, а значит, и <math>h \circ f</math> — тоже инволюция. Наконец, <math> h\circ \mid f = h \circ f \circ h \Longleftrightarrow h\circ f = f \circ h</math>, то есть <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}</math>. ''Ответ'': <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}.</math> |} <code>Пример 4</code>. Функция <math>f(x)= -ln\left(-e^{x}\right)</math>. <u>'''Упражнение'''</u>. Убедитесь, что представленная функция действительно обладает таким свойством. ''Схемой'', или ''строением'', функции <math>f</math> назовём последовательность функций <math>f_{1}, f_{2}, ... , f_{n-1}, f_{n}</math> так, что каждая из них является либо элементарной, либо инволюцией и <math>f=f_{n} \circ f_{n-1} \circ ... \circ f_{2} \circ f_{1}</math>. <code>Пример 5</code>. Пусть <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. Тогда схемой функции <math>f</math> будет <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math>. == Фокус == {| class="wikitable collapsible collapsed" width=100% ! Целое общество гостей, непосвящённых в арифметические тайны, вы можете поразить следующим фокусом. |- | Фокусник просит одного человека написать на бумажке, секретно от него, трёхзначное число, какое этот человек хочет, и затем просит приписать к нему ещё раз то же самое число. Получится шестизначное число, состоящее из трёх повторяющихся цифр. Фокусник предлагает тому же товарищу или его соседу разделить — секретно от него — это число на 7; при этом фокусник заранее предсказывает, что остатка не получится. Результат деления передаётся соседу, который, по предложению ведущего, делит его на 11; и хотя фокусник не знает делимого, он всё же смело утверждает, что и оно разделится без остатка. Полученный результат фокусник направляет следующему соседу, которого просит разделить это число на 13 — деление снова выполняется без остатка, о чём он заранее предупреждает. Результат третьего деления фокусник, не глядя на полученное число, вручает первому товарищу со словами: — Вот число, которое вы задумали! — Так и есть: вы угадали. |} <code>Какова разгадка этого фокуса?</code> ''Указание''. Возьмите за функцию <math>f</math> алгоритм приписывания к числу <math>x\rightleftharpoons \overline{abc}</math>, то есть <math>f(x)= \overline{abcabc}</math>. Так как результат совпадает с исходным числом <math>x\rightleftharpoons \overline{abc}</math>, то <math>f^{-1}</math> над числом — это умножение его на 7, 11 и 13. Осталось найти связь <math>f</math> и <math>f^{-1}</math>. == Лирическое отступление == Приведём пример композиции двух инволюций, которая не будет уже инволюцией. <code>Пример</code>. Функция <math>\tau(x)=\dfrac{1}{1-x}</math> не является инволюцией; её строение таково: <math>\tau=\alpha \circ \beta</math>, где <math>\alpha (x) = \dfrac{1}{x}</math> и <math>\beta (x) = 1-x</math> у нас — обе инволюции. '''''Упражнение'''''. Докажите: для <math>\tau(x)=\dfrac{1}{1-x}</math> верно, что <math>\tau \neq {\tau}^{-1}</math>. ''Замечание''. Функция <math>{{\tau}^{-1}}{\left(x\right)}=1-{\dfrac{1}{x}}=\dfrac{x-1}{x}</math> со схемой <math>{\tau}^{-1}=\beta \circ \alpha</math> также не есть инволюция. Легко видеть, что <math>\alpha \circ {{\tau}^{-1}}</math> — инволюция. Делаем вывод, что композиция инволюции и неинволютивной функции может давать инволюцию в результате. Вопрос: ''в каком случае это происходит?'' Перед тем, как ответить на этот вопрос, сперва-наперво выясним, а каким свойством, в принципе, обладает введённая функция <math>\tau(x)=\dfrac{1}{1-x}</math>. Вычислим <math>{\tau}^{2}(x)</math>. У нас получится: : <math>{\tau}^{2}(x)=\dfrac{1}{1-\dfrac{1}{1-x}} = \dfrac{1-x}{1-x-1}=\dfrac{x-1}{x}={\tau}^{-1}(x).</math> Значит, <math>{\tau}^{3}=e</math>. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>f{\left(x\right)}\cdot {f{\left(\dfrac{1}{1-x}\right)}}=\dfrac{1-x}{x}</math>. |- | <code>Шаг 1</code> Напишем схему данного уравнения: <math>f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}}=-{\tau}^{-1}(x)</math>. <code>Шаг 2</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}^{-1}(x)</math>. Получим: : <center><math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(\tau({\tau}^{-1}(x))\right)}}=-{\tau}^{-1}({\tau}^{-1}(x)) \Longrightarrow f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}^{-2}(x).</math></center> Но так как <math>{\tau}^{2}(x)={\tau}^{-1}(x)</math>, то <math>{\tau}^{-2}(x)={\tau}(x)</math>. Поэтому <math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}(x)</math>. <code>Шаг 3</code> Теперь из результатов <code>Шага 1</code> и <code>Шага 2</code> делаем простой вывод: : <center><math>f(x)=\dfrac{-{\tau(x)}}{f{\left({\tau}^{-1}(x)\right)}} = \dfrac{{-{\tau}}^{-1}(x)}{f{\left({\tau}(x)\right)}}.</math></center> <code>Шаг 4</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}(x)</math>. Имеем: : <center><math>f{\left({\tau}^{-1}(x)\right)}=\dfrac{-x}{f{\left({\tau}(x)\right)}}=\dfrac{{-{\tau}}(x)}{f{\left(x\right)}}.</math></center> <code>Шаг 5</code> Наконец-то, мы <br><br><math> \begin{cases} \begin{array} {rcrcc} \dfrac{-x}{f{\left({\tau}(x)\right)}} = \dfrac{{-{\tau}}(x)}{f{\left(x\right)}}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases} \Longrightarrow \begin{cases} \begin{array} {rcrcc} {f{\left({\tau}(x)\right)}} = \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases}.</math> <code>Шаг 6</code> Подставим выражение <math>{f{\left({\tau}(x)\right)}}</math> во вторую строчку системы. Итак, : <math>f{\left(x\right)}\cdot \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)} = -{\tau}^{-1}(x) \Longleftrightarrow f{\left(x\right)}\cdot f{\left(x\right)} = \dfrac{{-{\tau}}(x) \cdot {{\tau}^{-1}{\left(x\right)}}}{x}.</math> <u>'''Ответ'''</u>: <math>f{\left(x\right)} = \pm{\sqrt{\dfrac{{-{\tau}}(x) \cdot {{\tau}^{-1}{\left(x\right)}}}{x}}} = \pm{\dfrac{1}{x}}</math>, или <math>f{\left(x\right)} = \dfrac{1}{x} \AND x\neq 0.</math> |} == Инволюция в алгебре == [[w:Перестановка|Перестановка]] <math>\tau</math> является инволюцией, если <math>\tau\circ\tau=id</math>, каждая инволюция является произведением непересекающихся транспозиций, например: : <math>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 5 & 7 & 4 & 3 & 1 & 8 & 2 & 6\end{pmatrix} = (1,5)(2,7)(3,4)(6,8)</math>. Число инволюций в [[w:Группа перестановок|группе перестановок]] порядка <math>n</math> определяется по формулам: * <math> a(0) = 1,\ a(1) = 1,\ a(n) = a(n-1) + (n-1)a(n-2),\ n>1</math> (рекуррентная формула), * <math>a(n) = \sum_{k=0}^{[ n/2 ]}{\frac{n!}{2^k\cdot (n-2k)!\cdot k!}}</math>, (первые значения <math>a(n)</math>: 1, {{w:nums|link=nrl|1|2|4|10|26|76|232|764|2620|9496|35696|140152}}<ref>{{OEIS long|A000085|lc=1}}</ref>). Свойства инволюции обеспечивают ей широкое применение в различных приложения, например, инволютивные преобразования над пространством булевых векторов используются в различных схемах построения симметричных [[w:криптоалгоритм|криптоалгоритм]]ов, таких как [[w:Сеть Фейстеля|сети Фейстеля]] и [[w:SP-сеть|подстановочно-перестановочные сети]]. == Примечания == lwjczhpp0lxgpuv1uk6jvpi8ik7qrcu 220989 220988 2022-07-19T20:55:31Z Va musinov 69698 /* Лирическое отступление */ wikitext text/x-wiki '''Инволю́ция''' (от {{lang-la|involutio}} — свёртывание, завиток) — нетождественное преобразование, которое является [[w:обратная функция|обратным]] самому себе, то есть своей собственной [[w:обратная функция|инверсией]]. Это [[w:унарная операция|унарная операция]]. Формально, функция <math>f</math> называется инволюцией, если <math>f(f(x)) = x</math> для всякого <math>x</math> из [[w:Область определения функции|области определения функции]] <math>f</math>. Иногда пишут: <math>f\circ f= {f}^{2}=id</math>, где <math>id</math> обозначает тождественное преобразование. Вместо <math>id(x)</math> используют запись: <math>e(x)=x</math>. Таким образом, двойное применение функции <math>f</math> даёт исходное значение. == Свойства == Любая инволюция — это [[w:биекция|биекция]]. Если преобразование <math>f</math> инволютивное, то для любого выражения <math>A</math> и его образа <math>B=f(A)</math> имеем <math>f(B)=A</math>. В самом деле, <math>f(B)= f(f(A))=id(A)={id}_{A}=A</math>. '''''Критерий инволюции'''''. Функция <math>f</math> является инволюцией тогда и только тогда, когда для всякого выражения <math>A</math> существует такое выражение <math>B</math>, что <math>f(A)=B\neq A</math> и <math>f(B)=A</math>. Другими словами, преобразование является инволюцией в том и только в том случае, когда оно меняет местами какие-либо два выражения. ---- Если <math>f</math> — инволюция, то имеют место следующие соотношения: * <math>\forall a \in D_{f}: f^{-1}(a) = f(a)</math> [основное свойство] * <math>D_{f} = E_{f}</math> * <math>\forall a : f(f(a)) = a</math> * <math>\forall a, \exists b : f(a) = b \land f(b) = a</math> [критерий] == Примеры == Примеры инволюций: * <math>f(x) = -x</math>, заданная на множестве [[w:целое число|целых]] <math>\mathbb{Z}</math>, [[w:рациональное число|рациональных]] <math>\mathbb{Q}</math> или [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>; * простейшие инволюции на множестве [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>: *: <math>\dfrac{a}{x}</math>, <math>a-x</math>, <math>\dfrac{x}{x-1}</math>, <math>\dfrac{x+1}{x-1}</math>, <math>\dfrac{x-1}{x+1}</math>, <math>\dfrac{ax+b}{cx-a}</math>; * инволюция <math>f(x) = \dfrac{b}{x-a} + a</math> при <math>x\in \mathbb{R} \setminus \left\{a\right\}</math> и <math>b\neq 0</math>; * <math>f(x)= \bar{x}</math> — [[w:дополнение множества|дополнение множества]], заданная для подмножеств некоторого универсального множества <math>U</math>; * <math>f(x)= \neg x</math> — [[w:логическое отрицание|логическое отрицание]] [[w:булева алгебра|булевой алгебры]]; * [[w:Симметрия|симметрии]]: [[w:Центральная симметрия|центральная]], [[w:Осевая симметрия|осевая]], [[w:Зеркальная симметрия|зеркальная]]; * [[w:инверсия (геометрия)|инверсия]]; * [[w:комплексное сопряжение|комплексное сопряжение]]; * [[w:преобразование Лежандра|преобразование Лежандра]] * при факторизации обычного тора (точнее, одномерного комплексного тора, ещё точнее, эллиптической кривой) <math>E</math> по инволюции вида <math>x\mapsto -x</math> получается сфера; * Если представить, что <math>f</math> — нажатие на клавишу [[w:выключатель бытовой| бытового накладного выключателя]] (т. е. включить либо выключить свет), то <math>f</math> будет инволюцией. == Важнейшие факты == ;'''Теорема 1'''. : Композиция <math>{f}\circ{g}</math> двух инволюций <math>f</math> и <math>g</math> является инволюцией тогда и только тогда, когда они коммутируют: <math>{f}\circ{g} =g\circ f</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Пусть дана композиция <math>{f}\circ{g}</math>, в которой <math>f</math>, <math>g</math> — инволюции. Это означает, что <math>f=f^{-1}</math> и <math>g=g^{-1}</math>, а также <math>{f}\circ{g}={\left({f}\circ{g}\right)}^{-1}</math>. Имеем: <math>{f}\circ{g}= {\left({f}\circ{g}\right)}^{-1}={g^{-1}}\circ {f^{-1}}={g}\circ{f}</math>. Если <math>{f}\circ{g}</math> — инволюция, то двигаемся слева направо. Обратно, если выполняется равенство <math>{f}\circ{g} =g\circ f</math>, то справа налево. |} <code>Пример 1</code>. Такая композиция <math>\left(f_{1} \circ f_{2}\right) (x) = \left(f_{2} \circ f_{1} \right) (x) = {f_{3}} (x) = -{\dfrac{1}{x}}</math> есть инволюция. Аналогично, если <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math> и <math>g</math>, <math>h</math>, <math>k</math> — инволюции, то и <math>f</math> — инволюция. <code>Пример 2</code>. <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. ; '''Теорема 2'''. : Если <math>{f}</math> — монотонно возрастающая функция, то уравнения <math>{f}(x)=x</math> и <math>f(f(x))=x</math>, или <math>{f}(x)={f^{-1}}(x)</math>, равносильны. Рассмотрим следующую задачу. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>\sqrt{1+\sqrt{x}}=x-1</math>. |- | Перепишем данное уравнение в виде: <math>1+\sqrt{1+\sqrt{x}}=x</math>. Рассмотрим теперь функцию <math>f(x)=1+\sqrt{x}</math>. Тогда полученное уравнение примет вид: <math>f(f(x))=x</math>. Для решений уравнений такого вида применим '''теорему 2'''. Но сначала следует убедиться, что введённая функция <math>f</math> действительно монотонно возрастает. Для того чтобы <math>f(x)</math> была строго возрастающей, достаточно (но не является необходимым условием), чтобы <math>f'(x)>0</math>. В нашем случае получается <math>f'(x)=\dfrac{1}{2\sqrt{x}}>0</math>. В соответствии с приведённой '''теоремой 2''' приходим к равносильному уравнению <math>{f}(x)=x</math>, или <math>1+\sqrt{x}=x</math>, решение которого уже не сложно. Ответ: <math>x = \dfrac{3+\sqrt{5}}{2}.</math> |} ; '''Теорема 3'''. : Функция вида <math>f={h}\circ{g}\circ{h^{-1}}</math> (где <math>h</math> — некоторое биективное отображение) будет инволюцией в том и только в том случае, если функция <math>g</math> — инволюция. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Имеем следующее: <math>f=f^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {\left({h}\circ{g}\circ{h^{-1}}\right)}^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {{h}\circ{g^{-1}}\circ{h^{-1}}} \mid { \circ h} \Longleftrightarrow {h}\circ{g}={h}\circ{g^{-1}} \Longleftrightarrow {h^{-1} \circ } \mid {{h}\circ{g}={h}\circ{g^{-1}}} \Longleftrightarrow g = g^{-1}.</math> Если <math>{f}</math> является инволюцией, то двигаемся слева направо. Обратно, если <math>{g}</math> — инволюция, то справа налево. Теорема доказана. |} ''Замечание''. Ясно, что '''теорема 3''' сохраняет свою силу, если <math>f={h^{-1}}\circ{g}\circ{h}</math>, где <math>h</math> — биекция. <code>Пример 3</code>. В положительных числах такая функция будет как раз инволюцией по доказанной выше теореме: : <math>ln\left(\dfrac{e^x+1}{e^x-1}\right).</math> ; '''Следствие'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Тогда если <math>h</math> — взаимно-однозначное отображение [биекция] множества <math>E</math> на <math>F</math> с обратной биекцией <math>h^{-1}</math>, то композиция <math>h\circ f\circ h^{-1}</math> — инволюция на множестве <math>F</math>. [[File:Involution4.png|Involution4]] {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Утверждение очевидно по предыдущему. ''Указание''. Воспользоваться '''теоремой 3'''. |} ; '''Теорема 4'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Если <math>h</math> — такое отображение из <math>E</math> в <math>E</math>, что <math>h\circ f\circ h = f</math>, то <math>h\circ f</math> и <math>f\circ h</math> — инволюции на <math>E</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Покажем, что из исходного равенства <math>h\circ f\circ h = f</math> и условия <math>f=f^{-1}</math> получается инволютивная функция <math>h\circ f</math>. Итак, : <math>h\circ f\circ h = f \mid { \circ h^{-1}} \Longrightarrow h\circ f = f \circ h^{-1} \Longrightarrow h \circ f = {\left(h \circ f^{-1}\right)}^{-1} \Longrightarrow h \circ f = {\left(h \circ f \right)}^{-1} \mid {\circ {\left(h \circ f \right)}} \Longrightarrow {\left(h \circ f \right)}^{2} = e.</math> Таким образом, композиция <math>h\circ f</math> по определению является инволюцией. Аналогично проводится доказательство для <math>f\circ h</math>. |} {| class="wikitable collapsible collapsed" width="100%" ! Пусть дана функция <math>f=h\circ g\circ h\circ g^{-1}</math>, где <math>g</math> — биекция, а <math>h=h^{-1}</math>. Выяснить, при каком условии <math>f</math> будет инволютивной. |- | <u>''Решение''</u>. Во-первых, функция <math>f</math> будет инволюцией, если выполняется равенство: <math>f=f^{-1}</math>. Во-вторых, стоит заметить, что <math>h \circ f = g\circ h\circ g^{-1} = f^{-1} \circ h </math>. Поэтому <math>f=f^{-1} \Longleftrightarrow f = h \circ f \circ h</math>. Но по '''следствию''' композиция <math>g \circ h \circ g^{-1}</math> является инволюцией, а значит, и <math>h \circ f</math> — тоже инволюция. Наконец, <math> h\circ \mid f = h \circ f \circ h \Longleftrightarrow h\circ f = f \circ h</math>, то есть <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}</math>. ''Ответ'': <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}.</math> |} <code>Пример 4</code>. Функция <math>f(x)= -ln\left(-e^{x}\right)</math>. <u>'''Упражнение'''</u>. Убедитесь, что представленная функция действительно обладает таким свойством. ''Схемой'', или ''строением'', функции <math>f</math> назовём последовательность функций <math>f_{1}, f_{2}, ... , f_{n-1}, f_{n}</math> так, что каждая из них является либо элементарной, либо инволюцией и <math>f=f_{n} \circ f_{n-1} \circ ... \circ f_{2} \circ f_{1}</math>. <code>Пример 5</code>. Пусть <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. Тогда схемой функции <math>f</math> будет <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math>. == Фокус == {| class="wikitable collapsible collapsed" width=100% ! Целое общество гостей, непосвящённых в арифметические тайны, вы можете поразить следующим фокусом. |- | Фокусник просит одного человека написать на бумажке, секретно от него, трёхзначное число, какое этот человек хочет, и затем просит приписать к нему ещё раз то же самое число. Получится шестизначное число, состоящее из трёх повторяющихся цифр. Фокусник предлагает тому же товарищу или его соседу разделить — секретно от него — это число на 7; при этом фокусник заранее предсказывает, что остатка не получится. Результат деления передаётся соседу, который, по предложению ведущего, делит его на 11; и хотя фокусник не знает делимого, он всё же смело утверждает, что и оно разделится без остатка. Полученный результат фокусник направляет следующему соседу, которого просит разделить это число на 13 — деление снова выполняется без остатка, о чём он заранее предупреждает. Результат третьего деления фокусник, не глядя на полученное число, вручает первому товарищу со словами: — Вот число, которое вы задумали! — Так и есть: вы угадали. |} <code>Какова разгадка этого фокуса?</code> ''Указание''. Возьмите за функцию <math>f</math> алгоритм приписывания к числу <math>x\rightleftharpoons \overline{abc}</math>, то есть <math>f(x)= \overline{abcabc}</math>. Так как результат совпадает с исходным числом <math>x\rightleftharpoons \overline{abc}</math>, то <math>f^{-1}</math> над числом — это умножение его на 7, 11 и 13. Осталось найти связь <math>f</math> и <math>f^{-1}</math>. == Лирическое отступление == Приведём пример композиции двух инволюций, которая не будет уже инволюцией. <code>Пример</code>. Функция <math>\tau(x)=\dfrac{1}{1-x}</math> не является инволюцией; её строение таково: <math>\tau=\alpha \circ \beta</math>, где <math>\alpha (x) = \dfrac{1}{x}</math> и <math>\beta (x) = 1-x</math> у нас — обе инволюции. '''''Упражнение'''''. Докажите: для <math>\tau(x)=\dfrac{1}{1-x}</math> верно, что <math>\tau \neq {\tau}^{-1}</math>. ''Замечание''. Функция <math>{{\tau}^{-1}}{\left(x\right)}=1-{\dfrac{1}{x}}=\dfrac{x-1}{x}</math> со схемой <math>{\tau}^{-1}=\beta \circ \alpha</math> также не есть инволюция. Легко видеть, что <math>\alpha \circ {{\tau}^{-1}}</math> — инволюция. Делаем вывод, что композиция инволюции и неинволютивной функции может давать инволюцию в результате. Вопрос: ''в каком случае это происходит?'' Перед тем, как ответить на этот вопрос, сперва-наперво выясним, а каким свойством, в принципе, обладает введённая функция <math>\tau(x)=\dfrac{1}{1-x}</math>. Вычислим <math>{\tau}^{2}(x)</math>. У нас получится: : <math>{\tau}^{2}(x)=\dfrac{1}{1-\dfrac{1}{1-x}} = \dfrac{1-x}{1-x-1}=\dfrac{x-1}{x}={\tau}^{-1}(x).</math> Значит, <math>{\tau}^{3}=e</math>. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>f{\left(x\right)}\cdot {f{\left(\dfrac{1}{1-x}\right)}}=\dfrac{1-x}{x}</math>. |- | <code>Шаг 1</code> Напишем схему данного уравнения: <math>f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}}=-{\tau}^{-1}(x)</math>. <code>Шаг 2</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}^{-1}(x)</math>. Получим: : <center><math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(\tau({\tau}^{-1}(x))\right)}}=-{\tau}^{-1}({\tau}^{-1}(x)) \Longrightarrow f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}^{-2}(x).</math></center> Но так как <math>{\tau}^{2}(x)={\tau}^{-1}(x)</math>, то <math>{\tau}^{-2}(x)={\tau}(x)</math>. Поэтому <math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}(x)</math>. <code>Шаг 3</code> Теперь из результатов <code>Шага 1</code> и <code>Шага 2</code> делаем простой вывод: : <center><math>f(x)=\dfrac{-{\tau(x)}}{f{\left({\tau}^{-1}(x)\right)}} = \dfrac{{-{\tau}}^{-1}(x)}{f{\left({\tau}(x)\right)}}.</math></center> <code>Шаг 4</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}(x)</math>. Имеем: : <center><math>f{\left({\tau}^{-1}(x)\right)}=\dfrac{-x}{f{\left({\tau}(x)\right)}}=\dfrac{{-{\tau}}(x)}{f{\left(x\right)}}.</math></center> <code>Шаг 5</code> Наконец-то, мы <br><br><math> \begin{cases} \begin{array} {rcrcc} \dfrac{-x}{f{\left({\tau}(x)\right)}} = \dfrac{{-{\tau}}(x)}{f{\left(x\right)}}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases} \Longrightarrow \begin{cases} \begin{array} {rcrcc} {f{\left({\tau}(x)\right)}} = \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases}.</math> <code>Шаг 6</code> Подставим выражение <math>{f{\left({\tau}(x)\right)}}</math> во вторую строчку системы. Итак, : <math>f{\left(x\right)}\cdot \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)} = -{\tau}^{-1}(x) \Longleftrightarrow f{\left(x\right)}\cdot f{\left(x\right)} = \dfrac{{-{\tau}}(x) \cdot {{\tau}^{-1}{\left(x\right)}}}{x}.</math> <u>'''Ответ'''</u>: <math>f{\left(x\right)} = \pm{\sqrt{\dfrac{{-{\tau}}(x) \cdot {{\tau}^{-1}{\left(x\right)}}}{x}}} = \pm{\dfrac{1}{x}}</math>, или <math>f{\left(x\right)} = \dfrac{1}{x} \& x\neq 0.</math> |} == Инволюция в алгебре == [[w:Перестановка|Перестановка]] <math>\tau</math> является инволюцией, если <math>\tau\circ\tau=id</math>, каждая инволюция является произведением непересекающихся транспозиций, например: : <math>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 5 & 7 & 4 & 3 & 1 & 8 & 2 & 6\end{pmatrix} = (1,5)(2,7)(3,4)(6,8)</math>. Число инволюций в [[w:Группа перестановок|группе перестановок]] порядка <math>n</math> определяется по формулам: * <math> a(0) = 1,\ a(1) = 1,\ a(n) = a(n-1) + (n-1)a(n-2),\ n>1</math> (рекуррентная формула), * <math>a(n) = \sum_{k=0}^{[ n/2 ]}{\frac{n!}{2^k\cdot (n-2k)!\cdot k!}}</math>, (первые значения <math>a(n)</math>: 1, {{w:nums|link=nrl|1|2|4|10|26|76|232|764|2620|9496|35696|140152}}<ref>{{OEIS long|A000085|lc=1}}</ref>). Свойства инволюции обеспечивают ей широкое применение в различных приложения, например, инволютивные преобразования над пространством булевых векторов используются в различных схемах построения симметричных [[w:криптоалгоритм|криптоалгоритм]]ов, таких как [[w:Сеть Фейстеля|сети Фейстеля]] и [[w:SP-сеть|подстановочно-перестановочные сети]]. == Примечания == nxqp1zs9ysw9ljbymsur71z28sobo5c 220990 220989 2022-07-19T20:56:01Z Va musinov 69698 wikitext text/x-wiki '''Инволю́ция''' (от {{lang-la|involutio}} — свёртывание, завиток) — нетождественное преобразование, которое является [[w:обратная функция|обратным]] самому себе, то есть своей собственной [[w:обратная функция|инверсией]]. Это [[w:унарная операция|унарная операция]]. Формально, функция <math>f</math> называется инволюцией, если <math>f(f(x)) = x</math> для всякого <math>x</math> из [[w:Область определения функции|области определения функции]] <math>f</math>. Иногда пишут: <math>f\circ f= {f}^{2}=id</math>, где <math>id</math> обозначает тождественное преобразование. Вместо <math>id(x)</math> используют запись: <math>e(x)=x</math>. Таким образом, двойное применение функции <math>f</math> даёт исходное значение. == Свойства == Любая инволюция — это [[w:биекция|биекция]]. Если преобразование <math>f</math> инволютивное, то для любого выражения <math>A</math> и его образа <math>B=f(A)</math> имеем <math>f(B)=A</math>. В самом деле, <math>f(B)= f(f(A))=id(A)={id}_{A}=A</math>. '''''Критерий инволюции'''''. Функция <math>f</math> является инволюцией тогда и только тогда, когда для всякого выражения <math>A</math> существует такое выражение <math>B</math>, что <math>f(A)=B\neq A</math> и <math>f(B)=A</math>. Другими словами, преобразование является инволюцией в том и только в том случае, когда оно меняет местами какие-либо два выражения. ---- Если <math>f</math> — инволюция, то имеют место следующие соотношения: * <math>\forall a \in D_{f}: f^{-1}(a) = f(a)</math> [основное свойство] * <math>D_{f} = E_{f}</math> * <math>\forall a : f(f(a)) = a</math> * <math>\forall a, \exists b : f(a) = b \land f(b) = a</math> [критерий] == Примеры == Примеры инволюций: * <math>f(x) = -x</math>, заданная на множестве [[w:целое число|целых]] <math>\mathbb{Z}</math>, [[w:рациональное число|рациональных]] <math>\mathbb{Q}</math> или [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>; * простейшие инволюции на множестве [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>: *: <math>\dfrac{a}{x}</math>, <math>a-x</math>, <math>\dfrac{x}{x-1}</math>, <math>\dfrac{x+1}{x-1}</math>, <math>\dfrac{x-1}{x+1}</math>, <math>\dfrac{ax+b}{cx-a}</math>; * инволюция <math>f(x) = \dfrac{b}{x-a} + a</math> при <math>x\in \mathbb{R} \setminus \left\{a\right\}</math> и <math>b\neq 0</math>; * <math>f(x)= \bar{x}</math> — [[w:дополнение множества|дополнение множества]], заданная для подмножеств некоторого универсального множества <math>U</math>; * <math>f(x)= \neg x</math> — [[w:логическое отрицание|логическое отрицание]] [[w:булева алгебра|булевой алгебры]]; * [[w:Симметрия|симметрии]]: [[w:Центральная симметрия|центральная]], [[w:Осевая симметрия|осевая]], [[w:Зеркальная симметрия|зеркальная]]; * [[w:инверсия (геометрия)|инверсия]]; * [[w:комплексное сопряжение|комплексное сопряжение]]; * [[w:преобразование Лежандра|преобразование Лежандра]] * при факторизации обычного тора (точнее, одномерного комплексного тора, ещё точнее, эллиптической кривой) <math>E</math> по инволюции вида <math>x\mapsto -x</math> получается сфера; * Если представить, что <math>f</math> — нажатие на клавишу [[w:выключатель бытовой| бытового накладного выключателя]] (т. е. включить либо выключить свет), то <math>f</math> будет инволюцией. == Важнейшие факты == ;'''Теорема 1'''. : Композиция <math>{f}\circ{g}</math> двух инволюций <math>f</math> и <math>g</math> является инволюцией тогда и только тогда, когда они коммутируют: <math>{f}\circ{g} =g\circ f</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Пусть дана композиция <math>{f}\circ{g}</math>, в которой <math>f</math>, <math>g</math> — инволюции. Это означает, что <math>f=f^{-1}</math> и <math>g=g^{-1}</math>, а также <math>{f}\circ{g}={\left({f}\circ{g}\right)}^{-1}</math>. Имеем: <math>{f}\circ{g}= {\left({f}\circ{g}\right)}^{-1}={g^{-1}}\circ {f^{-1}}={g}\circ{f}</math>. Если <math>{f}\circ{g}</math> — инволюция, то двигаемся слева направо. Обратно, если выполняется равенство <math>{f}\circ{g} =g\circ f</math>, то справа налево. |} <code>Пример 1</code>. Такая композиция <math>\left(f_{1} \circ f_{2}\right) (x) = \left(f_{2} \circ f_{1} \right) (x) = {f_{3}} (x) = -{\dfrac{1}{x}}</math> есть инволюция. Аналогично, если <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math> и <math>g</math>, <math>h</math>, <math>k</math> — инволюции, то и <math>f</math> — инволюция. <code>Пример 2</code>. <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. ; '''Теорема 2'''. : Если <math>{f}</math> — монотонно возрастающая функция, то уравнения <math>{f}(x)=x</math> и <math>f(f(x))=x</math>, или <math>{f}(x)={f^{-1}}(x)</math>, равносильны. Рассмотрим следующую задачу. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>\sqrt{1+\sqrt{x}}=x-1</math>. |- | Перепишем данное уравнение в виде: <math>1+\sqrt{1+\sqrt{x}}=x</math>. Рассмотрим теперь функцию <math>f(x)=1+\sqrt{x}</math>. Тогда полученное уравнение примет вид: <math>f(f(x))=x</math>. Для решений уравнений такого вида применим '''теорему 2'''. Но сначала следует убедиться, что введённая функция <math>f</math> действительно монотонно возрастает. Для того чтобы <math>f(x)</math> была строго возрастающей, достаточно (но не является необходимым условием), чтобы <math>f'(x)>0</math>. В нашем случае получается <math>f'(x)=\dfrac{1}{2\sqrt{x}}>0</math>. В соответствии с приведённой '''теоремой 2''' приходим к равносильному уравнению <math>{f}(x)=x</math>, или <math>1+\sqrt{x}=x</math>, решение которого уже не сложно. Ответ: <math>x = \dfrac{3+\sqrt{5}}{2}.</math> |} ; '''Теорема 3'''. : Функция вида <math>f={h}\circ{g}\circ{h^{-1}}</math> (где <math>h</math> — некоторое биективное отображение) будет инволюцией в том и только в том случае, если функция <math>g</math> — инволюция. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Имеем следующее: <math>f=f^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {\left({h}\circ{g}\circ{h^{-1}}\right)}^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {{h}\circ{g^{-1}}\circ{h^{-1}}} \mid { \circ h} \Longleftrightarrow {h}\circ{g}={h}\circ{g^{-1}} \Longleftrightarrow {h^{-1} \circ } \mid {{h}\circ{g}={h}\circ{g^{-1}}} \Longleftrightarrow g = g^{-1}.</math> Если <math>{f}</math> является инволюцией, то двигаемся слева направо. Обратно, если <math>{g}</math> — инволюция, то справа налево. Теорема доказана. |} ''Замечание''. Ясно, что '''теорема 3''' сохраняет свою силу, если <math>f={h^{-1}}\circ{g}\circ{h}</math>, где <math>h</math> — биекция. <code>Пример 3</code>. В положительных числах такая функция будет как раз инволюцией по доказанной выше теореме: : <math>ln\left(\dfrac{e^x+1}{e^x-1}\right).</math> ; '''Следствие'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Тогда если <math>h</math> — взаимно-однозначное отображение [биекция] множества <math>E</math> на <math>F</math> с обратной биекцией <math>h^{-1}</math>, то композиция <math>h\circ f\circ h^{-1}</math> — инволюция на множестве <math>F</math>. [[File:Involution4.png|Involution4]] {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Утверждение очевидно по предыдущему. ''Указание''. Воспользоваться '''теоремой 3'''. |} ; '''Теорема 4'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Если <math>h</math> — такое отображение из <math>E</math> в <math>E</math>, что <math>h\circ f\circ h = f</math>, то <math>h\circ f</math> и <math>f\circ h</math> — инволюции на <math>E</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Покажем, что из исходного равенства <math>h\circ f\circ h = f</math> и условия <math>f=f^{-1}</math> получается инволютивная функция <math>h\circ f</math>. Итак, : <math>h\circ f\circ h = f \mid { \circ h^{-1}} \Longrightarrow h\circ f = f \circ h^{-1} \Longrightarrow h \circ f = {\left(h \circ f^{-1}\right)}^{-1} \Longrightarrow h \circ f = {\left(h \circ f \right)}^{-1} \mid {\circ {\left(h \circ f \right)}} \Longrightarrow {\left(h \circ f \right)}^{2} = e.</math> Таким образом, композиция <math>h\circ f</math> по определению является инволюцией. Аналогично проводится доказательство для <math>f\circ h</math>. |} {| class="wikitable collapsible collapsed" width="100%" ! Пусть дана функция <math>f=h\circ g\circ h\circ g^{-1}</math>, где <math>g</math> — биекция, а <math>h=h^{-1}</math>. Выяснить, при каком условии <math>f</math> будет инволютивной. |- | <u>''Решение''</u>. Во-первых, функция <math>f</math> будет инволюцией, если выполняется равенство: <math>f=f^{-1}</math>. Во-вторых, стоит заметить, что <math>h \circ f = g\circ h\circ g^{-1} = f^{-1} \circ h </math>. Поэтому <math>f=f^{-1} \Longleftrightarrow f = h \circ f \circ h</math>. Но по '''следствию''' композиция <math>g \circ h \circ g^{-1}</math> является инволюцией, а значит, и <math>h \circ f</math> — тоже инволюция. Наконец, <math> h\circ \mid f = h \circ f \circ h \Longleftrightarrow h\circ f = f \circ h</math>, то есть <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}</math>. ''Ответ'': <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}.</math> |} <code>Пример 4</code>. Функция <math>f(x)= -ln\left(-e^{x}\right)</math>. <u>'''Упражнение'''</u>. Убедитесь, что представленная функция действительно обладает таким свойством. ''Схемой'', или ''строением'', функции <math>f</math> назовём последовательность функций <math>f_{1}, f_{2}, ... , f_{n-1}, f_{n}</math> так, что каждая из них является либо элементарной, либо инволюцией и <math>f=f_{n} \circ f_{n-1} \circ ... \circ f_{2} \circ f_{1}</math>. <code>Пример 5</code>. Пусть <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. Тогда схемой функции <math>f</math> будет <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math>. == Фокус == {| class="wikitable collapsible collapsed" width=100% ! Целое общество гостей, непосвящённых в арифметические тайны, вы можете поразить следующим фокусом. |- | Фокусник просит одного человека написать на бумажке, секретно от него, трёхзначное число, какое этот человек хочет, и затем просит приписать к нему ещё раз то же самое число. Получится шестизначное число, состоящее из трёх повторяющихся цифр. Фокусник предлагает тому же товарищу или его соседу разделить — секретно от него — это число на 7; при этом фокусник заранее предсказывает, что остатка не получится. Результат деления передаётся соседу, который, по предложению ведущего, делит его на 11; и хотя фокусник не знает делимого, он всё же смело утверждает, что и оно разделится без остатка. Полученный результат фокусник направляет следующему соседу, которого просит разделить это число на 13 — деление снова выполняется без остатка, о чём он заранее предупреждает. Результат третьего деления фокусник, не глядя на полученное число, вручает первому товарищу со словами: — Вот число, которое вы задумали! — Так и есть: вы угадали. |} <code>Какова разгадка этого фокуса?</code> ''Указание''. Возьмите за функцию <math>f</math> алгоритм приписывания к числу <math>x\rightleftharpoons \overline{abc}</math>, то есть <math>f(x)= \overline{abcabc}</math>. Так как результат совпадает с исходным числом <math>x\rightleftharpoons \overline{abc}</math>, то <math>f^{-1}</math> над числом — это умножение его на 7, 11 и 13. Осталось найти связь <math>f</math> и <math>f^{-1}</math>. == Лирическое отступление == Приведём пример композиции двух инволюций, которая не будет уже инволюцией. <code>Пример</code>. Функция <math>\tau(x)=\dfrac{1}{1-x}</math> не является инволюцией; её строение таково: <math>\tau=\alpha \circ \beta</math>, где <math>\alpha (x) = \dfrac{1}{x}</math> и <math>\beta (x) = 1-x</math> у нас — обе инволюции. '''''Упражнение'''''. Докажите: для <math>\tau(x)=\dfrac{1}{1-x}</math> верно, что <math>\tau \neq {\tau}^{-1}</math>. ''Замечание''. Функция <math>{{\tau}^{-1}}{\left(x\right)}=1-{\dfrac{1}{x}}=\dfrac{x-1}{x}</math> со схемой <math>{\tau}^{-1}=\beta \circ \alpha</math> также не есть инволюция. Легко видеть, что <math>\alpha \circ {{\tau}^{-1}}</math> — инволюция. Делаем вывод, что композиция инволюции и неинволютивной функции может давать инволюцию в результате. Вопрос: ''в каком случае это происходит?'' Перед тем, как ответить на этот вопрос, сперва-наперво выясним, а каким свойством, в принципе, обладает введённая функция <math>\tau(x)=\dfrac{1}{1-x}</math>. Вычислим <math>{\tau}^{2}(x)</math>. У нас получится: : <math>{\tau}^{2}(x)=\dfrac{1}{1-\dfrac{1}{1-x}} = \dfrac{1-x}{1-x-1}=\dfrac{x-1}{x}={\tau}^{-1}(x).</math> Значит, <math>{\tau}^{3}=e</math>. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>f{\left(x\right)}\cdot {f{\left(\dfrac{1}{1-x}\right)}}=\dfrac{1-x}{x}</math>. |- | <code>Шаг 1</code> Напишем схему данного уравнения: <math>f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}}=-{\tau}^{-1}(x)</math>. <code>Шаг 2</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}^{-1}(x)</math>. Получим: : <center><math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(\tau({\tau}^{-1}(x))\right)}}=-{\tau}^{-1}({\tau}^{-1}(x)) \Longrightarrow f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}^{-2}(x).</math></center> Но так как <math>{\tau}^{2}(x)={\tau}^{-1}(x)</math>, то <math>{\tau}^{-2}(x)={\tau}(x)</math>. Поэтому <math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}(x)</math>. <code>Шаг 3</code> Теперь из результатов <code>Шага 1</code> и <code>Шага 2</code> делаем простой вывод: : <center><math>f(x)=\dfrac{-{\tau(x)}}{f{\left({\tau}^{-1}(x)\right)}} = \dfrac{{-{\tau}}^{-1}(x)}{f{\left({\tau}(x)\right)}}.</math></center> <code>Шаг 4</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}(x)</math>. Имеем: : <center><math>f{\left({\tau}^{-1}(x)\right)}=\dfrac{-x}{f{\left({\tau}(x)\right)}}=\dfrac{{-{\tau}}(x)}{f{\left(x\right)}}.</math></center> <code>Шаг 5</code> Наконец-то, мы <br><br><math> \begin{cases} \begin{array} {rcrcc} \dfrac{-x}{f{\left({\tau}(x)\right)}} = \dfrac{{-{\tau}}(x)}{f{\left(x\right)}}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases} \Longrightarrow \begin{cases} \begin{array} {rcrcc} {f{\left({\tau}(x)\right)}} = \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases}.</math> <code>Шаг 6</code> Подставим выражение <math>{f{\left({\tau}(x)\right)}}</math> во вторую строчку системы. Итак, : <math>f{\left(x\right)}\cdot \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)} = -{\tau}^{-1}(x) \Longleftrightarrow f{\left(x\right)}\cdot f{\left(x\right)} = \dfrac{{-{\tau}}(x) \cdot {{\tau}^{-1}{\left(x\right)}}}{x}.</math> <u>'''Ответ'''</u>: <math>f{\left(x\right)} = \pm{\sqrt{\dfrac{{-{\tau}}(x) \cdot {{\tau}^{-1}{\left(x\right)}}}{x}}} = \pm{\dfrac{1}{x}}</math>, или <math>f{\left(x\right)} = \dfrac{1}{x} &{\&}& x\neq 0.</math> |} == Инволюция в алгебре == [[w:Перестановка|Перестановка]] <math>\tau</math> является инволюцией, если <math>\tau\circ\tau=id</math>, каждая инволюция является произведением непересекающихся транспозиций, например: : <math>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 5 & 7 & 4 & 3 & 1 & 8 & 2 & 6\end{pmatrix} = (1,5)(2,7)(3,4)(6,8)</math>. Число инволюций в [[w:Группа перестановок|группе перестановок]] порядка <math>n</math> определяется по формулам: * <math> a(0) = 1,\ a(1) = 1,\ a(n) = a(n-1) + (n-1)a(n-2),\ n>1</math> (рекуррентная формула), * <math>a(n) = \sum_{k=0}^{[ n/2 ]}{\frac{n!}{2^k\cdot (n-2k)!\cdot k!}}</math>, (первые значения <math>a(n)</math>: 1, {{w:nums|link=nrl|1|2|4|10|26|76|232|764|2620|9496|35696|140152}}<ref>{{OEIS long|A000085|lc=1}}</ref>). Свойства инволюции обеспечивают ей широкое применение в различных приложения, например, инволютивные преобразования над пространством булевых векторов используются в различных схемах построения симметричных [[w:криптоалгоритм|криптоалгоритм]]ов, таких как [[w:Сеть Фейстеля|сети Фейстеля]] и [[w:SP-сеть|подстановочно-перестановочные сети]]. == Примечания == 2hv30m0f807z6ws2br1wl1q54mgeb02 220991 220990 2022-07-19T20:58:02Z Va musinov 69698 /* Лирическое отступление */ wikitext text/x-wiki '''Инволю́ция''' (от {{lang-la|involutio}} — свёртывание, завиток) — нетождественное преобразование, которое является [[w:обратная функция|обратным]] самому себе, то есть своей собственной [[w:обратная функция|инверсией]]. Это [[w:унарная операция|унарная операция]]. Формально, функция <math>f</math> называется инволюцией, если <math>f(f(x)) = x</math> для всякого <math>x</math> из [[w:Область определения функции|области определения функции]] <math>f</math>. Иногда пишут: <math>f\circ f= {f}^{2}=id</math>, где <math>id</math> обозначает тождественное преобразование. Вместо <math>id(x)</math> используют запись: <math>e(x)=x</math>. Таким образом, двойное применение функции <math>f</math> даёт исходное значение. == Свойства == Любая инволюция — это [[w:биекция|биекция]]. Если преобразование <math>f</math> инволютивное, то для любого выражения <math>A</math> и его образа <math>B=f(A)</math> имеем <math>f(B)=A</math>. В самом деле, <math>f(B)= f(f(A))=id(A)={id}_{A}=A</math>. '''''Критерий инволюции'''''. Функция <math>f</math> является инволюцией тогда и только тогда, когда для всякого выражения <math>A</math> существует такое выражение <math>B</math>, что <math>f(A)=B\neq A</math> и <math>f(B)=A</math>. Другими словами, преобразование является инволюцией в том и только в том случае, когда оно меняет местами какие-либо два выражения. ---- Если <math>f</math> — инволюция, то имеют место следующие соотношения: * <math>\forall a \in D_{f}: f^{-1}(a) = f(a)</math> [основное свойство] * <math>D_{f} = E_{f}</math> * <math>\forall a : f(f(a)) = a</math> * <math>\forall a, \exists b : f(a) = b \land f(b) = a</math> [критерий] == Примеры == Примеры инволюций: * <math>f(x) = -x</math>, заданная на множестве [[w:целое число|целых]] <math>\mathbb{Z}</math>, [[w:рациональное число|рациональных]] <math>\mathbb{Q}</math> или [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>; * простейшие инволюции на множестве [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>: *: <math>\dfrac{a}{x}</math>, <math>a-x</math>, <math>\dfrac{x}{x-1}</math>, <math>\dfrac{x+1}{x-1}</math>, <math>\dfrac{x-1}{x+1}</math>, <math>\dfrac{ax+b}{cx-a}</math>; * инволюция <math>f(x) = \dfrac{b}{x-a} + a</math> при <math>x\in \mathbb{R} \setminus \left\{a\right\}</math> и <math>b\neq 0</math>; * <math>f(x)= \bar{x}</math> — [[w:дополнение множества|дополнение множества]], заданная для подмножеств некоторого универсального множества <math>U</math>; * <math>f(x)= \neg x</math> — [[w:логическое отрицание|логическое отрицание]] [[w:булева алгебра|булевой алгебры]]; * [[w:Симметрия|симметрии]]: [[w:Центральная симметрия|центральная]], [[w:Осевая симметрия|осевая]], [[w:Зеркальная симметрия|зеркальная]]; * [[w:инверсия (геометрия)|инверсия]]; * [[w:комплексное сопряжение|комплексное сопряжение]]; * [[w:преобразование Лежандра|преобразование Лежандра]] * при факторизации обычного тора (точнее, одномерного комплексного тора, ещё точнее, эллиптической кривой) <math>E</math> по инволюции вида <math>x\mapsto -x</math> получается сфера; * Если представить, что <math>f</math> — нажатие на клавишу [[w:выключатель бытовой| бытового накладного выключателя]] (т. е. включить либо выключить свет), то <math>f</math> будет инволюцией. == Важнейшие факты == ;'''Теорема 1'''. : Композиция <math>{f}\circ{g}</math> двух инволюций <math>f</math> и <math>g</math> является инволюцией тогда и только тогда, когда они коммутируют: <math>{f}\circ{g} =g\circ f</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Пусть дана композиция <math>{f}\circ{g}</math>, в которой <math>f</math>, <math>g</math> — инволюции. Это означает, что <math>f=f^{-1}</math> и <math>g=g^{-1}</math>, а также <math>{f}\circ{g}={\left({f}\circ{g}\right)}^{-1}</math>. Имеем: <math>{f}\circ{g}= {\left({f}\circ{g}\right)}^{-1}={g^{-1}}\circ {f^{-1}}={g}\circ{f}</math>. Если <math>{f}\circ{g}</math> — инволюция, то двигаемся слева направо. Обратно, если выполняется равенство <math>{f}\circ{g} =g\circ f</math>, то справа налево. |} <code>Пример 1</code>. Такая композиция <math>\left(f_{1} \circ f_{2}\right) (x) = \left(f_{2} \circ f_{1} \right) (x) = {f_{3}} (x) = -{\dfrac{1}{x}}</math> есть инволюция. Аналогично, если <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math> и <math>g</math>, <math>h</math>, <math>k</math> — инволюции, то и <math>f</math> — инволюция. <code>Пример 2</code>. <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. ; '''Теорема 2'''. : Если <math>{f}</math> — монотонно возрастающая функция, то уравнения <math>{f}(x)=x</math> и <math>f(f(x))=x</math>, или <math>{f}(x)={f^{-1}}(x)</math>, равносильны. Рассмотрим следующую задачу. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>\sqrt{1+\sqrt{x}}=x-1</math>. |- | Перепишем данное уравнение в виде: <math>1+\sqrt{1+\sqrt{x}}=x</math>. Рассмотрим теперь функцию <math>f(x)=1+\sqrt{x}</math>. Тогда полученное уравнение примет вид: <math>f(f(x))=x</math>. Для решений уравнений такого вида применим '''теорему 2'''. Но сначала следует убедиться, что введённая функция <math>f</math> действительно монотонно возрастает. Для того чтобы <math>f(x)</math> была строго возрастающей, достаточно (но не является необходимым условием), чтобы <math>f'(x)>0</math>. В нашем случае получается <math>f'(x)=\dfrac{1}{2\sqrt{x}}>0</math>. В соответствии с приведённой '''теоремой 2''' приходим к равносильному уравнению <math>{f}(x)=x</math>, или <math>1+\sqrt{x}=x</math>, решение которого уже не сложно. Ответ: <math>x = \dfrac{3+\sqrt{5}}{2}.</math> |} ; '''Теорема 3'''. : Функция вида <math>f={h}\circ{g}\circ{h^{-1}}</math> (где <math>h</math> — некоторое биективное отображение) будет инволюцией в том и только в том случае, если функция <math>g</math> — инволюция. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Имеем следующее: <math>f=f^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {\left({h}\circ{g}\circ{h^{-1}}\right)}^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {{h}\circ{g^{-1}}\circ{h^{-1}}} \mid { \circ h} \Longleftrightarrow {h}\circ{g}={h}\circ{g^{-1}} \Longleftrightarrow {h^{-1} \circ } \mid {{h}\circ{g}={h}\circ{g^{-1}}} \Longleftrightarrow g = g^{-1}.</math> Если <math>{f}</math> является инволюцией, то двигаемся слева направо. Обратно, если <math>{g}</math> — инволюция, то справа налево. Теорема доказана. |} ''Замечание''. Ясно, что '''теорема 3''' сохраняет свою силу, если <math>f={h^{-1}}\circ{g}\circ{h}</math>, где <math>h</math> — биекция. <code>Пример 3</code>. В положительных числах такая функция будет как раз инволюцией по доказанной выше теореме: : <math>ln\left(\dfrac{e^x+1}{e^x-1}\right).</math> ; '''Следствие'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Тогда если <math>h</math> — взаимно-однозначное отображение [биекция] множества <math>E</math> на <math>F</math> с обратной биекцией <math>h^{-1}</math>, то композиция <math>h\circ f\circ h^{-1}</math> — инволюция на множестве <math>F</math>. [[File:Involution4.png|Involution4]] {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Утверждение очевидно по предыдущему. ''Указание''. Воспользоваться '''теоремой 3'''. |} ; '''Теорема 4'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Если <math>h</math> — такое отображение из <math>E</math> в <math>E</math>, что <math>h\circ f\circ h = f</math>, то <math>h\circ f</math> и <math>f\circ h</math> — инволюции на <math>E</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Покажем, что из исходного равенства <math>h\circ f\circ h = f</math> и условия <math>f=f^{-1}</math> получается инволютивная функция <math>h\circ f</math>. Итак, : <math>h\circ f\circ h = f \mid { \circ h^{-1}} \Longrightarrow h\circ f = f \circ h^{-1} \Longrightarrow h \circ f = {\left(h \circ f^{-1}\right)}^{-1} \Longrightarrow h \circ f = {\left(h \circ f \right)}^{-1} \mid {\circ {\left(h \circ f \right)}} \Longrightarrow {\left(h \circ f \right)}^{2} = e.</math> Таким образом, композиция <math>h\circ f</math> по определению является инволюцией. Аналогично проводится доказательство для <math>f\circ h</math>. |} {| class="wikitable collapsible collapsed" width="100%" ! Пусть дана функция <math>f=h\circ g\circ h\circ g^{-1}</math>, где <math>g</math> — биекция, а <math>h=h^{-1}</math>. Выяснить, при каком условии <math>f</math> будет инволютивной. |- | <u>''Решение''</u>. Во-первых, функция <math>f</math> будет инволюцией, если выполняется равенство: <math>f=f^{-1}</math>. Во-вторых, стоит заметить, что <math>h \circ f = g\circ h\circ g^{-1} = f^{-1} \circ h </math>. Поэтому <math>f=f^{-1} \Longleftrightarrow f = h \circ f \circ h</math>. Но по '''следствию''' композиция <math>g \circ h \circ g^{-1}</math> является инволюцией, а значит, и <math>h \circ f</math> — тоже инволюция. Наконец, <math> h\circ \mid f = h \circ f \circ h \Longleftrightarrow h\circ f = f \circ h</math>, то есть <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}</math>. ''Ответ'': <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}.</math> |} <code>Пример 4</code>. Функция <math>f(x)= -ln\left(-e^{x}\right)</math>. <u>'''Упражнение'''</u>. Убедитесь, что представленная функция действительно обладает таким свойством. ''Схемой'', или ''строением'', функции <math>f</math> назовём последовательность функций <math>f_{1}, f_{2}, ... , f_{n-1}, f_{n}</math> так, что каждая из них является либо элементарной, либо инволюцией и <math>f=f_{n} \circ f_{n-1} \circ ... \circ f_{2} \circ f_{1}</math>. <code>Пример 5</code>. Пусть <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. Тогда схемой функции <math>f</math> будет <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math>. == Фокус == {| class="wikitable collapsible collapsed" width=100% ! Целое общество гостей, непосвящённых в арифметические тайны, вы можете поразить следующим фокусом. |- | Фокусник просит одного человека написать на бумажке, секретно от него, трёхзначное число, какое этот человек хочет, и затем просит приписать к нему ещё раз то же самое число. Получится шестизначное число, состоящее из трёх повторяющихся цифр. Фокусник предлагает тому же товарищу или его соседу разделить — секретно от него — это число на 7; при этом фокусник заранее предсказывает, что остатка не получится. Результат деления передаётся соседу, который, по предложению ведущего, делит его на 11; и хотя фокусник не знает делимого, он всё же смело утверждает, что и оно разделится без остатка. Полученный результат фокусник направляет следующему соседу, которого просит разделить это число на 13 — деление снова выполняется без остатка, о чём он заранее предупреждает. Результат третьего деления фокусник, не глядя на полученное число, вручает первому товарищу со словами: — Вот число, которое вы задумали! — Так и есть: вы угадали. |} <code>Какова разгадка этого фокуса?</code> ''Указание''. Возьмите за функцию <math>f</math> алгоритм приписывания к числу <math>x\rightleftharpoons \overline{abc}</math>, то есть <math>f(x)= \overline{abcabc}</math>. Так как результат совпадает с исходным числом <math>x\rightleftharpoons \overline{abc}</math>, то <math>f^{-1}</math> над числом — это умножение его на 7, 11 и 13. Осталось найти связь <math>f</math> и <math>f^{-1}</math>. == Лирическое отступление == Приведём пример композиции двух инволюций, которая не будет уже инволюцией. <code>Пример</code>. Функция <math>\tau(x)=\dfrac{1}{1-x}</math> не является инволюцией; её строение таково: <math>\tau=\alpha \circ \beta</math>, где <math>\alpha (x) = \dfrac{1}{x}</math> и <math>\beta (x) = 1-x</math> у нас — обе инволюции. '''''Упражнение'''''. Докажите: для <math>\tau(x)=\dfrac{1}{1-x}</math> верно, что <math>\tau \neq {\tau}^{-1}</math>. ''Замечание''. Функция <math>{{\tau}^{-1}}{\left(x\right)}=1-{\dfrac{1}{x}}=\dfrac{x-1}{x}</math> со схемой <math>{\tau}^{-1}=\beta \circ \alpha</math> также не есть инволюция. Легко видеть, что <math>\alpha \circ {{\tau}^{-1}}</math> — инволюция. Делаем вывод, что композиция инволюции и неинволютивной функции может давать инволюцию в результате. Вопрос: ''в каком случае это происходит?'' Перед тем, как ответить на этот вопрос, сперва-наперво выясним, а каким свойством, в принципе, обладает введённая функция <math>\tau(x)=\dfrac{1}{1-x}</math>. Вычислим <math>{\tau}^{2}(x)</math>. У нас получится: : <math>{\tau}^{2}(x)=\dfrac{1}{1-\dfrac{1}{1-x}} = \dfrac{1-x}{1-x-1}=\dfrac{x-1}{x}={\tau}^{-1}(x).</math> Значит, <math>{\tau}^{3}=e</math>. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>f{\left(x\right)}\cdot {f{\left(\dfrac{1}{1-x}\right)}}=\dfrac{1-x}{x}</math>. |- | <code>Шаг 1</code> Напишем схему данного уравнения: <math>f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}}=-{\tau}^{-1}(x)</math>. <code>Шаг 2</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}^{-1}(x)</math>. Получим: : <center><math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(\tau({\tau}^{-1}(x))\right)}}=-{\tau}^{-1}({\tau}^{-1}(x)) \Longrightarrow f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}^{-2}(x).</math></center> Но так как <math>{\tau}^{2}(x)={\tau}^{-1}(x)</math>, то <math>{\tau}^{-2}(x)={\tau}(x)</math>. Поэтому <math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}(x)</math>. <code>Шаг 3</code> Теперь из результатов <code>Шага 1</code> и <code>Шага 2</code> делаем простой вывод: : <center><math>f(x)=\dfrac{-{\tau(x)}}{f{\left({\tau}^{-1}(x)\right)}} = \dfrac{{-{\tau}}^{-1}(x)}{f{\left({\tau}(x)\right)}}.</math></center> <code>Шаг 4</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}(x)</math>. Имеем: : <center><math>f{\left({\tau}^{-1}(x)\right)}=\dfrac{-x}{f{\left({\tau}(x)\right)}}=\dfrac{{-{\tau}}(x)}{f{\left(x\right)}}.</math></center> <code>Шаг 5</code> Наконец-то, мы <br><br><math> \begin{cases} \begin{array} {rcrcc} \dfrac{-x}{f{\left({\tau}(x)\right)}} = \dfrac{{-{\tau}}(x)}{f{\left(x\right)}}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases} \Longrightarrow \begin{cases} \begin{array} {rcrcc} {f{\left({\tau}(x)\right)}} = \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases}.</math> <code>Шаг 6</code> Подставим выражение <math>{f{\left({\tau}(x)\right)}}</math> во вторую строчку системы. Итак, : <math>f{\left(x\right)}\cdot \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)} = -{\tau}^{-1}(x) \Longleftrightarrow f{\left(x\right)}\cdot f{\left(x\right)} = \dfrac{{-{\tau}}(x) \cdot {{\tau}^{-1}{\left(x\right)}}}{x}.</math> <u>'''Ответ'''</u>: <math>f{\left(x\right)} = \pm{\sqrt{\dfrac{{-{\tau}}(x) \cdot {{\tau}^{-1}{\left(x\right)}}}{x}}} = \pm{\dfrac{1}{x}}</math>, или <math>f{\left(x\right)} = \dfrac{1}{x} // \& // x\neq 0.</math> |} == Инволюция в алгебре == [[w:Перестановка|Перестановка]] <math>\tau</math> является инволюцией, если <math>\tau\circ\tau=id</math>, каждая инволюция является произведением непересекающихся транспозиций, например: : <math>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 5 & 7 & 4 & 3 & 1 & 8 & 2 & 6\end{pmatrix} = (1,5)(2,7)(3,4)(6,8)</math>. Число инволюций в [[w:Группа перестановок|группе перестановок]] порядка <math>n</math> определяется по формулам: * <math> a(0) = 1,\ a(1) = 1,\ a(n) = a(n-1) + (n-1)a(n-2),\ n>1</math> (рекуррентная формула), * <math>a(n) = \sum_{k=0}^{[ n/2 ]}{\frac{n!}{2^k\cdot (n-2k)!\cdot k!}}</math>, (первые значения <math>a(n)</math>: 1, {{w:nums|link=nrl|1|2|4|10|26|76|232|764|2620|9496|35696|140152}}<ref>{{OEIS long|A000085|lc=1}}</ref>). Свойства инволюции обеспечивают ей широкое применение в различных приложения, например, инволютивные преобразования над пространством булевых векторов используются в различных схемах построения симметричных [[w:криптоалгоритм|криптоалгоритм]]ов, таких как [[w:Сеть Фейстеля|сети Фейстеля]] и [[w:SP-сеть|подстановочно-перестановочные сети]]. == Примечания == bb67b5pkhqbuvqyjdicd3vjopqan786 220992 220991 2022-07-19T20:59:42Z Va musinov 69698 /* Лирическое отступление */ wikitext text/x-wiki '''Инволю́ция''' (от {{lang-la|involutio}} — свёртывание, завиток) — нетождественное преобразование, которое является [[w:обратная функция|обратным]] самому себе, то есть своей собственной [[w:обратная функция|инверсией]]. Это [[w:унарная операция|унарная операция]]. Формально, функция <math>f</math> называется инволюцией, если <math>f(f(x)) = x</math> для всякого <math>x</math> из [[w:Область определения функции|области определения функции]] <math>f</math>. Иногда пишут: <math>f\circ f= {f}^{2}=id</math>, где <math>id</math> обозначает тождественное преобразование. Вместо <math>id(x)</math> используют запись: <math>e(x)=x</math>. Таким образом, двойное применение функции <math>f</math> даёт исходное значение. == Свойства == Любая инволюция — это [[w:биекция|биекция]]. Если преобразование <math>f</math> инволютивное, то для любого выражения <math>A</math> и его образа <math>B=f(A)</math> имеем <math>f(B)=A</math>. В самом деле, <math>f(B)= f(f(A))=id(A)={id}_{A}=A</math>. '''''Критерий инволюции'''''. Функция <math>f</math> является инволюцией тогда и только тогда, когда для всякого выражения <math>A</math> существует такое выражение <math>B</math>, что <math>f(A)=B\neq A</math> и <math>f(B)=A</math>. Другими словами, преобразование является инволюцией в том и только в том случае, когда оно меняет местами какие-либо два выражения. ---- Если <math>f</math> — инволюция, то имеют место следующие соотношения: * <math>\forall a \in D_{f}: f^{-1}(a) = f(a)</math> [основное свойство] * <math>D_{f} = E_{f}</math> * <math>\forall a : f(f(a)) = a</math> * <math>\forall a, \exists b : f(a) = b \land f(b) = a</math> [критерий] == Примеры == Примеры инволюций: * <math>f(x) = -x</math>, заданная на множестве [[w:целое число|целых]] <math>\mathbb{Z}</math>, [[w:рациональное число|рациональных]] <math>\mathbb{Q}</math> или [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>; * простейшие инволюции на множестве [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>: *: <math>\dfrac{a}{x}</math>, <math>a-x</math>, <math>\dfrac{x}{x-1}</math>, <math>\dfrac{x+1}{x-1}</math>, <math>\dfrac{x-1}{x+1}</math>, <math>\dfrac{ax+b}{cx-a}</math>; * инволюция <math>f(x) = \dfrac{b}{x-a} + a</math> при <math>x\in \mathbb{R} \setminus \left\{a\right\}</math> и <math>b\neq 0</math>; * <math>f(x)= \bar{x}</math> — [[w:дополнение множества|дополнение множества]], заданная для подмножеств некоторого универсального множества <math>U</math>; * <math>f(x)= \neg x</math> — [[w:логическое отрицание|логическое отрицание]] [[w:булева алгебра|булевой алгебры]]; * [[w:Симметрия|симметрии]]: [[w:Центральная симметрия|центральная]], [[w:Осевая симметрия|осевая]], [[w:Зеркальная симметрия|зеркальная]]; * [[w:инверсия (геометрия)|инверсия]]; * [[w:комплексное сопряжение|комплексное сопряжение]]; * [[w:преобразование Лежандра|преобразование Лежандра]] * при факторизации обычного тора (точнее, одномерного комплексного тора, ещё точнее, эллиптической кривой) <math>E</math> по инволюции вида <math>x\mapsto -x</math> получается сфера; * Если представить, что <math>f</math> — нажатие на клавишу [[w:выключатель бытовой| бытового накладного выключателя]] (т. е. включить либо выключить свет), то <math>f</math> будет инволюцией. == Важнейшие факты == ;'''Теорема 1'''. : Композиция <math>{f}\circ{g}</math> двух инволюций <math>f</math> и <math>g</math> является инволюцией тогда и только тогда, когда они коммутируют: <math>{f}\circ{g} =g\circ f</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Пусть дана композиция <math>{f}\circ{g}</math>, в которой <math>f</math>, <math>g</math> — инволюции. Это означает, что <math>f=f^{-1}</math> и <math>g=g^{-1}</math>, а также <math>{f}\circ{g}={\left({f}\circ{g}\right)}^{-1}</math>. Имеем: <math>{f}\circ{g}= {\left({f}\circ{g}\right)}^{-1}={g^{-1}}\circ {f^{-1}}={g}\circ{f}</math>. Если <math>{f}\circ{g}</math> — инволюция, то двигаемся слева направо. Обратно, если выполняется равенство <math>{f}\circ{g} =g\circ f</math>, то справа налево. |} <code>Пример 1</code>. Такая композиция <math>\left(f_{1} \circ f_{2}\right) (x) = \left(f_{2} \circ f_{1} \right) (x) = {f_{3}} (x) = -{\dfrac{1}{x}}</math> есть инволюция. Аналогично, если <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math> и <math>g</math>, <math>h</math>, <math>k</math> — инволюции, то и <math>f</math> — инволюция. <code>Пример 2</code>. <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. ; '''Теорема 2'''. : Если <math>{f}</math> — монотонно возрастающая функция, то уравнения <math>{f}(x)=x</math> и <math>f(f(x))=x</math>, или <math>{f}(x)={f^{-1}}(x)</math>, равносильны. Рассмотрим следующую задачу. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>\sqrt{1+\sqrt{x}}=x-1</math>. |- | Перепишем данное уравнение в виде: <math>1+\sqrt{1+\sqrt{x}}=x</math>. Рассмотрим теперь функцию <math>f(x)=1+\sqrt{x}</math>. Тогда полученное уравнение примет вид: <math>f(f(x))=x</math>. Для решений уравнений такого вида применим '''теорему 2'''. Но сначала следует убедиться, что введённая функция <math>f</math> действительно монотонно возрастает. Для того чтобы <math>f(x)</math> была строго возрастающей, достаточно (но не является необходимым условием), чтобы <math>f'(x)>0</math>. В нашем случае получается <math>f'(x)=\dfrac{1}{2\sqrt{x}}>0</math>. В соответствии с приведённой '''теоремой 2''' приходим к равносильному уравнению <math>{f}(x)=x</math>, или <math>1+\sqrt{x}=x</math>, решение которого уже не сложно. Ответ: <math>x = \dfrac{3+\sqrt{5}}{2}.</math> |} ; '''Теорема 3'''. : Функция вида <math>f={h}\circ{g}\circ{h^{-1}}</math> (где <math>h</math> — некоторое биективное отображение) будет инволюцией в том и только в том случае, если функция <math>g</math> — инволюция. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Имеем следующее: <math>f=f^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {\left({h}\circ{g}\circ{h^{-1}}\right)}^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {{h}\circ{g^{-1}}\circ{h^{-1}}} \mid { \circ h} \Longleftrightarrow {h}\circ{g}={h}\circ{g^{-1}} \Longleftrightarrow {h^{-1} \circ } \mid {{h}\circ{g}={h}\circ{g^{-1}}} \Longleftrightarrow g = g^{-1}.</math> Если <math>{f}</math> является инволюцией, то двигаемся слева направо. Обратно, если <math>{g}</math> — инволюция, то справа налево. Теорема доказана. |} ''Замечание''. Ясно, что '''теорема 3''' сохраняет свою силу, если <math>f={h^{-1}}\circ{g}\circ{h}</math>, где <math>h</math> — биекция. <code>Пример 3</code>. В положительных числах такая функция будет как раз инволюцией по доказанной выше теореме: : <math>ln\left(\dfrac{e^x+1}{e^x-1}\right).</math> ; '''Следствие'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Тогда если <math>h</math> — взаимно-однозначное отображение [биекция] множества <math>E</math> на <math>F</math> с обратной биекцией <math>h^{-1}</math>, то композиция <math>h\circ f\circ h^{-1}</math> — инволюция на множестве <math>F</math>. [[File:Involution4.png|Involution4]] {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Утверждение очевидно по предыдущему. ''Указание''. Воспользоваться '''теоремой 3'''. |} ; '''Теорема 4'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Если <math>h</math> — такое отображение из <math>E</math> в <math>E</math>, что <math>h\circ f\circ h = f</math>, то <math>h\circ f</math> и <math>f\circ h</math> — инволюции на <math>E</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Покажем, что из исходного равенства <math>h\circ f\circ h = f</math> и условия <math>f=f^{-1}</math> получается инволютивная функция <math>h\circ f</math>. Итак, : <math>h\circ f\circ h = f \mid { \circ h^{-1}} \Longrightarrow h\circ f = f \circ h^{-1} \Longrightarrow h \circ f = {\left(h \circ f^{-1}\right)}^{-1} \Longrightarrow h \circ f = {\left(h \circ f \right)}^{-1} \mid {\circ {\left(h \circ f \right)}} \Longrightarrow {\left(h \circ f \right)}^{2} = e.</math> Таким образом, композиция <math>h\circ f</math> по определению является инволюцией. Аналогично проводится доказательство для <math>f\circ h</math>. |} {| class="wikitable collapsible collapsed" width="100%" ! Пусть дана функция <math>f=h\circ g\circ h\circ g^{-1}</math>, где <math>g</math> — биекция, а <math>h=h^{-1}</math>. Выяснить, при каком условии <math>f</math> будет инволютивной. |- | <u>''Решение''</u>. Во-первых, функция <math>f</math> будет инволюцией, если выполняется равенство: <math>f=f^{-1}</math>. Во-вторых, стоит заметить, что <math>h \circ f = g\circ h\circ g^{-1} = f^{-1} \circ h </math>. Поэтому <math>f=f^{-1} \Longleftrightarrow f = h \circ f \circ h</math>. Но по '''следствию''' композиция <math>g \circ h \circ g^{-1}</math> является инволюцией, а значит, и <math>h \circ f</math> — тоже инволюция. Наконец, <math> h\circ \mid f = h \circ f \circ h \Longleftrightarrow h\circ f = f \circ h</math>, то есть <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}</math>. ''Ответ'': <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}.</math> |} <code>Пример 4</code>. Функция <math>f(x)= -ln\left(-e^{x}\right)</math>. <u>'''Упражнение'''</u>. Убедитесь, что представленная функция действительно обладает таким свойством. ''Схемой'', или ''строением'', функции <math>f</math> назовём последовательность функций <math>f_{1}, f_{2}, ... , f_{n-1}, f_{n}</math> так, что каждая из них является либо элементарной, либо инволюцией и <math>f=f_{n} \circ f_{n-1} \circ ... \circ f_{2} \circ f_{1}</math>. <code>Пример 5</code>. Пусть <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. Тогда схемой функции <math>f</math> будет <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math>. == Фокус == {| class="wikitable collapsible collapsed" width=100% ! Целое общество гостей, непосвящённых в арифметические тайны, вы можете поразить следующим фокусом. |- | Фокусник просит одного человека написать на бумажке, секретно от него, трёхзначное число, какое этот человек хочет, и затем просит приписать к нему ещё раз то же самое число. Получится шестизначное число, состоящее из трёх повторяющихся цифр. Фокусник предлагает тому же товарищу или его соседу разделить — секретно от него — это число на 7; при этом фокусник заранее предсказывает, что остатка не получится. Результат деления передаётся соседу, который, по предложению ведущего, делит его на 11; и хотя фокусник не знает делимого, он всё же смело утверждает, что и оно разделится без остатка. Полученный результат фокусник направляет следующему соседу, которого просит разделить это число на 13 — деление снова выполняется без остатка, о чём он заранее предупреждает. Результат третьего деления фокусник, не глядя на полученное число, вручает первому товарищу со словами: — Вот число, которое вы задумали! — Так и есть: вы угадали. |} <code>Какова разгадка этого фокуса?</code> ''Указание''. Возьмите за функцию <math>f</math> алгоритм приписывания к числу <math>x\rightleftharpoons \overline{abc}</math>, то есть <math>f(x)= \overline{abcabc}</math>. Так как результат совпадает с исходным числом <math>x\rightleftharpoons \overline{abc}</math>, то <math>f^{-1}</math> над числом — это умножение его на 7, 11 и 13. Осталось найти связь <math>f</math> и <math>f^{-1}</math>. == Лирическое отступление == Приведём пример композиции двух инволюций, которая не будет уже инволюцией. <code>Пример</code>. Функция <math>\tau(x)=\dfrac{1}{1-x}</math> не является инволюцией; её строение таково: <math>\tau=\alpha \circ \beta</math>, где <math>\alpha (x) = \dfrac{1}{x}</math> и <math>\beta (x) = 1-x</math> у нас — обе инволюции. '''''Упражнение'''''. Докажите: для <math>\tau(x)=\dfrac{1}{1-x}</math> верно, что <math>\tau \neq {\tau}^{-1}</math>. ''Замечание''. Функция <math>{{\tau}^{-1}}{\left(x\right)}=1-{\dfrac{1}{x}}=\dfrac{x-1}{x}</math> со схемой <math>{\tau}^{-1}=\beta \circ \alpha</math> также не есть инволюция. Легко видеть, что <math>\alpha \circ {{\tau}^{-1}}</math> — инволюция. Делаем вывод, что композиция инволюции и неинволютивной функции может давать инволюцию в результате. Вопрос: ''в каком случае это происходит?'' Перед тем, как ответить на этот вопрос, сперва-наперво выясним, а каким свойством, в принципе, обладает введённая функция <math>\tau(x)=\dfrac{1}{1-x}</math>. Вычислим <math>{\tau}^{2}(x)</math>. У нас получится: : <math>{\tau}^{2}(x)=\dfrac{1}{1-\dfrac{1}{1-x}} = \dfrac{1-x}{1-x-1}=\dfrac{x-1}{x}={\tau}^{-1}(x).</math> Значит, <math>{\tau}^{3}=e</math>. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>f{\left(x\right)}\cdot {f{\left(\dfrac{1}{1-x}\right)}}=\dfrac{1-x}{x}</math>. |- | <code>Шаг 1</code> Напишем схему данного уравнения: <math>f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}}=-{\tau}^{-1}(x)</math>. <code>Шаг 2</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}^{-1}(x)</math>. Получим: : <center><math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(\tau({\tau}^{-1}(x))\right)}}=-{\tau}^{-1}({\tau}^{-1}(x)) \Longrightarrow f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}^{-2}(x).</math></center> Но так как <math>{\tau}^{2}(x)={\tau}^{-1}(x)</math>, то <math>{\tau}^{-2}(x)={\tau}(x)</math>. Поэтому <math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}(x)</math>. <code>Шаг 3</code> Теперь из результатов <code>Шага 1</code> и <code>Шага 2</code> делаем простой вывод: : <center><math>f(x)=\dfrac{-{\tau(x)}}{f{\left({\tau}^{-1}(x)\right)}} = \dfrac{{-{\tau}}^{-1}(x)}{f{\left({\tau}(x)\right)}}.</math></center> <code>Шаг 4</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}(x)</math>. Имеем: : <center><math>f{\left({\tau}^{-1}(x)\right)}=\dfrac{-x}{f{\left({\tau}(x)\right)}}=\dfrac{{-{\tau}}(x)}{f{\left(x\right)}}.</math></center> <code>Шаг 5</code> Наконец-то, мы <br><br><math> \begin{cases} \begin{array} {rcrcc} \dfrac{-x}{f{\left({\tau}(x)\right)}} = \dfrac{{-{\tau}}(x)}{f{\left(x\right)}}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases} \Longrightarrow \begin{cases} \begin{array} {rcrcc} {f{\left({\tau}(x)\right)}} = \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases}.</math> <code>Шаг 6</code> Подставим выражение <math>{f{\left({\tau}(x)\right)}}</math> во вторую строчку системы. Итак, : <math>f{\left(x\right)}\cdot \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)} = -{\tau}^{-1}(x) \Longleftrightarrow f{\left(x\right)}\cdot f{\left(x\right)} = \dfrac{{-{\tau}}(x) \cdot {{\tau}^{-1}{\left(x\right)}}}{x}.</math> <u>'''Ответ'''</u>: <math>f{\left(x\right)} = \pm{\sqrt{\dfrac{{-{\tau}}(x) \cdot {{\tau}^{-1}{\left(x\right)}}}{x}}} = \pm{\dfrac{1}{x}}</math>, или <math>f{\left(x\right)} = \dfrac{1}{x} \, \& \, x\neq 0.</math> |} == Инволюция в алгебре == [[w:Перестановка|Перестановка]] <math>\tau</math> является инволюцией, если <math>\tau\circ\tau=id</math>, каждая инволюция является произведением непересекающихся транспозиций, например: : <math>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 5 & 7 & 4 & 3 & 1 & 8 & 2 & 6\end{pmatrix} = (1,5)(2,7)(3,4)(6,8)</math>. Число инволюций в [[w:Группа перестановок|группе перестановок]] порядка <math>n</math> определяется по формулам: * <math> a(0) = 1,\ a(1) = 1,\ a(n) = a(n-1) + (n-1)a(n-2),\ n>1</math> (рекуррентная формула), * <math>a(n) = \sum_{k=0}^{[ n/2 ]}{\frac{n!}{2^k\cdot (n-2k)!\cdot k!}}</math>, (первые значения <math>a(n)</math>: 1, {{w:nums|link=nrl|1|2|4|10|26|76|232|764|2620|9496|35696|140152}}<ref>{{OEIS long|A000085|lc=1}}</ref>). Свойства инволюции обеспечивают ей широкое применение в различных приложения, например, инволютивные преобразования над пространством булевых векторов используются в различных схемах построения симметричных [[w:криптоалгоритм|криптоалгоритм]]ов, таких как [[w:Сеть Фейстеля|сети Фейстеля]] и [[w:SP-сеть|подстановочно-перестановочные сети]]. == Примечания == ne69n37iek99ztb1vkrwfd6b4wkqz76 220994 220992 2022-07-20T11:08:53Z Va musinov 69698 wikitext text/x-wiki '''Инволю́ция''' (от {{lang-la|involutio}} — свёртывание, завиток) — нетождественное преобразование, которое является [[w:обратная функция|обратным]] самому себе, то есть своей собственной [[w:обратная функция|инверсией]]. Это [[w:унарная операция|унарная операция]]. Формально, функция <math>f</math> называется инволюцией, если <math>f(f(x)) = x</math> для всякого <math>x</math> из [[w:Область определения функции|области определения функции]] <math>f</math>. Иногда пишут: <math>f\circ f= {f}^{2}=id</math>, где <math>id</math> обозначает тождественное преобразование. Вместо <math>id(x)</math> используют запись: <math>e(x)=x</math>. Таким образом, двойное применение функции <math>f</math> даёт исходное значение. == Свойства == Любая инволюция — это [[w:биекция|биекция]]. Если преобразование <math>f</math> инволютивное, то для любого выражения <math>A</math> и его образа <math>B=f(A)</math> имеем <math>f(B)=A</math>. В самом деле, <math>f(B)= f(f(A))=id(A)={id}_{A}=A</math>. '''''Критерий инволюции'''''. Функция <math>f</math> является инволюцией тогда и только тогда, когда для всякого выражения <math>A</math> существует такое выражение <math>B</math>, что <math>f(A)=B\neq A</math> и <math>f(B)=A</math>. Другими словами, преобразование является инволюцией в том и только в том случае, когда оно меняет местами какие-либо два выражения. ---- Если <math>f</math> — инволюция, то имеют место следующие соотношения: * <math>\forall a \in D_{f}: f^{-1}(a) = f(a)</math> [основное свойство] * <math>D_{f} = E_{f}</math> * <math>\forall a : f(f(a)) = a</math> * <math>\forall a, \exists b : f(a) = b \land f(b) = a</math> [критерий] == Примеры == Примеры инволюций: * <math>f(x) = -x</math>, заданная на множестве [[w:целое число|целых]] <math>\mathbb{Z}</math>, [[w:рациональное число|рациональных]] <math>\mathbb{Q}</math> или [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>; * простейшие инволюции на множестве [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>: *: <math>\dfrac{a}{x}</math>, <math>a-x</math>, <math>\dfrac{x}{x-1}</math>, <math>\dfrac{x+1}{x-1}</math>, <math>\dfrac{x-1}{x+1}</math>, <math>\dfrac{ax+b}{cx-a}</math>; * инволюция <math>f(x) = \dfrac{b}{x-a} + a</math> при <math>x\in \mathbb{R} \setminus \left\{a\right\}</math> и <math>b\neq 0</math>; * <math>f(x)= \bar{x}</math> — [[w:дополнение множества|дополнение множества]], заданная для подмножеств некоторого универсального множества <math>U</math>; * <math>f(x)= \neg x</math> — [[w:логическое отрицание|логическое отрицание]] [[w:булева алгебра|булевой алгебры]]; * [[w:Симметрия|симметрии]]: [[w:Центральная симметрия|центральная]], [[w:Осевая симметрия|осевая]], [[w:Зеркальная симметрия|зеркальная]]; * [[w:инверсия (геометрия)|инверсия]]; * [[w:комплексное сопряжение|комплексное сопряжение]]; * [[w:преобразование Лежандра|преобразование Лежандра]] * при факторизации обычного тора (точнее, одномерного комплексного тора, ещё точнее, эллиптической кривой) <math>E</math> по инволюции вида <math>x\mapsto -x</math> получается сфера; * Если представить, что <math>f</math> — нажатие на клавишу [[w:выключатель бытовой| бытового накладного выключателя]] (т. е. включить либо выключить свет), то <math>f</math> будет инволюцией. == Важнейшие факты == ;'''Теорема 1'''. : Композиция <math>{f}\circ{g}</math> двух инволюций <math>f</math> и <math>g</math> является инволюцией тогда и только тогда, когда они коммутируют: <math>{f}\circ{g} =g\circ f</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Пусть дана композиция <math>{f}\circ{g}</math>, в которой <math>f</math>, <math>g</math> — инволюции. Это означает, что <math>f=f^{-1}</math> и <math>g=g^{-1}</math>, а также <math>{f}\circ{g}={\left({f}\circ{g}\right)}^{-1}</math>. Имеем: <math>{f}\circ{g}= {\left({f}\circ{g}\right)}^{-1}={g^{-1}}\circ {f^{-1}}={g}\circ{f}</math>. Если <math>{f}\circ{g}</math> — инволюция, то двигаемся слева направо. Обратно, если выполняется равенство <math>{f}\circ{g} =g\circ f</math>, то справа налево. |} <code>Пример 1</code>. Такая композиция <math>\left(f_{1} \circ f_{2}\right) (x) = \left(f_{2} \circ f_{1} \right) (x) = {f_{3}} (x) = -{\dfrac{1}{x}}</math> есть инволюция. Аналогично, если <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math> и <math>g</math>, <math>h</math>, <math>k</math> — инволюции, то и <math>f</math> — инволюция. <code>Пример 2</code>. <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. ; '''Теорема 2'''. : Если <math>{f}</math> — монотонно возрастающая функция, то уравнения <math>{f}(x)=x</math> и <math>f(f(x))=x</math>, или <math>{f}(x)={f^{-1}}(x)</math>, равносильны. Рассмотрим следующую задачу. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>\sqrt{1+\sqrt{x}}=x-1</math>. |- | Перепишем данное уравнение в виде: <center><math>1+\sqrt{1+\sqrt{x}}=x.</math></center> Рассмотрим теперь функцию <math>f(x)=1+\sqrt{x}</math>. Тогда полученное уравнение примет вид: <math>f(f(x))=x.</math> Для решений уравнений такого вида применим '''теорему 2'''. Но сначала следует убедиться, что введённая функция <math>f</math> действительно монотонно возрастает. Для того чтобы <math>f(x)</math> была строго возрастающей, достаточно (но не является необходимым условием), чтобы <math>f'(x)>0</math>. В нашем случае получается <math>f'(x)=\dfrac{1}{2\sqrt{x}}>0</math>. В соответствии с приведённой '''теоремой 2''' приходим к равносильному уравнению <math>{f}(x)=x</math>, или <math>1+\sqrt{x}=x</math>, решение которого уже не сложно. Ответ: <math>x = \dfrac{3+\sqrt{5}}{2}.</math> |} ; '''Теорема 3'''. : Функция вида <math>f={h}\circ{g}\circ{h^{-1}}</math> (где <math>h</math> — некоторое биективное отображение) будет инволюцией в том и только в том случае, если функция <math>g</math> — инволюция. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Имеем следующее: <math>f=f^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {\left({h}\circ{g}\circ{h^{-1}}\right)}^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {{h}\circ{g^{-1}}\circ{h^{-1}}} \mid { \circ h} \Longleftrightarrow {h}\circ{g}={h}\circ{g^{-1}} \Longleftrightarrow {h^{-1} \circ } \mid {{h}\circ{g}={h}\circ{g^{-1}}} \Longleftrightarrow g = g^{-1}.</math> Если <math>{f}</math> является инволюцией, то двигаемся слева направо. Обратно, если <math>{g}</math> — инволюция, то справа налево. Теорема доказана. |} ''Замечание''. Ясно, что '''теорема 3''' сохраняет свою силу, если <math>f={h^{-1}}\circ{g}\circ{h}</math>, где <math>h</math> — биекция. <code>Пример 3</code>. В положительных числах такая функция будет как раз инволюцией по доказанной выше теореме: : <math>ln\left(\dfrac{e^x+1}{e^x-1}\right).</math> ; '''Следствие'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Тогда если <math>h</math> — взаимно-однозначное отображение [биекция] множества <math>E</math> на <math>F</math> с обратной биекцией <math>h^{-1}</math>, то композиция <math>h\circ f\circ h^{-1}</math> — инволюция на множестве <math>F</math>. [[File:Involution4.png|Involution4]] {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Утверждение очевидно по предыдущему. ''Указание''. Воспользоваться '''теоремой 3'''. |} ; '''Теорема 4'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Если <math>h</math> — такое отображение из <math>E</math> в <math>E</math>, что <math>h\circ f\circ h = f</math>, то <math>h\circ f</math> и <math>f\circ h</math> — инволюции на <math>E</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Покажем, что из исходного равенства <math>h\circ f\circ h = f</math> и условия <math>f=f^{-1}</math> получается инволютивная функция <math>h\circ f</math>. Итак, : <math>h\circ f\circ h = f \mid { \circ h^{-1}} \Longrightarrow h\circ f = f \circ h^{-1} \Longrightarrow h \circ f = {\left(h \circ f^{-1}\right)}^{-1} \Longrightarrow h \circ f = {\left(h \circ f \right)}^{-1} \mid {\circ {\left(h \circ f \right)}} \Longrightarrow {\left(h \circ f \right)}^{2} = e.</math> Таким образом, композиция <math>h\circ f</math> по определению является инволюцией. Аналогично проводится доказательство для <math>f\circ h</math>. |} {| class="wikitable collapsible collapsed" width="100%" ! Пусть дана функция <math>f=h\circ g\circ h\circ g^{-1}</math>, где <math>g</math> — биекция, а <math>h=h^{-1}</math>. Выяснить, при каком условии <math>f</math> будет инволютивной. |- | <u>''Решение''</u>. Во-первых, функция <math>f</math> будет инволюцией, если выполняется равенство: <math>f=f^{-1}</math>. Во-вторых, стоит заметить, что <math>h \circ f = g\circ h\circ g^{-1} = f^{-1} \circ h </math>. Поэтому <math>f=f^{-1} \Longleftrightarrow f = h \circ f \circ h</math>. Но по '''следствию''' композиция <math>g \circ h \circ g^{-1}</math> является инволюцией, а значит, и <math>h \circ f</math> — тоже инволюция. Наконец, <math> h\circ \mid f = h \circ f \circ h \Longleftrightarrow h\circ f = f \circ h</math>, то есть <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}</math>. ''Ответ'': <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}.</math> |} <code>Пример 4</code>. Функция <math>f(x)= -ln\left(-e^{x}\right)</math>. <u>'''Упражнение'''</u>. Убедитесь, что представленная функция действительно обладает таким свойством. ''Схемой'', или ''строением'', функции <math>f</math> назовём последовательность функций <math>f_{1}, f_{2}, ... , f_{n-1}, f_{n}</math> так, что каждая из них является либо элементарной, либо инволюцией и <math>f=f_{n} \circ f_{n-1} \circ ... \circ f_{2} \circ f_{1}</math>. <code>Пример 5</code>. Пусть <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. Тогда схемой функции <math>f</math> будет <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math>. == Фокус == {| class="wikitable collapsible collapsed" width=100% ! Целое общество гостей, непосвящённых в арифметические тайны, вы можете поразить следующим фокусом. |- | Фокусник просит одного человека написать на бумажке, секретно от него, трёхзначное число, какое этот человек хочет, и затем просит приписать к нему ещё раз то же самое число. Получится шестизначное число, состоящее из трёх повторяющихся цифр. Фокусник предлагает тому же товарищу или его соседу разделить — секретно от него — это число на 7; при этом фокусник заранее предсказывает, что остатка не получится. Результат деления передаётся соседу, который, по предложению ведущего, делит его на 11; и хотя фокусник не знает делимого, он всё же смело утверждает, что и оно разделится без остатка. Полученный результат фокусник направляет следующему соседу, которого просит разделить это число на 13 — деление снова выполняется без остатка, о чём он заранее предупреждает. Результат третьего деления фокусник, не глядя на полученное число, вручает первому товарищу со словами: — Вот число, которое вы задумали! — Так и есть: вы угадали. |} <code>Какова разгадка этого фокуса?</code> ''Указание''. Возьмите за функцию <math>f</math> алгоритм приписывания к числу <math>x\rightleftharpoons \overline{abc}</math>, то есть <math>f(x)= \overline{abcabc}</math>. Так как результат совпадает с исходным числом <math>x\rightleftharpoons \overline{abc}</math>, то <math>f^{-1}</math> над числом — это умножение его на 7, 11 и 13. Осталось найти связь <math>f</math> и <math>f^{-1}</math>. == Лирическое отступление == Приведём пример композиции двух инволюций, которая не будет уже инволюцией. <code>Пример</code>. Функция <math>\tau(x)=\dfrac{1}{1-x}</math> не является инволюцией; её строение таково: <math>\tau=\alpha \circ \beta</math>, где <math>\alpha (x) = \dfrac{1}{x}</math> и <math>\beta (x) = 1-x</math> у нас — обе инволюции. '''''Упражнение'''''. Докажите: для <math>\tau(x)=\dfrac{1}{1-x}</math> верно, что <math>\tau \neq {\tau}^{-1}</math>. ''Замечание''. Функция <math>{{\tau}^{-1}}{\left(x\right)}=1-{\dfrac{1}{x}}=\dfrac{x-1}{x}</math> со схемой <math>{\tau}^{-1}=\beta \circ \alpha</math> также не есть инволюция. Легко видеть, что <math>\alpha \circ {{\tau}^{-1}}</math> — инволюция. Делаем вывод, что композиция инволюции и неинволютивной функции может давать инволюцию в результате. Вопрос: ''в каком случае это происходит?'' Перед тем, как ответить на этот вопрос, сперва-наперво выясним, а каким свойством, в принципе, обладает введённая функция <math>\tau(x)=\dfrac{1}{1-x}</math>. Вычислим <math>{\tau}^{2}(x)</math>. У нас получится: : <math>{\tau}^{2}(x)=\dfrac{1}{1-\dfrac{1}{1-x}} = \dfrac{1-x}{1-x-1}=\dfrac{x-1}{x}={\tau}^{-1}(x).</math> Значит, <math>{\tau}^{3}=e</math>. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>f{\left(x\right)}\cdot {f{\left(\dfrac{1}{1-x}\right)}}=\dfrac{1-x}{x}</math>. |- | <code>Шаг 1</code> Напишем схему данного уравнения: <math>f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}}=-{\tau}^{-1}(x)</math>. <code>Шаг 2</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}^{-1}(x)</math>. Получим: : <center><math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(\tau({\tau}^{-1}(x))\right)}}=-{\tau}^{-1}({\tau}^{-1}(x)) \Longrightarrow f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}^{-2}(x).</math></center> Но так как <math>{\tau}^{2}(x)={\tau}^{-1}(x)</math>, то <math>{\tau}^{-2}(x)={\tau}(x)</math>. Поэтому <math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}(x)</math>. <code>Шаг 3</code> Теперь из результатов <code>Шага 1</code> и <code>Шага 2</code> делаем простой вывод: : <center><math>f(x)=\dfrac{-{\tau(x)}}{f{\left({\tau}^{-1}(x)\right)}} = \dfrac{{-{\tau}}^{-1}(x)}{f{\left({\tau}(x)\right)}}.</math></center> <code>Шаг 4</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}(x)</math>. Имеем: : <center><math>f{\left({\tau}^{-1}(x)\right)}=\dfrac{-x}{f{\left({\tau}(x)\right)}}=\dfrac{{-{\tau}}(x)}{f{\left(x\right)}}.</math></center> <code>Шаг 5</code> Наконец-то, мы <br><br><math> \begin{cases} \begin{array} {rcrcc} \dfrac{-x}{f{\left({\tau}(x)\right)}} = \dfrac{{-{\tau}}(x)}{f{\left(x\right)}}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases} \Longrightarrow \begin{cases} \begin{array} {rcrcc} {f{\left({\tau}(x)\right)}} = \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases}.</math> <code>Шаг 6</code> Подставим выражение <math>{f{\left({\tau}(x)\right)}}</math> во вторую строчку системы. Итак, : <math>f{\left(x\right)}\cdot \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)} = -{\tau}^{-1}(x) \Longleftrightarrow f{\left(x\right)}\cdot f{\left(x\right)} = \dfrac{{-{\tau}}(x) \cdot {{\tau}^{-1}{\left(x\right)}}}{x}.</math> <u>'''Ответ'''</u>: <math>f{\left(x\right)} = \pm{\sqrt{\dfrac{{-{\tau}}(x) \cdot {{\tau}^{-1}{\left(x\right)}}}{x}}} = \pm{\dfrac{1}{x}}</math>, или <math>f{\left(x\right)} = \dfrac{1}{x} \, \& \, x\neq 0.</math> |} == Инволюция в алгебре == [[w:Перестановка|Перестановка]] <math>\tau</math> является инволюцией, если <math>\tau\circ\tau=id</math>, каждая инволюция является произведением непересекающихся транспозиций, например: : <math>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 5 & 7 & 4 & 3 & 1 & 8 & 2 & 6\end{pmatrix} = (1,5)(2,7)(3,4)(6,8)</math>. Число инволюций в [[w:Группа перестановок|группе перестановок]] порядка <math>n</math> определяется по формулам: * <math> a(0) = 1,\ a(1) = 1,\ a(n) = a(n-1) + (n-1)a(n-2),\ n>1</math> (рекуррентная формула), * <math>a(n) = \sum_{k=0}^{[ n/2 ]}{\frac{n!}{2^k\cdot (n-2k)!\cdot k!}}</math>, (первые значения <math>a(n)</math>: 1, {{w:nums|link=nrl|1|2|4|10|26|76|232|764|2620|9496|35696|140152}}<ref>{{OEIS long|A000085|lc=1}}</ref>). Свойства инволюции обеспечивают ей широкое применение в различных приложения, например, инволютивные преобразования над пространством булевых векторов используются в различных схемах построения симметричных [[w:криптоалгоритм|криптоалгоритм]]ов, таких как [[w:Сеть Фейстеля|сети Фейстеля]] и [[w:SP-сеть|подстановочно-перестановочные сети]]. == Примечания == dwikk49e8i8p4ayx9greqf5dg13ulpz 220995 220994 2022-07-20T11:10:04Z Va musinov 69698 wikitext text/x-wiki '''Инволю́ция''' (от {{lang-la|involutio}} — свёртывание, завиток) — нетождественное преобразование, которое является [[w:обратная функция|обратным]] самому себе, то есть своей собственной [[w:обратная функция|инверсией]]. Это [[w:унарная операция|унарная операция]]. Формально, функция <math>f</math> называется инволюцией, если <math>f(f(x)) = x</math> для всякого <math>x</math> из [[w:Область определения функции|области определения функции]] <math>f</math>. Иногда пишут: <math>f\circ f= {f}^{2}=id</math>, где <math>id</math> обозначает тождественное преобразование. Вместо <math>id(x)</math> используют запись: <math>e(x)=x</math>. Таким образом, двойное применение функции <math>f</math> даёт исходное значение. == Свойства == Любая инволюция — это [[w:биекция|биекция]]. Если преобразование <math>f</math> инволютивное, то для любого выражения <math>A</math> и его образа <math>B=f(A)</math> имеем <math>f(B)=A</math>. В самом деле, <math>f(B)= f(f(A))=id(A)={id}_{A}=A</math>. '''''Критерий инволюции'''''. Функция <math>f</math> является инволюцией тогда и только тогда, когда для всякого выражения <math>A</math> существует такое выражение <math>B</math>, что <math>f(A)=B\neq A</math> и <math>f(B)=A</math>. Другими словами, преобразование является инволюцией в том и только в том случае, когда оно меняет местами какие-либо два выражения. ---- Если <math>f</math> — инволюция, то имеют место следующие соотношения: * <math>\forall a \in D_{f}: f^{-1}(a) = f(a)</math> [основное свойство] * <math>D_{f} = E_{f}</math> * <math>\forall a : f(f(a)) = a</math> * <math>\forall a, \exists b : f(a) = b \land f(b) = a</math> [критерий] == Примеры == Примеры инволюций: * <math>f(x) = -x</math>, заданная на множестве [[w:целое число|целых]] <math>\mathbb{Z}</math>, [[w:рациональное число|рациональных]] <math>\mathbb{Q}</math> или [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>; * простейшие инволюции на множестве [[w:Вещественное число|вещественных чисел]] <math>\mathbb{R}</math>: *: <math>\dfrac{a}{x}</math>, <math>a-x</math>, <math>\dfrac{x}{x-1}</math>, <math>\dfrac{x+1}{x-1}</math>, <math>\dfrac{x-1}{x+1}</math>, <math>\dfrac{ax+b}{cx-a}</math>; * инволюция <math>f(x) = \dfrac{b}{x-a} + a</math> при <math>x\in \mathbb{R} \setminus \left\{a\right\}</math> и <math>b\neq 0</math>; * <math>f(x)= \bar{x}</math> — [[w:дополнение множества|дополнение множества]], заданная для подмножеств некоторого универсального множества <math>U</math>; * <math>f(x)= \neg x</math> — [[w:логическое отрицание|логическое отрицание]] [[w:булева алгебра|булевой алгебры]]; * [[w:Симметрия|симметрии]]: [[w:Центральная симметрия|центральная]], [[w:Осевая симметрия|осевая]], [[w:Зеркальная симметрия|зеркальная]]; * [[w:инверсия (геометрия)|инверсия]]; * [[w:комплексное сопряжение|комплексное сопряжение]]; * [[w:преобразование Лежандра|преобразование Лежандра]] * при факторизации обычного тора (точнее, одномерного комплексного тора, ещё точнее, эллиптической кривой) <math>E</math> по инволюции вида <math>x\mapsto -x</math> получается сфера; * Если представить, что <math>f</math> — нажатие на клавишу [[w:выключатель бытовой| бытового накладного выключателя]] (т. е. включить либо выключить свет), то <math>f</math> будет инволюцией. == Важнейшие факты == ;'''Теорема 1'''. : Композиция <math>{f}\circ{g}</math> двух инволюций <math>f</math> и <math>g</math> является инволюцией тогда и только тогда, когда они коммутируют: <math>{f}\circ{g} =g\circ f</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Пусть дана композиция <math>{f}\circ{g}</math>, в которой <math>f</math>, <math>g</math> — инволюции. Это означает, что <math>f=f^{-1}</math> и <math>g=g^{-1}</math>, а также <math>{f}\circ{g}={\left({f}\circ{g}\right)}^{-1}</math>. Имеем: <math>{f}\circ{g}= {\left({f}\circ{g}\right)}^{-1}={g^{-1}}\circ {f^{-1}}={g}\circ{f}</math>. Если <math>{f}\circ{g}</math> — инволюция, то двигаемся слева направо. Обратно, если выполняется равенство <math>{f}\circ{g} =g\circ f</math>, то справа налево. |} <code>Пример 1</code>. Такая композиция <math>\left(f_{1} \circ f_{2}\right) (x) = \left(f_{2} \circ f_{1} \right) (x) = {f_{3}} (x) = -{\dfrac{1}{x}}</math> есть инволюция. Аналогично, если <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math> и <math>g</math>, <math>h</math>, <math>k</math> — инволюции, то и <math>f</math> — инволюция. <code>Пример 2</code>. <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. ; '''Теорема 2'''. : Если <math>{f}</math> — монотонно возрастающая функция, то уравнения <math>{f}(x)=x</math> и <math>f(f(x))=x</math>, или <math>{f}(x)={f^{-1}}(x)</math>, равносильны. Рассмотрим следующую задачу. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>\sqrt{1+\sqrt{x}}=x-1</math>. |- | Перепишем данное уравнение в виде: <center><math>1+\sqrt{1+\sqrt{x}}=x.</math></center> Рассмотрим теперь функцию <center><math>f(x)=1+\sqrt{x}.</math></center> Тогда полученное уравнение примет вид: <center><math>f(f(x))=x.</math></center> Для решений уравнений такого вида применим '''теорему 2'''. Но сначала следует убедиться, что введённая функция <math>f</math> действительно монотонно возрастает. Для того чтобы <math>f(x)</math> была строго возрастающей, достаточно (но не является необходимым условием), чтобы <math>f'(x)>0</math>. В нашем случае получается <math>f'(x)=\dfrac{1}{2\sqrt{x}}>0</math>. В соответствии с приведённой '''теоремой 2''' приходим к равносильному уравнению <math>{f}(x)=x</math>, или <math>1+\sqrt{x}=x</math>, решение которого уже не сложно. Ответ: <math>x = \dfrac{3+\sqrt{5}}{2}.</math> |} ; '''Теорема 3'''. : Функция вида <math>f={h}\circ{g}\circ{h^{-1}}</math> (где <math>h</math> — некоторое биективное отображение) будет инволюцией в том и только в том случае, если функция <math>g</math> — инволюция. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Имеем следующее: <math>f=f^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {\left({h}\circ{g}\circ{h^{-1}}\right)}^{-1} \Longleftrightarrow {h}\circ{g}\circ{h^{-1}} = {{h}\circ{g^{-1}}\circ{h^{-1}}} \mid { \circ h} \Longleftrightarrow {h}\circ{g}={h}\circ{g^{-1}} \Longleftrightarrow {h^{-1} \circ } \mid {{h}\circ{g}={h}\circ{g^{-1}}} \Longleftrightarrow g = g^{-1}.</math> Если <math>{f}</math> является инволюцией, то двигаемся слева направо. Обратно, если <math>{g}</math> — инволюция, то справа налево. Теорема доказана. |} ''Замечание''. Ясно, что '''теорема 3''' сохраняет свою силу, если <math>f={h^{-1}}\circ{g}\circ{h}</math>, где <math>h</math> — биекция. <code>Пример 3</code>. В положительных числах такая функция будет как раз инволюцией по доказанной выше теореме: : <math>ln\left(\dfrac{e^x+1}{e^x-1}\right).</math> ; '''Следствие'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Тогда если <math>h</math> — взаимно-однозначное отображение [биекция] множества <math>E</math> на <math>F</math> с обратной биекцией <math>h^{-1}</math>, то композиция <math>h\circ f\circ h^{-1}</math> — инволюция на множестве <math>F</math>. [[File:Involution4.png|Involution4]] {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Утверждение очевидно по предыдущему. ''Указание''. Воспользоваться '''теоремой 3'''. |} ; '''Теорема 4'''. : Пусть <math>f</math> — инволюция на множестве <math>E</math>. Если <math>h</math> — такое отображение из <math>E</math> в <math>E</math>, что <math>h\circ f\circ h = f</math>, то <math>h\circ f</math> и <math>f\circ h</math> — инволюции на <math>E</math>. {| class="wikitable collapsible collapsed" width=100% ! Доказательство |- | Покажем, что из исходного равенства <math>h\circ f\circ h = f</math> и условия <math>f=f^{-1}</math> получается инволютивная функция <math>h\circ f</math>. Итак, : <math>h\circ f\circ h = f \mid { \circ h^{-1}} \Longrightarrow h\circ f = f \circ h^{-1} \Longrightarrow h \circ f = {\left(h \circ f^{-1}\right)}^{-1} \Longrightarrow h \circ f = {\left(h \circ f \right)}^{-1} \mid {\circ {\left(h \circ f \right)}} \Longrightarrow {\left(h \circ f \right)}^{2} = e.</math> Таким образом, композиция <math>h\circ f</math> по определению является инволюцией. Аналогично проводится доказательство для <math>f\circ h</math>. |} {| class="wikitable collapsible collapsed" width="100%" ! Пусть дана функция <math>f=h\circ g\circ h\circ g^{-1}</math>, где <math>g</math> — биекция, а <math>h=h^{-1}</math>. Выяснить, при каком условии <math>f</math> будет инволютивной. |- | <u>''Решение''</u>. Во-первых, функция <math>f</math> будет инволюцией, если выполняется равенство: <math>f=f^{-1}</math>. Во-вторых, стоит заметить, что <math>h \circ f = g\circ h\circ g^{-1} = f^{-1} \circ h </math>. Поэтому <math>f=f^{-1} \Longleftrightarrow f = h \circ f \circ h</math>. Но по '''следствию''' композиция <math>g \circ h \circ g^{-1}</math> является инволюцией, а значит, и <math>h \circ f</math> — тоже инволюция. Наконец, <math> h\circ \mid f = h \circ f \circ h \Longleftrightarrow h\circ f = f \circ h</math>, то есть <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}</math>. ''Ответ'': <math>f=f^{-1} \Longleftrightarrow f \circ h = h \circ f = g\circ h\circ g^{-1}.</math> |} <code>Пример 4</code>. Функция <math>f(x)= -ln\left(-e^{x}\right)</math>. <u>'''Упражнение'''</u>. Убедитесь, что представленная функция действительно обладает таким свойством. ''Схемой'', или ''строением'', функции <math>f</math> назовём последовательность функций <math>f_{1}, f_{2}, ... , f_{n-1}, f_{n}</math> так, что каждая из них является либо элементарной, либо инволюцией и <math>f=f_{n} \circ f_{n-1} \circ ... \circ f_{2} \circ f_{1}</math>. <code>Пример 5</code>. Пусть <math>k(x) = -x</math>, <math>h(x) = \dfrac{x+1}{x-1}</math>, <math>g(x) = \dfrac{1}{x}</math>. Тогда схемой функции <math>f</math> будет <math>f={g}\circ{h}\circ{k}= {k}\circ{h}\circ{g}</math>. == Фокус == {| class="wikitable collapsible collapsed" width=100% ! Целое общество гостей, непосвящённых в арифметические тайны, вы можете поразить следующим фокусом. |- | Фокусник просит одного человека написать на бумажке, секретно от него, трёхзначное число, какое этот человек хочет, и затем просит приписать к нему ещё раз то же самое число. Получится шестизначное число, состоящее из трёх повторяющихся цифр. Фокусник предлагает тому же товарищу или его соседу разделить — секретно от него — это число на 7; при этом фокусник заранее предсказывает, что остатка не получится. Результат деления передаётся соседу, который, по предложению ведущего, делит его на 11; и хотя фокусник не знает делимого, он всё же смело утверждает, что и оно разделится без остатка. Полученный результат фокусник направляет следующему соседу, которого просит разделить это число на 13 — деление снова выполняется без остатка, о чём он заранее предупреждает. Результат третьего деления фокусник, не глядя на полученное число, вручает первому товарищу со словами: — Вот число, которое вы задумали! — Так и есть: вы угадали. |} <code>Какова разгадка этого фокуса?</code> ''Указание''. Возьмите за функцию <math>f</math> алгоритм приписывания к числу <math>x\rightleftharpoons \overline{abc}</math>, то есть <math>f(x)= \overline{abcabc}</math>. Так как результат совпадает с исходным числом <math>x\rightleftharpoons \overline{abc}</math>, то <math>f^{-1}</math> над числом — это умножение его на 7, 11 и 13. Осталось найти связь <math>f</math> и <math>f^{-1}</math>. == Лирическое отступление == Приведём пример композиции двух инволюций, которая не будет уже инволюцией. <code>Пример</code>. Функция <math>\tau(x)=\dfrac{1}{1-x}</math> не является инволюцией; её строение таково: <math>\tau=\alpha \circ \beta</math>, где <math>\alpha (x) = \dfrac{1}{x}</math> и <math>\beta (x) = 1-x</math> у нас — обе инволюции. '''''Упражнение'''''. Докажите: для <math>\tau(x)=\dfrac{1}{1-x}</math> верно, что <math>\tau \neq {\tau}^{-1}</math>. ''Замечание''. Функция <math>{{\tau}^{-1}}{\left(x\right)}=1-{\dfrac{1}{x}}=\dfrac{x-1}{x}</math> со схемой <math>{\tau}^{-1}=\beta \circ \alpha</math> также не есть инволюция. Легко видеть, что <math>\alpha \circ {{\tau}^{-1}}</math> — инволюция. Делаем вывод, что композиция инволюции и неинволютивной функции может давать инволюцию в результате. Вопрос: ''в каком случае это происходит?'' Перед тем, как ответить на этот вопрос, сперва-наперво выясним, а каким свойством, в принципе, обладает введённая функция <math>\tau(x)=\dfrac{1}{1-x}</math>. Вычислим <math>{\tau}^{2}(x)</math>. У нас получится: : <math>{\tau}^{2}(x)=\dfrac{1}{1-\dfrac{1}{1-x}} = \dfrac{1-x}{1-x-1}=\dfrac{x-1}{x}={\tau}^{-1}(x).</math> Значит, <math>{\tau}^{3}=e</math>. {| class="wikitable collapsible collapsed" width="100%" ! Решить уравнение <math>f{\left(x\right)}\cdot {f{\left(\dfrac{1}{1-x}\right)}}=\dfrac{1-x}{x}</math>. |- | <code>Шаг 1</code> Напишем схему данного уравнения: <math>f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}}=-{\tau}^{-1}(x)</math>. <code>Шаг 2</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}^{-1}(x)</math>. Получим: : <center><math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(\tau({\tau}^{-1}(x))\right)}}=-{\tau}^{-1}({\tau}^{-1}(x)) \Longrightarrow f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}^{-2}(x).</math></center> Но так как <math>{\tau}^{2}(x)={\tau}^{-1}(x)</math>, то <math>{\tau}^{-2}(x)={\tau}(x)</math>. Поэтому <math>f{\left({\tau}^{-1}(x)\right)}\cdot {f{\left(x\right)}}=-{\tau}(x)</math>. <code>Шаг 3</code> Теперь из результатов <code>Шага 1</code> и <code>Шага 2</code> делаем простой вывод: : <center><math>f(x)=\dfrac{-{\tau(x)}}{f{\left({\tau}^{-1}(x)\right)}} = \dfrac{{-{\tau}}^{-1}(x)}{f{\left({\tau}(x)\right)}}.</math></center> <code>Шаг 4</code> Подставим везде, где есть <math>x</math> функцию <math>{\tau}(x)</math>. Имеем: : <center><math>f{\left({\tau}^{-1}(x)\right)}=\dfrac{-x}{f{\left({\tau}(x)\right)}}=\dfrac{{-{\tau}}(x)}{f{\left(x\right)}}.</math></center> <code>Шаг 5</code> Наконец-то, мы <br><br><math> \begin{cases} \begin{array} {rcrcc} \dfrac{-x}{f{\left({\tau}(x)\right)}} = \dfrac{{-{\tau}}(x)}{f{\left(x\right)}}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases} \Longrightarrow \begin{cases} \begin{array} {rcrcc} {f{\left({\tau}(x)\right)}} = \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)}, \\ f{\left(x\right)}\cdot {f{\left(\tau(x)\right)}} = -{\tau}^{-1}(x) \end{array} \end{cases}.</math> <code>Шаг 6</code> Подставим выражение <math>{f{\left({\tau}(x)\right)}}</math> во вторую строчку системы. Итак, : <math>f{\left(x\right)}\cdot \dfrac{{\left(-x\right)}\cdot {f{\left(x\right)}}}{{-{\tau}}(x)} = -{\tau}^{-1}(x) \Longleftrightarrow f{\left(x\right)}\cdot f{\left(x\right)} = \dfrac{{-{\tau}}(x) \cdot {{\tau}^{-1}{\left(x\right)}}}{x}.</math> <u>'''Ответ'''</u>: <math>f{\left(x\right)} = \pm{\sqrt{\dfrac{{-{\tau}}(x) \cdot {{\tau}^{-1}{\left(x\right)}}}{x}}} = \pm{\dfrac{1}{x}}</math>, или <math>f{\left(x\right)} = \dfrac{1}{x} \, \& \, x\neq 0.</math> |} == Инволюция в алгебре == [[w:Перестановка|Перестановка]] <math>\tau</math> является инволюцией, если <math>\tau\circ\tau=id</math>, каждая инволюция является произведением непересекающихся транспозиций, например: : <math>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 5 & 7 & 4 & 3 & 1 & 8 & 2 & 6\end{pmatrix} = (1,5)(2,7)(3,4)(6,8)</math>. Число инволюций в [[w:Группа перестановок|группе перестановок]] порядка <math>n</math> определяется по формулам: * <math> a(0) = 1,\ a(1) = 1,\ a(n) = a(n-1) + (n-1)a(n-2),\ n>1</math> (рекуррентная формула), * <math>a(n) = \sum_{k=0}^{[ n/2 ]}{\frac{n!}{2^k\cdot (n-2k)!\cdot k!}}</math>, (первые значения <math>a(n)</math>: 1, {{w:nums|link=nrl|1|2|4|10|26|76|232|764|2620|9496|35696|140152}}<ref>{{OEIS long|A000085|lc=1}}</ref>). Свойства инволюции обеспечивают ей широкое применение в различных приложения, например, инволютивные преобразования над пространством булевых векторов используются в различных схемах построения симметричных [[w:криптоалгоритм|криптоалгоритм]]ов, таких как [[w:Сеть Фейстеля|сети Фейстеля]] и [[w:SP-сеть|подстановочно-перестановочные сети]]. == Примечания == rbzau478z4b7l390fxlt1mcu7k9dg3z 4 30040 220982 220926 2022-07-19T19:28:22Z Alexis Jazz 57039 Updating gadget usage statistics from [[Special:GadgetUsage]] ([[phab:T121049]]) wikitext text/x-wiki {{#ifexist:Project:GUS2Wiki/top|{{/top}}}} {|style="width:100%; color:#606000; background-color: #FFFFE0; border:1px solid #EEEE80; padding:2px; margin-bottom:1em" cellpadding=0 |- |<imagemap>Image:Clock and warning.svg|20px rect 100 100 100 100 [[##]] desc none</imagemap> | Следующие данные '''взяты из кеша''', последний раз он обновлялся в '''2022-07-17T14:38:23Z'''. |} {| class="sortable wikitable" ! Гаджет !! data-sort-type="number" | Количество участников !! data-sort-type="number" | Активные участники |- |gadget-histcomb || 149 || 0 |- |gadget-Navigation popups || 142 || 0 |- |gadget-preview || 110 || 0 |- |exlinks || 91 || 1 |- |gadget-edittop || 75 || 0 |- |HotCat || 70 || 1 |- |gadget-contribsrange || 61 || 0 |- |markadmins || 40 || 2 |- |markblocked || 31 || 1 |- |gadget-popups || 29 || 0 |- |gadget-urldecoder || 22 || 0 |- |gadget-directLinkToCommons || 22 || 0 |- |DotsSyntaxHighlighter || 21 || 1 |- |gadget-removeAccessKeys || 20 || 0 |- |gadget-referenceTooltips || 20 || 0 |- |gadget-ImageAnnotator || 20 || 0 |- |gadget-extWikiLinksMarker || 7 || 0 |- |gadget-DisableImageAnnotator || 1 || 0 |} * [[Служебная:Использование гаджетов]] * [[w:en:User:Alexis Jazz/GUS2Wiki|GUS2Wiki]] g010ujpdnaqxyr1glr4xu7gnqzn6x9l