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

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

${\ displaystyle [P] = {\ begin {cases} 1 & {\ text {if}} P {\ text {is true;}} \\ 0 & {\ text {в противном случае.}} \ end {cases}}}$

В контексте суммирования обозначение может использоваться для записи любой суммы в виде бесконечной суммы без ограничений: если - любое свойство целого числа ,${\ Displaystyle P (k)}$${\ displaystyle k}$

${\ displaystyle \ sum _ {k} f (k) \, [P (k)] = \ sum _ {P (k)} f (k).}$

Обратите внимание, что по этому соглашению слагаемое должно оцениваться как 0 независимо от того , определено ли оно. Аналогично для продуктов :${\ displaystyle f (k) [{\ textbf {false}}]}$${\ displaystyle f (k)}$

${\ Displaystyle \ prod _ {k} f (k) ^ {[P (k)]} = \ prod _ {P (k)} 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}}}$

Обмен суммированием [ править ]

Известное правило также легко выводится:${\displaystyle \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 \phi (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для n = 1 . Чтобы получить идентичность, действительную для всех положительных целых чисел n (т. Е. Всех значений, для которых определено), можно добавить поправочный член, включающий скобку Айверсона:${\displaystyle \phi (n)}$

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

Общие функции [ править ]

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

${\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\geq 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-х годах Гульельмо далла Соммаджа использовал это выражение для обозначения того, что будет написано сейчас ; dalla Sommaja также использовала варианты, например for . ^[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}}}$

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

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

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