Скобка Айверсона

Эта статья — о скобках для логических утверждений. О скобках для округления нецелых чисел в ту или иную сторону см. Символы Айверсона.

Скобка Айверсона — функция, возвращающая 1 для истинного высказывания, и 0, если аргумент ложный:

[math]\displaystyle{ [\,P\,] = \begin{cases} 1, &\text{если } P \text{ истинно} \\ 0, &\text{если } P \text{ ложно} \end{cases} }[/math]

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

• символ Кронекера: [math]\displaystyle{ \delta_{ij} = [\,i=j\,] }[/math],
• индикаторную функцию: [math]\displaystyle{ \mathbf{1}_A(x) = [\,x \in A\,] }[/math],
• функцию Хевисайда: [math]\displaystyle{ \theta(x)=[\,x\geqslant 0\,] }[/math],
• функцию знака числа: [math]\displaystyle{ \sgn(x) = [\,x \gt 0\,] - [\,x \lt 0\,] }[/math].

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

[math]\displaystyle{ \sum_{i=1}^n a_i = \sum_{k} a_k [\, 1 \leqslant k \leqslant n\, ] }[/math],

то есть индекс [math]\displaystyle{ k }[/math] пробегает всё множество [math]\displaystyle{ \Z }[/math] целых чисел, и формально суммируется бесконечное число слагаемых, но лишь конечное число их отлично от нуля.

Пример вычисления с использованием нотации Айверсона суммы [math]\displaystyle{ S = \sum_{i=1}^{n-1} \sum_{j=i+1}^n a_i a_j }[/math] для последовательности [math]\displaystyle{ \{ a_i \} }[/math]:

[math]\displaystyle{ [\,i \lt j\,] + [\,i = j\,] + [\,i \gt j\,] = 1 }[/math],

[math]\displaystyle{ \sum\limits_{i , j} a_i a_j [\,i \lt j\,] + \sum\limits_{i , j} a_i a_j [\,i = j\,] + \sum\limits_{i , j} a_i a_j [\,i \gt j\,] = \sum\limits_{i , j} a_i a_j }[/math],

[math]\displaystyle{ S + \sum\limits_{i} a_i^2 + S = \biggl(\sum\limits_{i} a_i \biggr)^2 }[/math],

а так как для правой части:

[math]\displaystyle{ \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 }[/math],

то:

[math]\displaystyle{ S = \sum_{1 \leq i \lt 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 }[/math].

Литература

• Грэхем Р., Кнут Д., Паташник О. Конкретная математика. — М.: Мир, 1998. — 703 с. — ISBN 5-03-001793-3.
• Kenneth E. Iverson. A Programming Language. — the University of California: Wiley, 1962. — 286 с. — ISBN 0471430145.