Нотация Айверсона

Нотация Айверсона, или скобка Айверсона, — обозначение в математике. Согласно этому обозначению, истинное или ложное утверждение, заключенное в квадратные скобки, равно 1, если данное утверждение истинно, и 0, если данное утверждение ложно. Другими словами, если $P$ — некоторый предикат, то

$[\,P\,] = \begin{cases} 1, &\text{if } P \text{ is true} \\ 0, &\text{if } P \text{ is false} \end{cases}$

Эта нотация была введена Кеннетом Айверсоном в его языке программирования АПЛ, и оказалась очень удобным математическим обозначением.

Специальные случаи

Символ Кронекера $\delta_{ij}$ является частным случаем нотации Айверсона:

$\delta_{ij} = [\,i=j\,]$

Индикаторная функция множества также может быть записана через нотацию Айверсона:

$\mathbf{1}_A(x) = [\,x \in A\,]$

Функция знака числа:

$\sgn(x) = [\,x >0\,] - [\,x < 0\,]$

Использование нотации Айверсона с суммами

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

$\sum_{k=1}^n a_k = \sum_{k} a_k [\, 1 \leq k \leq n\, ]$

В первой сумме индекс $k$ ограничен числами $1$ и $n$. Во второй он пробегает все множество $\mathbb{Z}$ целых чисел. Формально мы имеем дело с суммой бесконечного числа слагаемых. Но фактически лишь конечное число из них отличны от нуля. Вообще, если $P(k)$ — некоторый предикат, то сумма всех $a_k$, таких, что целое $k$ удовлетворяет условию $P(k)$, может быть записана в виде

$\sum_{P(k)} a_k = \sum_{k} a_k [\,P(k)\,]$

Пример вычисления суммы

В качестве примера использования нотации Айверсона с суммами вычислим сумму $S = \sum\nolimits_{1 \leq i < j \leq n} a_i a_j$.

Имеем,

$[\,i < j\,] + [\,i = j\,] + [\,i >j\,] = 1$

$\sum\limits_{i , j} a_i a_j [\,i < j\,] + \sum\limits_{i , j} a_i a_j [\,i = j\,] + \sum\limits_{i , j} a_i a_j [\,i >j\,] = \sum\limits_{i , j} a_i a_j$

$S + \sum\limits_{i} a_i^2 + S = \biggl(\sum\limits_{i} a_i \biggr)^2$

Значит,

$S = \sum_{1 \leq i < j \leq n} a_i a_j = \frac{1}{2} \biggl(\sum_{i=1}^n a_i \biggr)^2 - \frac{1}{2}\sum_{i=1}^n a_i^2$

Литература

• Р. Грэхем, Д. Кнут, О. Паташник Конкретная математика. — М.: «Мир», 1998. — 703 с. — ISBN 5-03-001793-3

См. также

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