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

В математике , скобка Айверсона названная в честь Кеннета Э. Айверсона , представляет собой обозначение, обобщающее дельту Кронекера , которая является скобкой Айверсона утверждения $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 . ^[1]^[2] защищал обобщение на произвольные утверждения, ограничение обозначений квадратными скобками и применение суммирования, Дональд Кнут чтобы избежать двусмысленности в логических выражениях, заключенных в круглые скобки. ^[3]

Свойства [ править ]

Существует прямая связь между арифметикой в скобках Айверсона, логикой и операциями над множествами. Например, пусть 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 для n $= 1$ . Чтобы получить тождество, действительное для всех положительных целых чисел $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].

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

{\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.

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

\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]$ . ^[3] Согласно одному общему соглашению , эти количества равны там, где они определены: $0^{0^{x}}$ равен 1, если $x > 0$ , равен 0, если $x = 0$ , и не определен в противном случае.

Варианты обозначений [ править ]

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

См. также [ править ]

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

Ссылки [ править ]

^ Перейти обратно: ^а ^б Кеннет Э. Айверсон (1962). Язык программирования . Уайли. п. 11 . Проверено 7 апреля 2016 г.
^ Рональд Грэм , Дональд Кнут и Орен Паташник . Конкретная математика , Раздел 2.1: Обозначения.
^ Перейти обратно: ^а ^б Дональд Кнут, «Два примечания к обозначениям», American Mathematical Monthly , том 99, номер 5, май 1992 г., стр. 403–422. ( TeX , arXiv : math/9205211 ).
^ Рональд Грэм , Дональд Кнут и Орен Паташник . Конкретная математика , Раздел 4.9: Фи и Му.

[APL-1] Перейти обратно: ^а ^б Кеннет Э. Айверсон (1962). Язык программирования . Уайли. п. 11 . Проверено 7 апреля 2016 г.

[2] Рональд Грэм , Дональд Кнут и Орен Паташник . Конкретная математика , Раздел 2.1: Обозначения.

[TNN-3] Перейти обратно: ^а ^б Дональд Кнут, «Два примечания к обозначениям», American Mathematical Monthly , том 99, номер 5, май 1992 г., стр. 403–422. ( TeX , arXiv : math/9205211 ).

[4] Рональд Грэм , Дональд Кнут и Орен Паташник . Конкретная математика , Раздел 4.9: Фи и Му.

[1]

[2]

[3]

[4]