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

Математическое обозначение набора значений, удовлетворяющих свойству

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

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

индикаторная функция

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

Обозначение было первоначально введено Кеннетом Э. Айверсоном в его языке программирования APL , ^{[1] [2]} , хотя и ограничивалось отдельными реляционными операторами, заключенными в круглые скобки, тогда как обобщение на произвольные утверждения, ограничение обозначения квадратными скобками и приложения к суммированию, был предложен Дональдом Кнутом , чтобы избежать двусмысленности в логических выражениях, заключенных в круглые скобки. ^[3]

Характеристики

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

$${\displaystyle {\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}}}$$

Примеры

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

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

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

$${\displaystyle {\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)}$

$${\displaystyle {\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 , может быть выражена формулой

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

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

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

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

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

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

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

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

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

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

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

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

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

и

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

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

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

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

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

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

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

${\displaystyle n}$

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

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

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

$${\displaystyle [a<b]+[a=b]+[a>b]=1.}$$

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

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

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

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

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

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

Смотрите также

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

Рекомендации

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