Ідемпотентна операція

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

Ідемпотентність
Досліджується в	теорія категорій
Підтримується Вікіпроєктом

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

Визначення

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

${\displaystyle f(f(x))=f(x).\!}$

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

${\displaystyle x\cdot x=x.\!}$

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

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

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

${\displaystyle a=a\lor (a\land b)=(a\lor a)\land (a\lor b)=(a\land (a\lor b))\lor (a\land (a\lor b))=a\lor a}$

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

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

${\displaystyle a\lor a=(a\lor a)\land 1=(a\lor a)\land (a\lor {\bar {a}})=a\lor (a\land {\bar {a}})=a\lor 0=a}$

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

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

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

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

${\displaystyle A=A\lor A=A\lor A\lor A=A\lor A\lor A\lor A=\dots }$

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

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

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

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

${\displaystyle a=a\lor a=a\lor a\lor a=...}$

${\displaystyle a=a\land a=a\land a\land a=...}$

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

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

${\displaystyle A_{k}=(B(1),\cup ,\cap ,{\bar {.}})}$

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

${\displaystyle M_{a}\cup M_{a}=M_{a}}$

${\displaystyle M_{a}\cap M_{a}=M_{a}}$

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

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

Елемент

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

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

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

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

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

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

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

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

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

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

Див. також

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

Література

• Ленг С. Алгебра. — Москва : Мир, 1968. — 564 с. — .(рос.)
• . Архів оригіналу за 20 грудня 2016. Процитовано 28 листопада 2016.
• . Архів оригіналу за 28 листопада 2016. Процитовано 28 листопада 2016.