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

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

Нотация Айверсона, или скобка Айверсона, — обозначение в математике. Согласно этому обозначению, истинное или ложное утверждение, заключенное в квадратные скобки, равно 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

См. также


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Полезное


Смотреть что такое "Нотация Айверсона" в других словарях:

  • нотация Айверсона — Компактный способ записи математических выражений, лежащий в основе языка IPL. [Е.С.Алексеев, А.А.Мячев. Англо русский толковый словарь по системотехнике ЭВМ. Москва 1993] Тематики информационные технологии в целом EN Inversion notation …   Справочник технического переводчика

  • Целая часть — График функции «пол» (целая часть числа) …   Википедия

  • Скобки — У этого термина существуют и другие значения, см. Скобки (значения). Сюда перенаправляются запросы :) и некоторые другие, начинающиеся с двоеточия. О них см. статью смайлик. ( ) Название символа Скобки Юникод U+0028 29 HTML …   Википедия

  • Индикатор (математика) — У этого термина существуют и другие значения, см. Индикатор. Индикатор, или характеристическая функция, или индикаторная функция подмножества   это функция, определённая на множестве , которая указывает на принадлежность элемента… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»