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

Iverson bracket

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

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

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

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

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

{ Displaystyle prod _ {k} f (k) ^ {[P (k)]} = prod _ {P (k)} f (k).}

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

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

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

{ Displaystyle { begin {align} [] [P land Q] & = [P] [Q], qquad [ neg P] = 1- [P]. [1em] [P lor Q ] & = [P] + [Q] - [P] [Q]. [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 { Big ( } 1, sum _ {m} [P (k, m)] { Big)} = 1- prod _ {m} left (1- [P (k, m)] right). [1em] # {m mid P (k, m) } & = sum _ {m} [P (k, m)]. End {выравнивается}}}

Примеры

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

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

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

{ Displaystyle { begin {align} 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 {выравнивается}}}

Суммирование обмена

Известное правило ${ 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 {align} 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 {align}}}

Подсчет

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

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

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

Скобка Айверсона также используется для упрощения уравнений с частными случаями. Например, формула

{ Displaystyle сумма _ {1 Leq к Leq п наверху НОД (к, п) = 1} ! ! к = { гидроразрыва {1} {2}} п varphi (п)}

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

{ Displaystyle сумма _ {1 Leq к Leq п наверху НОД (к, п) = 1} ! ! к = { гидроразрыва {1} {2}} п ( varphi (n) + [n = 1])}

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

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

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

В индикаторная функция, часто обозначаемый ${ Displaystyle mathbf {1} _ {A} (х)}$ , ${ Displaystyle mathbf {I} _ {A} (х)}$ или же ${ Displaystyle чи _ {А} (х)}$ , является скобкой Айверсона с установленным членством в качестве условия:

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

.

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

{ displaystyle { begin {align} H (x) & = [x geq 0], operatorname {sgn} (x) & = [x> 0] - [x <0], end {выровнено }}}

и

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

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

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

и

{ Displaystyle мин (х, у) = х [х Leq у] + у [х> у]}

.

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

{ Displaystyle lfloor x rfloor = sum _ {n} n cdot [n leq x

и

{ Displaystyle lceil х rceil = сумма _ {п} п CDOT [п-1 <х Leq п],}

где индекс ${ displaystyle n}$ Под суммированием понимается диапазон всех целых чисел.

В функция рампы можно выразить

{ Displaystyle R (x) = x cdot [x geq 0].}

В трихотомия реалов эквивалентно следующему тождеству:

{ displaystyle [a b] = 1.}

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

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

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

В 1830-х годах Гульельмо далла Соммая использовал выражение ${ 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]}$ .^[3]После одного общее соглашение, эти количества равны, где они определены: ${ displaystyle 0 ^ {0 ^ {x}}}$ равно 1, если $Икс$ > 0, равно 0, если $Икс$ = 0, иначе не определено.