Дужка Айверсона

Ду́жка Айверсона — функція, що повертає 1 для істинного висловлювання, і 0, якщо аргумент хибний:

$[\,P\,]={\begin{cases}1,&{\text{якщо }}P{\text{ істинне}}\\0,&{\text{якщо }}P{\text{ хибне}}\end{cases}}$

Нотація, яку Кеннет Айверсон ввів для мови програмування APL, виявилася дуже зручним математичним позначенням, наприклад, з ним можна лаконічно визначити:

• символ Кронекера: $\delta _{ij}=[\,i=j\,]$ ,
• індикаторну функцію: $\mathbf {1} _{A}(x)=[\,x\in A\,]$,
• функцію Гевісайда: $\theta (x)=[\,x\geqslant 0\,]$,
• функцію знака числа: $\operatorname {sgn}(x)=[\,x>0\,]-[\,x<0\,]$.

Також нотація зручна при користуванні сумами, оскільки дозволяє виражати їх без обмежень на індекс підсумовування, наприклад:

$\sum _{i=1}^{n}a_{i}=\sum _{k}a_{k}[\,1\leqslant k\leqslant n\,]$,

тобто індекс $k$ пробігає всю множину $\mathbb {Z}$ цілих чисел, і формально підсумовується нескінченна кількість доданків, але лише скінченне число їх відмінне від нуля.

Приклад обчислення з використанням дужок Айверсона суми $S=\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}a_{i}a_{j}$ для послідовності $\{a_{i}\}$:

$[\,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}$ ,

а оскільки для правої частини:

$\sum \limits _{i,j}a_{i}a_{j}=\sum \limits _{i}\sum \limits _{j}a_{i}a_{j}=\sum \limits _{i}a_{i}\sum \limits _{j}a_{j}={\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.
• Kenneth E. Iverson. A Programming Language. — the University of California : Wiley, 1962. — 286 с. — ISBN 0471430145.