Кронштейн Айверсона

В математике скобка Айверсона , названная в честь Кеннета Иверсона , представляет собой обозначение, которое обобщает дельту Кронекера , которая является скобкой Айверсона утверждения x = y . Он отображает любой оператор в функцию в свободных переменных этом операторе. Эта функция определена так, чтобы принимать значение 1 для значений переменных, для которых утверждение истинно, и принимать значение 0 в противном случае. Обычно это обозначается помещением утверждения в квадратные скобки:

$$[P]={\begin{cases}1&{\text{if }}P{\text{ is true;}}\\0&{\text{otherwise.}}\end{cases}}$$

Другими словами, скобка Айверсона утверждения — это индикаторная функция набора значений, для которых утверждение истинно.

Скобка Айверсона позволяет использовать сигму с заглавной буквы без ограничений на индекс суммирования. То есть для любого имущества $P(k)$ целого числа $k$, можно переписать ограниченную сумму $\sum _{k:P(k)}f(k)$ в неограниченной форме $\sum _{k}f(k)\cdot [P(k)]$. Благодаря этой конвенции, $f(k)$ не требуется определять значения k , для которых скобка Айверсона равна 0 ; то есть слагаемое $f(k)[{\textbf {false}}]$ должен оцениваться как 0 независимо от того, $f(k)$ определяется.

Обозначение было первоначально введено Кеннетом Э. Айверсоном в его языке программирования APL . хотя и ограничивается отдельными операторами отношения, заключенными в круглые скобки, в то время как обобщение на произвольные утверждения, ограничение обозначений квадратными скобками и приложения к суммированию были защищены Дональдом Кнутом , чтобы избежать двусмысленности в логических выражениях в скобках.

Свойства

Существует прямая связь между арифметикой в ​​скобках Айверсона, логикой и операциями над множествами. Например, пусть A и B — множества и $P(k_{1},\dots )$ любое свойство целых чисел; тогда у нас есть

$${\begin{aligned}[][\,P\land Q\,]~&=~[\,P\,]\,[\,Q\,]~~;\\[1em][\,P\lor Q\,]~&=~[\,P\,]\;+\;[\,Q\,]\;-\;[\,P\,]\,[\,Q\,]~~;\\[1em][\,\neg \,P\,]~&=~1-[\,P\,]~~;\\[1em][\,P{\scriptstyle {\mathsf {\text{ XOR }}}}Q\,]~&=~{\Bigl |}\,[\,P\,]\;-\;[\,Q\,]\,{\Bigr |}~~;\\[1em][\,k\in A\,]\;+\;[\,k\in B\,]~&=~[\,k\in A\cup B\,]\;+\;[\,k\in A\cap B\,]~~;\\[1em][\,x\in A\cap B\,]~&=~[\,x\in A\,]\,[\,x\in B\,]~~;\\[1em][\,\forall \,m\ :\,P(k,m)\,]~&=~\prod _{m}\,[\,P(k,m)\,]~~;\\[1em][\,\exists \,m\ :\,P(k,m)\,]~&=~\min {\Bigl \{}\;1\,,\,\sum _{m}\,[\,P(k,m)\,]\;{\Bigr \}}=1\;-\;\prod _{m}\,[\,\neg \,P(k,m)\,]~~;\\[1em]\#{\Bigl \{}\;m\,{\Big |}\,P(k,m)\;{\Bigr \}}~&=~\sum _{m}\,[\,P(k,m)\,]~~.\end{aligned}}$$

Примеры

Обозначения позволяют перемещать граничные условия суммирования (или интегралов) как отдельный фактор в слагаемое, освобождая пространство вокруг оператора суммирования, но, что более важно, позволяя им алгебраически манипулировать.

Правило двойного счета

Мы механически выводим известное правило манипуляции суммами с помощью скобок Айверсона:

$${\begin{aligned}\sum _{k\in A}f(k)+\sum _{k\in B}f(k)&=\sum _{k}f(k)\,[k\in A]+\sum _{k}f(k)\,[k\in B]\\&=\sum _{k}f(k)\,([k\in A]+[k\in B])\\&=\sum _{k}f(k)\,([k\in A\cup B]+[k\in A\cap B])\\&=\sum _{k\in A\cup B}f(k)\ +\sum _{k\in A\cap B}f(k).\end{aligned}}$$

Обмен суммированием

Общеизвестное правило ${\textstyle \sum _{j=1}^{n}\sum _{k=1}^{j}f(j,k)=\sum _{k=1}^{n}\sum _{j=k}^{n}f(j,k)}$ также легко выводится:

$${\begin{aligned}\sum _{j=1}^{n}\,\sum _{k=1}^{j}f(j,k)&=\sum _{j,k}f(j,k)\,[1\leq j\leq n]\,[1\leq k\leq j]\\&=\sum _{j,k}f(j,k)\,[1\leq k\leq j\leq n]\\&=\sum _{j,k}f(j,k)\,[1\leq k\leq n]\,[k\leq j\leq n]\\&=\sum _{k=1}^{n}\,\sum _{j=k}^{n}f(j,k).\end{aligned}}$$

Подсчет

Например, функция тотента Эйлера , подсчитывающая количество натуральных чисел до n , взаимно простых с n, может быть выражена формулой

$$\varphi (n)=\sum _{i=1}^{n}[\gcd(i,n)=1],\qquad {\text{for }}n\in \mathbb {N} ^{+}.$$

Упрощение особых случаев

Другое использование скобки Айверсона — упрощение уравнений в особых случаях. Например, формула

$$\sum _{1\leq k\leq n \atop \gcd(k,n)=1}\!\!k={\frac {1}{2}}n\varphi (n)$$

справедливо для n > 1 , но отключено 1/2 ​ 1 для n = . Чтобы получить тождество, действительное для всех положительных целых чисел n (т. е. всех значений, для которых $\phi (n)$ определено), можно добавить поправочный член, включающий скобку Айверсона:

$$\sum _{1\leq k\leq n \atop \gcd(k,n)=1}\!\!k={\frac {1}{2}}n{\Big (}\varphi (n)+[n=1]{\Big )}$$

Общие функции

Многие общие функции, особенно те, которые имеют естественное кусочное определение, могут быть выражены через скобку Айверсона. — Дельта-нотация Кронекера это частный случай нотации Айверсона, когда условием является равенство. То есть,

$$\delta _{ij}=[i=j].$$

Индикаторная функция , часто обозначаемая $\mathbf {1} _{A}(x)$, $\mathbf {I} _{A}(x)$ или $\chi _{A}(x)$, представляет собой скобку Айверсона с условием принадлежности к множеству:

$$\mathbf {I} _{A}(x)=[x\in A].$$

Ступенчатая функция Хевисайда , знаковая функция , и функция абсолютного значения также легко выражаются в таких обозначениях:

$${\begin{aligned}H(x)&=[x>0],\\\operatorname {sgn}(x)&=[x>0]-[x<0],\end{aligned}}$$

и

$${\begin{aligned}|x|&=x[x>0]-x[x<0]\\&=x([x>0]-[x<0])\\&=x\cdot \operatorname {sgn}(x).\end{aligned}}$$

Функции сравнения max и min (возвращающие больший или меньший из двух аргументов) можно записать как

$$\max(x,y)=x[x>y]+y[x\leq y]$$

и

$$\min(x,y)=x[x\leq y]+y[x>y].$$

Функции пола и потолка можно выразить как

$$\lfloor x\rfloor =\sum _{n}n\cdot [n\leq x<n+1]$$

и

$$\lceil x\rceil =\sum _{n}n\cdot [n-1<x\leq n],$$

где индекс $n$ Под суммированием понимают все целые числа.

Функция линейного изменения может быть выражена

$$R(x)=x\cdot [x\geq 0].$$

Трихотомия действительных чисел эквивалентна следующему тождеству:

$$[a<b]+[a=b]+[a>b]=1.$$

Функция Мёбиуса обладает свойством (и может быть определена посредством рекуррентности как )

$$\sum _{d|n}\mu (d)\ =\ [n=1].$$

Формулировка в терминах обычных функций

В 1830-х годах Гульельмо далла Соммаха использовал выражение $0^{0^{x}}$ представлять то, что сейчас будет написано $[x>0]$; он также использовал такие варианты, как $\left(1-0^{0^{-x}}\right)\left(1-0^{0^{x-a}}\right)$ для $[0\leq x\leq a]$. Согласно одному общему соглашению , эти количества равны там, где они определены: $0^{0^{x}}$ равен 1, если x > 0 , равен 0, если x = 0 , и не определен в противном случае.

Варианты обозначений

В дополнение к теперь стандартным квадратным скобкам [ · ] и первоначальным круглым скобкам ( · ) жирные скобки для доски также использовались , например ⟦ · ⟧ , а также другие необычные формы скобок, доступные в шрифте издателя, сопровождаемые по примечанию на полях.

См. также

• Булева функция
• Преобразование типов в компьютерном программировании: многие языки числовые или указательные позволяют использовать величины в качестве логических величин.
• Функция индикатора