Ідемпотентність

Бенжамін Пірс

Ідемпотентність (Шаблон:Lang-la — такий самий, Шаблон:Lang-la — сильний) — властивість унарних та бінарних операцій в алгебрі та логіці. Термін «ідемпотентність» означає властивість, яка проявляється в тому, що повторна її дія над будь-яким об'єктом уже не змінює результату. Тобто повторне виконання операцій з об'єктом не змінює результату, досягнутого при першому виконанні. Термін запропонував американський математик Бенджамін Пірс в статтях 1870-х років.

Визначення

• Унарна операція чи функція називається ідемпотентною, якщо її застосування двічі до будь-якого значення аргументу дає таке ж значення, як і застосування один раз:

$f(f(x))=f(x).$

• Бінарна операція називається ідемпотентною, якщо для довільного елемента $x$ виконується:

$x\cdot x=x.$

Закон ідемпотентності кон'юнкції та диз'юнкції

Закон ідемпотентності — це закон математичної логіки, по якому з логіки виключаються коефіцієнти і показники ступенів.

Закон ідемпотентності можна отримати з закону поглинання, з використанням закону дистрибутивності:

$a=a\vee (a\wedge b)=(a\vee a)\wedge (a\vee b)=(a\wedge (a\vee b))\vee (a\wedge (a\vee b))=a\vee a$

Так логічне множення двох висловлювань $a$ рівносильне $a$, тобто: $a\wedge a\equiv a$ і читається так «$a$ і $a$ рівносильне $a$».

Закон ідемпотентності відносно диз'юнкції виводиться безпосередньо із закону нуля та одиниці:

$a\vee a=(a\vee a)\wedge 1=(a\vee a)\wedge (a\vee \overline{a})=a\vee (a\wedge \overline{a})=a\vee 0=a$

Логічне додавання двох висловлювань $a$, рівносильне $a$, тобто: $a\vee a\equiv a$ і читається так «$a$ або $a$ рівносильне $a$».

Формулювання закону: повторення висловлювання через «і» та «або» рівносильне самому висловлюванню. Наприклад, «Марс — планета і Марс — планета» є те ж саме, що «Марс — планета»; « Сонце — зірка або Сонце — зірка» те ж саме, що «Сонце — зірка».

Наслідки ідемпотентності кон'юнкції та диз'юнкції

• Наслідками ідемпотентності диз'юнкції є рівність

$A=A\vee A=A\vee A\vee A=A\vee A\vee A\vee A=\dots$

• Наслідками ідемпотентності кон'юнкції є рівність А = АА = ААА = АААА =…

В алгебрі логіки можна обходитися без степенів. Всі «степені» висловлення А рівні самому А (звідси літерний сенс слова «ідемпотентність»).

Приклади ідемпотентних операцій

• Об'єднання і перетин множин є ідемпотентними бінарними операціями.
• Операції булевої алгебри: кон'юнкція та диз'юнкція є ідемпотентними бінарними операціями.
• Бінарні операції $\max (\cdot ,\cdot ),\min (\cdot ,\cdot )$ є ідемпотентними.
• Операція проектування (знаходження проєкції) є ідемпотентною унарною операцією.
• Звернемо увагу на те, що одну і ту ж імпліканту можна склеїти з іншими імплікантами багаторазово, так як в логіці Джоржа Буля діє закон ідемпотентності:

$a=a\vee a=a\vee a\vee a=...$

$a=a\wedge a=a\wedge a\wedge a=...$

тому будь-яку константу можна розмножити

• Розглянемо алгебру множин (алгебру Кантора, алгебру класів)

$A_k=(B(1),\cup ,\cap ,\overline{.})$

Носієм якої є булеан універсальної множини 1, сигнатурою — операції об'єднання $\cup$, перетину $\cap$ та доповнення $\overline{.}$. Закон ідемпотентності об'єднання та перетину виконується для операції алгебри Кантора:

$M_a\cup M_a=M_a$

$M_a\cap M_a=M_a$

• Ідемпотентна операція в інформатиці — дія, багаторазове повторення якої призводить до тих же змін, що й при одноразовому.

Прикладом такої операції можуть служити GET- запити в протоколі HTTP. По специфікації сервер повинен повертати одні й ті ж відповіді на ідентичні запити (за умови що ресурс не змінився між ними з інших причин). Така особливість дозволяє кешувати відповіді, знижуючи навантаження на мережу

Елемент

• Ідемпотентний елемент в алгебрі — елемент напівгрупи, що зберігається при піднесення до степеня.

Варіант: Ідемпотентний елемент  — елемент $e$ напівгрупи або кільця, рівний своєму квадрату: $e^2=e$.

• Ідемпотентний елемент $e$ містить ідемпотентний елемент $f$ (позначається $e⩾f$), якщо $ef=e=fe$.
  • Для асоціативних кілець і напівгруп відношення $⩾$ є відношенням часткового порядку в множині $E$ ідемпотентних елементів і називається природним частковим порядком на множині $E$.
• Два ідемпотентних елемента $u$ та $v$ кільця називаються ортогональними, якщо $uv=0=vu$.

Прикладні приклади

Прикладні приклади, з якими багато людей змогло зіткнутися в їх щоденному житті, включаючи кнопки виклику ліфта і кнопки переходу. Початкова активація кнопки переміщає систему в очікування. Подальші активації кнопки між початковою активацією і запитом, що задовольняється, не мають ніякого ефекту.

Лінійний оператор

Ідемпотентний лінійний оператор — те саме, що і проектор.

Для простору нескінченної розмірності

$A=\underset{\sigma }{\int }\lambda P(d\lambda )$

де σ — спектр A, а P — ідемпотентний оператор.

Див. також

• Ідемпотентний елемент
• Асоціативність
• Комутативність
• Дистрибутивність
• Кон'юнкція
• Диз'юнкція
• Булева алгебра

Література

• Шаблон:Ленг.Алгебра
• Шаблон:Cite web
• Шаблон:Cite web